Author: TEERAPONG TOVIRAT
Date: 10:41:04 06/30/00
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??? Thanks for any comments Teerapong
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.