Author: Vincent Diepeveen
Date: 16:56:58 01/18/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.
>
>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?
I fear you are. No need for a linked list. Just make that
array as big as possible, and then overwrite.
Now we get to a different problem, when to overwrite?
First we try delaying overwrite by trying next 7 tuples (called 8 probe
as you try 8 probes). If nothing is in one of those other 8 tuples, then
you store it there. If there is, then store it in the tuple with
the smallest depth.
Simply overwrite it!
Of course there are other things: if one of the tuples already contains
this position, then simply overwrite it to that position if depth is
larger.
Etc. etc.
hashtables are easy, but also difficult....
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.