Computer Chess Club Archives




Subject: Re: double hash tables

Author: Robert Hyatt

Date: 05:50:17 10/01/97

Go up one level in this thread

On October 01, 1997 at 06:32:46, Chris Whittington wrote:

>CSTal always used to have one depth-based hash table with five bucket
>attempts on clashes. After reading the threads in rgcc, I tried it out
>with two hash table, an always replace and a depth-priority table.
>Some test positions get faster, some get slower, but, on the whole,
>there's an improvement.
>Until, that is, the hash gets overloaded, when the old depth-only table
>starts to come out on top.
>Is this a generally observed phenomenon ?

yes.  I have two hash algorithms for Crafty.  I use Ken's two-tiered
normally, because it is very fast execution-wise, and simple to
understand.  I
include this version in the "released" source code, and use this version
on ICC

The other approach, which goes by multiple names depending on exactly
how it
is implemented (rehashing as I used in Cray Blitz, which is likely the
best of
the best approaches), buckets, and chains, all offer advantages when the
becomes saturated.  Don Beal tested this in an ICCA article and found
the same thing.

The only saving grace for me is that I have not hashed q-search nodes
for way
over a year.  When I compared hashing in the q-search with hashing the
search only, I found it to be a few percent faster.  The tree got a
bigger, but the search speeded up enough to offset this and even give me
couple of percent more in speed.  A side-effect of this is that since I
hash q-search nodes, my hash table is much less stressed than the
programs that
do.  I'd guess that for middlegame positions, at least 50% of the nodes
be classified as "leaf" or "quiescence".  And they never make it into
the table.

So I get by with smaller tables.

But the idea of multiple probes is significantly superior to this
approach, *if* you don't have enough memory and the table becomes

This page took 0.01 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.