Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hashing in distributed perft

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.