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