Zobrist hashing
From Wikipedia, the free encyclopedia
Zobrist Hashing is a technique for creating hash codes, usually from something like a Go position. A table of random values is created, with each position on the board having a value associated with it for every possible state it can be in (eg, Black, White or Empty). Sometimes one of the states is set as all "0." Then, to create a hash code from the position, the value for each point is determined based on its state. These values are then XORed together to create the final hash code.
This method has several advantages: it is reasonably collision resistant, the code is easy to write and the values are easy to compute, and where necessary it can be updated incrementally for speed -- if only one point changes, it is just necessary to do two XOR operations: original hash XOR old point value XOR new point value = new hash. If one of the states is the empty state and the corresponding value is 0, then only one operation is needed.
In computer go, this technique is used with transposition tables and superko detection. Normally the values used range in size from 32 bits to 96 bits (longer hashes provide more collision resistance). Frequently an exact hash collision is taken to mean the positions are the same, without checking the actual positions. Often the original positions are not even stored in the transposition table in order to save time and memory.
[edit] See also
[edit] References
- Zobrist, Albert L. A Hashing Method with Applications for Game Playing, Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, (1969).
