Rotated Bitboards

Vectors of attack masks for all pieces on each square of an otherwise empty chess board enable an easy attack detection for sliding pieces without having to loop over the squares of the respective diagonals, files, and ranks [214]. This loop-less attack-detection scheme operates on consecutive strings of bits representing the rays of squares potentially covered by the sliding piece. In order to really excel, it therefore requires efficient access to consecutive strings of ray bits. As listed below, the normal row-major mapping of squares to bits in a bitboard consecutively aligns the bits of each file. Hence, it only provides efficient access to consecutive strings of file bits.

Normal Bitboard.
#7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte
a8 b8 c8 d8 e8 f8 g8 h8 #7
a7 b7 c7 d7 e7 f7 g7 h7 #6
a6 b6 c6 d6 e6 f6 g6 h6 #5
a5 b5 c5 d5 e5 f5 g5 h5 #4
a4 b4 c4 d4 e4 f4 g4 h4 #3
a3 b3 c3 d3 e3 f3 g3 h3 #2
a2 b2 c2 d2 e2 f2 g2 h2 #1
a1 b1 c1 d1 e1 f1 g1 h1 #0

A column-major mapping of squares to bits in a bitboard, however, consecutively aligns the bits of each rank. Consequently, such flipped bitboards allow for efficient access to consecutive strings of rank bits.

Flipped Bitboard.
#7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte
a8 a7 a6 a5 a4 a3 a2 a1 #7
b8 b7 b6 b5 b4 b3 b2 b1 #6
c8 c7 c6 c5 c4 c3 c2 c1 #5
d8 d7 d6 d5 d4 d3 d2 d1 #4
e8 e7 e6 e5 e4 e3 e2 e1 #3
f8 f7 f6 f5 f4 f3 f2 f1 #2
g8 g7 g6 g5 g4 g3 g2 g1 #1
h8 h7 h6 h5 h4 h3 h2 h1 #0

In the case of diagonals, the necessary mappings prove to be more complex. The number of diagonals amounts to 15 in each of the two directions a1-h8 and a8-h1. Furthermore, diagonals are of variable lengths ranging from 1 to 8. Because not all diagonals can be stuffed into separate bytes of a bitboard the mapping must pack some together in a clever way.

Figuratively, viable mappings can be deduced as follows: slice a normal bitboard along one of the main diagonals (a1-h8 or a8-h1), then rotate the half with the squares of the main diagonal to lie at the bottom, and finally paste the other half such that it results in a parallelogram. As shown below, the diagonalized mappings of squares to bits in a bitboard consecutively align the bits of each a1-h8 and a8-h1 diagonal. Thus, diagonalized bitboards enable efficient access to consecutive strings of diagonal bits if the ends of the diagonals (as marked by vertical bars) are known.

A1-H8 Bitboard.
#7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte
a8 | b1 c2 d3 e4 f5 g6 h7 #7
a7 b8 | c1 d2 e3 f4 g5 h6 #6
a6 b7 c8 | d1 e2 f3 g4 h5 #5
a5 b6 c7 d8 | e1 f2 g3 h4 #4
a4 b5 c6 d7 e8 | f1 g2 h3 #3
a3 b4 c5 d6 e7 f8 | g1 h2 #2
a2 b3 c4 d5 e6 f7 g8 | h1 #1
a1 b2 c3 d4 e5 f6 g7 h8 #0

A8-H1 Bitboard.
#7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte
a8 b7 c6 d5 e4 f3 g2 h1 #7
a7 b6 c5 d4 e3 f2 g1 | h8 #6
a6 b5 c4 d3 e2 f1 | g8 h7 #5
a5 b4 c3 d2 e1 | f8 g7 h6 #4
a4 b3 c2 d1 | e8 f7 g6 h5 #3
a3 b2 c1 | d8 e7 f6 g5 h4 #2
a2 b1 | c8 d7 e6 f5 g4 h3 #1
a1 | b8 c7 d6 e5 f4 g3 h2 #0

For historical reasons, diagonalized and flipped bitboards are both called rotated. In order to fully exploit the benefits of rotation, DARKTHOUGHT incrementally updates rotated bitboards with 1-bits for all occupied squares of the current position. Additionally, it manages compressed vectors of rotated attack masks that strike a good balance between instruction and memory efficiency.

Created by Ernst A. Heinz, Thu Dec 16 23:28:11 EST 1999