Author: Robert Hyatt
Date: 05:13:52 01/19/99
Go up one level in this thread
On January 18, 1999 at 19:01:01, Dann Corbit wrote:
>I am curious as to how most computer chess writers constuct their hash tables.
>I suspect it may be something like this:
>
>Using a hash function, like zobrist, compute an n-bit hash that maps to a 2^n
>hash table. For each hash, store collisions in a linked list.
no linked list, generally. This leads to lots of 'chaining' because in most
cases, the table is going to be greatly over-used, and chaining would become
way too expensive. There are two commonly-used approaches. (1) use two hash
tables, one you store in based on depth (depth-preferred) the other you always
store in if you don't store in the first. I use a modified version of this
that stores in the depth-preferred table if the draft of the current position
is > the draft of the position to replace, but first I move the current entry
from depth-preferred to the always-store table. Otherwise I storein the
always store table. (2) use some form of hash 'buckets'. IE in cray blitz,
I took the low order N bits of the hash signature as the probe address. I took
the next 10 bits as a 'rehash offset'. (call this RO). I then checked the
positions at offset, offset+RO, offset+2RO, ... offset+7RO. Either approach is
ok. The latter tends to solve the 'chaining' problem because two different
hash keys identical in the last N bits (probe address) still may be different in
the next 10 bits, giving a different 'bucket'.
>
>If that is the case, then I have a suggestion that could improve speed when
>there are lots of collisions. Instead of an ordinary singly linked list, use a
>skiplist. Then, when you have a list longer than one, you can find the data
>object in log[base2](n) operations {where n is the length of the collision
>chain}, and it only costs about .25 pointer per element. Or am I totally all
>wet?
lists don't work well... because we do this lookup once per node. And fiddling
with a linked list is too slow and requires too much memory bandwidth...
This page took 0.01 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.