Zobrist Hashing: What It Is and How It Works

⏱️ Reading time: 13 min

A chess engine that analyzes thousands of positions per second can’t stop to compare the board square by square on every move. Instead, it keeps a single 64-bit number that gets updated with one XOR operation: Zobrist hashing. That number acts as a fingerprint of the position, letting the engine instantly recognize whether it has already analyzed that same board before, without looking at it in full again.

📑 En este artículo

1. TL;DR
2. What Is Zobrist Hashing?
3. Why It Matters
4. How the Zobrist Key Works
5. Practical Examples
6. Getting Started
7. Real-World Use Cases
8. Common Mistakes and Best Practices
9. Comparison with Alternatives
10. Going Deeper: Collisions and Lock-Free Hashing
11. Frequently Asked Questions
    1. What distinguishes a Zobrist key from a cryptographic hash like SHA-256?
    2. Why does a chess engine need a transposition table?
    3. Can the incremental board hash fail and produce false positives?
    4. Can the Zobrist signature be used in games other than chess?
    5. How many Zobrist keys need to be precomputed for a full chess implementation?
    6. What happens if two engine threads access the transposition table at the same time?
12. References

TL;DR

• Zobrist hashing assigns a random 64-bit number to each piece-and-square combination, then combines them with XOR.
• A single XOR operation per move updates the entire hash, without scanning all 64 squares of the board again.
• The resulting key indexes the transposition table, the memory structure that avoids reanalyzing the same position twice.
• XOR applied twice cancels itself out, which is why removing and placing a piece is a reversible operation.
• Go, shogi, and other board games use the same trick to detect position repetitions without storing the full history.

What Is Zobrist Hashing?

Zobrist hashing is a method for summarizing the entire state of a game board into a single 64-bit number, generated by combining with XOR a distinct random key for each occupied piece-and-square pair, so that any change on the board is reflected with a single operation.

The idea first appeared in 1970, when Albert Zobrist described it in his doctoral thesis at the University of Wisconsin, applied to a Go-playing program, as documented by the Wikipedia entry on the technique. Decades later it became a standard in chess engines, checkers, shogi, and any board game where quickly recognizing repeated positions matters.

The key to the scheme is choosing, ahead of time, a distinct random number for every possible piece-on-square combination, for example a white bishop on c4. To build the hash of a specific position, it’s enough to XOR the numbers corresponding to the pieces present at that moment.

Why It Matters

Chess engines exploit a phenomenon called transposition: two different move sequences can end up at the same board. If the engine already evaluated that position via a different path, repeating the work wastes time. The solution is to store each evaluation in a transposition table, indexed by a unique identifier for the position.

That’s where Zobrist hashing comes in. Without it, identifying a position would require serializing all 64 squares and comparing them one by one against everything already stored, far too slow for an algorithm that visits millions of nodes. With a 64-bit key, the comparison reduces to comparing two integers.

The same problem shows up in Go, where the superko rule forbids repeating an exact position anywhere in the game. Comparing the full board against every previous position would be prohibitive, so Go programs also use a Zobrist signature for that check.

How the Zobrist Key Works

Before a single game is played, the engine generates a table of random 64-bit numbers: one for each combination of piece type (pawn, knight, bishop, rook, queen, king, for each color) and board square. In chess that’s 12 piece types times 64 squares, plus an extra key for the side to move and keys for castling rights and the en passant file. The chess programming wiki documents the full scheme: 64 times 12 piece keys, plus one for the turn, plus four for castling, plus eight for the en passant file, a total of 781 random numbers fixed for the entire game.

Computing the hash of any given position is as simple as XORing the keys of every piece present. What’s interesting isn’t that initial calculation, but what happens after each move: instead of recalculating everything, the engine removes from the hash the key of the piece at its origin square, adds the key for that piece at the destination square, and toggles the turn key. Three XOR operations, regardless of how many pieces are on the board.

flowchart TD
    A["Current position with hash H"] --> B["Move a piece from origin to destination"]
    B --> C["XOR with the key of the piece at the origin square"]
    C --> D["XOR with the key of the piece at the destination square"]
    D --> E["XOR with the turn-change key"]
    E --> F["New hash, computed in constant time"]

That property depends on XOR being its own inverse: applying the same key twice cancels it out. That’s why undoing a move is trivial, you just repeat the same three operations, and why there’s no need to keep the previous board around to compute the next hash.

