Author: Dan Homan
Date: 06:14:20 09/16/99
Go up one level in this thread
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
(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.