SEE algorithm on chessprogramming wiki

[hgm]

I handle that outside of Swap(). That is, I pass Swap() a move and ask "what is the simple SEE approximation of the material score if I make this move?" That is, I assume that the move I pass it must be made, so it starts with a + score of whever is on the destination square (zero if empty) and then does the usual SEE thing after that. I don't bail out internally because I see that the material score is not enough to get us back above alpha, or get us back below beta. I do that test outside of Swap() since I can phrase that simply enough. Might be a bit better to do it inside, and I might give that a test, but it does mean passing in two more parameters (or at least an alpha value) which is not completely free.

There is no reason to pass anything, as the alpha and beta of the SEE and of the main search are not the same. (They might even be in different units.) As you remarked above, you don't want to merely know if the SEE fails high or low, you want to know exactly by how much, so you have to re-open the window in the root of the SEE. (It would be posible to pass alpha = -INF or -1 to distinguish the cases where you are interested in how much a bad capture exactly loses, and where you are not. But you could also make two different SEE routines for that.)

It seems that what you are doing is equivalent to setting alpha and beta from the stand-pat scores after the first and second ply, respectively. (But not from before the first ply, as you want to force that move, and do not allow stand pat there as an alternative it can switch to if the capture is bad.) This alpha and beta is than passed unmodified to the deeper nodes. But a ful implementation of alpha-beta would raise alpha every time the stand-pat score is above it, before it started to search the move. Also in the deeper nodes.

[Sven]

Based on the example positions given above, I can accept that there are cases where it is possible to reduce the number of "SEE nodes" somehow. Now I have thought about the proper way of doing that.

Please excuse my long posting.

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 improve over the well-known SEE algorithm that provides us with a defined level of accuracy. Let's also assume that we want to keep as much accuracy of SEE as we need for our purpose.

In the following I stick with the recursive notation for simplicity, while knowing that there is always an equivalent iterative algorithm producing identical results and potentially being faster.

My next basic assumption is that the recursive see() function always returns a value representing the material gain relative to the current node, not to the "SEE root node". So see() always returns either 0 or the non-negative value expressed by:

Code: Select all

value_of_piece_just_captured - see_value_for_opponent_after_making_my_capture(...)

Now we "always" (but see my note about promotions further down!) know the following bounds:
- The maximum gain for the side to move relative to the current node is equal to value_of_piece_just_captured, since the opponent can decide to stand pat to avoid losing even more.
- The maximum gain for the opponent after I made my capture is the value of my moving piece, for a very similar reason.

Let's have two consecutive captures, the first captures the value C0 with a piece of value M0, and the second captures the value C1 (C1 == M0) with a piece of value M1.

Now I can express when it would definitely be safe to skip doing another recursive see() call:

The second capture will safely refute the first one if (C1 - M1 >= C0). The second see() call will return at least C1 - M1 (since this is definitely >= 0, and would even grow if the enemy's gain is less than M1), and due to the given condition this will make (C0 - (C1 - M1)) go negative or zero when backing up to the parent node, so there the opponent can safely decide to stand pat.

In other words: we can always skip calling another level of see() if the following condition is true:

Code: Select all

value_of_piece_just_captured - value_of_my_piece_just_moved >= value_of_my_piece_that_was_previously_captured

and simply return (value_of_piece_just_captured - value_of_my_piece_just_moved) instead.

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

Example 2: BxP is always refuted by PxB since "B > P + P".

The implementation would require to pass one additional parameter: the value of the previously captured piece. The total material balance relative to the SEE root node would be irrelevant here.

Since this approach does not have any impact on the final SEE result at the root, i.e. does not lose accuracy, I state that it is safe to "always" apply this kind of cutoff. (Another question is, as mentioned above, whether this additional intelligence can be implemented effectively and passes the "cluster test".)

An exception to "always" could occur if a promoting pawn is involved in the capture sequence for which it is possible to postpone its promotion until all enemy attackers are gone, and then do the final capture move gloriously promoting to a queen which stays on board and increments the SEE result by value_of_queen - value_of_pawn. I guess it is not trivial to handle this case properly, since the possibility of xray attacks can make it impossible sometimes to decide whether the promoting capture shall be handled like all other pawn moves, thus ordered to the top of the attack list, or postponed until the end of the capture sequence (which is exactly when?). Knowing about this additional complexity, for now I vote for keeping that case out of my consideration and thinking further about its proper handling. Your proposals are very welcome.

Returning to the "SEE cutoff" topic, now I would like to know if and why any of the two other approaches that have been discussed within this thread is really better than the approach I have presented above:

a) HGM: use an alpha-beta window for SEE

b) Bob: "bail out [and return which value?] if, after making a capture, the current sum of material exchanged less the current capturing piece is still greater than zero"

Note my question added in brackets within b).

Currently I assume, until being disproven, that my approach is superior to both others since it does not affect SEE accuracy at all, and also since it is easy to derive it from the "original" SEE algorithm and therefore easy to prove its correctness (still excluding the promotion problem for now), while both others still appear partially unclear to me.

Your comments are welcome. Also, regarding the HGM approach I would appreciate to see some pseudocode that illustrates this alpha-beta based SEE algorithm.

Sven

[bob]

Based on the example positions given above, I can accept that there are cases where it is possible to reduce the number of "SEE nodes" somehow. Now I have thought about the proper way of doing that.

