Sign In/My Account | View Cart  

advertisement

AddThis Social Bookmark Button

Listen Print Discuss

Bitwise Optimization in Java: Bitfields, Bitboards, and Beyond
Pages: 1, 2

Impressive Hacking, Comrade (The Bitboard Chess Pattern)

At this point, you can grab a bottle of vodka and a shot glass, because things are getting serious.

Chess used to be a hot research area in computer science during the height of the Cold War. Apparently, independently of one another, both Soviet and American teams came up with a new data structure called a bitboard. The American team, Slate and Atkin, seem to have been first to print with a chapter in Chess Skill in Man and Machine on Chess 4.x. The Soviet team, including Mikhail Donskoy, among others, wrote a bitboard-enabled program called Kaissa. Both programs competed successfully internationally.

Before looking at bitboards, let's first look at the standard way to represent a chess board in Java (and many other languages). 

//declare an integer enum for the possible 
//state of the 64 individual squares.

final int EMPTY        = 0;
final int WHITE_PAWN   = 1;
final int WHITE_KNIGHT = 2;
final int WHITE_BISHOP = 3;
final int WHITE_ROOK   = 4;
final int WHITE_QUEEN  = 5;
final int WHITE_KING   = 6;
final int BLACK_PAWN   = 7;
final int BLACK_KNIGHT = 8;
final int BLACK_BISHOP = 9;
final int BLACK_ROOK   = 10;
final int BLACK_QUEEN  = 11;
final int BLACK_KING   = 12;

//And we have an array of 64 squares.

int[] board= new int[64];

The array method is extremely straightforward. In contrast, the bitboard structure is made up of twelve 64-bit bitsets; one for each type of piece. They are visualized as being stacked on top of each other. 

//Declare twelve 64-bit integers for one board:
long WP, WN, WB, WR, WQ, WK, BP, BN, BB, BR, BQ, BK;

bitboard
Figure 1. The bitboard data structure

Why is there no layer for empty squares? Since EMPTY is a function of the other twelve layers, including it would create redundant data. To calculate EMPTY, we just join the 12 layers and negate: 

long NOT_EMPTY=
  WP | WN | WB | WR | WQ | WK |
  BP | BN | BB | BR | BQ | BK  ;
long EMPTY = ~NOT_EMPTY;

Chess-playing programs work by generating lots of legal moves and then choosing the best one. A number of calculations need to be done. The squares being attacked have to be determined, so that they can be avoided and so that check and checkmate can be determined. Each chess piece has a different way of attacking. Looking at code that affects these different attacks will demonstrate some pros and cons of the bitboard. Some of the pieces fit in our bitboard scheme elegantly, while others don't.

Let's look at the kings first. They simply attack the squares adjacent to them. Depending on where they are, that's from three to eight squares. The king can be in the center, on the edge, or in the corner of the board--all need to be considered while coding.

To generate the king's 64 attacks programmatically at runtime, we can first start with the base case, eight attacks, and transform it into the special cases. First, create a mask for one of the squares in the center--say the 10th square. Figure 2 shows some longs that will be used to create this mask.

King attacks
Figure 2. Finding the king's attacks 

long KING_ON_B2=
1L       | 1L << 1  | 1L << 2  |
1L << 7  |            1L << 9  |
1L << 15 | 1L << 16 | 1L << 17;

We want to shift that box of ones around left and right and up and down visually speaking, but when shifting left and right watch the wrap-around effect:

SHIFTED_LEFT= KING_ON_B2 >>> 1;

Oops. We wrapped the box around (see Figure 2). In chess, a vertical row is called a file. If we shift a layer visually left by one, we know that the rightmost file, file H, should always be zeros. Let's code that: 

final long FILE_H=
1L       |  (1L<<8) | (1L<<16) | (1L<<24) |
(1L<<32) | (1L<<40) | (1L<<48) | (1L<<56);

KING_ON_A2= (KING_ON_B2 >>> 1) & ~FILE_H;

If we want to shift visually right, that's a different case:

