Author: Don Dailey
Date: 23:30:37 02/21/99
Go up one level in this thread
On February 21, 1999 at 15:58:16, Robert Hyatt wrote: >On February 21, 1999 at 13:23:24, William Bryant wrote: > >>On February 21, 1999 at 10:21:50, Robert Hyatt wrote: >> >>>On February 21, 1999 at 01:14:37, KarinsDad wrote: >>> >>>>I posted this the other day, but it may have been obscured (or not if nobody has >>>>any information on it). >>>> >>>>I have been wondering if changing the Zobrist hash from a set of random number >>>>to a set of non-random and very specific numbers could result in a more even >>>>distribution in the hash table. Has anyone done any work in this area? >>>> >>>>KarinsDad >>> >>> >>>Burt Wendroff and Tony Warnock published a paper in the JICCA a few years >>>ago discussing this. The main issue is to find the hamming distances between >>>_all_ the random numbers, and maximize all of them. Random numbers work fine >>>if they have been tested (I ran all of mine thru a hamming distance analysis >>>when I first started). >>> >>>As far as 'distribution' this is done by the low order N bits >>>(N=log2(hash_size)) of the hash signature. You _could_ do the hamming analysis >>>on just those bits as well. >> >>I check all my random numbers for uniqueness, ie no duplicates,and use >>0xFFFFFFFFFFFFFFFF for the side to move (compliment the side to move), >>but would appreciate information on 'hamming distance analysis' in not to >>complicated to post or send via email. >> >>Thank you, >> >>William >>wbryant@ix.netcom.com > > >"hamming distance" is simply the number of bits two numbers differ in. To >compute the hamming distance for a and b, you just compute popcnt(a^b). Two >numbers can differ in all bits. But more than two can not... I shoot for >no worse than 32 bits that are the same in two random numbers... Assuming >64 bit values... Are you sure NO two are closer (in hamming distance) than 32 bits? How many numbers are in your table? Are you talking about the worst case or is it some kind of average? I have a little piece of code I wrote that generates 64 bit random numbers one at a time and tests each one against all the ones previously generated. If the new number is closer than my specified hamming distance, I regenerate that number until it is. To get even 24 bit distances between any two I've had to generate almost half a million numbers. I have 1024 numbers in my table. I don't believe your random number generator is returning numbers this good. Maybe you can precompute them this good, I don't know. I'm trying right now with 32 bits but it's going awfully slow. So my code is either wrong or I'm not understanding your method. Can you either clarify or send me your table to analyze? - Don - Don
This page took 0.02 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.