SEE algorithm on chessprogramming wiki

[yoshiharu]

Aha, Zach's code! You are right Sven, should be

Code: Select all

if (see_value + piece_just_captured() >= 0 aka value )

May be this pseudo code for a didactic see?

Code: Select all

int see(int square, int side)
{
  value = 0;
  piece = get_smallest_attacker(square, side);
  if ( piece )
  {
    make_capture(piece, square);
    value = max (0, piece_just_captured() -see(square, other(side)) );
    undo_capture(piece, square);
  }
  return value;
}

Is this recursive implementation really needed? Wouldn't it be enough to just try the sequence of captures sorted putting the LVA's first? After all we are just playing the captures on a single square, and since this kind of sorting would put bishops and rooks before queens, I can't envision an example in which a "PV" of SEE would not come out sorted this way.
Am I missing something?

Cheers, Mauro

[hgm]

You would miss the X-rays.

In Joker's SEE I natuarally find blockers of aligned sliders when looking for captures (I use the 0x88 test, so I have to scan the board ray), and mark them on an auxiliary board. If A piece is used in the capture sequence that is marked that way, it means it was blocking a lower or equal piece that we tried before, and we have to "rewind" the LVA-sorted list of attackers to the point of the now unblocked piece.

There is no real need for a recursive implementation: because you try at most one move in every position, it is trivial to convert this tail-recursion to an iterative version, without the need to implement your own variable stack. I do implement full alpha-beta, though. (I mark it with the number of the blocked piece, to make that efficient.) In Chess one piece can fortunately block only a single piece to a given square. (No Cannons...)

As Gerd remarks, the presented code is just for didactic purposes. Efficiency is totally ignored.

[yoshiharu]

You would miss the X-rays.

Of course you are right: I missed an important point in my explaination.
What I do in my engine is to iteratively find pieces that attack the given square, starting from the least valuable ones (P,N/B,R,Q,K) and alternating colours. In this fashion I fill an array of attackers: the claim is that this would be equivalent to a full alpha-beta, but I admit I didn't spend much time to prove this claim

There is no real need for a recursive implementation: because you try at most one move in every position, it is trivial to convert this tail-recursion to an iterative version, without the need to implement your own variable stack.
(snip)
As Gerd remarks, the presented code is just for didactic purposes. Efficiency is totally ignored.

Yes, I see this point. My objection wasn't only on the recursion, but on the need to have the full AB search implemented. Since the number of captures is not too large, there is not a great difference in terms of speed in any case, at least according to the tests I've made.
Of course this is if I didn't totally screwed my SEE up

Cheers, Mauro

[Sven]

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

Sven

[Sven]

Mauro and Harm-Geert, could one of you please explain how using alpha-beta for SEE can be any better than the presented (now corrected) SEE algorithm, of course while keeping it correct?

Regarding recursion, it is true of course that there is always an iterative solution if a recursive one exists, and that the iterative solution is slightly more efficient since it saves the typical recursion overhead of function calls and stack management. However, my point, and that of the wiki, is more about
1) correctness and
2) understanding the algorithm well (therefore Gerd's "didactic" proposal).
So I would leave the iterative implementation as an exercise to the reader

Sven

[hgm]

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.

[Gerd Isenberg]

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

[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