SEE algorithm on chessprogramming wiki

[Sven]

Is the SEE algorithm given at chessprogramming wiki correct? It contains the condition "if (see_value >= 0)" but I wonder if this should be "if (see_value >= -piece_just_captured())" instead.

I accept a capture somewhere within the recursion if the possible material gain for the opponent after my move does not outweigh the piece I have captured. The code given with ">= 0" seems to reject capturing a knight if the opponent can win a pawn afterwards, for instance.

Any comments?

Sven

[hgm]

Is the SEE algorithm given at chessprogramming wiki correct?

Definitely not. It makes no sense. See_value can never be > 0. And on top of that it is extremely inefficient, using minimax in stead of alpha-beta. Normally you test first if the current value (i.e. stand-pat) is alraedy above alpha, and if it i, you won't bother capturing anything. And of course you actually d that even before making the recursive call, if current eval + captured piece does not get above beta (futility).

[Gerd Isenberg]

Is the SEE algorithm given at chessprogramming wiki correct? It contains the condition "if (see_value >= 0)" but I wonder if this should be "if (see_value >= -piece_just_captured())" instead.

I accept a capture somewhere within the recursion if the possible material gain for the opponent after my move does not outweigh the piece I have captured. The code given with ">= 0" seems to reject capturing a knight if the opponent can win a pawn afterwards, for instance.

Any comments?

Sven

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;
}

Thanks for pointing that out.

Cheers,
Gerd

[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