SEE algorithm on chessprogramming wiki

[bob]

No, you have misunderstood my idea. NxP does not occur at the SEE root but somewhere below.

You need a capture chain of at least 5 pieces to make your idea usable, it happens in about 2% of cases so I would foreseen a very little speed up in real cases.

I see your point, although I would like to read your explanation for "at least 5". I would have thought "at least 3" instead: root move - capture to be refuted - refuting capture. For the third move, the recursive see() call can potentially be skipped which includes "making" that capture but possibly also trying to extend the attacker list by the next xray attacker that may appear.

Your comment closely matches what I wrote:

My first thought was: each additional intelligence being put into the SEE algorithm can make its implementation more complex by an amount that has potential for a significant slowdown, and it might even be possible that this effect outweighs any effort we save by adding intelligence, taking also into account that really saving some SEE nodes might turn out to be statistically rare since we need special circumstances to successfully apply a "cutoff".

But let's assume we really want to be smart [...]

and further down:

(Another question is, as mentioned above, whether this additional intelligence can be implemented effectively and passes the "cluster test".)

My only point when bringing up that idea was that there were two other "being smart" approaches mentioned by HGM and Bob which *might* be inferior compared to my approach. Nothing more

And when arguing about speedup, the first thing to check must always be "correctness" w.r.t. the overall SEE requirements. E.g. if all three approaches are "correct" in that sense, we can try to identify the fastest one and compare its speed to the speed of plain SEE as we all know it.

Maybe then we get the result you are predicting.

Maybe this could also be the reason why Fruit 2.1, for instance, does not include that kind of optimization effort. I hope we'll know more soon

Btw, is there any proposal for the promotion topic I mentioned? How do others solve that, besides perhaps ignoring it?

Sven

Promotions in SEE were discussed a few years back. Several of us tested the idea and found no difference in quality by ignoring them. It will slow things down very slightly, and since SEE is used multiple times at every node in the tree, it is a very small net loss in speed and rating.

[bob]

I see your point, although I would like to read your explanation for "at least 5". I would have thought "at least 3" instead: root move - capture to be refuted - refuting capture. For the third move, the recursive see() call can potentially be skipped which includes "making" that capture but possibly also trying to extend the attacker list by the next xray attacker that may appear.

In your example:

Example 1: QxN is always refuted by RxQ since "Q > R + N" and therefore especially "Q - R >= N".


If QxN is _not_ the root move (as I have understood) it means you have:

root move / opponent move / QxN / RXQ

So you need to know that an opponent rook can capture the queen. Is the above correct or I miss something ?

My only point when bringing up that idea was that there were two other "being smart" approaches mentioned by HGM and Bob which *might* be inferior compared to my approach. Nothing more

They are different because are "SEE sign" only solutions, i.e. they only give you the correct sign of a capture, not the correct value.

I have found some time I can use a "SEE sign" function, but in other cases I need the correct SEE value, so at the end I have found the best thing is to use a full SEE alghoritm with a small check at the beginning for (in case) early return the positive sign when only this is need and the captured piece is bigger then the capturing one (at the root move).

Another _big_ shortcoming of approximate solutions above proposed is that don't take in account x-ray attacks that can be activated at some point in the capture chain.


IMHO the main two points to have in mind when thinking about SEE optimization are:

1) The chain captures longer then 3 pieces account only for less then 10% of cases.

2) X-ray attacks activated by a previous capture cannot be overlooked.

However, the effect is unimportant for using a SEE procedure to answer the question "does this capture appear to lose material?" which is the most common application. In the NxP PxN RxP there is no need to look beyond PxN since you are now up in material, and even if your opponent can recapture the P, you can stand pat and _still_ remain up in material. That's perfectly safe for excluding "losing captures".

[Sven]

In this example:

NxP PxN BxP

true SEE value should be -100. (pawn = 100). Winning two pawns, losing a knight. The modified see value would return -200. NxP = +100, PxN = -200 and there is no way this will win more than another 100 because of the pawn recapture and if the opponent takes it I can always stand pat. So The new version would return -200, which is less accurate, but still shows this loses material.

If I read your idea, it would seem you have this same shortcoming??? Not that it is particularly bad.

