Rotated Bitboards,
a bitboard move generation technique coined by Robert Hyatt^{[1]}, and later by Ernst A. Heinz^{[2]} and Peter Gillgasch from the DarkThought team. This variation uses rotated copies of the occupancy in order to place bits along a file, diagonal or anti-diagonal in adjacent bits. Because of this, these bits can be easily extracted to obtain a dense occupancy map for a rank, file, diagonal, and anti-diagonal. These are used, along with the square of the sliding piece, to lookup a bitboard, containing attacks, in an array.

While the attack generation per line is more or less only one memory lookup, the incrementalupdate of the occupancy during make and unmake move becomes more expensive, since beside the usual occupied bitboard there are three more rotated bitboards to update, including additional mapping from square coordinates to the rotated indices.

As example file-attacks of rook a5 with occupancy along the a-file. The 90-degree rotated bitboard has consecutive bits of that file along its 8th rank, which serves as an index to lookup the pre-calculated file-attacks:

With a rook on the square marked 'R', an attack bitboard can be obtained with the array lookup file_attacks[R][10011011].

Square Mapping

Interesting is the different mapping of both approaches. Crafty seemed to use little endian square mapping but bit 0 (A1) is mentioned as MSB, while bit 63 (H8) is LSB. DarkThought uses big-endian file-mapping (H1 = 0).

by Hyatt

Crafty didn't use byte aligned diagonals, but visual rotation.

