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.