No, you have misunderstood my idea. NxP does not occur at the SEE root but somewhere below. So the real SEE value at the node where NxP is possible is 0 because NxP is losing so the side to move decides to stand pat instead. And that is discovered one ply later, by the method I described. It is kind of a "beta cutoff". PxN refutes the previous NxP so for PxN we return a value that is safe to cause the parent node to return 0 (stand pat) instead of the value resulting from the losing NxP.

You would be right if NxP would be the root move to be considered for SEE, of course. But that is not the case here. Sorry for confusion, maybe that came due to the length of my posting.

Sven

OK. In my use of SEE, it is used to decide whether a move appears to win or lose material, or is a "break-even" move. I pass Swap() (my SEE procedure) a move and expect a numeric result back that gives me the expected effect on material by making the move. In the above case, my Swap() procedure is passed the NxP move and would return a material change delta. What you are doing sounds like a normal q-search approach, where SEE is intended to be faster although less accurate, since it focuses directly on one square only, not the entire board.

(Highlighting added by intent.)
No idea where you read this from, sorry. I am talking about the same kind of SEE as you do, so nothing about looking on the entire board.

Does that affect your statement?

Sven

[Sven]

However, the effect is unimportant for using a SEE procedure to answer the question "does this capture appear to lose material?" which is the most common application. In the NxP PxN RxP there is no need to look beyond PxN since you are now up in material, and even if your opponent can recapture the P, you can stand pat and _still_ remain up in material. That's perfectly safe for excluding "losing captures".

But you seem to do a slightly different check than what I propose. You wrote that you added a one-line change where the overall material balance (relative to starting SEE) is involved. Instead of that, my approach only refers to the value of the previous capture (read my long post to see exactly how). The intention of your and my solution (and also the alpha-beta approach of HGM) is the same, to cut off futile capture moves.

So my question to you is which of the two (three) approaches is better in your opinion, if I add that I believe my approach guarantees to keep 100% accuracy.

Sven

[Sven]

Btw, is there any proposal for the promotion topic I mentioned? How do others solve that, besides perhaps ignoring it?

Promotions in SEE were discussed a few years back. Several of us tested the idea and found no difference in quality by ignoring them. It will slow things down very slightly, and since SEE is used multiple times at every node in the tree, it is a very small net loss in speed and rating.

Good news, thanks, so promotions can be safely ignored and handled like pawn moves capturing a piece. I had the same feeling, and it greatly simplifies the SEE algorithm.

Sven

[Sven]

My proposal would lead to skipping this second recursive call (so skipping the third of three nodes) since it is already known in advance that QxN is refuted by RxQ, without actually descending into the position after RxQ.

Yes, I see. Problem is that in the way SEE is implemented in SF (not by recursive calls but it is iterative) once you find that there is a rook that could attack the queen you have almost done all for that ply. IOW the biggest effort is in finding if and what kind of attacker is the next one, not in actually update the stack after you have found it.

So, due to how SEE is implemented in SF, finding the rook and not descending saves very little (the biggest cost is in finding the rook).

Does that mean that SF currently does *not* look for newly appearing x-ray attacks at each SEE node, which I would imagine to be a quite expensive part even if no new x-rays are found in fact?

Sven

[diep]

hi,

Originally SEE was standing for Static Exchange Evaluation which completely REPLACED the evaluation function. However past 10-15 years such quiescencesearches were not so popular anymore and have been 'overpowered' by quiescencesearches playing moves; then SEE was getting used to approximate just 1 single move each time.

One of the last engines i know of using a real SEE, was the program Arthur from Walter Ravenek. A result of using a SEE is that you search much deeper. I was really impressed by what Walter had achieved there back then and how he did do this with Arthur. Especially if you consider that Arthur got a relative low nps

With more system time coming available to engines, of course such SEE's became less interesting and we really started to make functions that approximate the value of a move.

So the correct terminology for what most call 'SEE' now would be something like Tactical Move Gain Approximation.

SEE as it is used today definitely is not an 'evaluation', it's only the expected delta of a move, usually in quiecenscesearch.

However it works so much better to do this in qsearch, than to use the 'old' methods, that we shouldn't forget the big progress there in computer chess.

