Author: TEERAPONG TOVIRAT
Date: 22:35:36 06/30/00
Go up one level in this thread
On June 30, 2000 at 15:19:29, Heiner Marxen wrote: >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 Let me explain ,, like you have 1000 tennis balls and you have to throw them into 10 baskets I suppose that finally every baskets should have approximately 100 balls. >(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.