Computer Chess Club Archives




Subject: Re: Hash Collisions (Bob Hyatt)

Author: Robert Hyatt

Date: 15:50:03 02/24/99

Go up one level in this thread

On February 24, 1999 at 18:06:48, Dan Newman wrote:

>On February 24, 1999 at 17:01:45, Robert Hyatt wrote:
>>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...
>I think I may have been the source of that bit of disinformation.  I use
>your piece numbering scheme in my 0x88 program (p=1,n=2,k=3,b=5,r=6,q=7)
>and use piece number to index my table of random numbers...

could be.  Because of the bitmap stuff, I have a separate block of code
for each piece type, when making moves.  So I only need 12 64-word arrays
of random values....  the 'holes' I don't have to deal with.

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

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