KING_ON_B3= (KING_ON_B2 >>> 1) & ~FILE_A;

To shift up and down visually, just shift by eight: 

KING_ON_B1= MASK_KING_ON_B2 <<  8;
KING_ON_B3= MASK_KING_ON_B2 >>> 8;

In the real world, we can avoid having to write code to generate the king attacks by just hardcoding the 64 possibilities. Also, we are trying to avoid arrays, so let's not just stuff our attacks into a 64-element array. An alternative is a 64-way switch statement--it may not be pretty, but it works well.

Let's look at the pawns next. While there is only one king per color, there up to eight pawns. We can find all eight attacks just as easily as we determined a single king's attack! Note that pawns attack diagonally. To shift visually up and down, we shift by eight, and for left or right, we shift by one. Shift by seven or nine to go diagonally (that's 8+1 and 8-1). Figure 3 shows how this works. 

PAWN_ATTACKS=
((WP << 7) & ~RANK_A) & ((WP <<9) & ~RANK_H)

Pawns
Figure 3. Pawn attacks for white

This code fragment works regardless of how many pawns are in play or where they are. Robert Hyatt, the author of Crafty, calls this a bit-parallel operation because it works on a number of pieces simultaneously. Bit-parallel expressions can be very powerful and are the key thing to look for in your own projects. If you see a lot of bit-parallel operations, you might have a good candidate for bitwise optimization.

For a counter example, let's look at how we have to do the pawns with arrays: 

for (int i=0; i<56; i++)
{
  if (board[i]= WHITE_PAWN)
  {
    if ((i+1) % 8 != 0) pawnAttacks[i+9]= true;
    if ((i+1) % 8 != 1) pawnAttacks[i+7]= true;
  }
}

Above, we loop through the almost entire array, but not very quickly. We could rewrite it so that we keep track of the pawns and iterate through the (up to eight) pawns rather than the squares, but we would still be looking at many more bytecodes that need to be run with the bitboard method.

Knights are similar to kings and pawns. We can determine knight attacks with a pre-computed table, just like we did with the king. Since there can be more than one knight per color, the attacks are technically bit-parallel. However, since there are rarely more than two knights per color, that isn't going to help much in a practice sense (there can be more than two if the player promotes his pawns to knights, but that isn't likely).

Bishops, rooks, and queens all slide around the board. While their potential attacks are always the same, the actual attacks depend on what pieces lie along their attack lines. To determine legal moves, you must look at the squares along the attack lines individually. This is our worst-case scenario. There are no bit-parallel operations possible. We are down to accessing individual squares as we would with the array. In addition, atomic access is more cumbersome (i.e., bug-prone) with the bitboard than it is with the array.

An advantage of bitboards is that we can use masks to answer a lot of typical chess questions. For example, if you have a bishop, you might want to know how many of your opponent's pawns are on your bishop's color. Figure 4 illustrates this "attack mask" problem.

Figure 4
Figure 4. How many white pawns on white squares?

Pros and Cons of the Bitboard Pattern

Chess has fairly complex rules, and this means there are pros and cons for using the bitboard. For some pieces bitboards are faster and for some they're slower. We went over the slower pieces to show that we aren't dealing with magic pixie dust. We can imagine a game that is very similar to chess, perhaps with different pieces, where bitsets might actually backfire or just not be worth the trouble. Bitset optimization must be considered carefully.

In general, bitsets have these pros and cons:

Pros:

  • Memory usage
  • Copy, set, and comparison operations
  • Bit-parallel transformations

Cons:

  • Debuggablity
  • Atomic access of bits
  • Extensibility
  • Not OOP
  • Not everything falls in their domain; mass calculations work best

Generalizing the Bitboard Pattern

