Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hashing in distributed perft

Author: Uri Blass

Date: 07:20:14 12/19/03

Go up one level in this thread


On December 19, 2003 at 10:04:48, Steffen Jakob wrote:

>On December 19, 2003 at 09:31:33, Uri Blass wrote:
>
>>On December 19, 2003 at 09:03:15, Steffen Jakob wrote:
>>
>>>On December 19, 2003 at 08:29:00, Uri Blass wrote:
>>>
>>>>>>If you use pseudo-random numbers for zobrist hashing it is always possible to
>>>>>>get a collision. Yes, this is paranoid. :-)
>>>>>
>>>>>No need to use pseudo random numbers.
>>>>>
>>>>>It is possible to store all the board with 192 bits easily as was explained in
>>>>>another post.
>>>>>
>>>>>Uri
>>>>
>>>>Here is the relevant post.
>>>
>>>This encoding is not appropriate for being used as a hash key. You have these
>>>192 bits. To get the index into the hash table you filter some of those bits.
>>>With the encoding of the posting which you mentioned it is very likely that a
>>>lot of similar positions are mapped to the same index. Therefore you will not
>>>use the hash table in an efficient way. It will be efficient with zobrist
>>>hashing.
>
>>
>>When looking again at that post I agree that it does not give side to move and
>>castling in the 192 bits but I think that it is not hard to change it to do it.
>>
>>12 bits for the squares of the kings
>>62 bits to give the empty squares of other pieces.
>>
>>The rest of the squares are at most 15 white pieces and 15 black pieces and you
>>can give 30 bits for side of the rest of the squares and every 3 squares now
>>have 5^3<2^7 options so you can use 7 bits for every 3 non empty squares or 70
>>more bits.
>>
>>Now you have:12+62+30+70=184 bits.
>>
>>side to move castling right and en passent can be easily stored in 8 bits.
>>
>>side to move is 1 bit
>>castling rights is 4 bits
>>enpassent right is 3 bits because 000 means no enpassent capture is possible
>>001 means that the first suspected pawn can be captured by enpassent rule and it
>>is impossible to have 8 pawns that we suspect them because if white has 8 pawns
>>in a4 b4,c4,...h4 it is obvious that enpassent capture is impossible.
>
>Is this a reply to my last posting? Did you read it? :-)
>
>Greetings,
>Steffen.

I read it and I understand now that you claim that the problem is not wrong
result but lack of efficiency and the problem is how to compress the 192 bits to
something that will usually avoid the problem when often the last n bits are the
same(assuming hash size of 2^n entries).

Uri



This page took 0.1 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.