25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * SEE - The Swap Algorithm''' The iterative SEE Swap-Algorithm i..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * SEE - The Swap Algorithm'''
The [[Iteration|iterative]] [[Static Exchange Evaluation|SEE]] Swap-Algorithm in Bitboards creates a swap-list of best case [[Material|material]] gains by traversing a [[Square Attacked By|square attacked/defended by]] set in least valuable piece order from [[Pawn|pawn]], [[Knight|knight]], [[Bishop|bishop]], [[Rook|rook]], [[Queen|queen]] until [[King|king]], with alternating sides. The swap-list, an unary tree since there are no branches but just a series of captures, is [[Negamax|negamaxed]] for a final static exchange evaluation <ref>[https://www.stmintz.com/ccc/index.php?id=178981 Subject: Re: Static Exchange Eval] by [[Robert Hyatt]] from [[Computer Chess Forums|CCC]], August 02, 2001</ref><ref>[[Crafty]] by [[Robert Hyatt]], see '''''swap.c'''''</ref>.
=Traversal of To-Attacks=
Assuming this arbitrary [[Bitboard Board-Definition#CBoardDef|Board-Definition]] with color as least significant piece bit and "even" pieces are the white ones, following routine returns a single populated square set and passes the least valuable piece per [[Cpp|C++]] reference to the caller. If no more piece is found for the appropriate side, it returns an empty set.
<pre>
U64 Board::getLeastValuablePiece(U64 attadef, int bySide, int &piece)
{
for (piece = nWhitePawn + bySide; piece <= nWhiteKing + bySide; piece += 2) {
U64 subset = attadef & pieceBB[piece];
if ( subset )
return subset & -subset; // single bit
}
return 0; // empty set
}
</pre>
=SEE a Capture=
The first two members of the gain swap-list are likely determined by the [[Captures|capture move]] we like to prove. Thus, the first element of the swap-list is the value of the target piece, while the second is only written (or used) if the target square is further defended. In this case it is the value of the capturing piece minus the value of captured piece, this is the best-case material gain from the defending point of view. However during traversal, [[X-ray Attacks (Bitboards)|X-ray attacks]] are considered while capturing with a piece, which may have indirect attacks or defends behind, which unions the set of attackers and defenders.
=Pseudo C-Code=
<pre>
int Board::see ( enumSquare toSq, enumPiece target, enumSquare frSq, enumPiece aPiece)
{
int gain[32], d = 0;
U64 mayXray = pawns | bishops | rooks | queen;
U64 fromSet = 1ULL << frSq;
U64 occ = occupiedBB;
U64 attadef = attacksTo( occ, toSq );
gain[d] = value[target];
do {
d++; // next depth and side
gain[d] = value[aPiece] - gain[d-1]; // speculative store, if defended
if (max (-gain[d-1], gain[d]) < 0) break; // pruning does not influence the result
attadef ^= fromSet; // reset bit in set to traverse
occ ^= fromSet; // reset bit in temporary occupancy (for x-Rays)
if ( fromSet & mayXray )
attadef |= considerXrays(occ, ..);
fromSet = getLeastValuablePiece (attadef, d & 1, aPiece);
} while (fromSet);
while (--d)
gain[d-1]= -max (-gain[d-1], gain[d])
return gain[0];
}
</pre>
Considering [[X-ray Attacks (Bitboards)|X-ray attacks]] leaves some implementation details left, dependent on what sliding attack-getter is handy, [[Classical Approach|ray attacks]] are sufficient, but requires some effort to determine the ray-direction. With [[Magic Bitboards]] one will likely use something similar as the sliding piece subset of [[Square Attacked By]]. The preliminary pruning of the swap-list fill (if (max (-gain[d-1], gain[d]) < 0) break;) and other improvements were proposed by [[Michael Hoffmann]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=419315&t=40054 Re: SEE with alpha beta] by [[Michael Hoffmann]], [[CCC]], August 14, 2011</ref>.
=Traces=
Two positions with traces of the swap-list during traversal and negamaxing with some arbitrary [[Material|piece values]].
==Position 1==
To demonstrate how SEE works in obvious cases, is Rook takes Pawn a winning capture?
<fentt border="double" style="font-size:24pt">1k1r4/1pp4p/p7/4p3/8/P5P1/1PP4P/2K1R3</fentt>
1k1r4/1pp4p/p7/4p3/8/P5P1/1PP4P/2K1R3 w - - ; Rxe5?
<pre>
gain[0] = 100 ; win for white if black pawn e5 is en-prise by rxp
gain[1] = 400 ; win for black if white rook e5 is en-prise, 500-100, speculative store
no further attacks for black at depth 1
-> SEE(rxe5) == 100
</pre>
==Position 2==
This position covers a more complicated case with X-rays. Is Knight takes pawn a winning capture?
<fentt border="double" style="font-size:24pt">1k1r3q/1ppn3p/p4b2/4p3/8/P2N2P1/1PP1R1BP/2K1Q3</fentt>
1k1r3q/1ppn3p/p4b2/4p3/8/P2N2P1/1PP1R1BP/2K1Q3 w - - ; Nxe5?
<pre>
gain[0] = 100 ; win for white if black pawn e5 is en-prise by nxp
gain[1] = 225 ; win for black if white knight e5 is en-prise by nxn, 325- 100
gain[2] = 100 ; win for white if black knight e5 is en-prise by rxn, 325- 225 -> x-rays includes queen e1
gain[3] = 400 ; win for black if white rook e5 is en-prise by bxr, 500- 100 -> x-rays includes queen h8
gain[4] = -75 ; win for white if black bishop e5 is en-prise by qxb, 325- 400
gain[5] = 1075 ; win for black if white queen e5 is en-prise by qxq, 1000- -75
gain[6] = -75 ; win for white if black queen e5 is en-prise, 1000-1075 speculative store
no further attacks for white at depth = 6
gain[4] = -max(--75, 1075) = -1075
gain[3] = -max(-400, -1075) = 400
gain[2] = -max(-100, 400) = -400
gain[1] = -max(-225, -400) = 225
gain[0] = -max(-100, 225) = -225
-> SEE(nxe5) == -225
</pre>
=See also=
* [[Attack and Defend Maps#EDsLookup|Ed's Lookup]] from [[Attack and Defend Maps]]
* [[MVV-LVA]]
* [[SOMA]]
* [[Static Exchange Evaluation]]
=Forum Posts=
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=178979 Static Exchange Eval] by [[Artem Petakov|Artem Pyatakov]], [[CCC]], August 02, 2001
* [https://www.stmintz.com/ccc/index.php?id=341658 Does swap of Crafty find bad promotions] by [[Uri Blass]], [[CCC]], January 11, 2004
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=46486&p=176048#p176025 Re: WBEC Ridderkerk new results] by [[Dann Corbit]], [[Computer Chess Forums|Winboard Forum]], February 15, 2004 » [[DanChess]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?t=6104 SEE with magic bitboards] by [[Pradu Kannan]], [[Computer Chess Forums|Winboard Forum]], January 24, 2007 » [[Magic Bitboards]]
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=123511&t=14168 Re: Movei added to Crafty vs Rybka comaprison data] by [[Edsel Apostol]], [[CCC]], June 06, 2007
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=31479 Question about SEE algorithm on Chessprogramming Wiki] by [[Mathieu Pagé]], [[CCC]], January 05, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=40046 Implementing SEE] by colin, [[CCC]], Aug 12, 2011
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=419174&t=40046 Re: Implementing SEE] by [[Michael Hoffmann]], [[CCC]], August 13, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=40054 SEE with alpha beta] by [[Onno Garms]], [[CCC]], August 14, 2011 » [[Onno]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64166 Problems with SEE] by [[Matthew R. Brades]], [[CCC]], June 03, 2017
=References=
<references />
'''[[Bitboards|Up one Level]]'''
The [[Iteration|iterative]] [[Static Exchange Evaluation|SEE]] Swap-Algorithm in Bitboards creates a swap-list of best case [[Material|material]] gains by traversing a [[Square Attacked By|square attacked/defended by]] set in least valuable piece order from [[Pawn|pawn]], [[Knight|knight]], [[Bishop|bishop]], [[Rook|rook]], [[Queen|queen]] until [[King|king]], with alternating sides. The swap-list, an unary tree since there are no branches but just a series of captures, is [[Negamax|negamaxed]] for a final static exchange evaluation <ref>[https://www.stmintz.com/ccc/index.php?id=178981 Subject: Re: Static Exchange Eval] by [[Robert Hyatt]] from [[Computer Chess Forums|CCC]], August 02, 2001</ref><ref>[[Crafty]] by [[Robert Hyatt]], see '''''swap.c'''''</ref>.
=Traversal of To-Attacks=
Assuming this arbitrary [[Bitboard Board-Definition#CBoardDef|Board-Definition]] with color as least significant piece bit and "even" pieces are the white ones, following routine returns a single populated square set and passes the least valuable piece per [[Cpp|C++]] reference to the caller. If no more piece is found for the appropriate side, it returns an empty set.
<pre>
U64 Board::getLeastValuablePiece(U64 attadef, int bySide, int &piece)
{
for (piece = nWhitePawn + bySide; piece <= nWhiteKing + bySide; piece += 2) {
U64 subset = attadef & pieceBB[piece];
if ( subset )
return subset & -subset; // single bit
}
return 0; // empty set
}
</pre>
=SEE a Capture=
The first two members of the gain swap-list are likely determined by the [[Captures|capture move]] we like to prove. Thus, the first element of the swap-list is the value of the target piece, while the second is only written (or used) if the target square is further defended. In this case it is the value of the capturing piece minus the value of captured piece, this is the best-case material gain from the defending point of view. However during traversal, [[X-ray Attacks (Bitboards)|X-ray attacks]] are considered while capturing with a piece, which may have indirect attacks or defends behind, which unions the set of attackers and defenders.
=Pseudo C-Code=
<pre>
int Board::see ( enumSquare toSq, enumPiece target, enumSquare frSq, enumPiece aPiece)
{
int gain[32], d = 0;
U64 mayXray = pawns | bishops | rooks | queen;
U64 fromSet = 1ULL << frSq;
U64 occ = occupiedBB;
U64 attadef = attacksTo( occ, toSq );
gain[d] = value[target];
do {
d++; // next depth and side
gain[d] = value[aPiece] - gain[d-1]; // speculative store, if defended
if (max (-gain[d-1], gain[d]) < 0) break; // pruning does not influence the result
attadef ^= fromSet; // reset bit in set to traverse
occ ^= fromSet; // reset bit in temporary occupancy (for x-Rays)
if ( fromSet & mayXray )
attadef |= considerXrays(occ, ..);
fromSet = getLeastValuablePiece (attadef, d & 1, aPiece);
} while (fromSet);
while (--d)
gain[d-1]= -max (-gain[d-1], gain[d])
return gain[0];
}
</pre>
Considering [[X-ray Attacks (Bitboards)|X-ray attacks]] leaves some implementation details left, dependent on what sliding attack-getter is handy, [[Classical Approach|ray attacks]] are sufficient, but requires some effort to determine the ray-direction. With [[Magic Bitboards]] one will likely use something similar as the sliding piece subset of [[Square Attacked By]]. The preliminary pruning of the swap-list fill (if (max (-gain[d-1], gain[d]) < 0) break;) and other improvements were proposed by [[Michael Hoffmann]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=419315&t=40054 Re: SEE with alpha beta] by [[Michael Hoffmann]], [[CCC]], August 14, 2011</ref>.
=Traces=
Two positions with traces of the swap-list during traversal and negamaxing with some arbitrary [[Material|piece values]].
==Position 1==
To demonstrate how SEE works in obvious cases, is Rook takes Pawn a winning capture?
<fentt border="double" style="font-size:24pt">1k1r4/1pp4p/p7/4p3/8/P5P1/1PP4P/2K1R3</fentt>
1k1r4/1pp4p/p7/4p3/8/P5P1/1PP4P/2K1R3 w - - ; Rxe5?
<pre>
gain[0] = 100 ; win for white if black pawn e5 is en-prise by rxp
gain[1] = 400 ; win for black if white rook e5 is en-prise, 500-100, speculative store
no further attacks for black at depth 1
-> SEE(rxe5) == 100
</pre>
==Position 2==
This position covers a more complicated case with X-rays. Is Knight takes pawn a winning capture?
<fentt border="double" style="font-size:24pt">1k1r3q/1ppn3p/p4b2/4p3/8/P2N2P1/1PP1R1BP/2K1Q3</fentt>
1k1r3q/1ppn3p/p4b2/4p3/8/P2N2P1/1PP1R1BP/2K1Q3 w - - ; Nxe5?
<pre>
gain[0] = 100 ; win for white if black pawn e5 is en-prise by nxp
gain[1] = 225 ; win for black if white knight e5 is en-prise by nxn, 325- 100
gain[2] = 100 ; win for white if black knight e5 is en-prise by rxn, 325- 225 -> x-rays includes queen e1
gain[3] = 400 ; win for black if white rook e5 is en-prise by bxr, 500- 100 -> x-rays includes queen h8
gain[4] = -75 ; win for white if black bishop e5 is en-prise by qxb, 325- 400
gain[5] = 1075 ; win for black if white queen e5 is en-prise by qxq, 1000- -75
gain[6] = -75 ; win for white if black queen e5 is en-prise, 1000-1075 speculative store
no further attacks for white at depth = 6
gain[4] = -max(--75, 1075) = -1075
gain[3] = -max(-400, -1075) = 400
gain[2] = -max(-100, 400) = -400
gain[1] = -max(-225, -400) = 225
gain[0] = -max(-100, 225) = -225
-> SEE(nxe5) == -225
</pre>
=See also=
* [[Attack and Defend Maps#EDsLookup|Ed's Lookup]] from [[Attack and Defend Maps]]
* [[MVV-LVA]]
* [[SOMA]]
* [[Static Exchange Evaluation]]
=Forum Posts=
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=178979 Static Exchange Eval] by [[Artem Petakov|Artem Pyatakov]], [[CCC]], August 02, 2001
* [https://www.stmintz.com/ccc/index.php?id=341658 Does swap of Crafty find bad promotions] by [[Uri Blass]], [[CCC]], January 11, 2004
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=46486&p=176048#p176025 Re: WBEC Ridderkerk new results] by [[Dann Corbit]], [[Computer Chess Forums|Winboard Forum]], February 15, 2004 » [[DanChess]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?t=6104 SEE with magic bitboards] by [[Pradu Kannan]], [[Computer Chess Forums|Winboard Forum]], January 24, 2007 » [[Magic Bitboards]]
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=123511&t=14168 Re: Movei added to Crafty vs Rybka comaprison data] by [[Edsel Apostol]], [[CCC]], June 06, 2007
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=31479 Question about SEE algorithm on Chessprogramming Wiki] by [[Mathieu Pagé]], [[CCC]], January 05, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=40046 Implementing SEE] by colin, [[CCC]], Aug 12, 2011
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=419174&t=40046 Re: Implementing SEE] by [[Michael Hoffmann]], [[CCC]], August 13, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=40054 SEE with alpha beta] by [[Onno Garms]], [[CCC]], August 14, 2011 » [[Onno]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64166 Problems with SEE] by [[Matthew R. Brades]], [[CCC]], June 03, 2017
=References=
<references />
'''[[Bitboards|Up one Level]]'''
