Piece List

The previous section described how the bitboard representation is implemented in Rustic. It also demonstrated some of the nice things that can be done with bitboards. Among these are quickly determining which squares are occupied or empty, and whether a move results in a capture.

However, there is one big problem with having two sets of six bitboards to represent a board. It is like having 12 chess boards in front of you while playing a game. A bitboard representation spreads information across twelve separate boards: one for White kings, one for Black kings, one for White rooks, and so on.

This is not a problem for the engine in most situations, because it is working with one piece at a time, or the occupancy of the board. For example, to answer this question: Can a White Knight on c3 go to e4? The engine would do the following to determine this:

• From the move generator, get all the squares the White Knight from c3 could go to on an empty board, and remove the ones that contain pieces of White itself. Black pieces don’t have to be removed because they can be captured.
• Make sure the Knight is not pinned, so the king is not in check when it moves.

What is left is all the legal moves of the Knight on c3, and if e4 is in the resulting bitboard of squares where the Knight is allowed to move, then the answer is “YES”: the Knight can go to e4.

Move generation is not the only operation an engine performs. When making and unmaking moves, it must also know exactly which piece occupies a square. For example, if a Knight moves from c3 to e4 and captures a piece, taking the move back requires restoring both the Knight and the captured piece to their original squares.

We can’t get this information from the occupancy of the board, because that only tells us if there are pieces on a square, but not which piece it is. Because of this, the question “Which piece is on e4?” means we will have to loop through the 6 bitboards (one for each piece type) of the opponent and check if the bit for e4 is set. This process is much slower than a direct array lookup.

To resolve this issue, we use a piece list. The piece list is just an array of 64 elements, one for each square. If a square is empty, it holds the value 0; if a piece is on a square, it holds the number for that piece type. The array looks like this:

piece_list: EverySquare<Piece>

When setting up the board, we first fill the 6 bitboards for each side. Then we loop through the bitboards for both White and Black, and put each piece we encounter into the correct square in the piece list. This happens when we start the engine, or when we initialize it with a new position. The piece list initialization looks like this:

fn init_piece_list(&self) -> EverySquare<Piece> {
    let bb_w = self.bb_pieces[Side::White]; // White piece bitboards
    let bb_b = self.bb_pieces[Side::Black]; // Black piece bitboards
    let mut piece_list: EverySquare<Piece> = EverySquare::new(Piece::None);

    // piece_type is enumerated, from 0 to 6.
    // 0 = KING, 1 = QUEEN, and so on, as defined in board::defs.
    for (piece_type, (w, b)) in bb_w.iter().zip(bb_b.iter()).enumerate() {
        let mut white_pieces = *w; // White pieces of type "piece_type"
        let mut black_pieces = *b; // Black pieces of type "piece_type"

        // Put white pieces into the piece list.
        while white_pieces > Bitboard::empty() {
            let square = bits::next(&mut white_pieces);
            piece_list[square] = Piece::from(piece_type);
        }

        // Put black pieces into the piece list.
        while black_pieces > Bitboard::empty() {
            let square = bits::next(&mut black_pieces);
            piece_list[square] = Piece::from(piece_type);
        }
    }

    piece_list
}

That’s it. The piece list is initialized. The engine now knows which piece type is on which square. Because Rustic already knows which side is moving and maintains separate color bitboards, the piece list only stores the piece type. The side can be determined from the board state when needed. After initialization, the piece list is updated incrementally whenever a move is made or taken back, just like the bitboards. Rebuilding it from scratch each move would be unnecessarily expensive.

So, when the Knight captures a piece on e4, we can know what it was by using this one-liner:

let captured_piece = board.piece_list[Square::E4];

A legal move can never capture a king, so Piece::King should never appear as a captured piece. Encountering such a position would indicate a bug in move generation or legality checking.

Now that we have the board and the pieces, we can focus on the next part, which is the handling of Zobrist Keys. These keys are used to identify unique positions, and they will be very useful throughout the engine.