💡 Tip: the quality of the random number generator matters. A generator with predictable patterns produces more collisions than theory predicts; a well-distributed 64-bit generator, like Mersenne Twister or xorshift64, is the way to go.

During the search, every time the engine reaches a position it looks up its hash in the transposition table before evaluating it from scratch.

sequenceDiagram
    participant M as Search engine
    participant T as Transposition table
    M->>T: looks up the hash of the current position
    alt hash found
    T-->>M: returns the stored evaluation
    else hash not found
    T-->>M: no previous entry
    M->>T: stores the new evaluation under that hash
    end

Practical Examples

The simplest possible example uses tiny 4-bit keys instead of 64, just so the result can be checked by hand. Imagine three fixed keys: one for a white pawn on e2, another for a white pawn on e4, and one for the turn.

KEY_PEON_E2 = 0b1011  # 11
KEY_PEON_E4 = 0b0110  # 6
KEY_TURNO   = 0b1001  # 9

hash_inicial = KEY_PEON_E2 ^ KEY_TURNO
print(bin(hash_inicial))

This prints 0b10: the bitwise XOR of 1011 and 1001 gives 0010. Now let’s simulate the pawn advancing from e2 to e4, which removes the e2 key, adds the e4 key, and toggles the turn:

nuevo_hash = hash_inicial ^ KEY_PEON_E2 ^ KEY_PEON_E4 ^ KEY_TURNO
print(bin(nuevo_hash))

The output is 0b110 (6), which is exactly KEY_PEON_E4: the e2 key and the turn key canceled each other out, since each appears twice, leaving only the key for the new square. It’s the same mechanism a real engine uses, just with 64-bit integers instead of 4-bit ones.

The next step is to verify that the incremental hash always matches the one obtained by recalculating everything from scratch, something any real implementation should check at least once during testing:

import random
random.seed(7)

CASILLAS = 64
TIPOS_DE_PIEZA = 12
tabla_zobrist = [[random.getrandbits(64) for _ in range(TIPOS_DE_PIEZA)] for _ in range(CASILLAS)]
clave_turno = random.getrandbits(64)

def hash_desde_cero(piezas_en_tablero, turno_blanco):
    h = 0
    for casilla, tipo_pieza in piezas_en_tablero:
        h ^= tabla_zobrist[casilla][tipo_pieza]
    if turno_blanco:
        h ^= clave_turno
    return h

def mover(hash_actual, tipo_pieza, origen, destino):
    h = hash_actual ^ tabla_zobrist[origen][tipo_pieza] ^ tabla_zobrist[destino][tipo_pieza]
    return h ^ clave_turno

piezas = [(12, 0)]
hash_a = hash_desde_cero(piezas, turno_blanco=True)
hash_b = mover(hash_a, tipo_pieza=0, origen=12, destino=28)
piezas_despues = [(28, 0)]
hash_c = hash_desde_cero(piezas_despues, turno_blanco=False)

print('Match:', hash_b == hash_c)

The output is Match: True, and it holds no matter what random numbers random.seed(7) generates: the equality holds because XOR is associative and commutative, not because the numbers happen to coincide. It’s the minimal check any Zobrist hashing implementation should pass before it’s trusted.

Getting Started

To try the incremental board hash from the previous example, there’s no need to install anything: Python 3.8 or later is enough, since random.getrandbits is part of the standard library.

1. Save the code from the previous example in a file called zobrist_demo.py.
2. Run it with python3 zobrist_demo.py on Linux or macOS (on Windows, python zobrist_demo.py).
3. Confirm that the last printed line is Match: True. If you modify the mover function and get False, the error is usually forgetting to toggle the turn key or using the wrong piece’s key.

To extend the example to a full 8×8 board, the natural next step is to represent the 32 starting pieces as a list of tuples of square, piece type, and color, and generate the initial hash by looping through that list once when the game starts. From there, every move is updated with just the three XOR operations described earlier.

Real-World Use Cases

• Chess engines: UCI engines use a 64-bit signature as the index into their transposition table, which lets them recognize transpositions during search instead of reevaluating the same position reached via different paths.
• Go programs: the superko rule requires checking that no position repeats anywhere in the game; without an incremental hash, that check would be too costly for a tree search.
• Puzzle solvers: algorithms exploring the state space of games like the 15-puzzle or Sokoban use the same trick to detect whether a state has already been visited, avoiding infinite loops in the search.
• Shogi and checkers: any board game with position-repetition rules, like shogi’s sennichite, can rely on the same technique to detect draws by repetition.

