• Zobrist Hashing
  • What is this?
  • Why do we need it?
  • Explanation
  • Extending this to chess
  • Implementation
  • Initialization
  • Access to the ZobristRandoms

Zobrist Hashing

What is this?

Zobrist hashing is a method of representing positions in a board game using a single large number. It was developed by Albert Lindsey Zobrist (1942) in 1970. When first studying this method it can be a bit confusing, but after you get familiar with it, I am sure you will appreciate its elegance.

Why do we need it?

In a chess engine there are numerous reasons to quickly identify a position. One would be to detect repetitions: if a position occurs for the third time, with the same player making the move that reaches that position, the game is a draw by rule. We don’t want to store all boards during the game and check each of them exhaustively. This would be very time consuming. Zobrist Hashing creates a Zobrist Key for each position. Now we can just compare two numbers instead of having to compare positions piece by piece.

Another use is for the implementation of a transposition table which holds positions that have been encountered and evaluated in the past. The Zobrist Keys are again a way to quickly find positions the engine has encountered before, so we can get their evaluation outcome from the table instead of recalculating it again. This saves an enormous amount of calculation time; so much so, that adding a transposition table to an engine will typically gain over 100 Elo points in playing strength, and it’s the Zobrist Key that makes this possible.

Explanation

To make it easier to explain, let us first boil it down to its essence. To do so, we’ll define a rather simple board game:

• There is 1 player.
• The board has 4 squares.
• There are 4 pieces, all of the same type.
• The player is allowed to take back moves and remove a piece.
• As soon as the player puts the fourth piece onto the board, he wins.

This game is trivial. It isn’t even a game, because there is no goal and no opponent. The player can win the game in 4 moves, or he can get stuck in a loop by adding and removing pieces one after the other. For our explanation, this doesn’t matter. The only thing we focus on is that the board position changes.

We now want to define the Zobrist Hashing method:

• We need a number that identifies a board position with an extremely low probability of collision. With 64-bit Zobrist keys, collisions are possible but extremely rare in practice, which is why most chess engines simply ignore the possibility.
• When the board position changes, we must be able to update this number. We do not want to recalculate the number from scratch on every change, because this would be too slow.

In this game, achieving this is simple. We have a board with 4 squares, and all pieces are of the same type. So, we can simply do this:

• 0000 (0), empty board.
• 0001 (1), piece on square 1
• 0010 (2), piece on square 2
• 0100 (4), piece on square 3
• 1000 (8), piece on square 4

There are only four board features in this game: a piece on square 1, square 2, square 3, or square 4. The empty board is represented by a board key of zero. We need a number for each. (Later, when extending this to chess, you’ll see we also have to define keys for special situations such as castling.)

We start with the empty board, so the Zobrist Key for the board is 0000. The player adds a piece on square 4. The key for a piece on this square is 1000. We now want to change the board’s Zobrist key, without looping through the entire board and recalculating it from scratch. The way to do this, is with the XOR operand from the bitwise operations. The board key is simply the XOR of all piece/square keys currently present on the board:

0000    (current board key)
1000    (piece/square key, added or removed)
----    xor
1000    (new key)

So the board’s key is 1000. The player now adds a piece to square 3:

1000    (current board key)
0100    (piece/square key, added or removed)
----    xor
1100    (new key)

So the board’s key is 1100. The player now adds a piece to square 1:

1100    (current board key)
0001    (piece added or removed)
----    xor
1101    (new key)

The board key is now 1101. The player takes back the move on square 3:

1101    (current board key)
0100    (piece added or removed)
----    xor
1001    (new key)

The key becomes 1001. The player adds the piece to square 3 again:

1001    (current board key)
0100    (piece added or removed)
----    xor
1101    (new key)

The key returns to 1101 again. This is the essence of the Zobrist Hashing method: By taking the current Zobrist board key and XOR-ing it with the key of the change you are making, you can either add this change to the board key, or take it out again. By XOR-ing the same key repeatedly as we have done in the last two steps, the Zobrist key flips back and forth between two values.

Extending this to chess

Now let’s extend this method to chess. The previous simple game had only 16 different positions (binary 0000 to 1111), so we could effectively give each square/piece combination its own number/key by hand and combining those into a board key. With chess this is not possible, because for all intents and purposes, the number of positions is astronomically large. Compared to the previous game, chess has:

