25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks''' FILE:Queen's_Star.jpg|border|right|thumb|267px|link=http://www.carinajorgensen.c..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * Sliding Piece Attacks'''
[[FILE:Queen's_Star.jpg|border|right|thumb|267px|link=http://www.carinajorgensen.com/Chess/queensstar.php|[[Arts#Jørgensen|Carina Jørgensen]], Queen's Star <ref>[http://www.carinajorgensen.com/Chess/queensstar.php Queen's Star] 2009 by [[Arts#Jørgensen|Carina Jørgensen]]</ref> ]]
**Sliding Piece Attacks** covers calculation of attack-sets of [[Sliding Pieces|sliding pieces]] for [[Evaluation|evaluation]] and [[Move Generation|move-generation]] purposes. While the attack-sets of [[Pawn|pawn]], [[King|king]] and [[Knight|knight]] are only dependent on their [[Origin Square|origin square]], sliding pieces like [[Rook|rook]], [[Bishop|bishop]] or [[Queen|queen]] have to consider [[Occupancy|occupancy]], as [[Pieces|pieces]] may block the attack-ray in one particular [[Direction|direction]].
=Move targets=
Move target sets from attack-sets require [[General Setwise Operations#Intersection|intersection]]
* with opponent pieces for [[Captures|captures]]
* with all empty squares for [[Quiet Moves|quiet moves]]
<span id="SingleSlidingPieceAttacks"></span>
=Single Sliding Piece Attacks=
The single sliding piece, a rook, bishop or queen is determined by square index, likely from a [[BitScan|bitscan]] of a piece-wise [[Bitboard Serialization|bitboard serialization]] of a sliding piece bitboard from a [[Bitboard Board-Definition|standard board-definition]].
==On an empty Board==
Sliding piece attack sets or their disjoint subsets on lines or rays on an otherwise empty board are that simple than none sliding pieces. They are often base of further attack calculations.
* [[On an empty Board|Attacks on the otherwise empty Board]]
==Tinker's Approach==
[[Brian Richardson]] proposed a move generation approach as used in [[Tinker]] based on rook or bishop attacks on the otherwise empty board <ref>[https://www.stmintz.com/ccc/index.php?id=107485 Movegen Re: Bitmap Type Re: Tinker 81 secs Re: Testing speed] by [[Brian Richardson]], [[CCC]], April 24, 2000</ref>. While [[Bitboard Serialization|serializing]] all potential targets, he tests for legality inside the loop body, that is whether the [[Square Attacked By#InBetween|inbetween squares]] of [[Origin Square|origin]] and [[Target Square|target]] are empty. This is not in the "real" bitboard spirit to determine attack sets in advance rather than to test individual elements of a superset belonging to a set, but at least it allows traversing disjoint target sets i.e. for captures in [[Quiescence Search|quiescence search]].
==By Calculation==
Some [[Bit-Twiddling|bit-twiddling]] ray-wise and line-wise approaches, unfortunately not always for all directions.
* [[Blockers and Beyond]]
* [[Classical Approach]]
: [[Bitfoot#ABBitboards|Bitfoot - A/B Bitboards]]
* [[Shifted Bitboards]]
* [[Subtracting a Rook from a Blocking Piece]]
* [[Reverse Bitboards]]
* [[Hyperbola Quintessence]]
* [[Obstruction Difference]]
* [[SBAMG]]
* [[Exploding Bitboards]]
<span id="AttacksbyOccupancyLookup"></span>
==By Occupancy Lookup==
Covering line-attacks in one run, [[Magic Bitboards|magic bitboards]] even covers rook- and bishop-attacks in one run.
* [[First Rank Attacks]]
* [[Occupancy of any Line]]
* [[Rotated Bitboards]]
* [[Rotated Indices]]
* [[Kindergarten Bitboards]]
: [[OliThink#SlidingPieceAttacks|Sliding Piece Attacks]] in [[OliThink]]
* [[Hashing Dictionaries]]
* [[Congruent Modulo Bitboards]]
* [[Magic Bitboards]]
: [[BMI2#PEXTBitboards|BMI2 - PEXT Bitboards]]
* [[Sherwin Bitboards]]
* [[Titboards]]
==Miscellaneous==
* [[The switch Approach]]
* [[SIMD techniques]]
* [[Hiding the Implementation]]
<span id="Multiple"></span>
=Multiple Sliding Pieces=
For bitsets with multiple sliding pieces one can apply a [[Fill Algorithms|fill algorithm]] in each of the eight [[Rays#RayDirections|ray-directions]] to determine attacks. Since we keep disjoint directions, there is still a unique 1:1 relation from each bit of the target set to it's source square. This approach is great to determine target sets we may reach in two or more moves. One may use the union of rooks and queen(s), respectively bishops or queen(s) though.
* [[Dumb7Fill]]
: [[AVX2#Dumb7Fill|AVX2 Dumb7Fill]]
* [[Kogge-Stone Algorithm]]
* [[Fill by Subtraction]]
If applied for [[Move Generation|move generation]] we better traverse directions rather than sliding pieces. Naturally this approach becomes less efficient, the less sliders are processed in parallel. Of course, one should avoid processing empty sets.
=See also=
* [[Efficient Generation of Sliding Piece Attacks]], a Summary of selected attack generation techniques, a short Talk by [[Gerd Isenberg]] from the [[Workshop Chess and Mathematics]], [https://en.wikipedia.org/wiki/Dresden Dresden], November 21st and 22nd, 2008
* [[Combinatorial Logic#CombinatorialAttackandDefendMap|Combinatorial Logic - Combinatorial Attacks]]
* [[Sequential Logic#SequentialRookAttack|Sequential Logic - Sequential Rook Attack]]
* [[Vector Attacks]]
=Forum Posts=
==1999==
* [https://www.stmintz.com/ccc/index.php?id=71016 Re: How do you represent chess boards in your chess programms] by [[Sven Reichard]], [[CCC]], September 29, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=107485 Movegen Re: Bitmap Type Re: Tinker 81 secs Re: Testing speed] by [[Brian Richardson]], [[CCC]], April 24, 2000
* [https://www.stmintz.com/ccc/index.php?id=134490 An idea to generate rook moves without rotated BBs] by [[Severi Salminen]], [[CCC]], October 22, 2000
* [https://www.stmintz.com/ccc/index.php?id=359243 sliding attacks in three #define] by [[Rasjid Chan]], [[CCC]], April 09, 2004
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=16002 BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits] by [[Brian Richardson]], [[CCC]], August 24, 2007
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=140111&t=16002 Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits] by [[Harald Lüßen]], [[CCC]], August 24, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=30356 Yet another bitboard attack generator] by [[Miguel A. Ballicora]], [[CCC]], October 28, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=30369 Other attack generator just for good measure ... C++ only...] by [[Filip Tvrzsky]], [[CCC]], October 29, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=30542 Caching AttackSets] by [[Michael Hoffmann]], [[CCC]], November 09, 2009
==2010 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=51076 Bitboards] by Jeroen de Bruin, [[Computer Chess Forums|Winboard Forum]], July 07, 2010
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=51996 Low memory usage attack bitboard generation] by crystalclear, [[Computer Chess Forums|Winboard Forum]], October 06, 2011
* [http://www.talkchess.com/forum/viewtopic.php?p=446380 Re: Bitboard implementation, how much time?] by [[Michael Hoffmann]], [[CCC]], January 26, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=49611 152k rook and bishop attacks using PEXT and PDEP] by [[Lasse Hansen]], [[CCC]], October 06, 2013 » [[BMI2]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55418 On Rook tables in magic move generation] by [[Syed Fahad]], [[CCC]], February 22, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55604 Yet another way of generating sliding attack masks] by [[Syed Fahad]], [[CCC]], March 09, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56468 Slider attack mask generation without table lookup] by [[Syed Fahad]], [[CCC]], May 24, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58795 Comparison of bitboard attack-getter variants] by [[Sven Schüle]], [[CCC]], January 04, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=59845 SBAMG - Completing Hyperbola Quintessence] by [[Syed Fahad]], [[CCC]], April 10, 2016
=External Links=
* [https://en.wikipedia.org/wiki/Slide_attack Slide attack from Wikipedia]
* [[Videos#Focus|Focus]] - Glider, [https://en.wikipedia.org/wiki/Ship_of_Memories Ship of Memories] 1976, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=kcYXSutFCXA|alignment=left|valignment=top}}
=References=
<references />
'''[[Bitboards|Up one Level]]'''
[[FILE:Queen's_Star.jpg|border|right|thumb|267px|link=http://www.carinajorgensen.com/Chess/queensstar.php|[[Arts#Jørgensen|Carina Jørgensen]], Queen's Star <ref>[http://www.carinajorgensen.com/Chess/queensstar.php Queen's Star] 2009 by [[Arts#Jørgensen|Carina Jørgensen]]</ref> ]]
**Sliding Piece Attacks** covers calculation of attack-sets of [[Sliding Pieces|sliding pieces]] for [[Evaluation|evaluation]] and [[Move Generation|move-generation]] purposes. While the attack-sets of [[Pawn|pawn]], [[King|king]] and [[Knight|knight]] are only dependent on their [[Origin Square|origin square]], sliding pieces like [[Rook|rook]], [[Bishop|bishop]] or [[Queen|queen]] have to consider [[Occupancy|occupancy]], as [[Pieces|pieces]] may block the attack-ray in one particular [[Direction|direction]].
=Move targets=
Move target sets from attack-sets require [[General Setwise Operations#Intersection|intersection]]
* with opponent pieces for [[Captures|captures]]
* with all empty squares for [[Quiet Moves|quiet moves]]
<span id="SingleSlidingPieceAttacks"></span>
=Single Sliding Piece Attacks=
The single sliding piece, a rook, bishop or queen is determined by square index, likely from a [[BitScan|bitscan]] of a piece-wise [[Bitboard Serialization|bitboard serialization]] of a sliding piece bitboard from a [[Bitboard Board-Definition|standard board-definition]].
==On an empty Board==
Sliding piece attack sets or their disjoint subsets on lines or rays on an otherwise empty board are that simple than none sliding pieces. They are often base of further attack calculations.
* [[On an empty Board|Attacks on the otherwise empty Board]]
==Tinker's Approach==
[[Brian Richardson]] proposed a move generation approach as used in [[Tinker]] based on rook or bishop attacks on the otherwise empty board <ref>[https://www.stmintz.com/ccc/index.php?id=107485 Movegen Re: Bitmap Type Re: Tinker 81 secs Re: Testing speed] by [[Brian Richardson]], [[CCC]], April 24, 2000</ref>. While [[Bitboard Serialization|serializing]] all potential targets, he tests for legality inside the loop body, that is whether the [[Square Attacked By#InBetween|inbetween squares]] of [[Origin Square|origin]] and [[Target Square|target]] are empty. This is not in the "real" bitboard spirit to determine attack sets in advance rather than to test individual elements of a superset belonging to a set, but at least it allows traversing disjoint target sets i.e. for captures in [[Quiescence Search|quiescence search]].
==By Calculation==
Some [[Bit-Twiddling|bit-twiddling]] ray-wise and line-wise approaches, unfortunately not always for all directions.
* [[Blockers and Beyond]]
* [[Classical Approach]]
: [[Bitfoot#ABBitboards|Bitfoot - A/B Bitboards]]
* [[Shifted Bitboards]]
* [[Subtracting a Rook from a Blocking Piece]]
* [[Reverse Bitboards]]
* [[Hyperbola Quintessence]]
* [[Obstruction Difference]]
* [[SBAMG]]
* [[Exploding Bitboards]]
<span id="AttacksbyOccupancyLookup"></span>
==By Occupancy Lookup==
Covering line-attacks in one run, [[Magic Bitboards|magic bitboards]] even covers rook- and bishop-attacks in one run.
* [[First Rank Attacks]]
* [[Occupancy of any Line]]
* [[Rotated Bitboards]]
* [[Rotated Indices]]
* [[Kindergarten Bitboards]]
: [[OliThink#SlidingPieceAttacks|Sliding Piece Attacks]] in [[OliThink]]
* [[Hashing Dictionaries]]
* [[Congruent Modulo Bitboards]]
* [[Magic Bitboards]]
: [[BMI2#PEXTBitboards|BMI2 - PEXT Bitboards]]
* [[Sherwin Bitboards]]
* [[Titboards]]
==Miscellaneous==
* [[The switch Approach]]
* [[SIMD techniques]]
* [[Hiding the Implementation]]
<span id="Multiple"></span>
=Multiple Sliding Pieces=
For bitsets with multiple sliding pieces one can apply a [[Fill Algorithms|fill algorithm]] in each of the eight [[Rays#RayDirections|ray-directions]] to determine attacks. Since we keep disjoint directions, there is still a unique 1:1 relation from each bit of the target set to it's source square. This approach is great to determine target sets we may reach in two or more moves. One may use the union of rooks and queen(s), respectively bishops or queen(s) though.
* [[Dumb7Fill]]
: [[AVX2#Dumb7Fill|AVX2 Dumb7Fill]]
* [[Kogge-Stone Algorithm]]
* [[Fill by Subtraction]]
If applied for [[Move Generation|move generation]] we better traverse directions rather than sliding pieces. Naturally this approach becomes less efficient, the less sliders are processed in parallel. Of course, one should avoid processing empty sets.
=See also=
* [[Efficient Generation of Sliding Piece Attacks]], a Summary of selected attack generation techniques, a short Talk by [[Gerd Isenberg]] from the [[Workshop Chess and Mathematics]], [https://en.wikipedia.org/wiki/Dresden Dresden], November 21st and 22nd, 2008
* [[Combinatorial Logic#CombinatorialAttackandDefendMap|Combinatorial Logic - Combinatorial Attacks]]
* [[Sequential Logic#SequentialRookAttack|Sequential Logic - Sequential Rook Attack]]
* [[Vector Attacks]]
=Forum Posts=
==1999==
* [https://www.stmintz.com/ccc/index.php?id=71016 Re: How do you represent chess boards in your chess programms] by [[Sven Reichard]], [[CCC]], September 29, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=107485 Movegen Re: Bitmap Type Re: Tinker 81 secs Re: Testing speed] by [[Brian Richardson]], [[CCC]], April 24, 2000
* [https://www.stmintz.com/ccc/index.php?id=134490 An idea to generate rook moves without rotated BBs] by [[Severi Salminen]], [[CCC]], October 22, 2000
* [https://www.stmintz.com/ccc/index.php?id=359243 sliding attacks in three #define] by [[Rasjid Chan]], [[CCC]], April 09, 2004
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=16002 BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits] by [[Brian Richardson]], [[CCC]], August 24, 2007
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=140111&t=16002 Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits] by [[Harald Lüßen]], [[CCC]], August 24, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=30356 Yet another bitboard attack generator] by [[Miguel A. Ballicora]], [[CCC]], October 28, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=30369 Other attack generator just for good measure ... C++ only...] by [[Filip Tvrzsky]], [[CCC]], October 29, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=30542 Caching AttackSets] by [[Michael Hoffmann]], [[CCC]], November 09, 2009
==2010 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=51076 Bitboards] by Jeroen de Bruin, [[Computer Chess Forums|Winboard Forum]], July 07, 2010
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=51996 Low memory usage attack bitboard generation] by crystalclear, [[Computer Chess Forums|Winboard Forum]], October 06, 2011
* [http://www.talkchess.com/forum/viewtopic.php?p=446380 Re: Bitboard implementation, how much time?] by [[Michael Hoffmann]], [[CCC]], January 26, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=49611 152k rook and bishop attacks using PEXT and PDEP] by [[Lasse Hansen]], [[CCC]], October 06, 2013 » [[BMI2]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55418 On Rook tables in magic move generation] by [[Syed Fahad]], [[CCC]], February 22, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=55604 Yet another way of generating sliding attack masks] by [[Syed Fahad]], [[CCC]], March 09, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56468 Slider attack mask generation without table lookup] by [[Syed Fahad]], [[CCC]], May 24, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58795 Comparison of bitboard attack-getter variants] by [[Sven Schüle]], [[CCC]], January 04, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=59845 SBAMG - Completing Hyperbola Quintessence] by [[Syed Fahad]], [[CCC]], April 10, 2016
=External Links=
* [https://en.wikipedia.org/wiki/Slide_attack Slide attack from Wikipedia]
* [[Videos#Focus|Focus]] - Glider, [https://en.wikipedia.org/wiki/Ship_of_Memories Ship of Memories] 1976, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=kcYXSutFCXA|alignment=left|valignment=top}}
=References=
<references />
'''[[Bitboards|Up one Level]]'''