Please excuse my long posting.

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 improve over the well-known SEE algorithm that provides us with a defined level of accuracy. Let's also assume that we want to keep as much accuracy of SEE as we need for our purpose.

In the following I stick with the recursive notation for simplicity, while knowing that there is always an equivalent iterative algorithm producing identical results and potentially being faster.

My next basic assumption is that the recursive see() function always returns a value representing the material gain relative to the current node, not to the "SEE root node". So see() always returns either 0 or the non-negative value expressed by:

Code: Select all

value_of_piece_just_captured - see_value_for_opponent_after_making_my_capture(...)

Now we "always" (but see my note about promotions further down!) know the following bounds:
- The maximum gain for the side to move relative to the current node is equal to value_of_piece_just_captured, since the opponent can decide to stand pat to avoid losing even more.
- The maximum gain for the opponent after I made my capture is the value of my moving piece, for a very similar reason.

Let's have two consecutive captures, the first captures the value C0 with a piece of value M0, and the second captures the value C1 (C1 == M0) with a piece of value M1.

Now I can express when it would definitely be safe to skip doing another recursive see() call:

The second capture will safely refute the first one if (C1 - M1 >= C0). The second see() call will return at least C1 - M1 (since this is definitely >= 0, and would even grow if the enemy's gain is less than M1), and due to the given condition this will make (C0 - (C1 - M1)) go negative or zero when backing up to the parent node, so there the opponent can safely decide to stand pat.

In other words: we can always skip calling another level of see() if the following condition is true:

Code: Select all

value_of_piece_just_captured - value_of_my_piece_just_moved >= value_of_my_piece_that_was_previously_captured

and simply return (value_of_piece_just_captured - value_of_my_piece_just_moved) instead.

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

Example 2: BxP is always refuted by PxB since "B > P + P".

The implementation would require to pass one additional parameter: the value of the previously captured piece. The total material balance relative to the SEE root node would be irrelevant here.

Since this approach does not have any impact on the final SEE result at the root, i.e. does not lose accuracy, I state that it is safe to "always" apply this kind of cutoff. (Another question is, as mentioned above, whether this additional intelligence can be implemented effectively and passes the "cluster test".)

An exception to "always" could occur if a promoting pawn is involved in the capture sequence for which it is possible to postpone its promotion until all enemy attackers are gone, and then do the final capture move gloriously promoting to a queen which stays on board and increments the SEE result by value_of_queen - value_of_pawn. I guess it is not trivial to handle this case properly, since the possibility of xray attacks can make it impossible sometimes to decide whether the promoting capture shall be handled like all other pawn moves, thus ordered to the top of the attack list, or postponed until the end of the capture sequence (which is exactly when?). Knowing about this additional complexity, for now I vote for keeping that case out of my consideration and thinking further about its proper handling. Your proposals are very welcome.

Returning to the "SEE cutoff" topic, now I would like to know if and why any of the two other approaches that have been discussed within this thread is really better than the approach I have presented above:

a) HGM: use an alpha-beta window for SEE

b) Bob: "bail out [and return which value?] if, after making a capture, the current sum of material exchanged less the current capturing piece is still greater than zero"

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.

Note my question added in brackets within b).

Currently I assume, until being disproven, that my approach is superior to both others since it does not affect SEE accuracy at all, and also since it is easy to derive it from the "original" SEE algorithm and therefore easy to prove its correctness (still excluding the promotion problem for now), while both others still appear partially unclear to me.

Your comments are welcome. Also, regarding the HGM approach I would appreciate to see some pseudocode that illustrates this alpha-beta based SEE algorithm.

Sven

[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

[mcostalba]

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.

[Sven]

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

[mcostalba]

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.

[Sven]

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 ?

You don't need to have an additional "opponent move" inbetween.

Consider this example. Within qsearch the following pattern occurs:
[D]8/8/8/q3p3/8/5N2/8/4R3 w - - 0 1[/D]

For move ordering, you want to know the SEE for the root move 1.NxP since it looks like a potentially losing capture (N>P). You call seeMove() which makes the move NxP and calls the recursive see() function for the next node. Now see() makes QxN. At this point the "traditional" SEE would descend to the next node by doing the next recursive see() call (which could include making RxQ as well as detecting new xray attacks [EDIT: removed wrong comment here]), and only after returning from there it would do the backing up, decide about stand pat or not, and so on. 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.

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 guess at least HGM will argue against that

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.

I think these are completely independent issues. You may or may not take care about x-ray, in both cases it is possible to apply cutoffs or not to do it. Maybe you think that the effect of x-ray attacks being newly activated would influence the statement about bounds that I gave but this is not the case. By which magic the opponent creates new power to attack the target square is irrelevant: if I capture a piece value C0 with an own piece C1 then whatever he does can't win more than my C1 since I can always reply with stand pat. Same for myself: whatever I try, including x-rays: I can't enforce to win more than C0 since my opponent can decide to reply with stand pat.

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.

What do you think is the portion of captures longer than 2 pieces?

Sven

[mcostalba]

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).

I think these are completely independent issues. You may or may not take care about x-ray, in both cases it is possible to apply cutoffs or not to do it.

Yes, I saw your solution is already x-ray safe. I was wondering about the others "approximate" ones.

What do you think is the portion of captures longer than 2 pieces?

I am not able to measure now this parameter. I will do later this evening and post the result.

[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.