25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * Classical Approach''' File:Classical Grotesque MET DT7804.jpg|border|right|th..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Classical Approach'''
[[File:Classical Grotesque MET DT7804.jpg|border|right|thumb|[[Arts#Klee|Paul Klee]] - Classical Grotesque, 1923 <ref>[[Arts#Klee|Paul Klee]] - Classical Grotesque, 1923, [https://commons.wikimedia.org/wiki/File:Classical_Grotesque_MET_DT7804.jpg] [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art Metropolitan Museum of Art]</ref>]]
The classical approach to generate [[Sliding Pieces|sliding piece]] attacks was probably first used by [[Chess (Program)|Chess]] and [[Kaissa]].
{{MappingHint}}
=Ray Attacks=
The classical approach works ray-wise and uses pre-calculated [[On an empty Board#RayAttacks|ray-attacks]] for each of the eight [[Rays#RayDirections|ray-directions]] and each of the 64 [[Squares|squares]]. It has to distinguish between [[On an empty Board#PositiveRays|positive]] and [[On an empty Board#NegativeRays|negative]] directions, because it has to [[BitScan|bitscan]] the ray-attack intersection with the [[Occupancy|occupancy]] in different orders. That usually don't cares for getting line- or piece attacks, since one likely unrolls all directions needed for a particular line or piece - otherwise one may rely on a [[BitScan#GeneralizedBitscan|generalized bitscan]].
''We rely on the compass rose to enumerate ray-directions:''
<pre>
noWe nort noEa
+7 +8 +9
\ | /
west -1 <- 0 -> +1 east
/ | \
-9 -8 -7
soWe sout soEa
</pre>
==Positive Rays==
Attacks of Positive Ray-Directions:
<pre>
East (+1) North (+8) NorthEast (+9) NorthWest (+7)
. . . . . . . . . . . 1 . . . . . . . . . . . 1 . . . . . . . .
. . . . . . . . . . . 1 . . . . . . . . . . 1 . 1 . . . . . . .
. . . . . . . . . . . 1 . . . . . . . . . 1 . . . 1 . . . . . .
. . . . . . . . . . . 1 . . . . . . . . 1 . . . . . 1 . . . . .
. . . R 1 1 1 1 . . . R . . . . . . . B . . . . . . . B . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
</pre>
===Conditional===
The first step gets the [[On an empty Board#RayAttacks|ray-attack]] on the otherwise empty board. Potential blockers are then determined by intersection with the [[Occupancy|occupancy]], the set of all pieces. The first blocker, if any, is the least significant one-bit of the intersection. A [[BitScan#Bitscanforward|bitscan forward]] determines the square of the first blocker, to reset it's ray-bits from the attack set. For instance a bishop on g2:
<pre>
occupied & NorthWest(g2) {a8, c6}
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 B 1 . . . . . . . . . . . . . . . .
1 1 1 1 1 . 1 1 . . . . . . . . . . . . . . . .
xor NorthWest(c6 = bitscanForward{a8,c6}
1 . . . . . . .
. 1 . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
= final northWest Attacks
. . . . . . . .
. . . . . . . .
. . 1 . . . . .
. . . 1 . . . .
. . . . 1 . . .
. . . . . 1 . .
. . . . . . . .
. . . . . . . .
</pre>
<pre>
U64 rayAttacks[8][64];
U64 getPositiveRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
U64 attacks = rayAttacks[dir8][square];
U64 blocker = attacks & occupied;
if ( blocker ) {
square = bitScanForward(blocker);
attacks ^= rayAttacks[dir8][square];
}
return attacks;
}
</pre>
<span id="Branchless"></span>
===Branchless===
Branches are evil with todays super pipelined processors. Even if branch-prediction heuristics become smarter, [[Avoiding Branches|branch-less]] solutions allow better scheduling and parallel speedup of independent instruction chains, like processing several directions.
Considering todays fast [[x86-64]] [[x86-64#gpinstructions|bsf-instruction]] of [https://en.wikipedia.org/wiki/Intel_Core_2 Core 2] or [https://en.wikipedia.org/wiki/AMD_K10 K10], a branch-less solution may be worth a try. Due to the fact the [[Occupancy|occupancy]] of [[First Rank Attacks#TheOuterSquares|the outer squares]] doesn't affect the attack set, setting the most significant bit ensures to scan at least an outer square, which would address an empty ray set anyway, therefor not affecting the final result with no blocker or a most outer one.
<pre>
U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {
U64 attacks = rayAttacks[dir8][square];
U64 blocker = attacks & occupied;
_BitScanForward64 (&square, blocker | C64(0x8000000000000000));
return attacks ^ rayAttacks[dir8][square];
}
</pre>
==Negative Rays==
Attacks of Negative Ray-Directions:
<pre>
West (-1) South (-8) SouthWest (-9) SouthEast (-7)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 1 1 R . . . . . . . R . . . . . . . B . . . . . . . B . . . .
. . . . . . . . . . . 1 . . . . . . 1 . . . . . . . . . 1 . . .
. . . . . . . . . . . 1 . . . . . 1 . . . . . . . . . . . 1 . .
. . . . . . . . . . . 1 . . . . 1 . . . . . . . . . . . . . 1 .
</pre>
===Conditional===
Works the same way, but needs [[BitScan#Bitscanreverse|reverse bitscan]] to find the first blocking piece, if any.
<pre>
U64 getNegativeRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
U64 attacks = rayAttacks[dir8][square];
U64 blocker = attacks & occupied;
if ( blocker ) {
square = bitScanReverse(blocker);
attacks ^= rayAttacks[dir8][square];
}
return attacks;
}
</pre>
===Branchless===
The branch-less solution with a fast [[x86-64]] [[x86-64#gpinstructions|bsr-instruction]] allows better scheduling and parallel speedup of independent instruction chains, like processing several directions. Setting the least significant bit ensures to scan at least an outer square, which would address an empty ray set anyway, therefor not affecting the final result with no blocker or a most outer one.
<pre>
U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {
U64 attacks = rayAttacks[dir8][square];
U64 blocker = attacks & occupied;
_BitScanReverse64 (&square, blocker | 1);
return attacks ^ rayAttacks[dir8][square];
}
</pre>
<span id="Generalized"></span>
==Generalized==
The idea of the [[BitScan#GeneralizedBitscan|generalized bitscan]] may be used to share the same code for all directions. The implementation of isNegative(dir8), a macro or inline-function, depends on the definition or enumeration of the directions and is likely a compare or test instruction.
===Conditional===
The conditional by a good predictable branch on blocker is favorable - specially for slow bitscans with some chance to skip it, e.g. in endings.
<pre>
U64 getRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
U64 attacks = rayAttacks[dir8][square];
U64 blocker = attacks & occupied;
if ( blocker ) {
square = bitScan(blocker, isNegative(dir8));
attacks ^= rayAttacks[dir8][square];
}
return attacks;
}
</pre>
===Branchless===
The branch-less routine provides a dirMask as universal set for negative rays and the empty set for positive rays, to implement the [[BitScan#GeneralizedBitscan|generalized bitscan]]. The dirBit-or ensures to scan at least outer square with empty ray sets.
<pre>
U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {
U64 attacks = rayAttacks[dir8][square];
U64 blocker = attacks & occupied;
blocker &= -blocker | dirMask[dir8];
blocker |= dirBit [dir8]
_BitScanReverse64 (&square, blocker | dirBit[dir8]);
return attacks ^ rayAttacks[dir8][square];
}
</pre>
==Zero Count==
If available, Leading- or Trailing Zero Count instructions may be used instead of bitscan for another branch-less solution of the classical attack getter. Since they leave 64 for empty sets, it needs to make the ray attack [[Array|arrays]] one greater to allow index by 64 which contains an empty set - or one needs to map 64 to 63 for positive directions.
<pre>
U64 rayAttacks[8][65];
U64 getPositiveRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
U64 attacks = rayAttacks[dir8][square];
U64 blocker = attacks & occupied;
int firstBlockingSquare = trailingZeroCount(blocker);
attacks ^= rayAttacks[dir8][firstBlockingSquare];
return attacks;
}
</pre>
LeadingZeroCount instead of bitscanReverse may be done similarly, considering the reversed order.
<span id="Wrapper"></span>
=Line Attacks=
As mentioned, line attacks are the [[General Setwise Operations#Union|union]] of positive and opposite negative [[Rays#RayDirections|ray-directions]] - since they are disjoint one may also use 'xor' or 'add':
<pre>
U64 diagonalAttacks(U64 occ, enumSquare sq) {
return getPositiveRayAttacks(occ, noEa, sq)
| getNegativeRayAttacks(occ, soWe, sq); // ^ +
}
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
return getPositiveRayAttacks(occ, noWe, sq)
| getNegativeRayAttacks(occ, soEa, sq); // ^ +
}
U64 fileAttacks (U64 occ, enumSquare sq) {
return getPositiveRayAttacks(occ, nort, sq)
| getNegativeRayAttacks(occ, sout, sq); // ^ +
}
U64 rankAttacks (U64 occ, enumSquare sq) {
return getPositiveRayAttacks(occ, east, sq)
| getNegativeRayAttacks(occ, west, sq); // ^ +
}
</pre>
=Piece Attacks=
==Union of Line Attacks==
Of course piece attacks are the union of the line attacks:
<pre>
U64 rookAttacks (U64 occ, enumSquare sq) {
return fileAttacks(occ, sq)
| rankAttacks(occ, sq); // ^ +
}
U64 bishopAttacks (U64 occ, enumSquare sq) {
return diagonalAttacks(occ, sq)
| antiDiagAttacks(occ, sq); // ^ +
}
U64 queenAttacks (U64 occ, enumSquare sq) {
return rookAttacks (occ, sq)
| bishopAttacks(occ, sq); // ^ +
}
</pre>
<span id="InOneRun"></span>
==In one Run==
As mentioned by [[Robert Hyatt]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=299564&t=30356 Re: Yet another bitboard attack generator] by [[Robert Hyatt]], [[CCC]], October 28, 2009</ref>, instead of fetching four [[On an empty Board#RayAttacks|ray-attacks]] on the otherwise empty board, one may already use the [[On an empty Board#PieceAttacks|rook- or bishop attacks]] to reset outer squares from that union set.
A further improvement was suggested by [[Michael Sherwin]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=30971 Modified old 64 bit attack getter] by [[Michael Sherwin]], [[CCC]], December 06, 2009</ref>, to union the occupancy with the outer bits 0 and 63. Together with appropriate bits set in separate ray-masks, this yields to an efficient branchless solution with 13 64-bit operations in total and 4.5 KByte for the lookup tables for both rooks and bishops each.
<pre>
struct {
U64 bitsN; // bits North, including MSB (bit 63)
U64 bitsE; // bits East, including MSB
U64 bitsS; // bits South, including LSB (bit 0 == 1)
U64 bitsW; // bits West, including LSB
} CACHE_ALIGN rayWstop[64];
U64 attacksEmpty[64];
U64 rayN[64];
U64 rayE[64];
U64 rayS[64];
U64 rayW[64];
U64 rookAttacks(U64 occ, unsigned int sq) {
unsigned long ulN, ulE, ulS, ulW;
occ |= C64(0x8000000000000001);
_BitScanForward64(&ulN, occ & rayWstop[sq].bitsN);
_BitScanForward64(&ulE, occ & rayWstop[sq].bitsE);
_BitScanReverse64(&ulS, occ & rayWstop[sq].bitsS);
_BitScanReverse64(&ulW, occ & rayWstop[sq].bitsW);
return attacksEmpty[sq]^rayN[ulN]^rayE[ulE]^rayS[ulS]^rayW[ulW];
}
</pre>
=See also=
* [[Bitfoot#ABBitboards|Bitfoot - A/B Bitboards]]
* [[Blockers and Beyond]]
* [[Obstruction Difference]]
* [[Pieces versus Directions]]
=Publications=
* [[Stuart Cracraft]] ('''1984'''). ''Bitmap move generation in Chess''. [[ICGA Journal|ICCA Journal]], Vol. 7, No. 3, pp. 146–153
* [[Fridel Fainshtein]] ('''2006'''). ''An Orthodox k-Move Problem-Composer for Chess Directmates''. M.Sc. thesis, [[Bar-Ilan University]], [http://www.problemschach.de/KMOVEComposer.pdf pdf], Appendix D - 64-bit Representation, pp. 105
* [[Fridel Fainshtein]], [[Yaakov HaCohen-Kerner]] ('''2006'''). ''A Chess Composer of Two-Move Mate Problems''. [[ICGA Journal]], Vol. 29, No. 1, [http://homedir.jct.ac.il/~kerner/pdf_docs/ICGA_computer_composer.pdf pdf], Appendix E: 64-bit representation
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=257692&t=27113 Re: Thinker output] by [[Robert Hyatt]], [[CCC]], March 25, 2009
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=299564&t=30356 Re: Yet another bitboard attack generator] by [[Robert Hyatt]], [[CCC]], October 28, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=30971 Modified old 64 bit attack getter] by [[Michael Sherwin]], [[CCC]], December 06, 2009
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
[[File:Classical Grotesque MET DT7804.jpg|border|right|thumb|[[Arts#Klee|Paul Klee]] - Classical Grotesque, 1923 <ref>[[Arts#Klee|Paul Klee]] - Classical Grotesque, 1923, [https://commons.wikimedia.org/wiki/File:Classical_Grotesque_MET_DT7804.jpg] [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art Metropolitan Museum of Art]</ref>]]
The classical approach to generate [[Sliding Pieces|sliding piece]] attacks was probably first used by [[Chess (Program)|Chess]] and [[Kaissa]].
{{MappingHint}}
=Ray Attacks=
The classical approach works ray-wise and uses pre-calculated [[On an empty Board#RayAttacks|ray-attacks]] for each of the eight [[Rays#RayDirections|ray-directions]] and each of the 64 [[Squares|squares]]. It has to distinguish between [[On an empty Board#PositiveRays|positive]] and [[On an empty Board#NegativeRays|negative]] directions, because it has to [[BitScan|bitscan]] the ray-attack intersection with the [[Occupancy|occupancy]] in different orders. That usually don't cares for getting line- or piece attacks, since one likely unrolls all directions needed for a particular line or piece - otherwise one may rely on a [[BitScan#GeneralizedBitscan|generalized bitscan]].
''We rely on the compass rose to enumerate ray-directions:''
<pre>
noWe nort noEa
+7 +8 +9
\ | /
west -1 <- 0 -> +1 east
/ | \
-9 -8 -7
soWe sout soEa
</pre>
==Positive Rays==
Attacks of Positive Ray-Directions:
<pre>
East (+1) North (+8) NorthEast (+9) NorthWest (+7)
. . . . . . . . . . . 1 . . . . . . . . . . . 1 . . . . . . . .
. . . . . . . . . . . 1 . . . . . . . . . . 1 . 1 . . . . . . .
. . . . . . . . . . . 1 . . . . . . . . . 1 . . . 1 . . . . . .
. . . . . . . . . . . 1 . . . . . . . . 1 . . . . . 1 . . . . .
. . . R 1 1 1 1 . . . R . . . . . . . B . . . . . . . B . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
</pre>
===Conditional===
The first step gets the [[On an empty Board#RayAttacks|ray-attack]] on the otherwise empty board. Potential blockers are then determined by intersection with the [[Occupancy|occupancy]], the set of all pieces. The first blocker, if any, is the least significant one-bit of the intersection. A [[BitScan#Bitscanforward|bitscan forward]] determines the square of the first blocker, to reset it's ray-bits from the attack set. For instance a bishop on g2:
<pre>
occupied & NorthWest(g2) {a8, c6}
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 B 1 . . . . . . . . . . . . . . . .
1 1 1 1 1 . 1 1 . . . . . . . . . . . . . . . .
xor NorthWest(c6 = bitscanForward{a8,c6}
1 . . . . . . .
. 1 . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
= final northWest Attacks
. . . . . . . .
. . . . . . . .
. . 1 . . . . .
. . . 1 . . . .
. . . . 1 . . .
. . . . . 1 . .
. . . . . . . .
. . . . . . . .
</pre>
<pre>
U64 rayAttacks[8][64];
U64 getPositiveRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
U64 attacks = rayAttacks[dir8][square];
U64 blocker = attacks & occupied;
if ( blocker ) {
square = bitScanForward(blocker);
attacks ^= rayAttacks[dir8][square];
}
return attacks;
}
</pre>
<span id="Branchless"></span>
===Branchless===
Branches are evil with todays super pipelined processors. Even if branch-prediction heuristics become smarter, [[Avoiding Branches|branch-less]] solutions allow better scheduling and parallel speedup of independent instruction chains, like processing several directions.
Considering todays fast [[x86-64]] [[x86-64#gpinstructions|bsf-instruction]] of [https://en.wikipedia.org/wiki/Intel_Core_2 Core 2] or [https://en.wikipedia.org/wiki/AMD_K10 K10], a branch-less solution may be worth a try. Due to the fact the [[Occupancy|occupancy]] of [[First Rank Attacks#TheOuterSquares|the outer squares]] doesn't affect the attack set, setting the most significant bit ensures to scan at least an outer square, which would address an empty ray set anyway, therefor not affecting the final result with no blocker or a most outer one.
<pre>
U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {
U64 attacks = rayAttacks[dir8][square];
U64 blocker = attacks & occupied;
_BitScanForward64 (&square, blocker | C64(0x8000000000000000));
return attacks ^ rayAttacks[dir8][square];
}
</pre>
==Negative Rays==
Attacks of Negative Ray-Directions:
<pre>
West (-1) South (-8) SouthWest (-9) SouthEast (-7)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 1 1 R . . . . . . . R . . . . . . . B . . . . . . . B . . . .
. . . . . . . . . . . 1 . . . . . . 1 . . . . . . . . . 1 . . .
. . . . . . . . . . . 1 . . . . . 1 . . . . . . . . . . . 1 . .
. . . . . . . . . . . 1 . . . . 1 . . . . . . . . . . . . . 1 .
</pre>
===Conditional===
Works the same way, but needs [[BitScan#Bitscanreverse|reverse bitscan]] to find the first blocking piece, if any.
<pre>
U64 getNegativeRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
U64 attacks = rayAttacks[dir8][square];
U64 blocker = attacks & occupied;
if ( blocker ) {
square = bitScanReverse(blocker);
attacks ^= rayAttacks[dir8][square];
}
return attacks;
}
</pre>
===Branchless===
The branch-less solution with a fast [[x86-64]] [[x86-64#gpinstructions|bsr-instruction]] allows better scheduling and parallel speedup of independent instruction chains, like processing several directions. Setting the least significant bit ensures to scan at least an outer square, which would address an empty ray set anyway, therefor not affecting the final result with no blocker or a most outer one.
<pre>
U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {
U64 attacks = rayAttacks[dir8][square];
U64 blocker = attacks & occupied;
_BitScanReverse64 (&square, blocker | 1);
return attacks ^ rayAttacks[dir8][square];
}
</pre>
<span id="Generalized"></span>
==Generalized==
The idea of the [[BitScan#GeneralizedBitscan|generalized bitscan]] may be used to share the same code for all directions. The implementation of isNegative(dir8), a macro or inline-function, depends on the definition or enumeration of the directions and is likely a compare or test instruction.
===Conditional===
The conditional by a good predictable branch on blocker is favorable - specially for slow bitscans with some chance to skip it, e.g. in endings.
<pre>
U64 getRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
U64 attacks = rayAttacks[dir8][square];
U64 blocker = attacks & occupied;
if ( blocker ) {
square = bitScan(blocker, isNegative(dir8));
attacks ^= rayAttacks[dir8][square];
}
return attacks;
}
</pre>
===Branchless===
The branch-less routine provides a dirMask as universal set for negative rays and the empty set for positive rays, to implement the [[BitScan#GeneralizedBitscan|generalized bitscan]]. The dirBit-or ensures to scan at least outer square with empty ray sets.
<pre>
U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {
U64 attacks = rayAttacks[dir8][square];
U64 blocker = attacks & occupied;
blocker &= -blocker | dirMask[dir8];
blocker |= dirBit [dir8]
_BitScanReverse64 (&square, blocker | dirBit[dir8]);
return attacks ^ rayAttacks[dir8][square];
}
</pre>
==Zero Count==
If available, Leading- or Trailing Zero Count instructions may be used instead of bitscan for another branch-less solution of the classical attack getter. Since they leave 64 for empty sets, it needs to make the ray attack [[Array|arrays]] one greater to allow index by 64 which contains an empty set - or one needs to map 64 to 63 for positive directions.
<pre>
U64 rayAttacks[8][65];
U64 getPositiveRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {
U64 attacks = rayAttacks[dir8][square];
U64 blocker = attacks & occupied;
int firstBlockingSquare = trailingZeroCount(blocker);
attacks ^= rayAttacks[dir8][firstBlockingSquare];
return attacks;
}
</pre>
LeadingZeroCount instead of bitscanReverse may be done similarly, considering the reversed order.
<span id="Wrapper"></span>
=Line Attacks=
As mentioned, line attacks are the [[General Setwise Operations#Union|union]] of positive and opposite negative [[Rays#RayDirections|ray-directions]] - since they are disjoint one may also use 'xor' or 'add':
<pre>
U64 diagonalAttacks(U64 occ, enumSquare sq) {
return getPositiveRayAttacks(occ, noEa, sq)
| getNegativeRayAttacks(occ, soWe, sq); // ^ +
}
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
return getPositiveRayAttacks(occ, noWe, sq)
| getNegativeRayAttacks(occ, soEa, sq); // ^ +
}
U64 fileAttacks (U64 occ, enumSquare sq) {
return getPositiveRayAttacks(occ, nort, sq)
| getNegativeRayAttacks(occ, sout, sq); // ^ +
}
U64 rankAttacks (U64 occ, enumSquare sq) {
return getPositiveRayAttacks(occ, east, sq)
| getNegativeRayAttacks(occ, west, sq); // ^ +
}
</pre>
=Piece Attacks=
==Union of Line Attacks==
Of course piece attacks are the union of the line attacks:
<pre>
U64 rookAttacks (U64 occ, enumSquare sq) {
return fileAttacks(occ, sq)
| rankAttacks(occ, sq); // ^ +
}
U64 bishopAttacks (U64 occ, enumSquare sq) {
return diagonalAttacks(occ, sq)
| antiDiagAttacks(occ, sq); // ^ +
}
U64 queenAttacks (U64 occ, enumSquare sq) {
return rookAttacks (occ, sq)
| bishopAttacks(occ, sq); // ^ +
}
</pre>
<span id="InOneRun"></span>
==In one Run==
As mentioned by [[Robert Hyatt]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=299564&t=30356 Re: Yet another bitboard attack generator] by [[Robert Hyatt]], [[CCC]], October 28, 2009</ref>, instead of fetching four [[On an empty Board#RayAttacks|ray-attacks]] on the otherwise empty board, one may already use the [[On an empty Board#PieceAttacks|rook- or bishop attacks]] to reset outer squares from that union set.
A further improvement was suggested by [[Michael Sherwin]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=30971 Modified old 64 bit attack getter] by [[Michael Sherwin]], [[CCC]], December 06, 2009</ref>, to union the occupancy with the outer bits 0 and 63. Together with appropriate bits set in separate ray-masks, this yields to an efficient branchless solution with 13 64-bit operations in total and 4.5 KByte for the lookup tables for both rooks and bishops each.
<pre>
struct {
U64 bitsN; // bits North, including MSB (bit 63)
U64 bitsE; // bits East, including MSB
U64 bitsS; // bits South, including LSB (bit 0 == 1)
U64 bitsW; // bits West, including LSB
} CACHE_ALIGN rayWstop[64];
U64 attacksEmpty[64];
U64 rayN[64];
U64 rayE[64];
U64 rayS[64];
U64 rayW[64];
U64 rookAttacks(U64 occ, unsigned int sq) {
unsigned long ulN, ulE, ulS, ulW;
occ |= C64(0x8000000000000001);
_BitScanForward64(&ulN, occ & rayWstop[sq].bitsN);
_BitScanForward64(&ulE, occ & rayWstop[sq].bitsE);
_BitScanReverse64(&ulS, occ & rayWstop[sq].bitsS);
_BitScanReverse64(&ulW, occ & rayWstop[sq].bitsW);
return attacksEmpty[sq]^rayN[ulN]^rayE[ulE]^rayS[ulS]^rayW[ulW];
}
</pre>
=See also=
* [[Bitfoot#ABBitboards|Bitfoot - A/B Bitboards]]
* [[Blockers and Beyond]]
* [[Obstruction Difference]]
* [[Pieces versus Directions]]
=Publications=
* [[Stuart Cracraft]] ('''1984'''). ''Bitmap move generation in Chess''. [[ICGA Journal|ICCA Journal]], Vol. 7, No. 3, pp. 146–153
* [[Fridel Fainshtein]] ('''2006'''). ''An Orthodox k-Move Problem-Composer for Chess Directmates''. M.Sc. thesis, [[Bar-Ilan University]], [http://www.problemschach.de/KMOVEComposer.pdf pdf], Appendix D - 64-bit Representation, pp. 105
* [[Fridel Fainshtein]], [[Yaakov HaCohen-Kerner]] ('''2006'''). ''A Chess Composer of Two-Move Mate Problems''. [[ICGA Journal]], Vol. 29, No. 1, [http://homedir.jct.ac.il/~kerner/pdf_docs/ICGA_computer_composer.pdf pdf], Appendix E: 64-bit representation
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=257692&t=27113 Re: Thinker output] by [[Robert Hyatt]], [[CCC]], March 25, 2009
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=299564&t=30356 Re: Yet another bitboard attack generator] by [[Robert Hyatt]], [[CCC]], October 28, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=30971 Modified old 64 bit attack getter] by [[Michael Sherwin]], [[CCC]], December 06, 2009
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
