Zobrist

A Zobrist hash is a hash function commonly used in computer programs that play abstract strategy games, such as chess, checkers, Go, and others. It's primarily employed for transposition table lookups.

The core idea is to assign a random number to each possible element of a game state. For instance, in chess, this would mean a unique random number for each piece type (pawn, knight, bishop, rook, queen, king) on each square of the board (a1, a2, ..., h8).

The Zobrist hash of a game state is calculated by XORing together all the random numbers corresponding to the elements currently present in that game state. If a piece moves, the hash is updated by XORing out the random number associated with the piece's original position and XORing in the random number associated with the piece's new position. This incremental updating is significantly faster than recalculating the entire hash from scratch.

Because XOR is its own inverse, moving the same piece back to its original square will revert the hash to its previous value. This property allows for quick and efficient updating of the hash during search algorithms, particularly those that explore many possible moves.

Collisions (different game states producing the same hash value) are possible, but with sufficiently large random numbers, they are statistically unlikely to occur frequently enough to significantly impact performance. Collision handling strategies, such as storing the full game state along with the hash value, are often employed to mitigate the effects of collisions.

The Zobrist hashing technique is named after Albert Lindsey Zobrist, who first described it in a 1970 paper. It provides a simple and computationally inexpensive method for representing and updating game states, making it a valuable tool in game programming.