25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * Subtracting a Rook from a Blocking Piece''' FILE:BishopKnightRook.jpg|border|..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Subtracting a Rook from a Blocking Piece'''
[[FILE:BishopKnightRook.jpg|border|right|thumb|[[Arts#Bak|Samuel Bak]] - Bishop, Knight, Rook <ref>[https://static1.squarespace.com/static/594044bd3a041171e0426683/t/5a12fe739140b703b4e45d85/1511194240551/Bak%2C+Sam+Your+Move+2003.pdf Chess in the Art of Samuel Bak - BK894] (pdf) from [https://www.puckergallery.com/artists/#/samuel-bak/ Samuel Bak represented by Pucker Gallery since 1969]</ref> ]]
If we think about an [[General Setwise Operations#ArithmeticalOperations|arithmetical operation]] to calculate rank-attacks of a [[Rook|rook]] or [[Queen|queen]] with bitboards, [[General Setwise Operations#Subtraction|subtraction]] comes in mind. The idea is to treat the arithmetical carry, or inverse, borrow propagation as a way to generate rook attacks in one ray direction. As long there are zeros left (empty squares) between blocker and subtracting rook, the borrow walks through, similar as a [[Sliding Pieces|sliding piece]] moves along the empty squares.
{{MappingHint}}
=How it Works=
''Again, we write [[Byte|bytes]] ([[Ranks|ranks]]) [[Square Mapping Considerations#LittleEndianRankFileMapping|little-endian-wise]], LSB (A-file) is left not right.''
<pre>
00000010 blocking piece
- 01000000 rook
01111100 piece(s) - rook
</pre>
The difference is already like an [[Dumb7Fill|occluded-fill]], including the rook (slider) but excluding the blocker. Therefor, also considering no or multiple blockers - or even multiple sliders, the [[General Setwise Operations#ExclusiveOr|xor difference]] with the [[General Setwise Operations#Union|union]] of both blocking and sliding sets determines the bit-changes, ...
<pre>
01000010 occupied = piece(s) | rook
xor 01111100 piece(s) - rook
= 00111110
</pre>
... yielding exactly the attack set of the rook(s) in positive rank direction, from left to right (from whites point of view) or A- to H-file.
=o^(o-2r)=
This trick is known as '''o^(o-2r)'''. [[Occupancy]] '''o''' may include the rook '''r''' or not, the subtraction or 2r does not affect this bit, and no matter whether it is set or not, the [[General Setwise Operations#ExclusiveOr|xor operation]] only yields the changed bits as sliding attacks. Unfortunately it only works on [[On an empty Board#PositiveRays|positive rays]], but can be applied for [[Files|files]] or [[Diagonals|diagonals]] with leading and trailing [[General Setwise Operations#Intersection|intersections]] with the [[On an empty Board#LineAttacks|line-masks]]. For instance, north attacks of a rook on d2:
<pre>
occupancy & filemask[d] = potential blockers
. . 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 . . . .
pot.blockers - 2*squarebit[d2] = difference
. . . 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 . . . .
difference ^ occupancy = changed
. . . 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 1 1 . . . . . . . .
. . . 1 . . . . . . . 1 . . 1 . . . . . . . 1 .
changed & filemask[d] = north attacks[d2]
. . 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 . . . . . . . . . . . .
</pre>
This operation was derived from the [[Reverse Bitboards]] idea by [[Ryan Mack]], and is base of the [[Hyperbola Quintessence]] to get single piece attacks on diagonals and files. Since the operation principally works set-wise, even with multiple rooks per rank, it can be applied in [[Fill by Subtraction|SIMD- or SWAR-wise]] manner on all eight ranks (bytes) simultaneously.
=See also=
* [[Reverse Bitboards]]
* [[Hyperbola Quintessence]]
* [[Obstruction Difference]]
* [[SBAMG]]
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
[[Category:Samuel Bak]]
[[FILE:BishopKnightRook.jpg|border|right|thumb|[[Arts#Bak|Samuel Bak]] - Bishop, Knight, Rook <ref>[https://static1.squarespace.com/static/594044bd3a041171e0426683/t/5a12fe739140b703b4e45d85/1511194240551/Bak%2C+Sam+Your+Move+2003.pdf Chess in the Art of Samuel Bak - BK894] (pdf) from [https://www.puckergallery.com/artists/#/samuel-bak/ Samuel Bak represented by Pucker Gallery since 1969]</ref> ]]
If we think about an [[General Setwise Operations#ArithmeticalOperations|arithmetical operation]] to calculate rank-attacks of a [[Rook|rook]] or [[Queen|queen]] with bitboards, [[General Setwise Operations#Subtraction|subtraction]] comes in mind. The idea is to treat the arithmetical carry, or inverse, borrow propagation as a way to generate rook attacks in one ray direction. As long there are zeros left (empty squares) between blocker and subtracting rook, the borrow walks through, similar as a [[Sliding Pieces|sliding piece]] moves along the empty squares.
{{MappingHint}}
=How it Works=
''Again, we write [[Byte|bytes]] ([[Ranks|ranks]]) [[Square Mapping Considerations#LittleEndianRankFileMapping|little-endian-wise]], LSB (A-file) is left not right.''
<pre>
00000010 blocking piece
- 01000000 rook
01111100 piece(s) - rook
</pre>
The difference is already like an [[Dumb7Fill|occluded-fill]], including the rook (slider) but excluding the blocker. Therefor, also considering no or multiple blockers - or even multiple sliders, the [[General Setwise Operations#ExclusiveOr|xor difference]] with the [[General Setwise Operations#Union|union]] of both blocking and sliding sets determines the bit-changes, ...
<pre>
01000010 occupied = piece(s) | rook
xor 01111100 piece(s) - rook
= 00111110
</pre>
... yielding exactly the attack set of the rook(s) in positive rank direction, from left to right (from whites point of view) or A- to H-file.
=o^(o-2r)=
This trick is known as '''o^(o-2r)'''. [[Occupancy]] '''o''' may include the rook '''r''' or not, the subtraction or 2r does not affect this bit, and no matter whether it is set or not, the [[General Setwise Operations#ExclusiveOr|xor operation]] only yields the changed bits as sliding attacks. Unfortunately it only works on [[On an empty Board#PositiveRays|positive rays]], but can be applied for [[Files|files]] or [[Diagonals|diagonals]] with leading and trailing [[General Setwise Operations#Intersection|intersections]] with the [[On an empty Board#LineAttacks|line-masks]]. For instance, north attacks of a rook on d2:
<pre>
occupancy & filemask[d] = potential blockers
. . 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 . . . .
pot.blockers - 2*squarebit[d2] = difference
. . . 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 . . . .
difference ^ occupancy = changed
. . . 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 1 1 . . . . . . . .
. . . 1 . . . . . . . 1 . . 1 . . . . . . . 1 .
changed & filemask[d] = north attacks[d2]
. . 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 . . . . . . . . . . . .
</pre>
This operation was derived from the [[Reverse Bitboards]] idea by [[Ryan Mack]], and is base of the [[Hyperbola Quintessence]] to get single piece attacks on diagonals and files. Since the operation principally works set-wise, even with multiple rooks per rank, it can be applied in [[Fill by Subtraction|SIMD- or SWAR-wise]] manner on all eight ranks (bytes) simultaneously.
=See also=
* [[Reverse Bitboards]]
* [[Hyperbola Quintessence]]
* [[Obstruction Difference]]
* [[SBAMG]]
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
[[Category:Samuel Bak]]
