Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash Collisions (Dan)

Author: Robert Hyatt

Date: 13:40:50 02/23/99

Go up one level in this thread


On February 23, 1999 at 14:33:03, Larry Griffiths wrote:

>Dan,
>
>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.  Since the a Bishop can only control 32 possible squares and
>there are 4 bishops, then 128 of the 768 are unused.  Also, Pawns only
>use 48 squares for each side, so 32 squares are unused by pawns.
>768-128-48 leaves 592 hashcodes for the piece square table.
>Food for thought?  Errors in my thinking?
>
>Larry.


A couple.  First there are 12 _types_ of pieces.  And since each side has
two bishops on opposite colors, all 64 random numbers are needed for the
bishops.

you can get away with leaving 16 out of the pawn random numbers since none
exist on the 1st/8th rank.  There are not 4 sets of 64 numbers for the 4
bishops.  There are two sets of 64, one for black bishops, one for white
bishops.  Because the bishops are not 'unique' and are interchangable.  In
fact, after promoting to a B, that B is identical to the B that existed early
in the game on the same color square.

So you _could_ reduce this to 752 numbers... but then you need a few more
for things like castling status, enpassant status, so you take those back
again.



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.