Common Mistakes and Best Practices

The most common mistake is forgetting to include the turn key in the hash. Two positions with the same pieces on the same squares but a different player to move are distinct positions, one might be winning for White and the other for Black, and if the hash doesn’t distinguish the turn, the engine treats them as identical.

The second mistake is ignoring castling and en passant. Two boards can look identical but have different available castling rights, which completely changes the legal moves. A hash that doesn’t include those extra keys generates false positives of I’ve already seen this position.

The most important best practice is never to blindly trust hash equality for irreversible decisions without some extra verification. Real engines’ transposition tables usually store, alongside each entry, the search depth it was generated at, and some also keep an extra check value to reduce the impact of an accidental collision.

📌 Note: a collision in the transposition table doesn’t corrupt the game: in the worst case the engine uses a slightly wrong evaluation for one move and corrects it on the next iterative-deepening pass. It’s not a catastrophic failure, but it is a source of hard-to-reproduce bugs if you’re not careful.

Comparison with Alternatives

The incremental board hash isn’t the only way to identify a position, but it’s the one that best balances speed and simplicity for game-tree search:

Going Deeper: Collisions and Lock-Free Hashing

With 64-bit keys, the number of distinct positions that need to be generated before a random collision becomes likely grows roughly with the square root of the total key space, following the same logic as the birthday paradox. In practice, no chess engine analyzes enough positions in a single game for that to be a real problem; that’s why most engines use just the 64-bit key without any extra cryptographic verification.

Engines that search in parallel across multiple threads face another problem: two threads can write to the same transposition table entry at the same time and corrupt it halfway through. The chess programming community documents a technique known as lock-free hashing. Instead of protecting the write with a lock, each entry stores the hash combined with XOR against the evaluation data, so that when it’s read, it’s possible to detect whether a partial write left it inconsistent, without paying the cost of synchronizing threads on every access.

Zobrist’s core idea generalizes easily: any set of independent elements that may or may not be present, pieces on squares, cards in a hand, active cells in a cellular automaton, can be summarized with one random key per element and XOR to combine them. What makes the chess case special is that it was, historically, the one that popularized the technique beyond Go research circles.

Your next step: copy this article’s verification script, change CASILLAS and TIPOS_DE_PIEZA to model a different game, like the 15-puzzle with 16 squares and 15 tile types, and check that the equality between the incremental hash and the from-scratch hash still holds.

Frequently Asked Questions

What distinguishes a Zobrist key from a cryptographic hash like SHA-256?

A Zobrist key isn’t designed to resist deliberate attacks, only to quickly distinguish different positions in a way that’s updatable with XOR. SHA-256 is much slower to recalculate and doesn’t offer the incremental property that a game-tree search needs.

Why does a chess engine need a transposition table?

Because moves played in a different order can lead to the same board. Without a hash-indexed table, the engine would repeat the analysis of that position every time it reaches it via a different path, multiplying the work.

Can the incremental board hash fail and produce false positives?

In theory yes, through a collision between two different positions sharing the same 64-bit hash, but the probability is extremely low and almost no engine treats it as a practical problem.

Can the Zobrist signature be used in games other than chess?

Yes. Go programs use it for the superko rule, and any state-search algorithm, like a Sokoban solver, can apply it to detect states that have already been visited.

How many Zobrist keys need to be precomputed for a full chess implementation?

The scheme documented by the chess programming wiki uses 781 keys: 64 squares times 12 piece types, plus one for the turn, four for castling, and eight for the en passant file.

What happens if two engine threads access the transposition table at the same time?

They can corrupt an entry halfway through. The lock-free hashing technique avoids that problem without using locks, combining the hash and the stored data with XOR to detect inconsistencies on read.

References

• Chess Programming Wiki: Zobrist Hashing: specification of the key scheme and its use in chess engines.
• Wikipedia: Zobrist hashing: origin of the technique in Albert Zobrist’s 1970 doctoral thesis.
• Chess Programming Wiki: Transposition Table: how engines index stored evaluations using the Zobrist key.
• Chess Programming Wiki: Shared Hash Table: the lock-free hashing technique for transposition tables shared across threads.

📱 Like this content? Follow @programacion on Telegram for daily tech content in Spanish: quick summaries, fresh content every day.

Featured image: Foto de Chase Clark en Unsplash