Zobrist hashing

Zobrist hashing assigns pseudorandom numbers to the features that can form a position. There is usually a number for every piece type, color, and square combination, plus numbers for the side to move, castling rights, which record whether king and rook may still make that special move, and relevant en passant state for the special pawn capture. Pseudorandom means the values appear random but are generated reproducibly.

The position key is formed by combining active values with XOR, short for exclusive OR, a binary operation that acts like a toggle: applying the same value twice reverses its effect. When a piece moves, the program can remove its old-square value and add its new-square value without rebuilding the key from scratch. Captures, promotions, and side changes can be updated in the same way.

This fingerprint lets a chess engine, a program that analyzes positions, recognize quickly that a position has appeared before. It can reuse stored analysis when different move sequences reach the same state, detect repetitions, and organize caches, which are fast stores of earlier results. Correct comparison requires more than piece placement because the side to move and special rights can change the legal possibilities.

A Zobrist key is not guaranteed to be unique. Two different positions can produce the same number, an event called a collision. Large keys make this unlikely, but storage and verification still need to account for the possibility. In tests such as perft, an incremental key can also expose update errors when it fails to return to its original value after a move is made and undone.