Talk:Transposition table

Old talk

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)[reply]

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)[reply]

The article says "In alpha-beta pruning, the search is fastest (in fact, optimal) when the child of a node corresponding to the best move is always considered first." This is not strictly true. It may be the case that a child that is not the best move is sufficiently good to allow the tree to prune. Thus one wants a sufficiently good move whose subtree has the minimal computation cost. Cesium62 06:03, 17 August 2007 (UTC)[reply]

Quote

Link broken at "Transposition Tables Gamedev.net, Francois-Dominic Laramee"