Author: Ricardo Gibert
Date: 12:30:41 02/07/01
Go up one level in this thread
On February 07, 2001 at 13:42:31, Tim Foden wrote: >On February 07, 2001 at 12:19:38, Andrew Dados wrote: > >>On February 07, 2001 at 10:59:31, Pat King wrote: >> >>>I have seen it written here that with 64 bit Zobrist hashing, the perfect key >>>should change 32 bits. When I had what I thought to be hashing problems, I >>>captured some stats on my hash keys. I found that most of them changed 28-36 >>>bits (within 4) with a few outliers as far as 13 bits from "perfection". I also >>>checked that I was not generating duplicate keys. How good or bad is this? >>>Should I work on the average, or the outliers? Any comments appreciated :) >>> >>>Pat >> >> >>You need about 800 random 64 bit values with maximized hamming distance >>(different number of bits for each pair of 64 bit keys). According to my >>experiments you can do much better then 32 (Why the perfect key should change >>32? It should change as much as possible...). I managed to generate 800 keys >>with hamming distance of 40 (so each key pair differ in exactly 40 bits); 41 >>seem to hit some limits around 760 keys. >> >>-Andrew- > >That's impressive. I only managed to get a minimum hamming distance of 24. >Here is a distribution for my 832 keys that took about 5 minutes to generate >(min hamming distance of 23 only takes about 10 seconds): > >hamm 24, freq 9952 >hamm 25, freq 2012 >hamm 26, freq 22139 >hamm 27, freq 3847 >hamm 28, freq 38982 >hamm 29, freq 5924 >hamm 30, freq 53744 >hamm 31, freq 7191 >hamm 32, freq 60519 >hamm 33, freq 7070 >hamm 34, freq 52957 >hamm 35, freq 5635 >hamm 36, freq 37333 >hamm 37, freq 3468 >hamm 38, freq 20096 >hamm 39, freq 1654 >hamm 40, freq 8637 >hamm 41, freq 588 >hamm 42, freq 2837 >hamm 43, freq 187 >hamm 44, freq 717 >hamm 45, freq 48 >hamm 46, freq 131 >hamm 47, freq 6 >hamm 48, freq 19 >hamm 49, freq 1 >hamm 50, freq 1 >hamm 51, freq 1 >avg 31.9546 > >It just keeps generating keys randomly, and checks each new key against the >rest. If the hamming distance is too small, it throws it away, and generates >another one. I did think of also throwing away the key it clashed with, but I >havn't tried it. > >How did you manage to get a min hamming distance of 40? > >Cheers, Tim. Hmm. The hamming distance between x and ~x is 64, but that does not seem very random to me. I would think that a hamming distance of 54 would do no better than 10. Wouldn't a hamming distance closer to 32 be better? The average for random numbers is 32. An average of 40 indicates some type of bias. Yes? No? Maybe?
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.