Author: Steffen Jakob
Date: 05:18:43 12/19/03
Go up one level in this thread
On December 19, 2003 at 08:11:51, Uri Blass wrote: >On December 19, 2003 at 08:06:28, Steffen Jakob wrote: > >>On December 19, 2003 at 05:45:00, Uri Blass wrote: >> >>>On December 19, 2003 at 02:27:17, Steffen Jakob wrote: >>> >>>>On December 19, 2003 at 01:24:27, Russell Reagan wrote: >>>> >>>>>On December 19, 2003 at 01:00:31, Steffen Jakob wrote: >>>>> >>>>>>I repeat my posting from below because the ruffian thread pushed it very fast to >>>>>>the bottom of the message list. :) >>>>>> >>>>>>What are you using for the hash key in your distributed perft implementation? >>>>>>How do you make sure that there are no hash key collisions which are possible in >>>>>>the usual zobrist key approach? Those collisions are too rare to influence the >>>>>>playing strength of a chess engine but would make the result of your perft >>>>>>project invalid. >>>>> >>>>>I remember Albert saying that he uses 128-bit hash keys, which is not >>>>>theoretically sound, but should work in practice. Deiter also uses hash tables >>>>>for this I think. Maybe he can tell us what he does. >>>> >>>>I like this distributed perft project very much (and contributed 4 solutions to >>>>subproblems ;-) but the only reason why we are doing this is to get the *exact* >>>>number of lines. Even if it is wrong by one line then the result is wrong and >>>>the whole effort was rather useless. Even if the result is correct then we >>>>cannot be sure about it. Therefore I would propose to run a validation without >>>>hash tables. Can it be estimated how long this would take? >>> >>>I do not see a reason not to use hash tables when it is possible to use hash >>>tables and be safe with 192 bytes. >> >>Can you tell me the likelihood that an error will occur because of an undetected >>hash key collision? If you can then you can say "perft(n) == x with a likelihood >>of p%". If you can´t then how can I trust a result from which I know that it >>might be incorrect? Why not make p=100 for the case of the hash table errors >>(e.g. by storing the complete board information in the hash entry [but not in >>the key])? >> >>Greetings, >>Steffen. > >192 bits are enough to get different hash key for different positions so there >is no problem with hash tables. If you use pseudo-random numbers for zobrist hashing it is always possible to get a collision. Yes, this is paranoid. :-) >The probability for hash collision with 128 bits is practically almost 0 and is >not the main problem but if you are afraid because of it then it is more logical >to hash all the board by 192 bits and not to avoid hash tables. I would rather use a 64 bit hash key which can be computed fast and if I get a hash key then I would compare the board position with the position information which is stored in the hashtable entry. I want to emphasize that I *don´t* think that e.g. in perft(11) happened a key collision. I also said before that I like this project very much. I only think it is important to provide a solution which doesn´t have known sources of errors especially if they can be avoided. Greetings, Steffen.
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.