Author: Dan Newman
Date: 01:19:45 09/22/98
Go up one level in this thread
On September 21, 1998 at 21:50:52, Dan Newman wrote:
>I once read a paper on this subject that found the two level table to
>be the best amonst various other schemes--at least I think I read such
>a paper... I've looked around and can't find it though. I'll look
>some more later...
I found the paper: D.M. Breuker, J.W.H.M. Uiterwijk and
H.J. van den Herik, "Replacement Schemes for Transposition
Tables," ICCAJ (1994), v17n4, p183-193. You can download
a postscript version of it via Breuker's page at
http://www.cs.rulimburg.nl/~breuker/. (My copy of the
postscript paper seems to be missing the figures though...)
They compare 7 different replacement schemes including two
versions of the two level scheme. They found that two level
schemes are better than one level. They found the worst
scheme was one they call "New" in which the entry is always
overwritten. The best was one they call "TwoBig1" in which
one level is "always replace", and the other is "replace if
the number of nodes searched below the position is greater".
(Depth takes far fewer bits to store than node counts, and
for that reason it may be preferable to use the other two
level scheme they describe, called "TwoDeep"--that's the one
that I use.)
Anyway, for large tables (>512 K entries) they found only
a 3% spread in nodecounts between the worst and best schemes.
For an 8K table they got 23%. (This makes sense since a
larger table has fewer collisions to start out with and then
later, once it's filled, its entries tend to hang around
longer.)
Carl Ebling in "All the Right Moves" (1986) describes a
two level hash table scheme. (I got a copy last year via
Amazon.com. It's a dissertation on Hitech's hardware.)
I'll excerpt a small section that explains the reasoning
behind the two level scheme, p.96:
"At the greater search depths, the main table becomes
static as it is filled with positions near the top of
the tree [I assume he means near the root], and the
FIFO table [this is analogous to the "always replace"
table] becomes a cache for nodes in the current subtree."
He goes on to describe a scheme which uses only one table
but which has much of the benefit of the two table scheme.
Nodes near to the root are subject to the depth replacement
scheme and are marked as "privileged". Those that are
further from the root are "always replace"--except they
aren't allowed to replace privileged nodes.
-Dan.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.