Bitboards / Bit arrays

General
#1

I’m working on Code of Ice and Fire at the moment and I’m thinking that it would be well suited to using bitboards. I haven’t really used them before and I’m not clear on weather or not they are worth the additional code complexity.

From what I understand, instead of storing your game state info in a 2D array, you store it in a number, with each bit representing a cell in the grid. I understand that they are a great way to speed up complex queries, using bitwise operators. Update can also be made quick using bitmasks. Am I right so far?

There are two main things that aren’t quite clear to me and have been holding me back from trying to use bitboards.

Game information needs to be converted from game coordinates to bit arrays and then from bit arrays to game coordinates.

  1. How is that typically handled.
  2. Doesn’t the need to constantly convert to and from bit arrays kind of negate the potential gains from faster querying.

So let’s say I’m getting the following inputs from CG for a 12 X 12 grid:

  • #: void
  • .: neutral
  • O: owned and active cell
  • o: owned and inactive
  • X: active opponent cell
  • x: inactive opponent cell

So 144 positions means that I need 5 32bit ints for each data set. How does one go about taking those inputs and converting them to a bitboard representation efficiently, and then back to outputs that can be used by the rest of your code and fed to CG?

#2

I’m no bitboard expert, but I used them a few times.

As you said, a bitboard is just a 1D representation of a 2D array, so the conversion between game information and bitboards is just a matter of indexing every cell of a 2D array. Personnally I use those macros to convert from 2D to 1D and vice versa :

#define C2POS(x, y) ((x)+(y)*GRID_W)
#define POS2X(p) ((p)%GRID_W)
#define POS2Y(p) ((p)/GRID_W)

The first one gives you the overall index of a cell according to its X/Y coordinates, and the two others do the opposite, for X and Y.

But sometimes it’s more efficient to align bits differently for bitboard purposes :

The macros I pasted above will give you the A layout, but the B layout will be more efficient for floodfill (better alignment). For the latter, my macros won’t work. In the end, each problem requires a different modelisation based on what you plan to do with the bitboards, there’s no go-to modelisation.

For the bitboards to be efficient, you need to avoid 1D/2D conversions at all costs. Typically you’ll only need to convert from 2D to 1D while reading inputs, and from 1D to 2D when outputing instructions. Your engine must then only treat 1D data, everywhere. But don’t worry, everything is doable in 1D without the need to convert back to 2D (think floodfilling, pathfinding, etc).

6 Likes