Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Bitboards

I assume you have studied the binary system and bitwise operations from the appendix, so we can now look at how bitboards are used to represent something within a chess engine. A bitboard can represent many things: pieces on squares, occupied squares, legal moves, attacks, and more.

In Rustic, the bitboard’s least significant bit (LSB) is bit 0, and in the case of squares, it represents square A1. Therefore, if we have a bitboard that indicates square A1 is occupied, it looks like this:

    00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001

This representation is not very practical to work with while developing the engine. A bitboard containing a piece on e4 has the integer value 268_435_456, which is not very informative in a debugger. It is much easier to debug when you can print the bitboard to the screen, with A1 being on the lower left, just as with a normal chess board.

Therefore, one of the first functions you should write is one to print bitboards to the screen in the layout of a chess board. This will be very useful in the initial stages of the engine’s development. After your board representation and move generator are done, you can remove this function if you so wish.

If we’d just print the bitboard from left to right, starting at the most significant bit, and starting a new row every 8 bits, square A1 would end up on the bottom right. This is because the least significant bit is the final bit to be printed. That’s obviously not correct, because A1 on a chess board is on the bottom left.

Let’s put a piece on e4:

bitboard, LSB on the far right:

00000000 00000000 00000000 00000000 00010000 00000000 00000000 00000000
                                       ^e4 ^a4      ^a3      ^a2      ^a1

The integer value of this bitboard is: 268_435_456. When we print this bitboard, we want to see this:

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0

So how do we achieve this? First let’s analyze which squares are which bits:

v-a8 (bit 56)
0 0 0 0 0 0 0 0 <- h8 (bit 63)
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 <- h3 (bit 23)
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 <- h1 (bit 7)
^-a1 (bit 0)

As you can see, the bitboard is printed from bit 56-63, followed by a newline, then bits 48-55 are printed, followed by a newline, and so on, until we end up with bit 0-7 on the last row. Below is a function that accomplishes this. It is a good idea to add such a function to your engine to assist with debugging.

fn print_bitboard(bitboard: u64) {
    const LAST_BIT: u64 = 63;
    for rank in 0..8 {
        for file in (0..8).rev() {
            let mask = 1u64 << (LAST_BIT - (rank * 8) - file);
            let char = if bitboard & mask != 0 { '1' } else { '0' };
            print!("{char} ");
        }
        println!();
    }
}

My suggestion would be to do a few iterations by hand. Note that the outer loop for ranks runs forward from 0 up to and including 7, while the inner loop for files runs backwards, from 7 down to and including 0. The mask variable will therefore be calculated as such, while printing the top row of bits. For example, the first row is printed as follows:

mask = 63 - (0 * 8) - 7 = 56
mask = 63 - (0 * 8) - 6 = 57
mask = 63 - (0 * 8) - 5 = 58
... and so on...

And for the second row:

mask = 63 - (1 * 8) - 7 = 48
mask = 63 - (1 * 8) - 6 = 49
mask = 63 - (1 * 8) - 5 = 50
... and so on...

Note how the mask is being created. First we calculate the target bit and then shift a 1 into that spot in the mask, so we can use it to determine if the incoming bitboard has a 1 set at that particular spot.

Now that we know how bitboards work, we can take a look at how they are used to represent an entire chess board. It is here that the actual implementation of the chess engine starts.

Rustic uses two arrays with 6 bitboards each. One array is for the white pieces, the other is for the black ones. There are 6 bitboards per side, because there are 6 piece types: King, Queen, Rook, Bishop, Knight and pawn. These 6 piece types are represented in this enum:

pub enum Piece {
    King = 0,
    Queen = 1,
    Rook = 2,
    Bishop = 3,
    Knight = 4,
    Pawn = 5,
    None = 6,
}

Piece is one of Rustic’s base types. Refer to the code repository for how it is implemented; this is Rust-specific, so it may be different in other programming languages.

The important part here is that it is an enum. This way we don’t have to remember that the King has piece value 0, the Queen is 1, and so on. We can just use Piece::King when we need to index into a pieces array.

Sidenote: A Rust enum cannot directly index into an array. “Piece” can, because we implemented the traits Index and IndexMut for Piece. That is what I meant when I said that the implementation of the base type is Rust-specific.

When indexing into an array of piece types, we MUST make sure that the king pieces are on index 0, the queen pieces are on index 1, because otherwise it doesn’t work. Assigning explicit numeric values ensures that each piece always maps to the correct array index, regardless of declaration order.

The two arrays for the pieces are defined as follows, within the Board struct discussed in the previous section:

pub bb_pieces: [[Bitboard; NrOf::PIECE_TYPES]; Sides::BOTH],
pub bb_side: [Bitboard; Sides::BOTH],

bb_pieces contains 6 arrays for white and 6 arrays for black. Each array is set up like this, containing only pieces for one color:

  • index 0: all kings (always only one)
  • index 1: all queens
  • index 2: all rooks
  • index 3: all bishops
  • index 4: all knights
  • index 5: all pawns

So if you want to get all the white rooks on the board, you do this:

let white_rooks = bb_pieces[Sides::WHITE][Piece::Rook];

Because this is something we need a lot, there’s a function for this. Many one-liners such as this are wrapped into a function:

pub fn get_pieces(&self, side: Side, piece: Piece) -> Bitboard {
    self.bb_pieces[side][piece]
}

These functions are described in the section Board Functionality.

Sidenote: In many places in the engine there are structs with all public fields. The board struct is one of those. These structs basically act as namespaces for a few variables and the functions that work on them. In the future I might decide to encapsulate everything if there is a way without having to write thousands of accessor methods and without having to use external crates or macro’s for this.

There is another array with only two elements:

pub bb_side: [Bitboard; Sides::BOTH],

This array holds two bitboards: one with all the pieces for the white side, one with all the pieces for the black side. This is very useful, because we often need to do things such as this:

if (bb_target_square & bb_side[OPPONENT] != Bitboard:new(0)) {
    // we captured something
}

This is much faster than iterating over all bitboards belonging to the opponent, or having to combine them into a single bitboard first. When working with pieces, the bb_side bitboard will also be updated to reflect where all the pieces of each color are. Using this we can do cool tricks such as this:

let empty = !(bb_side[Sides::WHITE] | bb_side[Sides::BLACK])

This is one of the key reasons bitboards are efficient. Because the engine keeps everything in bitboards that can be combined like this, it is easy to “ask” the board for certain things. This expression produces a bitboard containing all empty squares. It works as follows:

  • Take the bb_side bitboard for all of White’s pieces.
  • Take the bb_side bitboard for all of Black’s pieces.
  • Combine them to get all the pieces on the board (called “occupancy”).
  • Then, all squares that are NOT in this bitboard must be empty.

This is why I keep hammering on the importance of understanding the binary system and bitwise operations. Lines such as this appear throughout the entire engine, especially in the move generator and evaluation function.

We need to initialize the bitboards before use. This is done when the engine starts, or when it receives a command to read a new FEN-string. A FEN-string encodes the current position, with all its characteristics. To initialize these bitboards, we use FEN parsing. See the chapter Handling FEN-strings in the Board Functionality section to see how a position given to the engine is converted into a set of bitboards.

Now let’s move on to something simpler. The next chapter deals with the piece list, which is related to bitboards but much easier to understand.