Author: Heiner Marxen
Date: 17:20:26 07/01/00
Go up one level in this thread
On July 01, 2000 at 01:35:36, TEERAPONG TOVIRAT wrote: >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. Yes, I did read this. Everything ok here. >>>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. Now look at this: P is cancelled out (for the approximation). We are left with N and H as influence for the probability of an error. >>>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. Yes, sure, you are right, and I think I do understand it quite well. I just wanted to say, that the resulting approximate formula for the error probability depends on N and H, and not on P (IMO). As long as H << P, it is not important how much larger P actually is. Heiner >>(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.