Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash Collisions

Author: Don Dailey

Date: 10:00:18 02/23/99

Go up one level in this thread


On February 22, 1999 at 21:57:24, Robert Hyatt wrote:

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

I would guess that using the "better" numbers will decrease the number of
collisions.  I don't know if the improvement is enough to actually
measure (Hey, the program is player stronger now!) but it is an improvement
that comes at no cost and as such should be hard coded into the program.

A good program will have a large number of little improvements like this
one.  Get 10 or 20 things like this together and they start adding up.
You can easily live without any particular one, but not all of them
together.

- Don








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.