• Two players instead of one, of which one has the turn and the other doesn’t
• 64 squares instead of 4
• 6 piece types instead of one, which can be all on the board, or not
• A bunch of special cases such as castling and en-passant

All of this needs to be encoded in the board Zobrist key, so we first need to know how many keys we need.

• We need 64 squares x 6 types x 2 players = 768 square/piece/player keys
• We need 16 keys for the castling positions. Castling is coded the same way as the game above: 0000 is no castling rights, 0001 is white can castle kingside, 0010 is white can castle queenside, and so on. This gives a binary number from 0000 to 1111, which are 16 values.
• We need 2 keys for the side to move.
• 17 en-passant keys (8 squares for white, 8 squares for black, and 1 for no en-passant square).

The total number of keys we have is 768 square/piece/player keys + 16 castling keys + 2 side-to-move keys + 17 en-passant keys = 803 keys.

Sidenote: Rustic, at least up until version 4, uses 65 en-passant keys; one for each square (and none), even though only 16 are valid en-passant squares. This makes no difference with regard to the Zobrist method or the performance. It just means that the engine generates 48 Zobrist keys it will never use.

Implementation

We need 803 random keys that represent the individual features that make up a chess position. Because there are so many, we want the number to be as big as possible. We are not just going to use the numbers from 1 to 803, because these keys wouldn’t contain enough bits to do the XOR-ing we discussed earlier, and still contain enough bits to try and make the final key unique. The solution to this is to create 64-bit keys, which we will then fill by randomly generating a 64-bit integer for each. Random values reduce the likelihood that different combinations of board features produce the same final hash value.

Sidenote: This is where the name “Zobrist Randoms” comes from: many engines call the randomly generated keys the “Zobrist Randoms”, and the result after XOR-ing is then called the “Zobrist Key” for that position. Rustic stays with that convention.

Implementing this is easy: you could just use an array of 803 elements, loop through it and generate a key for each. After that you index into the array. The first 768 keys are for square/piece/player combinations, the next 16 are for castling, and so on.

Personally I opted to split this up to make it easier to reason about, so I defined a ZobristRandoms struct.

type PieceRandoms = [[[u64; NrOf::SQUARES]; NrOf::PIECE_TYPES]; NrOf::SIDES];
type CastlingRandoms = [u64; NrOf::CASTLING_PERMISSIONS];
type SideRandoms = [u64; NrOf::SIDES];
type EpRandoms = [u64; NrOf::SQUARES + 1];

pub type ZobristKey = u64;

const RNG_SEED: [u8; 32] = [125; 32];

pub struct ZobristRandoms {
    rnd_pieces: PieceRandoms,
    rnd_castling: CastlingRandoms,
    rnd_sides: SideRandoms,
    rnd_en_passant: EpRandoms,
}

Sidenote This version uses the 65 en-passant square keys as mentioned in the previous side-note, but for the overall implementation this makes no difference.

Then we fill up each of the arrays with random numbers. For example, for the square/piece/side part, Rustic uses this code:

zobrist_randoms.rnd_pieces.iter_mut().for_each(|side| {
    side.iter_mut().for_each(|piece| {
        piece
            .iter_mut()
            .for_each(|square| *square = random.random::<u64>())
    })
});

It is a short piece of functional code and it literally says what it is doing: for each side, for each piece, on each square, generate a random number. The code for the other keys (castling, side to move, and en-passant) is very similar. This is the new() function, which creates the ZobristRandoms struct:

pub fn new() -> Self {
    let mut random = ChaChaRng::from_seed(RNG_SEED);
    let mut zobrist_randoms = Self {
        rnd_pieces: [[[EMPTY; NrOf::SQUARES]; NrOf::PIECE_TYPES]; NrOf::SIDES],
        rnd_castling: [EMPTY; NrOf::CASTLING_PERMISSIONS],
        rnd_sides: [EMPTY; NrOf::SIDES],
        rnd_en_passant: [EMPTY; NrOf::SQUARES + 1],
    };

    zobrist_randoms.rnd_pieces.iter_mut().for_each(|side| {
        side.iter_mut().for_each(|piece| {
            piece
                .iter_mut()
                .for_each(|square| *square = random.random::<u64>())
        })
    });

    zobrist_randoms
        .rnd_castling
        .iter_mut()
        .for_each(|permission| *permission = random.random::<u64>());

    zobrist_randoms
        .rnd_sides
        .iter_mut()
        .for_each(|side| *side = random.random::<u64>());

    zobrist_randoms
        .rnd_en_passant
        .iter_mut()
        .for_each(|ep| *ep = random.random::<u64>());

    zobrist_randoms
}

