Author: Carmelo Calzerano
Date: 02:37:41 02/08/01
Go up one level in this thread
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. 800 64-bit keys, with each pair having _exactly_ 40 hamming distance?! I really would like to see those numbers... :-) Anyway, what you mean when you say that 40 is "much better" than 32? I don't know it for sure, but 32 looks to me a "much better" (or at least much reasonable) estimate of the optimal hamming distance for hashing pourposes: too big hamming distances should bring to the same problems than too small, when XORing. Remember that the goal is to aproximate a sort of "linear independency" (regarding XOR operations) between the numbers, not just maximize the hamming distance: having an _average_ hamming distance of about 32, along with a _minimum_ hamming distance as big as possible (say 20, if possible; at least 16 anyway) is nothing more than an easy-to-check condition, and a reasonable estimate of the goodness of your random numbers. At least, that's my idea... :) Bye, Carmelo
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.