Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash Collisions

Author: Don Dailey

Date: 15:42:21 02/22/99

Go up one level in this thread


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

>I ran some quick tests... to produce a minimum distance of 16, producing
>768 random numbers (64 bits), takes 769 numbers from my Random64() function
>in crafty.

I get pretty much the same results.  Starting at about 15 bits, you
start getting the occasional retry.  I think I get 1 retry with 15
bits and maybe 2 with 16 bits.  I am of course generating a slightly
bigger table.

To go to 24 jumps this to a really big number (it took my code
>200 million random numbers to find 768 with a hamming distance >= 24 between
>_all_ of them.

But this is not consistant with my result, getting 32 bits in less
tries.   Are you sure it's not 200,000?    I'll recheck my code and
make sure I'm counting right.  I haven't done much to test or debug
the hamming code so maybe that is the problem.

>One minor trick is that in general, if N is a good number, ~N is also good.
>
>I've been trying to find my notes on CB... but now think that maybe '32' was
>an 'average' number rather than the abs minimum for all the numbers.
>
>If I had some time, I'd try to study just what the 'optimal' set would be,
>because it must be computable...
>
>
>
>>I'll try to figure out a way to post my values here if you are interested.
>>64 * 12 isn't horribly big, but when you display them as 64 bit values, they
>>are big. The main issue is how to initialize such an array in a portable
>>way...  IE (BITBOARD ran[12][64] = {{1,2,3},{4,5,6}};  The numbers 1,2,3
>>default to 'int' which is bad.  I don't know what to do for all compilers
>>(IE 123ULL or (BITBOARD) 123)



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