25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Square Attacked By''' FILE:L'Ange du Foyeur.jpg|border|right|thumb|link=https://www.chessprogramming.org/..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * Square Attacked By'''
[[FILE:L'Ange du Foyeur.jpg|border|right|thumb|link=https://www.chessprogramming.org/File:L%27Ange_du_Foyeur.jpg|[[Arts#Ernst|Max Ernst]] - L'Ange du Foyer, 1937 <ref>[https://en.wikipedia.org/wiki/Max_Ernst Max Ernst from Wikipedia]</ref> ]]
'''Square Attacked By''',<br/>
determines whether a [[Squares|square]] is attacked and/or defended by various or specific [[Pieces|pieces]]. So far, as elaborated in [[Pawn Pattern and Properties|pawn]]-, [[Knight Pattern|knight]]- and [[King Pattern|king pattern]], as well as [[Sliding Piece Attacks|sliding piece attacks]], we are able to generate all attacks and target-sets of all pieces, sufficient to [[Move Generation|generate]] all [[Pseudo-Legal Move|pseudo legal moves]]. It is often useful to generate [[Attacks|attacks]] '''to''' a certain square, or to look whether [[Moves|moves]] retrieved elsewhere are pseudo legal or [[Legal Move|legal]]. Some programs maintain [[Incremental Updates|incremental updated]] [[Attack and Defend Maps|attack tables]] for that purpose. The techniques proposed on this page are intended to use on the fly.
=Attacks to a Square=
<span id="ByAllPieces"></span>
==By all Pieces==
A common approach is to put a '''super-piece''' on the to-square, to look up all kind of piece-type attacks from there and to [[General Setwise Operations#Intersection|intersect]] them with all appropriate pieces able to attack that square. Note that white pawn attacks intersect black pawns and vice versa. Knights, kings and sliders are considered as [[General Setwise Operations#Union|union]] of both sides. The set of all attacking and defending pieces is the union of all piece-attack intersections. Assuming a [[Cpp|C++]] member function of a [[Bitboard Board-Definition]] class. [[Robert Hyatt]] further checks whether there are any sliding pieces on relevant rays at all, in order to save calling the attack getter in case there are none <ref>[http://www.talkchess.com/forum/viewtopic.php?t=50684&start=2 Re: AttacksTo() bitboard] by [[Robert Hyatt]], [[CCC]], December 29, 2013</ref>:
<pre>
U64 CBoard::attacksTo(U64 occupied, enumSquare sq) {
U64 knights, kings, bishopsQueens, rooksQueens;
knights = pieceBB[nWhiteKnight] | pieceBB[nBlackKnight];
kings = pieceBB[nWhiteKing] | pieceBB[nBlackKing];
rooksQueens =
bishopsQueens = pieceBB[nWhiteQueen] | pieceBB[nBlackQueen];
rooksQueens |= pieceBB[nWhiteRook] | pieceBB[nBlackRook];
bishopsQueens |= pieceBB[nWhiteBishop] | pieceBB[nBlackBishop];
return (arrPawnAttacks[nWhite][sq] & pieceBB[nBlackPawn])
| (arrPawnAttacks[nBlack][sq] & pieceBB[nWhitePawn])
| (arrKnightAttacks [sq] & knights)
| (arrKingAttacks [sq] & kings)
| (bishopAttacks(occupied,sq) & bishopsQueens)
| (rookAttacks (occupied,sq) & rooksQueens)
;
}
</pre>
<span id="AnyAttackBySide"></span>
==Any Attack by Side==
If boolean information is required, whether a square is attacked by a side, one may use conditionals to return early. This might be useful to determine whether a [[Checks and Pinned Pieces (Bitboards)|king is in check]]. Assuming a [[Cpp|C++]] member function of a [[Bitboard Board-Definition]] class:
<pre>
bool CBoard::attacked(U64 occupied, enumSquare square, enumColor bySide) {
U64 pawns = pieceBB[nWhitePawn + bySide];
if ( arrPawnAttacks[bySide^1][square] & pawns ) return true;
U64 knights = pieceBB[nWhiteKnight + bySide];
if ( arrKnightAttacks[square] & knights ) return true;
U64 king = pieceBB[nWhiteKing + bySide];
if ( arrKingAttacks[square] & king ) return true;
U64 bishopsQueens = pieceBB[nWhiteQueen + bySide]
| pieceBB[nWhiteBishop + bySide];
if ( bishopAttacks(occupied, square) & bishopsQueens ) return true;
U64 rooksQueens = pieceBB[nWhiteQueen + bySide]
| pieceBB[nWhiteRook + bySide];
if ( rookAttacks (occupied, square) & rooksQueens ) return true;
return false;
}
</pre>
<span id="LegalityTest"></span>
=Legality Test=
One application inside a chess program, is to test whether a certain move is [[Pseudo-Legal Move|psuedo-legal]]. This could be a [[Hash Move|hash move]] probed from the [[Transposition Table|transposition table]], or a [[Killer Move|killer move]] supplied by the [[Killer Heuristic|killer heuristic]]. In [[Node Types#CUT|cut-nodes]] one may save the complete move-generation by one legality test.
<span id="InBetween"></span>
==In Between==
Assuming otherwise legal from-to coordinates, it is about distant moves of [[Sliding Pieces|sliding pieces]] (and [[Pawn Push#DoublePush|double pawn push]] and [[Castling|castling]]) - whether a square between from and to is obstructed or not. One obvious solution is to switch on piece-type and call the appropriate attack- or move-target getter by from-square, to see whether the target bit is set. For a queen that may take quite some instructions for up to four sliding lines, thus there seems to be a cheaper solution.
<span id="Obstructed"></span>
===Rectangular Lookup===
The common approach is to lookup a two-dimensional 64 times 64 [[Array|array]], initialized with empty sets and appropriate in-between sets for distant squares on the same line. If the intersection of in-between sets with the [[Occupancy|occupancy]] is empty, there are no obstructions, and the move is considered pseudo legal. This is implicitly true for squares in king- and knight distance as well, since they already contain zero.
<pre>
U64 arrRectangular[64][64]; // 4096*8 = 32KByte
U64 inBetween(enumSquare from, enumSquare to) {
return arrRectangular[from][to];
}
bool mayMove(enumSquare from, enumSquare to, U64 occ) {
return (inBetween(from, to) & occ) == 0;
}
</pre>
That looks cheap, and likely is the fastest for recent processor architectures, but 32KByte is just another thing competing with the caches. Three further [[Space-Time Tradeoff|space-time tradeoffs]] are mentioned, triangular lookup, 0x88 difference and rotate, and pure calculation.
<span id="TriangularLookup"></span>
===Triangular Lookup===
Due to the [https://en.wikipedia.org/wiki/Commutative_property commutative property] of from- and to-squares, each in-between set is stored twice in the 64x64 array. [[Eugene Nalimov]] once suggested to roughly half the table-size by making the rectangle a triangle, and already noted "''Not sure that it will make sense, as index code will be more complex''" <ref>[https://www.stmintz.com/ccc/index.php?id=72098 Re: Bitboard user's information request] by [[Eugene Nalimov]], [[CCC]], October 06, 1999</ref>. Applying [[Avoiding Branches#Max|max]] and [[Avoiding Branches#Min|min]] by sign-mask, and some packing with the [https://en.wikipedia.org/wiki/Triangular_number triangular number], following index calculation may be used:
<pre>
U64 arrTriangular[64*65/2];
int triangularIndex(int a, int b) {
int d = a - b; /* difference */
d &= d >> 31; /* only if negative */
b += d; /* min */
a -= d; /* max */
b *= b ^ 127; /* min * (127-min) ... */
return (b>>1) + a; /* ... /2 + max */
}
U64 inBetween(enumSquare from, enumSquare to) {
return arrTriangular[ triangularIndex(from, to) ];
}
</pre>
<span id="By0x88Difference"></span>
===0x88 Difference===
What about a translation of one square (the smallest) to a1 and shifting the occupancy right? Unfortunately, the square difference is ambiguous according to the 8 [[Direction|ray-]] and 8 knight directions, +-7 occurs as rank- or anti-diagonal-difference, +-6 occurs as rank- and knight-difference. If we keep other stuff like [[Distance|distance]], [[Manhattan-Distance|Manhattan-distance]], [[Direction|ray-direction]] and so on - it might be worth to rely on [[Vector Attacks]] or the difference of [[0x88]] coordinates and their property of being unambiguous according to ray-direction and distance. By [[General Setwise Operations#Rotate|rotating left]] the pre-calculated obstructions, the order of squares don't cares. [[Don Dailey]] reported the 64x64 array lookup slightly faster, apparently inside [[Komodo]] <ref>[http://www.talkchess.com/forum/viewtopic.php?start=0&t=46240&start=14 Re: bit boards - what is betwen] by [[Don Dailey]], [[CCC]], December 04, 2012</ref>.:
<pre>
U64 arrInBetweenBy0x88Diff[240]; // 1920 bytes, 2KByte - 128 Byte
unsigned int x88diff(enumSquare f, enumSquare t) {
return t - f + (t|7) - (f|7) + 120;
}
U64 inBetween(enumSquare from, enumSquare to) {
return rotateLeft(arrInBetweenBy0x88Diff[x88diff(from,to)], from);
}
</pre>
===Pure Calculation===
A branch-less solution without any lookups and some parallel gain is likely too expensive on the fly and may at most used for initialization purposes:
<pre>
U64 inBetween(enumSquare sq1, enumSquare sq2) {
const U64 m1 = C64(-1);
const U64 a2a7 = C64(0x0001010101010100);
const U64 b2g7 = C64(0x0040201008040200);
const U64 h1b7 = C64(0x0002040810204080); /* Thanks Dustin, g2b7 did not work for c1-a3 */
U64 btwn, line, rank, file;
btwn = (m1 << sq1) ^ (m1 << sq2);
file = (sq2 & 7) - (sq1 & 7);
rank = ((sq2 | 7) - sq1) >> 3 ;
line = ( (file & 7) - 1) & a2a7; /* a2a7 if same file */
line += 2 * (( (rank & 7) - 1) >> 58); /* b1g1 if same rank */
line += (((rank - file) & 15) - 1) & b2g7; /* b2g7 if same diagonal */
line += (((rank + file) & 15) - 1) & h1b7; /* h1b7 if same antidiag */
line *= btwn & -btwn; /* mul acts like shift by smaller square */
return line & btwn; /* return the bits on that line in-between */
}
</pre>
First, the in-between set as superset of the possible line-bits is calculated, excluding the "greater" square but including the "smaller", e.g. f6 and c3.
<pre>
btwn including c3
-1<<f6 -1<<c3 excluding f6
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 . . . . . . . .
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 . . . . . . . .
. . . . . 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 . . .
. . . . . . . . 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
. . . . . . . . ^ 1 1 1 1 1 1 1 1 = 1 1 1 1 1 1 1 1
. . . . . . . . . . 1 1 1 1 1 1 . . 1 1 1 1 1 1
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
b2g7 * LS1B(btwn) = line
. . . . . . . . . . . . . . . . . . . . . . . 1
. . . . . . 1 . . . . . . . . . . . . . . . 1 .
. . . . . 1 . . . . . . . . . . . . . . . 1 . .
. . . . 1 . . . . . . . . . . . . . . . 1 . . .
. . . 1 . . . . * . . . . . . . . = . . . 1 . . . .
. . 1 . . . . . . . 1 . . . . . . . . . . . . .
. 1 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
line & btwn = inBetween
. . . . . . . 1 . . . . . . . . . . . . . . . .
. . . . . . 1 . . . . . . . . . . . . . . . . .
. . . . . 1 . . 1 1 1 1 1 . . . . . . . . . . .
. . . . 1 . . . 1 1 1 1 1 1 1 1 . . . . 1 . . .
. . . 1 . . . . & 1 1 1 1 1 1 1 1 = . . . 1 . . . .
. . . . . . . . . . 1 1 1 1 1 1 . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
</pre>
If both squares share either a rank, file, diagonal or anti-diagonal, one [[Byte|byte]]-difference of the four lines becomes zero, which is (zero) extended to a bitboard, otherwise a value 1 ... 255. Subtracting '1' either leaves all bits (-1) set, otherwise 0..254. The a1-scaled mask is shifted left left by the "smallest" square, which can be done by multiplication with the isolated LS1B of the in-between set. The final intersection leaves the obstructed bits between two squares.
<span id="AttackedByPieceOnSquare"></span>
==Attacked by Piece on Square==
The obstructed lookup idea may be advanced to determine one particular attack by one piece. To lookup whether a certain square is attacked by that piece on another square. Thus, we need a second obstructed-array dimension by piece code. All legal attacks by none sliding pieces are initialized by the empty set zero, all others with the universal set -1. Any intersection with the occupancy (which we need for the sliding pieces anyway) is either empty or not. Sliding pieces have the appropriate obstructed bits set for squares on a common diagonal for bishops and queens - and a common orthogonal for rooks and queens. To safe some memory we rely on the [[Square Attacked By#By0x88Difference|0x88 trick]].
Except pawns all white and black pieces have the same attacks - thus based on the piece enumeration mentioned in the [[Bitboard Board-Definition]], one may divide the piece code by two to shift right the least significant piece color bit: {1,2,3,4,5,6} for {pawn, knight, bishop, rook, queen, king}. In case of a black pawn we subtract one, to get a 0..6 range:
<pre>
U64 attacksBy0x88DiffAndPiece[7][256]; // 14KByte
/* is square <to> attacked by <piece> from square <from> */
bool isAttacked(enumSquare from, enumSquare to, enumPiece piece, U64 occ) {
int isBlackPawn = (piece ^ nBlackPawn) - 1;
isBlackPawn >>= 31; /* -1 if black pawn, otherwise 0 */
return (attacksBy0x88DiffAndPiece [piece/2 + isBlackPawn] [x88diff(from,to)]
& rotateRight (occ, from) ) == 0;
}
</pre>
See [[General Setwise Operations#Rotate|rotateRight]].
If one considers white and black pawns as disjoint pieces even without color information, one may safe that isBlackPawn calculation obtaining the same table size. With a 11 or 12 array-range one may index by piece-2 or similar according to the piece definition.
=See also=
* [[Attack and Defend Maps]]
* [[InBetween]]
=Forum Posts=
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=516 Two questions for bitboard experts] by [[Tord Romstad]], [[Computer Chess Forums|Winboard Forum]], November 06, 2004 » [[Piece-Lists]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6573 Bitboard of squares between] by [[Onno Garms]], [[Computer Chess Forums|Winboard Forum]], June 15, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=46240 bit boards - what is betwen] by [[Don Dailey]], [[CCC]], December 02, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=48322 Extract direction (ray) informations from two squares] by [[Mathieu Pagé]], [[CCC]], June 18, 2013 » [[Rays]], [[Direction]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50684 AttacksTo() bitboard] by [[Tony Soares]], [[CCC]], December 29, 2013
* [https://groups.google.com/forum/#!topic/fishcooking/RXLXONHPw-A help with bitboards] by stefano.c... , [[Computer Chess Forums|FishCooking]], December 06, 2017
=References=
<references />
'''[[Bitboards|Up one Level]]'''
[[FILE:L'Ange du Foyeur.jpg|border|right|thumb|link=https://www.chessprogramming.org/File:L%27Ange_du_Foyeur.jpg|[[Arts#Ernst|Max Ernst]] - L'Ange du Foyer, 1937 <ref>[https://en.wikipedia.org/wiki/Max_Ernst Max Ernst from Wikipedia]</ref> ]]
'''Square Attacked By''',<br/>
determines whether a [[Squares|square]] is attacked and/or defended by various or specific [[Pieces|pieces]]. So far, as elaborated in [[Pawn Pattern and Properties|pawn]]-, [[Knight Pattern|knight]]- and [[King Pattern|king pattern]], as well as [[Sliding Piece Attacks|sliding piece attacks]], we are able to generate all attacks and target-sets of all pieces, sufficient to [[Move Generation|generate]] all [[Pseudo-Legal Move|pseudo legal moves]]. It is often useful to generate [[Attacks|attacks]] '''to''' a certain square, or to look whether [[Moves|moves]] retrieved elsewhere are pseudo legal or [[Legal Move|legal]]. Some programs maintain [[Incremental Updates|incremental updated]] [[Attack and Defend Maps|attack tables]] for that purpose. The techniques proposed on this page are intended to use on the fly.
=Attacks to a Square=
<span id="ByAllPieces"></span>
==By all Pieces==
A common approach is to put a '''super-piece''' on the to-square, to look up all kind of piece-type attacks from there and to [[General Setwise Operations#Intersection|intersect]] them with all appropriate pieces able to attack that square. Note that white pawn attacks intersect black pawns and vice versa. Knights, kings and sliders are considered as [[General Setwise Operations#Union|union]] of both sides. The set of all attacking and defending pieces is the union of all piece-attack intersections. Assuming a [[Cpp|C++]] member function of a [[Bitboard Board-Definition]] class. [[Robert Hyatt]] further checks whether there are any sliding pieces on relevant rays at all, in order to save calling the attack getter in case there are none <ref>[http://www.talkchess.com/forum/viewtopic.php?t=50684&start=2 Re: AttacksTo() bitboard] by [[Robert Hyatt]], [[CCC]], December 29, 2013</ref>:
<pre>
U64 CBoard::attacksTo(U64 occupied, enumSquare sq) {
U64 knights, kings, bishopsQueens, rooksQueens;
knights = pieceBB[nWhiteKnight] | pieceBB[nBlackKnight];
kings = pieceBB[nWhiteKing] | pieceBB[nBlackKing];
rooksQueens =
bishopsQueens = pieceBB[nWhiteQueen] | pieceBB[nBlackQueen];
rooksQueens |= pieceBB[nWhiteRook] | pieceBB[nBlackRook];
bishopsQueens |= pieceBB[nWhiteBishop] | pieceBB[nBlackBishop];
return (arrPawnAttacks[nWhite][sq] & pieceBB[nBlackPawn])
| (arrPawnAttacks[nBlack][sq] & pieceBB[nWhitePawn])
| (arrKnightAttacks [sq] & knights)
| (arrKingAttacks [sq] & kings)
| (bishopAttacks(occupied,sq) & bishopsQueens)
| (rookAttacks (occupied,sq) & rooksQueens)
;
}
</pre>
<span id="AnyAttackBySide"></span>
==Any Attack by Side==
If boolean information is required, whether a square is attacked by a side, one may use conditionals to return early. This might be useful to determine whether a [[Checks and Pinned Pieces (Bitboards)|king is in check]]. Assuming a [[Cpp|C++]] member function of a [[Bitboard Board-Definition]] class:
<pre>
bool CBoard::attacked(U64 occupied, enumSquare square, enumColor bySide) {
U64 pawns = pieceBB[nWhitePawn + bySide];
if ( arrPawnAttacks[bySide^1][square] & pawns ) return true;
U64 knights = pieceBB[nWhiteKnight + bySide];
if ( arrKnightAttacks[square] & knights ) return true;
U64 king = pieceBB[nWhiteKing + bySide];
if ( arrKingAttacks[square] & king ) return true;
U64 bishopsQueens = pieceBB[nWhiteQueen + bySide]
| pieceBB[nWhiteBishop + bySide];
if ( bishopAttacks(occupied, square) & bishopsQueens ) return true;
U64 rooksQueens = pieceBB[nWhiteQueen + bySide]
| pieceBB[nWhiteRook + bySide];
if ( rookAttacks (occupied, square) & rooksQueens ) return true;
return false;
}
</pre>
<span id="LegalityTest"></span>
=Legality Test=
One application inside a chess program, is to test whether a certain move is [[Pseudo-Legal Move|psuedo-legal]]. This could be a [[Hash Move|hash move]] probed from the [[Transposition Table|transposition table]], or a [[Killer Move|killer move]] supplied by the [[Killer Heuristic|killer heuristic]]. In [[Node Types#CUT|cut-nodes]] one may save the complete move-generation by one legality test.
<span id="InBetween"></span>
==In Between==
Assuming otherwise legal from-to coordinates, it is about distant moves of [[Sliding Pieces|sliding pieces]] (and [[Pawn Push#DoublePush|double pawn push]] and [[Castling|castling]]) - whether a square between from and to is obstructed or not. One obvious solution is to switch on piece-type and call the appropriate attack- or move-target getter by from-square, to see whether the target bit is set. For a queen that may take quite some instructions for up to four sliding lines, thus there seems to be a cheaper solution.
<span id="Obstructed"></span>
===Rectangular Lookup===
The common approach is to lookup a two-dimensional 64 times 64 [[Array|array]], initialized with empty sets and appropriate in-between sets for distant squares on the same line. If the intersection of in-between sets with the [[Occupancy|occupancy]] is empty, there are no obstructions, and the move is considered pseudo legal. This is implicitly true for squares in king- and knight distance as well, since they already contain zero.
<pre>
U64 arrRectangular[64][64]; // 4096*8 = 32KByte
U64 inBetween(enumSquare from, enumSquare to) {
return arrRectangular[from][to];
}
bool mayMove(enumSquare from, enumSquare to, U64 occ) {
return (inBetween(from, to) & occ) == 0;
}
</pre>
That looks cheap, and likely is the fastest for recent processor architectures, but 32KByte is just another thing competing with the caches. Three further [[Space-Time Tradeoff|space-time tradeoffs]] are mentioned, triangular lookup, 0x88 difference and rotate, and pure calculation.
<span id="TriangularLookup"></span>
===Triangular Lookup===
Due to the [https://en.wikipedia.org/wiki/Commutative_property commutative property] of from- and to-squares, each in-between set is stored twice in the 64x64 array. [[Eugene Nalimov]] once suggested to roughly half the table-size by making the rectangle a triangle, and already noted "''Not sure that it will make sense, as index code will be more complex''" <ref>[https://www.stmintz.com/ccc/index.php?id=72098 Re: Bitboard user's information request] by [[Eugene Nalimov]], [[CCC]], October 06, 1999</ref>. Applying [[Avoiding Branches#Max|max]] and [[Avoiding Branches#Min|min]] by sign-mask, and some packing with the [https://en.wikipedia.org/wiki/Triangular_number triangular number], following index calculation may be used:
<pre>
U64 arrTriangular[64*65/2];
int triangularIndex(int a, int b) {
int d = a - b; /* difference */
d &= d >> 31; /* only if negative */
b += d; /* min */
a -= d; /* max */
b *= b ^ 127; /* min * (127-min) ... */
return (b>>1) + a; /* ... /2 + max */
}
U64 inBetween(enumSquare from, enumSquare to) {
return arrTriangular[ triangularIndex(from, to) ];
}
</pre>
<span id="By0x88Difference"></span>
===0x88 Difference===
What about a translation of one square (the smallest) to a1 and shifting the occupancy right? Unfortunately, the square difference is ambiguous according to the 8 [[Direction|ray-]] and 8 knight directions, +-7 occurs as rank- or anti-diagonal-difference, +-6 occurs as rank- and knight-difference. If we keep other stuff like [[Distance|distance]], [[Manhattan-Distance|Manhattan-distance]], [[Direction|ray-direction]] and so on - it might be worth to rely on [[Vector Attacks]] or the difference of [[0x88]] coordinates and their property of being unambiguous according to ray-direction and distance. By [[General Setwise Operations#Rotate|rotating left]] the pre-calculated obstructions, the order of squares don't cares. [[Don Dailey]] reported the 64x64 array lookup slightly faster, apparently inside [[Komodo]] <ref>[http://www.talkchess.com/forum/viewtopic.php?start=0&t=46240&start=14 Re: bit boards - what is betwen] by [[Don Dailey]], [[CCC]], December 04, 2012</ref>.:
<pre>
U64 arrInBetweenBy0x88Diff[240]; // 1920 bytes, 2KByte - 128 Byte
unsigned int x88diff(enumSquare f, enumSquare t) {
return t - f + (t|7) - (f|7) + 120;
}
U64 inBetween(enumSquare from, enumSquare to) {
return rotateLeft(arrInBetweenBy0x88Diff[x88diff(from,to)], from);
}
</pre>
===Pure Calculation===
A branch-less solution without any lookups and some parallel gain is likely too expensive on the fly and may at most used for initialization purposes:
<pre>
U64 inBetween(enumSquare sq1, enumSquare sq2) {
const U64 m1 = C64(-1);
const U64 a2a7 = C64(0x0001010101010100);
const U64 b2g7 = C64(0x0040201008040200);
const U64 h1b7 = C64(0x0002040810204080); /* Thanks Dustin, g2b7 did not work for c1-a3 */
U64 btwn, line, rank, file;
btwn = (m1 << sq1) ^ (m1 << sq2);
file = (sq2 & 7) - (sq1 & 7);
rank = ((sq2 | 7) - sq1) >> 3 ;
line = ( (file & 7) - 1) & a2a7; /* a2a7 if same file */
line += 2 * (( (rank & 7) - 1) >> 58); /* b1g1 if same rank */
line += (((rank - file) & 15) - 1) & b2g7; /* b2g7 if same diagonal */
line += (((rank + file) & 15) - 1) & h1b7; /* h1b7 if same antidiag */
line *= btwn & -btwn; /* mul acts like shift by smaller square */
return line & btwn; /* return the bits on that line in-between */
}
</pre>
First, the in-between set as superset of the possible line-bits is calculated, excluding the "greater" square but including the "smaller", e.g. f6 and c3.
<pre>
btwn including c3
-1<<f6 -1<<c3 excluding f6
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 . . . . . . . .
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 . . . . . . . .
. . . . . 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 . . .
. . . . . . . . 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
. . . . . . . . ^ 1 1 1 1 1 1 1 1 = 1 1 1 1 1 1 1 1
. . . . . . . . . . 1 1 1 1 1 1 . . 1 1 1 1 1 1
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
b2g7 * LS1B(btwn) = line
. . . . . . . . . . . . . . . . . . . . . . . 1
. . . . . . 1 . . . . . . . . . . . . . . . 1 .
. . . . . 1 . . . . . . . . . . . . . . . 1 . .
. . . . 1 . . . . . . . . . . . . . . . 1 . . .
. . . 1 . . . . * . . . . . . . . = . . . 1 . . . .
. . 1 . . . . . . . 1 . . . . . . . . . . . . .
. 1 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
line & btwn = inBetween
. . . . . . . 1 . . . . . . . . . . . . . . . .
. . . . . . 1 . . . . . . . . . . . . . . . . .
. . . . . 1 . . 1 1 1 1 1 . . . . . . . . . . .
. . . . 1 . . . 1 1 1 1 1 1 1 1 . . . . 1 . . .
. . . 1 . . . . & 1 1 1 1 1 1 1 1 = . . . 1 . . . .
. . . . . . . . . . 1 1 1 1 1 1 . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
</pre>
If both squares share either a rank, file, diagonal or anti-diagonal, one [[Byte|byte]]-difference of the four lines becomes zero, which is (zero) extended to a bitboard, otherwise a value 1 ... 255. Subtracting '1' either leaves all bits (-1) set, otherwise 0..254. The a1-scaled mask is shifted left left by the "smallest" square, which can be done by multiplication with the isolated LS1B of the in-between set. The final intersection leaves the obstructed bits between two squares.
<span id="AttackedByPieceOnSquare"></span>
==Attacked by Piece on Square==
The obstructed lookup idea may be advanced to determine one particular attack by one piece. To lookup whether a certain square is attacked by that piece on another square. Thus, we need a second obstructed-array dimension by piece code. All legal attacks by none sliding pieces are initialized by the empty set zero, all others with the universal set -1. Any intersection with the occupancy (which we need for the sliding pieces anyway) is either empty or not. Sliding pieces have the appropriate obstructed bits set for squares on a common diagonal for bishops and queens - and a common orthogonal for rooks and queens. To safe some memory we rely on the [[Square Attacked By#By0x88Difference|0x88 trick]].
Except pawns all white and black pieces have the same attacks - thus based on the piece enumeration mentioned in the [[Bitboard Board-Definition]], one may divide the piece code by two to shift right the least significant piece color bit: {1,2,3,4,5,6} for {pawn, knight, bishop, rook, queen, king}. In case of a black pawn we subtract one, to get a 0..6 range:
<pre>
U64 attacksBy0x88DiffAndPiece[7][256]; // 14KByte
/* is square <to> attacked by <piece> from square <from> */
bool isAttacked(enumSquare from, enumSquare to, enumPiece piece, U64 occ) {
int isBlackPawn = (piece ^ nBlackPawn) - 1;
isBlackPawn >>= 31; /* -1 if black pawn, otherwise 0 */
return (attacksBy0x88DiffAndPiece [piece/2 + isBlackPawn] [x88diff(from,to)]
& rotateRight (occ, from) ) == 0;
}
</pre>
See [[General Setwise Operations#Rotate|rotateRight]].
If one considers white and black pawns as disjoint pieces even without color information, one may safe that isBlackPawn calculation obtaining the same table size. With a 11 or 12 array-range one may index by piece-2 or similar according to the piece definition.
=See also=
* [[Attack and Defend Maps]]
* [[InBetween]]
=Forum Posts=
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=516 Two questions for bitboard experts] by [[Tord Romstad]], [[Computer Chess Forums|Winboard Forum]], November 06, 2004 » [[Piece-Lists]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6573 Bitboard of squares between] by [[Onno Garms]], [[Computer Chess Forums|Winboard Forum]], June 15, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=46240 bit boards - what is betwen] by [[Don Dailey]], [[CCC]], December 02, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=48322 Extract direction (ray) informations from two squares] by [[Mathieu Pagé]], [[CCC]], June 18, 2013 » [[Rays]], [[Direction]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50684 AttacksTo() bitboard] by [[Tony Soares]], [[CCC]], December 29, 2013
* [https://groups.google.com/forum/#!topic/fishcooking/RXLXONHPw-A help with bitboards] by stefano.c... , [[Computer Chess Forums|FishCooking]], December 06, 2017
=References=
<references />
'''[[Bitboards|Up one Level]]'''
