Computer Chess Club Archives




Subject: Re: Hash Collisions

Author: Robert Hyatt

Date: 14:05:48 02/24/99

Go up one level in this thread

On February 24, 1999 at 06:29:36, Rémi Coulom wrote:

>On February 23, 1999 at 11:07:12, Robert Hyatt wrote:
>>On February 23, 1999 at 05:59:24, Rémi Coulom wrote:
>>>I'd like to have the Hamming distance maximizers' opinion about these points.
>>First, I don't do _any_ of the above in Crafty at present.  So it is a pretty
>>much moot point at present for me.
>>second, the ran[n+1]=~ran[n] was just a simple optimization for the test
>>program.  And even there it was just a quick way to find 768 random numbers.
>>(ie that is quicker to compute than a new random number).  I only wanted to
>>see how many different 64 bit values I would have to try to get a hamming
>>distance of 24, because Don's number was way smaller than mine.
>What I would like to know is the reason why some people think that maximizing
>the minimum Hamming distance is good for hash codes. I have not got the ICCA
>Journal article that was indicated earlier and I wonder if their author measured
>any improvement over random hash keys. I would appreciate very much if someone
>who has it could post a summary of the content of this ICCA Journal article.

The issue is collisions.  Burt did some analysis on depth of search and
probability of collisions.  What you worry about is you start with a hash
signature at the root, and you permute it every ply along the path from that
root position to the various tips.  How frequently do you permute it in a
circle so that you arrive back at the root hash signature somewhere else in
the tree?  Intuitively if all your random numbers are 1 bit different, you could
reach the same hash signature after 2 plies.  Or even after 1 in fact...

that's the bottom line of all this... trying to make the numbers different
enough that N permutations won't cycle around to the original again...

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