Search code examples
javachessbitboard

9x9 bitboard implementation

I want to implement a 9x9 board game similar to chess, that has only rook-like moving pieces. Performance is crucial since I want to develope an AI also.

I read articles about bitboards, an efficient way to represent the game engine. There are several interesting articles about that, such as Chess bitboard implementation in Java and https://www.chessprogramming.org/Bitboards. Of course they refer to 8x8 boards, and they apply very well to 64bit CPUs, since it allows fast bitwise operations.

In this case I need a 9x9 board, so I expect to use at least two primitive data (64 bit + 32 bit, in order to represent the 81 squares I need).

// 9x9 board, possible representation (64bits+32bits)
  000000000
  000000000
  000000000
  000000000
  000000000
  000000000
  000000000
  000000000
  000000000
  +15 unused bits

Besides the more complicated logic I will need, is it worth to use bitboards in this case? Will I actually get a good gain in performance?

Solution

  • One of the nicest things about bitboards and rooks is that you can precompute legal moves given a rank or file's occupancy. This is great because you can find all the legal moves without any if instructions. For example, let's say you isolate the current rank via shifting and masking and you get

    10100R001

    where 1 is an occupied square, 0 is an empty square, and your rook starts in square 3 (counting from the least significant bit, which is bit 0). Let's say you precomputed:

    ROOK_MOVE[3][101000001] = 000110110
ROOK_CAPTURE[3][101000001] = 001000001

    (The naive approach is good enough here because there are only 9 starting positions and 256 occupancies for the remaining 8 squares.) Then you can generate the four legal moves to squares 1, 2, 4 and 5. This requires no branching because you can extract bits one by one (for example with Kernighan's method). To get the list of legal captures, you need to AND the second mask with the opponent's pieces on that rank.

    I expect this to work well even for a 9x9 board. The extra bit handling functions should still be a lot faster than the alternative (ifs and branching). As mentioned in the comments, the best way to find out is to test several approaches!