a bitboard move generation technique coined by Robert Hyatt , and later by Ernst A. Heinz  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.
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:
non-rotated rotated file_attacks[a5][rotated] ┌─┐ ┌───────────────┐ ┌─┐ │1│0 0 0 0 0 0 0 │1_0_0_1_R_0_1_1│════>│0│0 0 0 0 0 0 0 │1│0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 │1│0 0 0 0 0 0 0 │0│0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 │1│0 0 0 0 0 0 0 │R│0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 │0│0 0 0 0 0 0 0 │1│0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 │1│0 0 0 0 0 0 0 │0│0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 │0│0 0 0 0 0 0 0 │0│0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 │0│0 0 0 0 0 0 0 │1│0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 │0│0 0 0 0 0 0 0 └─┘ └─┘
With a rook on the square marked 'R', an attack bitboard can be obtained with the array lookup file_attacks[R].
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).
Crafty didn't use byte aligned diagonals, but visual rotation.
normal chess board bitmap occupied_squares 90 degrees A8 B8 C8 D8 E8 F8 G8 H8 H8 H7 H6 H5 H4 H3 H2 H1 A7 B7 C7 D7 E7 F7 G7 H7 G8 G7 G6 G5 G4 G3 G2 G1 A6 B6 C6 D6 E6 F6 G6 H6 F8 F7 F6 F5 F4 F3 F2 F1 A5 B5 C5 D5 E5 F5 G5 H5 E8 E7 E6 E5 E4 E3 E2 E1 A4 B4 C4 D4 E4 F4 G4 H4 D8 D7 D6 D5 D4 D3 D2 D1 A3 B3 C3 D3 E3 F3 G3 H3 C8 C7 C6 C5 C4 C3 C2 C1 A2 B2 C2 D2 E2 F2 G2 H2 B8 B7 B6 B5 B4 B3 B2 B1 A1 B1 C1 D1 E1 F1 G1 H1 A8 A7 A6 A5 A4 A3 A2 A1 original left 45 original right 45 H8 A8 G8 H7 A7 B8 F8 G7 H6 A6 B7 C8 E8 F7 G6 H5 A5 B6 C7 D8 D8 E7 F6 G5 H4 A4 B5 C6 D7 E8 C8 D7 E6 F5 G4 H3 A3 B4 C5 D6 E7 F8 B8 C7 D6 E5 F4 G3 H2 A2 B3 C4 D5 E6 F7 G8 A8 B7 C6 D5 E4 F3 G2 H1 A1 B2 C3 D4 E5 F6 G7 H8 A7 B6 C5 D4 E3 F2 G1 B1 C2 D3 E4 F5 G6 H7 A6 B5 C4 D3 E2 F1 C1 D2 E3 F4 G5 H6 A5 B4 C3 D2 E1 D1 E2 F3 G4 H5 A4 B3 C2 D1 E1 F2 G3 H4 A3 B2 C1 F1 G2 H3 A2 B1 G1 H2 A1 H1 original left 45 original right 45 G6 H5|F8 G7 H6|G8 H7|H8| C7 D8|A6 B7 C8|A7 B8|A8| H3|D8 E7 F6 G5 H4|E8 F7 F8|A4 B5 C6 D7 E8|A5 B6 F4 G3 H2|C8 D7 E6 F5 G4 E6 F7 G8|A3 B4 C5 D6 E7 E4 F3 G2 H1|B8 C7 D6 E5 E5 F6 G7 H8|A2 B3 C4 D5 D4 E3 F2 G1|A8 B7 C6 D5 E4 F5 G6 H7|A1 B2 C3 D4 B5 C4 D3 E2 F1|A7 B6 C5 D2 E3 F4 G5 H6|B1 C2 D3 C2 D1|A5 B4 C3 D2 E1|A6 G3 H4|D1 E2 F3 G4 H5|C1 |A1|A2 B1|A3 B2 C1|A4 B3 |H1|G1 H2|F1 G2 H3|E1 F2
by Gillgasch and Heinz
Normal Bitboard. Flipped Bitboard. #7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte #7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte a8 b8 c8 d8 e8 f8 g8 h8 #7 a8 a7 a6 a5 a4 a3 a2 a1 #7 a7 b7 c7 d7 e7 f7 g7 h7 #6 b8 b7 b6 b5 b4 b3 b2 b1 #6 a6 b6 c6 d6 e6 f6 g6 h6 #5 c8 c7 c6 c5 c4 c3 c2 c1 #5 a5 b5 c5 d5 e5 f5 g5 h5 #4 d8 d7 d6 d5 d4 d3 d2 d1 #4 a4 b4 c4 d4 e4 f4 g4 h4 #3 e8 e7 e6 e5 e4 e3 e2 e1 #3 a3 b3 c3 d3 e3 f3 g3 h3 #2 f8 f7 f6 f5 f4 f3 f2 f1 #2 a2 b2 c2 d2 e2 f2 g2 h2 #1 g8 g7 g6 g5 g4 g3 g2 g1 #1 a1 b1 c1 d1 e1 f1 g1 h1 #0 h8 h7 h6 h5 h4 h3 h2 h1 #0 A1-H8 Bitboard. A8-H1 Bitboard. #7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte #7 #6 #5 #4 #3 #2 #1 #0 Bit/Byte a8|b1 c2 d3 e4 f5 g6 h7 #7 a8 b7 c6 d5 e4 f3 g2 h1 #7 a7 b8|c1 d2 e3 f4 g5 h6 #6 a7 b6 c5 d4 e3 f2 g1|h8 #6 a6 b7 c8|d1 e2 f3 g4 h5 #5 a6 b5 c4 d3 e2 f1|g8 h7 #5 a5 b6 c7 d8|e1 f2 g3 h4 #4 a5 b4 c3 d2 e1|f8 g7 h6 #4 a4 b5 c6 d7 e8|f1 g2 h3 #3 a4 b3 c2 d1|e8 f7 g6 h5 #3 a3 b4 c5 d6 e7 f8|g1 h2 #2 a3 b2 c1|d8 e7 f6 g5 h4 #2 a2 b3 c4 d5 e6 f7 g8|h1 #1 a2 b1|c8 d7 e6 f5 g4 h3 #1 a1 b2 c3 d4 e5 f6 g7 h8|#0 a1|b8 c7 d6 e5 f4 g3 h2 #0
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). 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) 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...
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 , 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.
- Ernst A. Heinz (1997). How DarkThought Plays Chess. ICCA Journal, Vol. 20, No. 3
- Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4  
- Borko Bošković, Sašo Greiner, Janez Brest, Viljem Žumer (2005). The Representation of Chess Game. Proceedings of the 27th International Conference on Information Technology Interfaces
- Johannes Buchner (2005). Rotated bitboards in FUSc#. Free University of Berlin, pdf » FUSc#
- bitmaps of rotated boards by Urban Koistinen, gnu.chess, March 2, 1995
- Re: Speed of Move Generator by Robert Hyatt, rgcc, August 17, 1995
- Rotated bitboards - experiment and result by Robert Hyatt, rgcc, February 28, 1996
- bitboard move generation question by Stuart Cracraft, rgcc, September 05, 1997
- Bitboard Representation by Carl Tillotson, rgcc, September 18, 1997
- Rotated bitboards by Mats Forsén, rgcc, October 29, 1997
- Rotated bitboards by Peter Fendrich, CCC, April 22, 1998
- Efficient Rotated Bitboard Representations by Roberto Waldteufel, CCC, October 28, 1998
- Extracting information from rotated Bitboards by John Stoneham, CCC, November 02, 1998
- Bitboard user's information request by Robert Hyatt, CCC, October 05, 1999
- Nice Rotated-bitmaps Article by Hyatt in ICCA by Tom Likens, CCC, February 07, 2000 
- Rotated Bitboards? by Mauricio Castro, rgcc, October 07, 2001
- Attack Bitboards by Sune Fischer, CCC, October 30, 2001
- Resources about rotated bitboards by Federico Corigliano, CCC, January 02, 2004
- Generating "through" attacks with rotated bitboard by Vlad Stamate, CCC, August 28, 2009 » X-ray Attacks (Bitboards)
- Rotated Bitboards by Ernst A. Heinz
- Rotated bitmaps, a new twist on an old idea by Robert Hyatt, revisited version of the ICCA Journal paper 
- Computer Chess Programming Theory - Bitboards by Colin Frayn
- Herb Alpert - Rotation (1979), YouTube Video
- Paul Klee - Mural from the Temple of Longing ↖Thither↗, Metropolitan Museum of Art
- Speed of Move Generator by Valavan Manohararajah, rgcc, August 15, 1995, post 5 by Robert Hyatt where he mentions on the fly generation with rotated bitboards
- Rotated Bitboards in Ernst A. Heinz (1997). How DarkThought Plays Chess. ICCA Journal, Vol. 20, No. 3
- Bitboard Representation by Carl Tillotson, rgcc, September 18, 1997, post 23 by Robert Hyatt
- Re: Extracting information from rotated Bitboards by Roberto Waldteufel, CCC, November 02, 1998
- Bitboard user's information request by Robert Hyatt, CCC, October 05, 1999
- Nice Rotated-bitmaps Article by Hyatt in ICCA by Tom Likens, CCC, February 07, 2000
- Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4
- The ICCA Journal paper does not mention the outer square optimization with the four fold table reduction