Computer Chess Club Archives


Search

Terms

Messages

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.
>>>
>>>Remi
>>
>>
>>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.
>Thanks.
>
>Remi

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.