Contents  Introduction  Basic Board  Representations  Bit Boards  Transposition  Tables  Generating Hash  Keys for Chess  Boards  History Tables  Pre-processing  move generation  Printable version     The Series  Getting Started  Data Structures  Move Generation  Basic Search  Advanced Search  Evaluation  Functions

Generating Hash Keys for Chess Boards

The transposition tables described above are usually implemented as hash dictionaries of some sort, which brings up the following topic: how do you generate hashing keys from chess boards, quickly and efficiently?

The following scheme was described by Zobrist in 1970:

• Generate 12x64 N-bit random numbers (where the transposition table has 2^N entries) and store them in a table.  Each random number is associated with a given piece on a given square (i.e., black rook on H4, etc.)  An empty square is represented by a null word.
• Start with a null hash key.
• Scan the board; when you encounter a piece, XOR its random number to the current hash key.  Repeat until the entire board has been examined.

An interesting side effect of the scheme is that it will be very easy to update the hash value after a move, without re-scanning the entire board.  Remember the old XOR-graphics?  The way you XOR'ed a bitmap on top of a background to make it appear (usually in distorted colors), and XOR'ed it again to make it go away and restore the background to its original state?  This works similarly.  Say, for example, that a white rook on H1 captures a black pawn on H4.  To update the hash key, XOR the "white rook on H1" random number once again (to "erase" its effects), the "black pawn on H4" (to destroy it) and the "white rook on H4" (to add a contribution from the new rook position).

Use the exact same method, with different random numbers, to generate a second key (or "hash lock") to store in the transposition table along with the truly useful information.  This is used to detect and avoid collisions: if, by chance, two boards hash to the exact same key and collide in the transposition table, odds are extremely low that they will also hash to the same lock!

Next : History Tables