When I first thought about doing the rotated bitmap idea, I discussed it with Peter G. of the DarkThought team. He thought (as I did) that the idea was pretty neat and worth trying. I (from the first thought) had always planned on updating the rotated bitmaps by the following approach: I have a set of 64 bitmaps callet set_mask[n]. To set bit 32, I simply AND(bit-map,set_mask[32]). If I have a rotated-90 bitmap, then I also create a rotated-90 set_mask, and do this: AND(bit-map-R90,set_mask_R90[32]) and I am done. Peter didn't like this, and wanted to get rid of the extra memory load for the rotated set_mask variable. (note there are actually 4 of these loads needed, for each of the rotated bitmaps). So he thought about it a bit and found a cute mathematical transformation based on shifts, AND's and OR's (I won't give it here since it is his idea) that avoide needing the set_mask_Rxx masks (note that on some machines, even the set_mask itself is not needed. to set bit 32 you just start with "1" and shift it to the right position avoiding the memory load altogether. However, the effect of Peter's approach is to map diagonal bits on the real bitmap to adjacent bits in a "psuedo-rotated" bitmap, without needing the set_mask_R90 stuff at all. Is it better? I'm not sure. My tests on the P6 said NO. My tests on the alpha with big cache also said NO. Peter's tests on the machine he used said YES. It definitely takes more instructions to do what Peter is doing. On a machine with a huge memory latency, like the PC, my memory loading can be slow. But with a decent sized cache, the 64 words X 8 bytes per word (512 bytes) really tucks into a corner in cache and doesn't hurt at all, particularly since a cache hit on the P6 operates at CPU speed. The PII is a different case since the cache operates at 1/2 CPU speed, which might swing things in his favor. For the record, they are *close* under all cases. We are not talking 10% here...one might be 2% faster on one machine, the other 3% faster on another machine... But the "mapping" is really odd and would not let us just simply swap the L45 and R45 maps...

Table size

The initial implementations of rotated bitboards missed the outer square optimization and used the 8-bit occupied state with four lookup tables of 256*64*8 or 128-Kbyte each, thus 1/2 MByte in total. Roberto Waldteufel seemed first time mentioned the optimization trick 1998 ^{[5]}, masking off the redundant outer occupancies for a four fold table reduction.

Of course one may use calculations similar to kindergarten bitboards to further shrink the tables. In fact, getting the occupancy state and pre-calculated information based on that are two different steps.

Home * Board Representation * Bitboards * Sliding Piece Attacks * Rotated BitboardsRotated Bitboards,a bitboard move generation technique coined by Robert Hyatt

^{[1]}, and later by Ernst A. Heinz^{[2]}and Peter Gillgasch from the DarkThought team. This variation uses rotated copies of the occupancy in order to place bits along a file, diagonal or anti-diagonal in adjacent bits. Because of this, these bits can be easily extracted to obtain a dense occupancy map for a rank, file, diagonal, and anti-diagonal. These are used, along with the square of the sliding piece, to lookup a bitboard, containing attacks, in an array.While the attack generation per line is more or less only one memory lookup, the incremental update of the occupancy during make and unmake move becomes more expensive, since beside the usual occupied bitboard there are three more rotated bitboards to update, including additional mapping from square coordinates to the rotated indices.

^{[3]}## Table of Contents

## An Example

As example file-attacks of rook a5 with occupancy along the a-file. The 90-degree rotated bitboard has consecutive bits of that file along its 8th rank, which serves as an index to lookup the pre-calculated file-attacks:With a rook on the square marked 'R', an attack bitboard can be obtained with the array lookup file_attacks[R][10011011].

## Square Mapping

Interesting is the different mapping of both approaches. Crafty seemed to use little endian square mapping but bit 0 (A1) is mentioned as MSB, while bit 63 (H8) is LSB. DarkThought uses big-endian file-mapping (H1 = 0).## by Hyatt

Crafty didn't use byte aligned diagonals, but visual rotation.## by Gillgasch and Heinz

DarkThought used a similar mapping as proposed in Pseudo Rotation by 45 degrees from Flipping Mirroring and Rotating, all diagonals are packed in file-aligned bytes.## Quotes

From Robert Hyatt as repost to Urban Koistinen from 1997^{[4]}:When I first thought about doing the rotated bitmap idea, I discussed it with Peter G. of the DarkThought team. He thought (as I did) that the idea was pretty neat and worth trying. I (from the first thought) had always planned on updating the rotated bitmaps by the following approach: I have a set of 64 bitmaps callet set_mask[n]. To set bit 32, I simply AND(bit-map,set_mask[32]). If I have a rotated-90 bitmap, then I also create a rotated-90 set_mask, and do this: AND(bit-map-R90,set_mask_R90[32]) and I am done. Peter didn't like this, and wanted to get rid of the extra memory load for the rotated set_mask variable. (note there are actually 4 of these loads needed, for each of the rotated bitmaps). So he thought about it a bit and found a cute mathematical transformation based on shifts, AND's and OR's (I won't give it here since it is his idea) that avoide needing the set_mask_Rxx masks (note that on some machines, even the set_mask itself is not needed. to set bit 32 you just start with "1" and shift it to the right position avoiding the memory load altogether. However, the effect of Peter's approach is to map diagonal bits on the real bitmap to adjacent bits in a "psuedo-rotated" bitmap, without needing the set_mask_R90 stuff at all. Is it better? I'm not sure. My tests on the P6 said NO. My tests on the alpha with big cache also said NO. Peter's tests on the machine he used said YES. It definitely takes more instructions to do what Peter is doing. On a machine with a huge memory latency, like the PC, my memory loading can be slow. But with a decent sized cache, the 64 words X 8 bytes per word (512 bytes) really tucks into a corner in cache and doesn't hurt at all, particularly since a cache hit on the P6 operates at CPU speed. The PII is a different case since the cache operates at 1/2 CPU speed, which might swing things in his favor. For the record, they are *close* under all cases. We are not talking 10% here...one might be 2% faster on one machine, the other 3% faster on another machine... But the "mapping" is really odd and would not let us just simply swap the L45 and R45 maps...## Table size

The initial implementations of rotated bitboards missed the outer square optimization and used the 8-bit occupied state with four lookup tables of 256*64*8 or 128-Kbyte each, thus 1/2 MByte in total. Roberto Waldteufel seemed first time mentioned the optimization trick 1998^{[5]}, masking off the redundant outer occupancies for a four fold table reduction.Of course one may use calculations similar to kindergarten bitboards to further shrink the tables. In fact, getting the occupancy state and pre-calculated information based on that are two different steps.

## See also

## Publications

1997).How DarkThought Plays Chess.ICCA Journal, Vol. 20, No. 31999).Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4^{[6]}^{[7]}2005).The Representation of Chess Game. Proceedings of the 27th International Conference on Information Technology Interfaces2005).Rotated bitboards in FUSc#. Free University of Berlin, pdf » FUSc### Forum Posts

## 1995 ...

## 2000 ...

^{[8]}## 2005 ...

## 2010 ...

## External Links

^{[9]}## References

1997).How DarkThought Plays Chess.ICCA Journal, Vol. 20, No. 31999).Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4## What links here?

Up one Level