Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash Collisions

Author: Robert Hyatt

Date: 18:57:24 02/22/99

Go up one level in this thread


On February 22, 1999 at 19:53:14, Peter McKenzie wrote:

>On February 22, 1999 at 18:42:21, Don Dailey wrote:
>
>>>>However, I don't have that many numbers (1024 you said?) as I only used 12*64
>>>>since we didn't use any sort of 'boundary squares' in cray blitz.  Ditto for
>>>>Crafty where I also use 12*64.  I have been meaning to go grab that table of
>>>>numbers and 'steal' it for crafty, but I haven't yet, because it is in the
>>>>syntax of 'fortran'.
>>
>>>>>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.
>>>>
>>>>I use the Numerical Recipes RNG code.  But you are right, it won't produce
>>>>such good hamming distances quickly.  I wouldn't be surprised if it takes
>>>>4 billion numbers to get decent random numbers...
>>
>>
>>Hi Bob,
>>
>>I just generated a 1024 entry table with hamming distances at least
>>32 bits between any two.  It took about 134 million random number
>>calls.
><snip>
>
>OK, so the $64 question is: will using this table cause any measurable
>improvement in your program?
>
>For example, will your node count drop if you do a fixed depth search on a test
>suite?
>
>cheers,
>Peter


No..but you should get fewer undetected hash signature collisions...  Whether
that will affect scores/moves at the root for any position is a good question.
Without a good answer, at present..



This page took 0.01 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.