Computer Chess Club Archives




Subject: Re: Hash Collisions (Bob Hyatt)

Author: Robert Hyatt

Date: 14:01:45 02/24/99

Go up one level in this thread

On February 24, 1999 at 15:09:52, Larry Griffiths wrote:

>On February 23, 1999 at 16:40:50, Robert Hyatt 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.  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?
>>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
>>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
>I can get away with leaving 16 out of the pawn random numbers and I have
>two pawn tables so 16 * 2 = 32.  So I could reduce this to 768-32 or 736?
>I also saw a post that your table is 1024 entries.  What are the other
>4 tables (256 entries) used for?
>Thanks for your reply.
>Larry   :-)

I think that was Don's post about 1024.  I have exactly 12 * 64 entries in
mine...  and yes you can safely leave those table entries 0 since they will
never be used anyway...

but don't forget you need to handle enpassant and castling privileges as well
for both sides...

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.