Bitboard for othello

Performance Tuning
#1

Hi,
im currently working on an ai for othello/reversi im using alpha/beta search without move ordering for searching the game tree.
Currently im using an 8x8 int array as board representation. But i want to use a Bitboard to make copying the boards easier. The board will contain 2 long variables 1 for the white stones, one for te black stones.
Somehow i cant come up with an efficient way of calculating the possible moves for a given state. Of course i can check the empy fields adjacent to discs and verify if the field is valid through extending a bitmask in every direction.
But i think this is slower than the int representation.
Anyone has some good ideads?

regards

#2

I wouldn’t worry about the speed of calculating valid moves. The array lookups you would need with the int representation will be much, much slower that the bit shifting and masking.

I would suggest just having two methods that are implementation-specific (doing the bit manipulation for longs, array access for the ints): an isWhite(x,y) and an isBlack(x,y) method. These should get in-lined by the compiler (make them private or final) so there shouldn’t be a performance hit, and the logic of the valid move checking that uses them will be implementation independent.

Another option is to keep a set of valid moves for each colour along with open states. I can’t remember all the rules for Othello, but I think a child state’s valid moves share a lot of the parent state’s. Then when generating the child states you would only need to check the few locations on the board that have changed with the last move.

#3

Why don’t you just use one 2-dimensional int array (int[][]) for the board. You can fill it with zero (empty space), one (white pieces) and two (black pieces).
That way you get the entire board in one array and you eliminate some potential bugs (like if you put a black and a white piece in the same spot)

#4

btw should be no need to make things private or final for them to be inlined.

Cas :slight_smile:

#5

@ jono thanks ill try that

i think the increase in performance is mostly due to faster copying of the boards and faster move generation which allows greater search depth
currently i have to manually copy all the values in one board representation into a new 2d array cause the .clone() method does not clone the array in the board representation
@captain
sry if it wasnt clear by 8x8 i was referring to a 2d-int array with length 8
thats what im currently using although black is -1 cause its easier to get the enemy color.

#6

Using bitmasks you can easily pick those bugs up with assert((black & white) == 0).

#7

You should be modelling the bitboards using 2 longs:

long white;
long black;

Then all the operations you need to do on the whole board can be done with single instructions and no array lookups, that’s the whole point of bitboards.

Cas :slight_smile:

#8

An additional thought:

You can construct an array of 64 longs giving the adjacency for each square. Then you can maintain alongside white and black a long representing positions which are adjacent to at least one piece. When someone places a piece in square x you update adjacent |= adjacency[ x ]. Then the set of possible moves can be pre-filtered to adjacency & ~(white | black).

#9

Just a thought–maybe you can optimize how you access the array, or optimize by using something other than an array? For example, iterating and inspecting via a “for each” loop can be quicker than incrementing an index repeatedly into an array. And certain structures iterate faster than others.

Also, is it absolutely necessary to make and inspect a full copy of the board to derive the possible plays list? Perhaps a single structure would suffice for directing this function, with the occupied squares being flagged, and removed from a list of available squares, as they are consumed. For example, remove a play from a list of possible plays (and store it in a Stack that coordinates with the alpha/beta tree), and use this list rather than generating a new list of available plays from scratch on each iteration.