Computer Chess Club Archives




Subject: Re: Hash Collisions

Author: Robert Hyatt

Date: 12:58:16 02/21/99

Go up one level in this thread

On February 21, 1999 at 13:23:24, William Bryant wrote:

>On February 21, 1999 at 10:21:50, Robert Hyatt wrote:
>>On February 21, 1999 at 01:14:37, KarinsDad wrote:
>>>I posted this the other day, but it may have been obscured (or not if nobody has
>>>any information on it).
>>>I have been wondering if changing the Zobrist hash from a set of random number
>>>to a set of non-random and very specific numbers could result in a more even
>>>distribution in the hash table. Has anyone done any work in this area?
>>Burt Wendroff and Tony Warnock published a paper in the JICCA a few years
>>ago discussing this.  The main issue is to find the hamming distances between
>>_all_ the random numbers, and maximize all of them.  Random numbers work fine
>>if they have been tested (I ran all of mine thru a hamming distance analysis
>>when I first started).
>>As far as 'distribution' this is done by the low order N bits
>>(N=log2(hash_size)) of the hash signature.  You _could_ do the hamming analysis
>>on just those bits as well.
>I check all my random numbers for uniqueness, ie no duplicates,and use
>0xFFFFFFFFFFFFFFFF for the side to move (compliment the side to move),
>but would appreciate information on 'hamming distance analysis' in not to
>complicated to post or send via email.
>Thank you,

"hamming distance" is simply the number of bits two numbers differ in.  To
compute the hamming distance for a and b, you just compute popcnt(a^b).  Two
numbers can differ in all bits.  But more than two can not...  I shoot for
no worse than 32 bits that are the same in two random numbers...  Assuming
64 bit values...

This page took 0.03 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.