Talk:Transposition table

From Wikipedia, the free encyclopedia

Instead of using a hash table, wouldn't a trie be more efficient? Actually, an acyclic deterministic finite automata may be able to store a huge number of positions efficiently, but I don't know that for sure. Neurodivergent 22:43, 11 November 2005 (UTC)

Nope, a hash table is about ideal, for several reasons:

• O(1) lookup / insert
• It's typical to fix the size beforehand and never rehash
• It's also typical to implement the buckets very simply -- one entry per bucket is not uncommon, since it's ok if things get dropped from the table occasionally. Slightly more sophisticated is two entries per bucket, one for the newest insert into the table, and one for the computationally most expensive (usually measured as plies searched by the alpha-beta searcher). This is actually remarkably close in hit rate to any sort of deeper function, and can be faster depending on the rest of the program because the hitrate is so good and the lookups so cheap (no dealing with linked list buckets, for example).
• automata are cheap to execute, but expensive to construct, and there doesn't tend to be a cheap way to add a position, which matters -- this is about keeping track of positions seen during the game, not things beforehand.
• the hash functions are usually implemented as Zobrist hashing, which can be cheaply and incrementally computed.

Evand 22:52, 12 November 2005 (UTC)