Rotated Bitboards

From Chessprogramming wiki
Jump to: navigation, search

Home * Board Representation * Bitboards * Sliding Piece Attacks * Rotated Bitboards

Paul Klee - Mural from the Temple of Longing ↖Thither↗ [1]

Rotated Bitboards,
a bitboard move generation technique coined by Robert Hyatt [2], and later by Ernst A. Heinz [3] 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.

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: 

  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][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. 

  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

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. 

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

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

Forum Posts

1995 ...

2000 ...

2005 ...

2010 ...

External Links

References

  1. ↑ Paul Klee - Mural from the Temple of Longing ↖Thither↗, Metropolitan Museum of Art
  2. ↑ 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
  3. ↑ Rotated Bitboards in Ernst A. Heinz (1997). How DarkThought Plays Chess. ICCA Journal, Vol. 20, No. 3
  4. ↑ Bitboard Representation by Carl Tillotson, rgcc, September 18, 1997, post 23 by Robert Hyatt
  5. ↑ Re: Extracting information from rotated Bitboards by Roberto Waldteufel, CCC, November 02, 1998
  6. ↑ Bitboard user's information request by Robert Hyatt, CCC, October 05, 1999
  7. ↑ Nice Rotated-bitmaps Article by Hyatt in ICCA by Tom Likens, CCC, February 07, 2000
  8. ↑ Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4
  9. ↑ The ICCA Journal paper does not mention the outer square optimization with the four fold table reduction

Up one Level

Retrieved from "https://www.chessprogramming.org/index.php?title=Rotated_Bitboards&oldid=15896"