Ever since I built my own chess-engine and lost against the chess-engine of a colleague of mine who used bitboards I wanted to learn this bitboard stuff. Recently I saw the perfect opportunity to use bitboards myself. This blogpost will describe my experiences and hopefully will demystify the complexity of bitboards for you.

Introduction

A while ago me and my colleague Roy decided to write a chess-engine and let our engines compete against each other. I spent days and nights on my engine. The TDD way. I created objects for the board, the cells on the board, every piece, moves, etc. And I was really proud of my completely object-oriented chess-engine. Well, at least until we started our competition. He really blew me away. He could calculate the best move in seconds with a search depth twice as deep as mine. WTF? How could this be possible? I asked him for his implementation and he told me he had used bitboards. I had to grasp the concept of bitboards too!

Tic-Tac-Toe-Tomek

Recently I stumbled upon a programming contest, the infamous Google Code Jam. Although the competition has already ended, I had to proof myself (what can I say, I am a competitive guy). So, let’s take a look at the problem description.

Tic-Tac-Toe-Tomek is a game played on a 4 x 4 square board. The board starts empty, except that a single ‘T’ symbol may appear in one of the 16 squares. There are two players: X and O. They take turns to make moves, with X starting. In each move a player puts her symbol in one of the empty squares. Player X’s symbol is ‘X’, and player O’s symbol is ‘O’.

After a player’s move, if there is a row, column or a diagonal containing 4 of that player’s symbols, or containing 3 of her symbols and the ‘T’ symbol, she wins and the game ends. Write a program that given a 4 x 4 board description containing ‘X’, ‘O’, ‘T’ and ‘.’ characters (where ‘.’ represents an empty square), describing the current state of a game, determine the status of the Tic-Tac-Toe-Tomek game going on. The statuses to choose from are:

• “X won” (the game is over, and X won)
• “O won” (the game is over, and O won)
• “Draw” (the game is over, and it ended in a draw)
• “Game has not completed” (the game is not over yet)

If there are empty cells, and the game is not over, you should output “Game has not completed”, even if the outcome of the game is inevitable.

Setting up the Bitboard

Let’s get started! We will skip the easy tests (source code is added as attachment). Let’s start with the first test where we have to setup the board.

@Test
public void buildWithTomekAtLowerRightCornerShouldPositionTomekCorrectly() {
    Board board = new Board.Builder()
            .tomek(4, 4)
            .build();
    assertThat(board.cellAt(4, 4)).isEqualTo(CellState.Tomek);
}

What does this test say? We have a Builder to setup a tic-tac-toe-tomek board. If we add the tomek to the lower right corner and we create the board, then we expect that the cellAt method for this position returns the tomek. Now we have to learn something about bitboards.

A bitboard is a datastructure where each bit represents a game position or state. In our situation we have a board containing 4 x 4 = 16 cells. This means, we can represent this board in 16 bits, where each bit represents a position on the board. This is visualized in the following picture.

The left hand side represents the board, the right hand side represents the equivalent datastructure of 16 bits. To store the position of the Tomek we create our first bitboard. In our test we added the Tomek at position (4, 4). As you can see in the picture this is equivalent to the first bit in our bitboard. Thus we have to set the first bit to 1 and all other bits to 0, e.g. 0000 0000 0000 0001. Below you will see the implementation.

public static class Builder {
    private short tomek = 0x0;

    public Builder tomek(final int row, final int column) {
        this.tomek = (short) Math.pow(2, ((4 - row) * 4) + (4 - column));
        return this;
    }
}

As you can see, we used a short to store the bitboard. This is the first advantage of bitboards: low memory footprint. We can use a second bitboard to store all the crosses on the board. Adding the first cross is equivalent to setting the Tomek. But how do we add more crosses to the board. In other words, how do we implement the following test.

@Test
public void buildWithTwoCrossesShouldPositionBothCrossesCorrectly() {
    Board board = new Board.Builder()
            .addCross(1, 4)
            .addCross(3, 3)
            .build();
    assertThat(board.cellAt(1, 4)).isEqualTo(CellState.Cross);
    assertThat(board.cellAt(3, 3)).isEqualTo(CellState.Cross);
}

Bitwise Operations – The Powerful Part

After adding the first cross, we have a bitboard like this: 0001 0000 0000 0000. The bitboard representation of the second cross will be: 0000 0000 0010 0000. How can we create a bitboard that represents both crosses? Simple, by using the bitwise operation OR:

0001 0000 0000 0000
0000 0000 0010 0000
——————————- OR
0001 0000 0010 0000

Our implementation will become:

public static class Builder {
    private short crosses = 0x0;

    public Builder addCross(final int row, final int column) {
        this.crosses |= (short) Math.pow(2, ((4 - row) * 4) + (4 - column));
        return this;
    }
}

Now that we have the bitboards in place, let’s take a look at the power of it. Of course we write a test first.

@Test
public void stateForBoardWithFourCrossesInTheFirstRowShouldReturnCrossWon() {
    Board board = new Board.Builder()
            .addCross(1, 1)
            .addCross(1, 2)
            .addCross(1, 3)
            .addCross(1, 4)
            .build();
    assertThat(board.state()).isEqualTo(BoardState.CrossWon);
}

So, when we create a board with four crosses on the first row, we expect that the board should have the state “X won”. The implementation is as simple as elegant. We create another bitboard representing the winline (this is called a mask) and do an AND bitwise operation. If the result of this operation is exactly the same as the winline, then we know that we had all crosses on the winline, and we have a winner!

1111 0000 0000 0000 // representation of crosses on the board
1111 0000 0000 0000 // winline 1: four in the first row
—————————– AND
1111 0000 0000 0000 // if equal to winline 1

In code this looks like the following.

public class Board {
    private static final short WINLINE = (short) 0xF000; // First Row

    public BoardState state() {
        if (crossWins()) {
            return BoardState.CrossWon;
        } 
        return BoardState.GameNotCompleted;
    }

    private boolean crossWins() {
        if ((crosses & WINLINE) == WINLINE) {
            return true;
        }
        return false;
    }
}

Now can you implement the code for the rule that cross also wins with 3 crosses and the Tomek in one row?

Conclusion

In essence, a bitboard is just a bunch of bits. A bunch of bits representing the state of your board game. The advantage of the bitboard representation is that it takes advantage of the essential logical bitwise operations available on nearly all CPUs that complete in one cycle and are fully pipelined and cached etc. Nearly all CPUs have AND, OR, NOR, and XOR. Bitboards are also extremely compact. Since only a very small amount of memory is required to represent a position or a mask, more positions can find their way into registers, full speed cache, Level 2 cache, etc. In this way, compactness translates into better performance. Had I know this in advance, I could have won the chess competition. On the other hand, Roy is also a clever guy and he probably had some more tricks for me (it’s always a pleasure competing him).

You can download the complete implementation at the end of this article.