Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: regular hash key & pawn hash key together--good idea?

Author: Dan Homan

Date: 06:20:05 09/16/99

Go up one level in this thread


On September 16, 1999 at 09:14:20, Dan Homan wrote:

>On September 16, 1999 at 04:00:43, Tom Kerrigan wrote:
>
>>If you have a program with 64 bit hash keys, is it a good idea to devote n bits
>>to pawns and the rest to pieces and side-to-move?
>>
>>I was thinking a good balance may be 24 bits for pawns, but I have no data to
>>back this up. Does anybody else?
>>
>>-Tom
>
>Very interesting idea!
>
>We can calculate the collision rate and see if it would work.  Here
>is a calculation I posted here a year or so ago.... I've adapted it
>at the end to fit this situation.
>
>Collision = two positions that are not the same having the same
>             hash signature
>
>P = probability of a collision on a given table lookup
>T = total number of table entries
>p = probability of two positions having the same hash
>    signature ( = 1/2^n , with n = number of bits in hash)
>N = nodes searched per second (assume one table lookup at each node)
>R = rate of collisions
>
>So
>
>P = 1 - (1-p)^T  (This is just 1 minus the probablity of no collision,
>                  and I have assumed that the hash table is full of
>                  entries that don't match the position being searched)
>
>The rate R of collisions is then given by....
>
>R = NP
>
>for a 256K entry table, 32 bit hash code, 30K nodes / sec

Oops,  I meant to change the above line to 100K nodes/sec, as it is in the
calculation below...

>(i.e.  T = 256000, n = 32, N = 100000/sec )
>
>R = 6 collisions/sec
>
>for a 48 bit hash code: R ~ 1E-4 collisions/sec
>for a 64 bit hash code: R ~ 1E-9 collisions/sec
>
>
>So far this is just a standard hash table setup.
>
>So, if we used 24 bits for the hash signature, we expect rather high
>collision rate on pawn table lookups (a few per second), but the
>assumption of entries that don't match the position being searched may
>break down.... so the collision rate might be less...
>
>Experimentally, I get about 2% misses in my pawn hashing when I have
>a table with 130K entries (17 bit addressing), so with only a 17 bit key
>we would get about 2% collisions in typical positions.  With a 24 bit
>key we expect about 1/128 times less collisions, so you would get a
>pawn hash collision in about 1 of every 10,000 positions evaluated using
>a 24 bit key.
>
>The 40 bits for the rest of the position is better than it seems at first
>because you can also use the 24 bits from the pawn structure to help
>avoid collisions.  The analysis of this is harder.  If we assume that
>positions that can collide are at least several moves apart, then it
>is reasonable to assume that both pieces and pawns have moved.  This
>case simply reduces to the 64 bit case, which provides quite good
>protection against collision.  In the cases where you have few/fixed
>pawns on the board, the protection against collision is worse - at
>worst it is the 40 bit case.
>
> - Dan



This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.