Computer Chess Club Archives




Subject: Re: Hash Collisions (Dan)

Author: Larry Griffiths

Date: 15:33:19 02/24/99

Go up one level in this thread

On February 24, 1999 at 18:19:23, Dan Newman wrote:

>On February 24, 1999 at 08:18:34, Larry Griffiths wrote:
>>On February 23, 1999 at 15:23:14, Dan Newman wrote:
>>>On February 23, 1999 at 14:43:29, Larry Griffiths wrote:
>>>>On February 23, 1999 at 14:33:03, Larry Griffiths wrote:
>>>>>I read your post on hash collisions.  I have tried some hamming distance
>>>>>code and I see little difference when compared to generating random
>>>>>numbers.  I have been thinking of writing code that does what you said
>>>>>where 64 bits must have 32 bits (or 50%) turned on in each number.  I also see
>>>>>where there are many references to the 12 pieces times 64 squares = 768
>>>>>hash codes.   Pawns only use 48 squares for each side, so 32 squares are unused by pawns.
>>>>Forget my reference to the Bishops.
>>>>>768-48 leaves 720 hashcodes for the piece square table.
>>>>>Food for thought?  Errors in my thinking?
>>>That's interesting.  You can generate a smaller set of random numbers and
>>>fill out only those portions of the table that are actually used.  And a
>>>smaller set can be better optimized in the same period of time. (Currently,
>>>IIRC, I use 1024 numbers for the piece-square part since I use Bob Hyatt's
>>>numbering scheme for pieces: P=1,N=2,K=3,B=5,R=6,Q=7 -- which is quite
>>>nice for distiguishing sliders from non-sliders.)
>>I actually only use a power of 2 for my hash keys.  If my hash table is
>>262144 entries, then I only use 18 bits for a hash key.  I currently store
>>a 64 bit bitboard in the hash entry for collision checking.  I did create
>>some code to choose numbers that have exactly 9 bits on with equal distances
>>between the numbers.  I ran 6 ply test using these keys but it did not seem
>>to make much difference.  I did try small number of bits and large number of
>>bits also.  I have a graph in my program to display the hash table usage.
>>I saw bands (16 of them) occur when using very few bits per number or
>>very many bits per number.  I think this is caused by the 16 pawn moves that
>>can be made on the very first ply but I am not sure of this.  I have "holes"
>>in my hash table that only get used after several moves by each side.
>I've been playing around with trying to get a better set of numbers
>(from the point of view of reducing hashing errors rather than filling
>in the holes).  But so far I've only managed to increase the error
>rate :).  (I went from about 1 error per second to 20/s using 32-bit
>hashcodes when I tried to generate a good set of numbers with exactly
>16 one bits.  I'm beginning to think that that wasn't such a great
>idea.)  I also tried Bob's idea of adding in ~N for every N (I put them
>right next to each other in my table) and got no change in error rate
>for a very short test.  This is also contrary to my expectations...
>but I need to do some more extensive tests.


I even took the rabbit trail down to using prime numbers and hamming distances
between numbers.  I am thinking that the 16 bands that I saw in my graph were
really blacks 16 pieces moving at the 1st ply. I guess I need to fire up that
code again and capture a black piece.  If 15 bands show up then I've hit the
nail on the head.


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