Zobrist hashing
Encyclopedia
Zobrist hashing is a hash function
construction used in computer program
s that play abstract board games, such as chess
and Go
, to implement transposition table
s, 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 collision
s will not occur, or will not greatly influence the results of the table if they do.
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.
Hash function
A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys. For example, a single integer can serve as an index to an array...
construction used in computer program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
s that play abstract board games, such as chess
Computer chess
Computer chess is computer architecture encompassing hardware and software capable of playing chess autonomously without human guidance. Computer chess acts as solo entertainment , as aids to chess analysis, for computer chess competitions, and as research to provide insights into human...
and Go
Computer Go
Computer Go is the field of artificial intelligence dedicated to creating a computer program that plays Go, a traditional board game.-Performance:...
, to implement transposition table
Transposition table
In computer chess and other computer games, transposition tables are used to speed up the search of the game tree. Transposition tables are primarily useful in perfect information games, meaning the entire state of the game is known to all players at all times....
s, a special kind of hash table
Hash table
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
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
Pseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
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 collision
Hash collision
Not to be confused with wireless packet collision.In computer science, a collision or clash is a situation that occurs when two distinct pieces of data have the same hash value, checksum, fingerprint, or cryptographic digest....
s will not occur, or will not greatly influence the results of the table if they do.
As an example, in chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
, 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
Rook (chess)
A rook is a piece in the strategy board game of chess. Formerly the piece was called the castle, tower, marquess, rector, and comes...
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
Game tree
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...
.
In computer go
Computer Go
Computer Go is the field of artificial intelligence dedicated to creating a computer program that plays Go, a traditional board game.-Performance:...
, this technique is also used for superko detection.