Zobrist hashing (also referred to as Zobrist keys or Zobrist signatures ) is a hash function construction used in computer programs that play abstract board games, such as chess and Go, to implement transposition tables, a special kind of hash table that is indexed by a board position and used to avoid analyzing the same position more than once. Zobrist hashing is named for its inventor, Albert Lindsey Zobrist.
Zobrist hashing starts by randomly generating bitstrings for each possible element of a board game. Given a certain board position, it breaks up the board into independent components, finds out what state each component is in, and combines the bitstrings representing those elements together using bitwise XOR. If the bitstrings are long enough, different board positions will almost certainly hash to different values; however longer bitstrings require proportionally more computer resources to manipulate. Many game engines store only the hash values in the transposition table, omitting the position information itself entirely to reduce memory usage, and assuming that hash collisions will not occur, or will not greatly influence the results of the table if they do.
Zobrist hashing is the first known instance of tabulation hashing. The result is a 3-wise independent hash family. In particular, it is strongly universal.
As an example, in chess, each of the 64 squares can at any time be empty, or contain one of the 6 game pieces, which are either black or white. That is, each square can be in one of 1 + 6 x 2 = 13 possible states at any time. Thus one needs to generate at most 13 x 64 = 832 random bitstrings. Given a position, one obtains its Zobrist hash by finding out which pieces are on which squares, and combining the relevant bitstrings together.
The position of a board can be updated simply by XORing out the bitstring(s) for states which have changed, and XORing in the bitstrings for the new states. For instance, if a pawn on a chessboard square is replaced by a rook from another square, the resulting position would be produced by XORing the existing hash with the bitstrings for:
'pawn at this square' (XORing out the pawn at this square) 'rook at this square' (XORing in the rook at this square) 'rook at source square' (XORing out the rook at the source square) 'nothing at source square' (XORing in nothing at the source square).This makes Zobrist hashing very efficient for traversing a game tree.
In computer go, this technique is also used for superko detection.