www.delorie.com/gnu/docs/gnugo/gnugo_169.html

search

	Buy GNU books!

GNU Go Documentation

14.2 Hashing of Positions

To speed up the reading process, we note that a position can be reached in several different ways. In fact, it is a very common occurrence that a previously checked position is rechecked, often within the same search but from a different branch in the recursion tree.

This wastes a lot of computing resources, so in a number of places, we store away the current position, the function we are in, and which worm is under attack or to be defended. When the search for this position is finished, we also store away the result of the search and which move made the attack or defense succeed.

All this data is stored in a hash table, sometimes also called a transposition table, where Go positions are the key and results of the reading for certain functions and groups are the data. You can increase the size of the Hash table using the `-M' or `--memory' option see section 3.9 Invoking GNU Go: Command line options.

The hash table is created once and for all at the beginning of the game by the function hashtable_new(). Although hash memory is thus allocated only once in the game, the table is reinitialized at the beginning of each move by a call to hashtable_clear() from genmove().

14.2.1 Calculation of the hash value
14.2.2 Organization of the hash table
14.2.3 Hash Structures		Structures in `hash.h'
14.2.4 Hash Functions		Hash functions and macros