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
SEE algorithm on chessprogramming wiki
Moderators: hgm, Rebel, chrisw
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
-
- Posts: 27809
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: SEE algorithm on chessprogramming wiki
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).Sven Schüle wrote:Is the SEE algorithm given at chessprogramming wiki correct?
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: SEE algorithm on chessprogramming wiki
Aha, Zach's code! You are right Sven, should beSven Schüle wrote: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
Code: Select all
if (see_value + piece_just_captured() >= 0 aka value )
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;
}
Cheers,
Gerd
-
- Posts: 56
- Joined: Sat Nov 11, 2006 11:14 pm
Re: SEE algorithm on chessprogramming wiki
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.Gerd Isenberg wrote: Aha, Zach's code! You are right Sven, should beMay be this pseudo code for a didactic see?Code: Select all
if (see_value + piece_just_captured() >= 0 aka value )
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; }
Am I missing something?
Cheers, Mauro
-
- Posts: 27809
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: SEE algorithm on chessprogramming wiki
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.
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.
-
- Posts: 56
- Joined: Sat Nov 11, 2006 11:14 pm
Re: SEE algorithm on chessprogramming wiki
Of course you are right: I missed an important point in my explaination.hgm wrote:You would miss the X-rays.
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
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.hgm wrote: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.
Of course this is if I didn't totally screwed my SEE up
Cheers, Mauro
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: SEE algorithm on chessprogramming wiki
Thanks, Gerd, I see that you have fixed the algorithm yesterday. Could you also update the text below the algorithm accordingly?
Sven
Sven
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: SEE algorithm on chessprogramming wiki
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
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
-
- Posts: 27809
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: SEE algorithm on chessprogramming wiki
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.
[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.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: SEE algorithm on chessprogramming wiki
Done...Sven Schüle wrote:Thanks, Gerd, I see that you have fixed the algorithm yesterday. Could you also update the text below the algorithm accordingly?
Sven
Of course, you (and others) are very welcome to fix such stuff by yourself.
Cheers,
Gerd