SEE algorithm on chessprogramming wiki

[bob]

Well, for instance in the following case:

[d] 5q2/8/8/8/RRQ2nrr/8/8/8 w

after QxN, RxQ RxR black would stand pat rather than gain another Rook by RxR, RxR, QxR. When properly implemented white wuld not even try the RxR on ply 3, because it is futile (being already Q vs N behind, i.e. -6). This, assuming that I am only interested to know if the capture is bad, and bnot how bad it is, so that I call it in the root with alpha = -1.

I you want an example with the window fully open in the root, imagine that the black Knight just captured a Pawn. Whte has then the choice to stand pat or pay QxN, and to conclude that QxN is bad it only need to go 3 ply deeper, (or 2 with futility), rather than 6.

Another one, not involving X-rays:

[d] 7q/3n1n2/3b4/4p3/3P1P2/3N1N2/8/8 w

dxe5 wins a Pawn, and you know it after Ndxe5, fxe5, as black has only futile captures left on a Pawn. No reason to play another NxP, NxN, BxN, NxB, QxN to gain it, it will not be enough.

The only drawback occurs if you want to use this to order moves and want a real score. If you give up when you prove a capture is futile (doesn't regain enough to bring the score back to zero or above) you lose any information about how bad it really is. Might not be important, and if so, I'd agree. But if you want to know how bad, then perhaps not. I don't like the recursive version due to speed. Procedure calls and returns are not exactly the fastest instructions in the book.

[hgm]

I only sort moves with poitive SEE on their SEE score (if they are not low x high or equal captures). Moves with negative SEE are bad captures, and I am not interested how bad. (In QS they are pruned, not sorted.) So I can set the root window to {-1,+INF}, and any loss of a Pawn or more will fail low.

Note that even if you set the root window to {-INF, +INF}, it very quickly narrows, and you will still get cutoffs later along the line. The second example I give would do the mentioned cutoff, saving us the trouble to do the last 5 moves, even with a fully open window in the root. So we are guaranteed to get the exact SEE score. But at reduced effort. You don't have to know if NxP on the defended Pawn does lose you 1 or 2 Pawns to decide that you rather stand pat. And the standing pat then is backed up to the root to provide the exact score.

[Sven]

Thanks, Gerd, I see that you have fixed the algorithm yesterday. Could you also update the text below the algorithm accordingly?

Sven

Done...

Of course, you (and others) are very welcome to fix such stuff by yourself.

Cheers,
Gerd

Yes, you are right. Maybe I'll do so next time.
But for the major point of my post, the question whether the previous version of the algorithm was correct, I would not change this on my own without consulting the expert forum first

Sven

[bob]

I only sort moves with poitive SEE on their SEE score (if they are not low x high or equal captures). Moves with negative SEE are bad captures, and I am not interested how bad. (In QS they are pruned, not sorted.) So I can set the root window to {-1,+INF}, and any loss of a Pawn or more will fail low.

Note that even if you set the root window to {-INF, +INF}, it very quickly narrows, and you will still get cutoffs later along the line. The second example I give would do the mentioned cutoff, saving us the trouble to do the last 5 moves, even with a fully open window in the root. So we are guaranteed to get the exact SEE score. But at reduced effort. You don't have to know if NxP on the defended Pawn does lose you 1 or 2 Pawns to decide that you rather stand pat. And the standing pat then is backed up to the root to provide the exact score.

I thought I did that as well, but there is an exception, which is the code to generate and select check evasion moves. Most of those are not captures, and if I want to interpose as the only way to get out, I want to interpose the piece that loses the least, with reasonable accuracy. I'm studying it to see if it matters.

I had tried this test a few years back and didn't keep it. I have just finished testing it speed-wise and it makes no difference whatsoever in my NPS. It does change the node counts very slightly for those cases where NextEvasion() now returns the moves in a slightly different order. But with no difference in speed there's little benefit to changing it would seem.

[hgm]

For such special move sorting in in-check nodes, you could then simply call SEE with alpha set to -INF, in stead of -1. Like always, the search window has to be adapted to what you want to know.

[bob]

For such special move sorting in in-check nodes, you could then simply call SEE with alpha set to -INF, in stead of -1. Like always, the search window has to be adapted to what you want to know.

I don't pass a bound to my Swap() (SEE) function. It just looks at the target square and goes to work. I simply modified it (one line change) to bail out if, after making a capture, the current sum of material exchanged less the current capturing piece is still greater than zero. Such as NxP PxN, RxP, RxR, RxR, all on the same square. I give up on this right after PxN since best case loses the knight for two pawns. Old version went to the bottom and backed its way up minimax-style.

For the above, the old version figures out that it is winning two pawns, losing a knight, for -100. The new version says -200. Either one is good enough for the exclusionary test that weeds out bad captures in the q-search.

[hgm]

Well, that sounds like a form of beta cutoff. In this unbranched tree, where the single LVA capture is the only alternative to stand pat, every node below you has already tried the stand pat, and does not have anything left to do once you return from the current node. So a beta cutoff can in fact abort the search by jumping directly to the root exit. Perhaps after flipping the sign of the score it s supposed to back up depending on if it was at an even or odd level.

I suppose that you do this test if you can bail out once for either side?

[bob]

Well, that sounds like a form of beta cutoff. In this unbranched tree, where the single LVA capture is the only alternative to stand pat, every node below you has already tried the stand pat, and does not have anything left to do once you return from the current node. So a beta cutoff can in fact abort the search by jumping directly to the root exit. Perhaps after flipping the sign of the score it s supposed to back up depending on if it was at an even or odd level.

I suppose that you do this test if you can bail out once for either side?

Yes. This is an iterated SEE, I check on every iteration to see if the current material score - value of current capturing piece is > 0, and bail out and start minimaxing the result back up the "tree"....

[hgm]

It sounds a bit like the iterative version of a search where you don't narrow the window by raising alpha. I think to get a full implementation of alpha-beta you would not have to compare against a fixed limit of zero, but compare to the best result you had so far. For instance, if you started winning an exchange in the first two ply, any later capture would already be futile if if it did not raise you above +2, rather than above 0.

E.g. NxR (+5), BxN (+2), QxB (+5), RxQ (-4), RxR (+1)

The last RxR (and everything that might be possible after it) is futile: the opponent can stand pat and keep you on +1, while if you had stopped before QxB yourself you would already have had +2. So QxB was a mistake. So despite the fact that you are still >0, you might as well stop and settle for +2.

[bob]

It sounds a bit like the iterative version of a search where you don't narrow the window by raising alpha. I think to get a full implementation of alpha-beta you would not have to compare against a fixed limit of zero, but compare to the best result you had so far. For instance, if you started winning an exchange in the first two ply, any later capture would already be futile if if it did not raise you above +2, rather than above 0.

E.g. NxR (+5), BxN (+2), QxB (+5), RxQ (-4), RxR (+1)

The last RxR (and everything that might be possible after it) is futile: the opponent can stand pat and keep you on +1, while if you had stopped before QxB yourself you would already have had +2. So QxB was a mistake. So despite the fact that you are still >0, you might as well stop and settle for +2.

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.