Author: Heiner Marxen
Date: 12:19:29 06/30/00
Go up one level in this thread
On June 30, 2000 at 13:41:04, TEERAPONG TOVIRAT wrote: >Hi, > >For my curiosity I want to estimate the incidence of Zobrist type 1 >error (different positions having the same hash value). > >1. Could anyone tell me how many possible positions in chess? >The exact value is not so important but the estimated value should be >known. I don't have any idea to calculate it. >Let it =P. > >2.Let H= number of total hash values eg. for 64 bit hash table >H=2^64. > >3.Suppose the positions distribute evenly onto their corresponding >signature so that every hash value has almost the same number of >positions. The average number of positions sharing the same hash >value is = P/H. > >4.After the 1st position hits on the table,the chance that the next >position will have the same hash value(Zobrist type 1 error) >= (P/H-1)/(P-1). > >5.After the N th position hit on the table, the chance of Zobrist type 1 >error = N*(P/H-1)/(P-N). > >6.In chess hash table,I expect 1 is relatively much less than P/H >and N is much less than P. So, the equation in (5) = N*(P/H)/P >= N/H. > >7.Let's assume that after 1million positions are stored in the 32 bit >hash table then the chance of type 1 error = 1million/2^32 (from (6)) >approximately = 1/4200 which is unacceptably high. That 's why >every one recommends 64 bit hash table instead. In case of 64 bits >the chance = 1million/2^64 which is about one in 16 million million. > >8.Conclusion: There are 3 factors affecting the incidence of Zobrist >type 1 error 1.N (number of entry occupied) 2. H(number of hash value)) >3. the number of positions of any hash value(P/H). > >Do you agree with my hypothesis??? Being ment as approximations your calculations look good to me. The influence of 3. P/H is unclear for me, except that H << P (i.e. H is much smaller than P). If P/H would not be much larger than 1 we would not need a hash function, at all: we would just use the key itself. >Thanks for any comments >Teerapong Heiner
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.