Author: Pham Minh Tri
Date: 08:10:47 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
Hi Cheok,
I think I could understand your difficulty because till last month I write my
hash table like code above - I learnt from same source (very good source, isn't
it?) :-)
I think other people make good explanations. I just add some specific points.
1) You should generate y like x (same method)
2) See other posts below and above ;-)
Actually, you need not to use 64-bit for x and y. Normal 32-bit (long) values
are enough for them (this is the main benefit of this way: easy to calculate in
32 bit integers and save memory of hash). They are safe because their total is
64 bit. But you have to maintain two hash values (x and y) - may be little
slower than maintain a 64 bit value. Thus, I finanlly change to popular way: use
only one 64 bit hash value. Use this value both for indexing and saving as a
checksum. But I may change back to check which one is the best.
Hope that helps,
Pham
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.