To generalize the chess example, think of the horizontal and vertical positions on the board as two independent variables or attributes. There are 8x8=64 bits required to represent this. In addition, we required 12 layers--one for each type of piece. There are two ways the bitboard can expand: 1) we can add more bits per layer, or 2) add more layers. In the real world, we are limited to 64 bits per layer maximum, but let's consider a fantasy 128-bit JVM with a doublelong 128-bit primitive. With 128 bits, we would have enough space to put all 16 pawns, black and white, on the same layer (8x8x2=128). That would reduce the number of layers needed and might simplify some obscure operations, but doing so would complicate (and also slow down) functions that work on all pawns of a certain color. All of Java's bit operations work on all of the bits in a primitive. Data that requires its own operations or functions benefits from being in its own layer. We can do bit-parallel operations on all of the bits in the layer faster than we can do bit-parallel operations on some of the bits. We might find some clever use for the extra 64 bits, but we don't want to mix the 12 types of pieces.

If we do use more than two variables per layer, we can still change all of the variables for all of the elements in a layer at the same time. Consider 3D tic-tac-toe, represented in Figure 5. There are three possible values for each of the three axes, or 3x3x3=27 possible values. We need a 32-bit bitset for each player.

tic-tac-toe bitmap format
Figure 5. A format for 3D tic-tac-toe

We can even chain together 64-bit bitsets (Figure 6) to implement Conway's Game of Life, a simulation game played on a large grid. The game goes through generations where the death or birth of a new "cell" is determined by the number of adjacent cells. A dead cell with exactly three live neighbors is (re-)born. A live cell with zero or one neighbor dies (of loneliness). A live cell with more than three neighbors dies (of overcrowding). There are many variants where a different number of neighbors result in birth, life, or death. Figure 6 shows a life construct that will actually survive and move across the grid. To generate the next turn of the simulation we can follow this algorithm:

  1. First, declare eight layers in addition to the main one, similar to the layers in the chess example. Each layer holds one of the cell's eight neighbors. Calculate these by doing shifts (some of the shifted data will have to come from neighboring bitsets).
  2. Now that you have the eight layers, you need to get the arithmetic sum for each cell. Declare nine more bitsets to hold the results; e.g., SUM_IS_0 up to SUM_IS_8. We can calculate these by using a recursive algorithm that first considers two layers, then three layers, then four, and so on up to the eighth.
  3. Now that we have bitsets representing the number of neighbors, it is easy to apply the rules of life to get the next generation.

To sum up layers: 

//S0 is short for "sum equals zero" etc.
//L1 is short for "layer one" etc.

//Look at just the first two layers:
S0= ~(L1 | L2);
S1= L1 ^ L2;
S2= L1 & L2;

//Now look at the third layer:
S3 =  L3 & S2;
S2 = (S2 & ~L3) | (S1 & L3);
S1 = (S1 & ~L3) | (S0 & L3);
S0 = S0 & ~L3;

//The fourth layer.
S4 = S3 & L4;
S3 = (S3 & ~L4) | (S2 & L4);
S2 = (S2 & ~L4) | (S1 & L4);
S1 = (S1 & ~L4) | (S0 & L4);
S0 = S0 & ~L4;

//Repeat this pattern up to the 8th layer.

The algorithm in takes 42 lines of code. It could be tuned a little more if needed, but it gives a number of advantages. It uses no conditionals--which can cause processors to slow. It's a nice simple block of code that a JIT or Hotspot Compiler is sure to compile. And, most importantly, it calculates all 64 cells in parallel.

the game of Life
Figure 6. A format for The Game of Life

Game-related applications of bitsets are easier to find than non-game examples. The reason is that games like chess have rich relationships between each bit. For chess, there are 12 layers of 64 bits, or 768 bits. Each of the 768 are essentially related to the rest somehow. In business apps, information is usually less tightly related.

Conclusion

Keeping an open mind may lead to uses of bitsets in any problem domain. However, it is up to the developer's good judgment whether a particular situation is right for bitsets. Frankly, you may never need to use these techniques. However, the methods above may be just what is needed to speed up certain Java applications. If not, you can still mystify your friends with your superior hacking. Enjoy.

Resources

Glen Pepicelli is a software guru living with his dog in upstate New York.

Return to ONJava.com.