Zobrist hashing

Zobrist hashing

Zobrist hashing is a technique for creating hash codes, usually from something like a Chess 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.

ee also

* Alpha-beta pruning
* Transposition table

References

# Zobrist, Albert L. A Hashing Method with Applications for Game Playing, Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, (1969).
# [http://web.archive.org/web/20070822204038/http://www.seanet.com/~brucemo/topics/zobrist.htm Zobrist keys: a means of enabling position comparison.]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Computer Go — Part of a series of articles on Go (board game) Game specifics Go rules Go handicaps Go proverbs Go terms Go strategy and tactics Fuseki (whole board openings) Joseki (corner based openings) Life and death Tsumego …   Wikipedia

  • Hash function — A hash function is any well defined procedure or mathematical function for turning some kind of data into a relatively small integer, that may serve as an index into an array. The values returned by a hash function are called hash values, hash… …   Wikipedia

  • 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… …   Wikipedia

  • Unsolved problems in computer science — This article is a list of open problems in computer science.A solution to the problems in this list will have a major impact on the field of study to which they belong. =P = NP?= ;Field : Theory of computation;Source : S. A. Cook and Leonid Levin …   Wikipedia

  • Table de finale — …   Wikipédia en Français

  • Endgame tablebase — A typical interface for querying a tablebase An endgame tablebase is a computerized database that co …   Wikipedia

  • Mizar chess engine — Mizar Developer(s) Nicola Rizzuti Stable release 3.0 / May 16, 2006 Written in C Operating system Windows …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”