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