Rotated Bitboards in Othello
Mike Maxim
 

Feel free to contact me if you have any more questions about this technique.

Basics:

The largest data type in Java that can fit in a machine register (fast storage on the CPU) is the int, which is 32 bits (Pentium CPUs are 32 bit). However, Java does also define a type, long, which is 64 bits wide. A 64-bit number is never stored in a register, although it can be treated in your Java code as if it were. 64 bit integers are particularly useful for Chess and Othello as described below.


Setup:

There will be 8 bitboards (64 bit long) that you will have to maintain to pull this off. They are as follows (each 1 has 2 bitboards for White and Black):

1.) Rotate 0
2.) Rotate 90 Right
3.) Rotate 45 Right
4.) Rotate 45 Left

These 8 bitboards will be the main board state your program will keep around during game play.

Lets deal with just Rotate 0 for now. The bitboard for White that looks like such:

0000000100000001000000010000000100000001000000010000000100000001

corresponds to White pieces along the H (rightmost) file. Notice now that I am implicitly defining the lower left as square 0. To reference square x in the bitboard, I would do this:

long bboard = <...> //Some position
boolean sqrnset = ((bboard & (1 << n)) != 0);

To set a bit, i.e during the make() operation, I would do:

bboard |= (1 << n);

To remove a bit (remove a piece)

bboard &= ~(1 << n);

***Note: You may want to pre-compute (1 << n), 0 <= n < 64.

To facilitate the rotated boards, you will need to create rotation maps. This may be called something like R90map. You can visualize this if you try hard enough. Think about physically rotating the Othello board to the right by 90 degrees. You will see that square 0 now becomes square 56, square 1 goes to 48, and so forth. During pre-computation, you will want to create this map (or hard code it) so that it performs the R90 mapping. To set a bit in the R90 bitboard, I would do something like this:

bboardR90 |= (1 << R90map[n]);

The other operations are similar.

WARNING: R45R and R45L are similar, except you need to know about the length of the diagonal. You must also pre-compute lengths of diagonals on the square. If you think of square 0 as A1 and square 7 as H1, we can see two principle diagonals at work, A1-H8 and A8-H1. For a given square n, it will have two diagonal lengths, the A1-H8 length and A8-H1 length. This information must be known a priori when doing move generation. More on this in a second.

Here are some links that help with this:

http://supertech.lcs.mit.edu/~heinz/dt/node8.html - For rotation clarification

http://www.galahadnet.com/chess/chessprg/rotated.htm - Explains how to to do it for chess.

Move Generation:

In order to get move generation out of all this, we will need more pre-computation.

Postulate a structure:

byte moves[256][256][2];

The first [256] corresponds to all possible combinations of White's pieces on a rank (row). The following is a sample with White having a piece on the A and E file:

10001000

Note 256 is correct because there are 8 squares and 2 options, empty or White, so 2⁸ = 256. The second [256] correspond to Black. The last 2 are for White and Black, that is, moves for White in this configuration, or moves for Black. The pre-comp loop would look a little something like this:

for (i = 0; i < 256; i++) {
    for (j = 0; j < 256; j++) {
        //Compute all legal white moves given i and j
        moves[i][j][WHITE] = compute_white_moves(i,j);

        //Compute all legal black moves given i and j
        moves[i][j][BLACK] = compute_black_moves(i,j);
    }
}

Keep in mind how rotation is working here. This is all we need because of it. The whole point of rotating everything (by 90 or 45), is so that we can get a file or diagonal configuration by shifting and and-ing. This would be done like so:

val = (bitboardR90Wh << file) & 0xff; //Get vertical configuration
val0 = (bitboardR0 << rank) & 0xff; //Get horizontal configuration

val and val0 are now indices into the moves vector. To get the White moves along that rank and file we could just do this:

val = moves[(bitboardR90Wh << file) & 0xff][(bitboardR90Bk << file) & 0xff][WHITE];
val0 = moves[(bitboardR0Wh << rank) & 0xff][(bitboardR0Bk << rank) & 0xff][WHITE];

WARNING: This code is not exact, there may be subtleties that you will have to figure out for yourselves!

There is an added complication for the R45R and R45L moves. You cannot just & against 0xff in this case since the diagonals are of varying length. You must compute the lengths of diagonals ahead of time so you can know how many bits to mask off during the lookup into the moves table:

To now extract the moves, you must loop through the val variable to find all the set bits. These set bits will then need to be translated back to the correct coordinates of the piece that is moving.

***Note: Most real chess programs will break into assembler for this, there is a special instruction, 'bsr', that can find a set bit in 1 CPU cycle (!) on Pentium Pro and up.

Here are some links to help with this:

http://www.galahadnet.com/chess/chessprg/rotated.htm - Mostly for chess but same ideas apply to Othello.

mmaxim