Subtracting a Rook from a Blocking Piece
Home * Board Representation * Bitboards * Sliding Piece Attacks * Subtracting a Rook from a Blocking Piece
If we think about an arithmetical operation to calculate rank-attacks of a rook or queen with bitboards, 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 piece moves along the empty squares.
| Code samples and bitboard diagrams rely on Little endian file and rank mapping. |
Contents
How it Works
Again, we write bytes (ranks) little-endian-wise, LSB (A-file) is left not right.
00000010 blocking piece
- 01000000 rook
01111100 piece(s) - rook
The difference is already like an occluded-fill, including the rook (slider) but excluding the blocker. Therefor, also considering no or multiple blockers - or even multiple sliders, the xor difference with the union of both blocking and sliding sets determines the bit-changes, ...
01000010 occupied = piece(s) | rook
xor 01111100 piece(s) - rook
= 00111110
... 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). Assuming rook r is member of the occupancy o, the single subtract would only clear that r-bit, therefor subtracting 2r is required to borrow from the closest blocker bit in o. However, even if o may not include the rook bit, the subtraction of 2r does not affect that bit - no matter whether r is set in o or not, the xor operation results in the changed bits as sliding rook attacks. Unfortunately, due to borrow is propagated in direction of arithmetical more significant bits, the trick only works on positive rays, but can be applied for files or diagonals with leading and trailing intersections with the line-masks. For instance, north attacks of a rook on d2:
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 . . . . . . . . . . . .
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 SIMD- or SWAR-wise manner on all eight ranks (bytes) simultaneously.
