Subtracting a rook from a blocking piece

Home * Board Representation * Bitboards * Sliding Piece Attacks * Subtracting a Rook from a Blocking Piece
BishopKnightRook.jpg

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.


mapping.JPG
Code samples and bitboard diagrams rely on Little endian file and rank mapping.

Samuel Bak - Bishop, Knight, Rook [1]

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). 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 xor operation only yields the changed bits as sliding attacks. Unfortunately it 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.

See also


References

  1. ^ Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota

What links here?


Up one Level