Difference between revisions of "Sliding Piece Attacks"

From Chessprogramming wiki
Jump to: navigation, search
(9 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|[[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> ]]  
+
[[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 45: Line 45:
 
: [[BMI2#PEXTBitboards|BMI2 - PEXT Bitboards]]
 
: [[BMI2#PEXTBitboards|BMI2 - PEXT Bitboards]]
 
* [[Sherwin Bitboards]]
 
* [[Sherwin Bitboards]]
 +
: [[SISSY Bitboards]]
 
* [[Titboards]]
 
* [[Titboards]]
  
 
==Miscellaneous==  
 
==Miscellaneous==  
* [[The switch Approach]]
+
* [[The Switch Approach]]
* [[SIMD techniques]]
+
* [[SIMD Techniques]]
 
* [[Hiding the Implementation]]
 
* [[Hiding the Implementation]]
 
<span id="Multiple"></span>
 
<span id="Multiple"></span>
Line 88: Line 89:
 
* [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]]
  
 
=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]
* [[Videos#Focus|Focus]] - Glider, [https://en.wikipedia.org/wiki/Ship_of_Memories Ship of Memories] 1976, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
+
* [[:Category: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}}
 
: {{#evu:https://www.youtube.com/watch?v=kcYXSutFCXA|alignment=left|valignment=top}}
  
Line 101: Line 108:
  
 
'''[[Bitboards|Up one Level]]'''
 
'''[[Bitboards|Up one Level]]'''
 +
[[Category:Carina Jørgensen]]
 +
[[Category:Focus]]

Revision as of 13:40, 16 February 2020

Home * Board Representation * Bitboards * Sliding Piece Attacks

Carina Jørgensen, Queen's Star [1]

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.

Move targets

Move target sets from attack-sets require intersection

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.

Bitfoot - A/B Bitboards

By Occupancy Lookup

Covering line-attacks in one run, magic bitboards even covers rook- and bishop-attacks in one run.

Sliding Piece Attacks in OliThink
BMI2 - PEXT Bitboards
SISSY Bitboards

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.

AVX2 Dumb7Fill

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

Forum Posts

1999

2000 ...

2005 ...

Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Harald Lüßen, CCC, August 24, 2007

2010 ...

2015 ...

2020 ...

External Links

References

Up one Level