Difference between revisions of "Sliding Piece Attacks"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
(13 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * Sliding Piece Attacks''' | '''[[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|[[ | + | [[FILE:Queen's_Star.jpg|border|right|thumb|267px|link=http://www.carinajorgensen.com/Chess/queensstar.php| [[:Category:Carina Jørgensen|Carina Jørgensen]], Queen's Star <ref>[http://www.carinajorgensen.com/Chess/queensstar.php Queen's Star] 2009 by [[:Category:Carina Jørgensen|Carina Jørgensen]]</ref> ]] |
− | This is basically about how to calculate 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]]. | + | This is basically about how to calculate [[Attacks|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 targets= | ||
Line 25: | Line 25: | ||
* [[Classical Approach]] | * [[Classical Approach]] | ||
: [[Bitfoot#ABBitboards|Bitfoot - A/B Bitboards]] | : [[Bitfoot#ABBitboards|Bitfoot - A/B Bitboards]] | ||
− | + | : [[CFish#AVX2 Attacks|CFish - AVX2 Attacks]] | |
− | * [[ | + | * [[Exploding Bitboards]] |
* [[Hyperbola Quintessence]] | * [[Hyperbola Quintessence]] | ||
+ | * [[Leorik#LeorikAttacks|Leorik Attacks]] | ||
* [[Obstruction Difference]] | * [[Obstruction Difference]] | ||
+ | * [[Reverse Bitboards]] | ||
* [[SBAMG]] | * [[SBAMG]] | ||
− | * [[ | + | * [[Shifted Bitboards]] |
+ | * [[Subtracting a Rook from a Blocking Piece]] | ||
<span id="AttacksbyOccupancyLookup"></span> | <span id="AttacksbyOccupancyLookup"></span> | ||
==By Occupancy Lookup== | ==By Occupancy Lookup== | ||
Line 45: | Line 48: | ||
: [[BMI2#PEXTBitboards|BMI2 - PEXT Bitboards]] | : [[BMI2#PEXTBitboards|BMI2 - PEXT Bitboards]] | ||
* [[Sherwin Bitboards]] | * [[Sherwin Bitboards]] | ||
+ | : [[SISSY Bitboards]] | ||
* [[Titboards]] | * [[Titboards]] | ||
Line 84: | Line 88: | ||
* [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.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?p=446380 Re: Bitboard implementation, how much time?] by [[Michael Hoffmann]], [[CCC]], January 26, 2012 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=49562 Simplest bitboard attack generation] by [[Russell Reagan]], [[CCC]], October 03, 2013 | ||
* [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]] | * [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 ...== | ==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=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=55604 Yet another way of generating sliding attack masks] by [[Syed Fahad]], [[CCC]], March 09, 2015 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=55739 New idea for Rook magic moves storage] by [[Fermin Serrano]], [[CCC]], March 22, 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=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=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 | * [http://www.talkchess.com/forum/viewtopic.php?t=59845 SBAMG - Completing Hyperbola Quintessence] by [[Syed Fahad]], [[CCC]], April 10, 2016 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=68741 very small bitboard move/attack generator] by [[Vivien Clauzon]], [[CCC]], October 27, 2018 | ||
+ | ==2020 ...== | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73063 New RookAttacks() - possibly] by [[Michael Sherwin]], [[CCC]], February 12, 2020 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73082 scan-cut slider attack generation] by [[Martin Sedlak]], [[CCC]], February 13, 2020 » [[Bitfoot#ABBitboards|A/B Bitboards]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73083 Split Index Super Set Yielding (SISSY) Bitboards] by [[Michael Sherwin]], [[CCC]], February 13, 2020 » [[SISSY Bitboards]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77133 I did some magic bitboard "science" and mostly learned not to worry about it] by [[Jakob Progsch]], [[CCC]], April 20, 2021 | ||
+ | * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=78693 Combining two of Bob's classic bitboard attack getters] by [[Michael Sherwin|Mike Sherwin]], [[CCC]], November 19, 2021 | ||
+ | * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=78843 Faster than Fancy magic: Hypercube Slider lookup <nowiki>[TEASER]</nowiki>] by [[Daniel Infuehr]], [[CCC]], December 09, 2021 | ||
+ | * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79004 Hypercube Slider Lookup - New Sliding Piece Algorithm <nowiki>[RELEASE]</nowiki>] by [[Daniel Infuehr]], [[CCC]], December 31, 2021 | ||
+ | * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79005 Comparison of all known Sliding lookup algorithms] by [[Daniel Infuehr]], [[CCC]], December 31, 2021 | ||
+ | * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79078 Comparison of all known Sliding lookup algorithms <nowiki>[CUDA]</nowiki>] by [[Daniel Infuehr]], [[CCC]], January 08, 2022 » [[GPU]] | ||
+ | * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79332 Binary Neural Networks Sliding Piece Inference <nowiki>[Release]</nowiki>] by [[Daniel Infuehr]], [[CCC]], February 10, 2022 » [[Neural Networks]] | ||
=External Links= | =External Links= | ||
* [https://en.wikipedia.org/wiki/Slide_attack Slide attack from Wikipedia] | * [https://en.wikipedia.org/wiki/Slide_attack Slide attack from Wikipedia] | ||
− | * [[:Category: | + | * [[:Category:Cymande|Cymande]] - Brothers On The Slide, [https://en.wikipedia.org/wiki/KCRW KCRW] session, [https://en.wikipedia.org/wiki/Santa_Monica,_California Santa Monica], 2016, [https://en.wikipedia.org/wiki/YouTube YouTube] Video |
− | : {{#evu:https://www.youtube.com/watch?v= | + | : {{#evu:https://www.youtube.com/watch?v=RCCSQtRXCnU|alignment=left|valignment=top}} |
=References= | =References= | ||
Line 102: | Line 120: | ||
'''[[Bitboards|Up one Level]]''' | '''[[Bitboards|Up one Level]]''' | ||
[[Category:Carina Jørgensen]] | [[Category:Carina Jørgensen]] | ||
− | [[Category: | + | [[Category:Cymande]] |
Latest revision as of 12:42, 25 March 2022
Home * Board Representation * Bitboards * Sliding Piece Attacks
This is basically about how to calculate attack-sets of sliding pieces for evaluation and move-generation purposes. While the attack-sets of pawn, king and knight are only dependent on their origin square, sliding pieces like rook, bishop or queen have to consider occupancy, as pieces may block the attack-ray in one particular direction.
Contents
Move targets
Move target sets from attack-sets require intersection
- with opponent pieces for captures
- with all empty squares for quiet moves
Single Sliding Piece Attacks
The single sliding piece, a rook, bishop or queen is determined by square index, likely from a bitscan of a piece-wise bitboard serialization of a sliding piece bitboard from a 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.
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 [2]. While serializing all potential targets, he tests for legality inside the loop body, that is whether the inbetween squares of origin and 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.
By Calculation
Some bit-twiddling ray-wise and line-wise approaches, unfortunately not always for all directions.
- Exploding Bitboards
- Hyperbola Quintessence
- Leorik Attacks
- Obstruction Difference
- Reverse Bitboards
- SBAMG
- Shifted Bitboards
- Subtracting a Rook from a Blocking Piece
By Occupancy Lookup
Covering line-attacks in one run, magic bitboards even covers rook- and bishop-attacks in one run.
Miscellaneous
Multiple Sliding Pieces
For bitsets with multiple sliding pieces one can apply a fill algorithm in each of the eight 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.
If applied for 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, Dresden, November 21st and 22nd, 2008
- Combinatorial Logic - Combinatorial Attacks
- Sequential Logic - Sequential Rook Attack
- Vector Attacks
Forum Posts
1999
- Re: How do you represent chess boards in your chess programms by Sven Reichard, CCC, September 29, 1999
2000 ...
- Movegen Re: Bitmap Type Re: Tinker 81 secs Re: Testing speed by Brian Richardson, CCC, April 24, 2000
- An idea to generate rook moves without rotated BBs by Severi Salminen, CCC, October 22, 2000
- sliding attacks in three #define by Rasjid Chan, CCC, April 09, 2004
2005 ...
- BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Brian Richardson, CCC, August 24, 2007
- Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Harald Lüßen, CCC, August 24, 2007
- Yet another bitboard attack generator by Miguel A. Ballicora, CCC, October 28, 2009
- Other attack generator just for good measure ... C++ only... by Filip Tvrzsky, CCC, October 29, 2009
- Caching AttackSets by Michael Hoffmann, CCC, November 09, 2009
2010 ...
- Bitboards by Jeroen de Bruin, Winboard Forum, July 07, 2010
- Low memory usage attack bitboard generation by crystalclear, Winboard Forum, October 06, 2011
- Re: Bitboard implementation, how much time? by Michael Hoffmann, CCC, January 26, 2012
- Simplest bitboard attack generation by Russell Reagan, CCC, October 03, 2013
- 152k rook and bishop attacks using PEXT and PDEP by Lasse Hansen, CCC, October 06, 2013 » BMI2
2015 ...
- On Rook tables in magic move generation by Syed Fahad, CCC, February 22, 2015
- Yet another way of generating sliding attack masks by Syed Fahad, CCC, March 09, 2015
- New idea for Rook magic moves storage by Fermin Serrano, CCC, March 22, 2015
- Slider attack mask generation without table lookup by Syed Fahad, CCC, May 24, 2015
- Comparison of bitboard attack-getter variants by Sven Schüle, CCC, January 04, 2016
- SBAMG - Completing Hyperbola Quintessence by Syed Fahad, CCC, April 10, 2016
- very small bitboard move/attack generator by Vivien Clauzon, CCC, October 27, 2018
2020 ...
- New RookAttacks() - possibly by Michael Sherwin, CCC, February 12, 2020
- scan-cut slider attack generation by Martin Sedlak, CCC, February 13, 2020 » A/B Bitboards
- Split Index Super Set Yielding (SISSY) Bitboards by Michael Sherwin, CCC, February 13, 2020 » SISSY Bitboards
- I did some magic bitboard "science" and mostly learned not to worry about it by Jakob Progsch, CCC, April 20, 2021
- Combining two of Bob's classic bitboard attack getters by Mike Sherwin, CCC, November 19, 2021
- Faster than Fancy magic: Hypercube Slider lookup [TEASER] by Daniel Infuehr, CCC, December 09, 2021
- Hypercube Slider Lookup - New Sliding Piece Algorithm [RELEASE] by Daniel Infuehr, CCC, December 31, 2021
- Comparison of all known Sliding lookup algorithms by Daniel Infuehr, CCC, December 31, 2021
- Comparison of all known Sliding lookup algorithms [CUDA] by Daniel Infuehr, CCC, January 08, 2022 » GPU
- Binary Neural Networks Sliding Piece Inference [Release] by Daniel Infuehr, CCC, February 10, 2022 » Neural Networks
External Links
- Slide attack from Wikipedia
- Cymande - Brothers On The Slide, KCRW session, Santa Monica, 2016, YouTube Video
References
- ↑ Queen's Star 2009 by Carina Jørgensen
- ↑ Movegen Re: Bitmap Type Re: Tinker 81 secs Re: Testing speed by Brian Richardson, CCC, April 24, 2000