Author: Andrew Williams
Date: 07:18:03 06/21/01
Go up one level in this thread
On June 21, 2001 at 09:56:50, Cheok Yan Cheng wrote:
>The below is a part of article picked from :
>http://www.ics.uci.edu/~eppstein/180a/970424.html
>------------------------------------------------------------
>struct {
> long checksum; // or long long might be even better
> int depth;
> enum { exact, lower_bound, upper_bound } entry_type;
> double eval;
>} hashtable[HASH_TABLE_SIZE];
>
>For each position you search, compute a "hash value" x indexing into the hash
>table and another "hash value" y for checking whether you've found the right
>position.
>
>Before searching a position, lookup hashtable[x]. If
>hashtable[x].checksum == y, hashtable[x].entry_type == exact, and
>hashtable[x].depth is at least the depth you are currently searching,
>return the eval stored there.
>------------------------------------------------------------
>
>For "hash value" x, I understand that it is generated using XOR from the table :
>64_bit_random_number[PIECE_TYPE][PIECE_LOCATION].
>
>1. For the "hash value" y that used for checksum, how should we generated it?
>2. What is checksum for ?
>
>thanks
Suppose you are using a 64-bit hash key. You can't possibly have an entry
for every possible hash key (that would be 2^64 entries), so you translate
the current hash key (y in your example). Typically, you might use an AND
operation to do this: if you have room in your hash table for 65536 entries,
you'd do:
x = (y & 65535);
So x is the index into the array. But you would still need to have access
to the whole hash key for the entry, to ensure that you don't get collisions.
So in the hash entry you store the whole hash key. In fact, you don't need
the whole hash key, because the bottom 16 (in the example with 65536 entries),
bits are implied by the position of the entry in the array. That's why it says
"checksum" in the struct instead of hashkey; some people save a bit of space
by only storing part of the hash key.
Andrew
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.