Initialization

We have to initialize the Zobrist Key for the position we are starting out with. This is done when a new board is set up. Here is the function that creates the position’s Zobrist Key by applying the XOR-technique discussed in the beginning of the section:

pub fn init_zobrist_key(&self) -> ZobristKey {
    // Keep the key here.
    let mut key: u64 = 0;

    // "bb_w" is shorthand for "self.bb_pieces[Sides::WHITE]".
    let bb_w = self.bb_pieces[Side::White];
    let bb_b = self.bb_pieces[Side::Black];

    // Iterate through all piece types, for both white and black.
    // "piece_type" is enumerated, and it'll start at 0 (KING), then 1
    // (QUEEN), and so on.
    for (piece_type, (w, b)) in bb_w.iter().zip(bb_b.iter()).enumerate() {
        // Assume the first iteration; piece_type will be 0 (KING). The
        // following two statements will thus get all the pieces of
        // type "KING" for white and black. (This will obviously only
        // be one king, but with rooks, there will be two in the
        // starting position.)
        let mut white_pieces = *w;
        let mut black_pieces = *b;

        // Iterate through all the piece locations of the current piece
        // type. Get the square the piece is on, and then hash that
        // square/piece combination into the zobrist key.
        while white_pieces > Bitboard::empty() {
            let square = bits::next(&mut white_pieces);
            key ^= self
                .zobrist_randoms
                .piece(Side::White, Piece::from(piece_type), square);
        }

        // Same for black.
        while black_pieces > Bitboard::empty() {
            let square = bits::next(&mut black_pieces);
            key ^= self
                .zobrist_randoms
                .piece(Side::Black, Piece::from(piece_type), square);
        }
    }

    // Hash the castling, active color, and en-passant state.
    key ^= self.zobrist_randoms.castling(self.game_state.castling);
    key ^= self.zobrist_randoms.side(self.game_state.active_color);
    key ^= self.zobrist_randoms.en_passant(self.game_state.en_passant);

    // Done; return the key.
    key
}

We need a place to put the board’s current Zobrist Key. The GameState struct, which collects all manner of data about the current position is an ideal location for this, so we’ll discuss this in the next section.

Access to the ZobristRandoms

Because the random numbers are hidden inside the ZobristRandoms struct, we also need some functions to get to them:

// Get the Random for this side, piece, and square combination
pub fn piece(&self, side: Side, piece: Piece, square: Square) -> ZobristKey {
    self.rnd_pieces[side.idx()][piece.idx()][square.idx()]
}

// Get the random for the passed-in castling permission
pub fn castling(&self, permissions: Bitboard) -> ZobristKey {
    self.rnd_castling[permissions.idx()]
}

// Get the Random for the side to move
pub fn side(&self, side: Side) -> u64 {
    self.rnd_sides[side.idx()]
}

// Get the Random for the en-passant square that is passed in, or the one for the "65th" square if there is none.
pub fn en_passant(&self, en_passant: Option<Square>) -> ZobristKey {
    match en_passant {
        Some(ep) => self.rnd_en_passant[ep as usize],
        None => self.rnd_en_passant[NrOf::SQUARES],
    }
}

That’s it for the Zobrist Keys. The next chapter deals with the GameState struct. This is where the engine will keep information about the position that can’t be determined by just looking at the board and pieces.

For experienced chess engine authors: I know it is also possible to use only 5 castling keys: one each for white kingside, white queenside, black kingside, black queenside and no castling permissions. In that case however, if a player moves his king, you’d need to do two Zobrist transformations instead of one. I found it easier to just create 16 castling keys and do all the castling changes with one key change. This is also faster.

It is even possible to cut down more on the keys in use. For example, you can have only 1 side-to-move key. If you include it in the board key, it’s white to move; if it’s not in there, it’s black to move. Same for the castling and en-passant keys. You don’t NEED to have the “empty” keys for no castling and no en-passant; you can just opt to not include any of the keys castling or en-passant keys to mark that these possibilities don’t exist in the position. Personally I find this confusing, so I use a key for each possible state: 16 to capture all possible combinations of castling permissions including empty, and 16+1 for en-passant. It is more consistent, because you always have a key included.