When i say progress i also indicate that a lot of engines did do really little to approximate which moves to try there.

Back in 90s popular thing to do in qsearch was doing first 2 plies all captures, or first ply, then after that just recaptures, or captures to equal or higher pieces.

That's really very effective.

[mcostalba]

Does that mean that SF currently does *not* look for newly appearing x-ray attacks at each SEE node, which I would imagine to be a quite expensive part even if no new x-rays are found in fact?

No, it does of course, but profiling shows this step is not the slowest one. I think that, again, we have to consider that in most cases after a capture you have a single recapture only (if any), so the overhead of x-ray calculation happens for a small part of cases.

In SF the slowest part (by far) is to compute all the attacks to the square that is done at the beginning.

The second slowest part is to find the lowest attacking piece at each step.

Just to add something, I have found a way to avoid calulcating x-ray attacks by checking in advance if a x-ray attack is possible using a "smart" and fast test at the beginning and skipping x-ray attacks update in the (common) case we are already sure there are none. To my surprise I got only a very minor speedup so I choose to discard the system due to added code complexity that didn't paid off as I was expecting.

[bob]

Does that mean that SF currently does *not* look for newly appearing x-ray attacks at each SEE node, which I would imagine to be a quite expensive part even if no new x-rays are found in fact?

No, it does of course, but profiling shows this step is not the slowest one. I think that, again, we have to consider that in most cases after a capture you have a single recapture only (if any), so the overhead of x-ray calculation happens for a small part of cases.

In SF the slowest part (by far) is to compute all the attacks to the square that is done at the beginning.

The second slowest part is to find the lowest attacking piece at each step.

Just to add something, I have found a way to avoid calulcating x-ray attacks by checking in advance if a x-ray attack is possible using a "smart" and fast test at the beginning and skipping x-ray attacks update in the (common) case we are already sure there are none. To my surprise I got only a very minor speedup so I choose to discard the system due to added code complexity that didn't paid off as I was expecting.

I would think that any program using bitboards and magic move generation could get x-ray attacks at almost no cost. All that is needed is to notice that this is a piece that moves diagonally, or vertically/horizontally. You remove the piece you just "used" to make the last capture, then use a magic move generation for either diagonals or ranks/files from the target square, and then AND that with the correct type of piece to see if a new piece is attacking the target. This has very low cost.

[bob]

In this example:

NxP PxN BxP

true SEE value should be -100. (pawn = 100). Winning two pawns, losing a knight. The modified see value would return -200. NxP = +100, PxN = -200 and there is no way this will win more than another 100 because of the pawn recapture and if the opponent takes it I can always stand pat. So The new version would return -200, which is less accurate, but still shows this loses material.

If I read your idea, it would seem you have this same shortcoming??? Not that it is particularly bad.

No, you have misunderstood my idea. NxP does not occur at the SEE root but somewhere below. So the real SEE value at the node where NxP is possible is 0 because NxP is losing so the side to move decides to stand pat instead. And that is discovered one ply later, by the method I described. It is kind of a "beta cutoff". PxN refutes the previous NxP so for PxN we return a value that is safe to cause the parent node to return 0 (stand pat) instead of the value resulting from the losing NxP.

You would be right if NxP would be the root move to be considered for SEE, of course. But that is not the case here. Sorry for confusion, maybe that came due to the length of my posting.

Sven

OK. In my use of SEE, it is used to decide whether a move appears to win or lose material, or is a "break-even" move. I pass Swap() (my SEE procedure) a move and expect a numeric result back that gives me the expected effect on material by making the move. In the above case, my Swap() procedure is passed the NxP move and would return a material change delta. What you are doing sounds like a normal q-search approach, where SEE is intended to be faster although less accurate, since it focuses directly on one square only, not the entire board.

(Highlighting added by intent.)
No idea where you read this from, sorry. I am talking about the same kind of SEE as you do, so nothing about looking on the entire board.

Does that affect your statement?

Sven

What I meant was the idea of "standing pat". You can still do a traditional q-search but limit it to just one square to make this happen. The idea for SEE is "very fast". That's why I have never used a recursive implementation even though the code becomes a bit simpler. And a bit slower.