Author: Paul Byrne
Date: 22:17:24 12/19/03
Go up one level in this thread
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. >> >>Greetings, >>Steffen. > >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. > >Uri If you use 64 bits to say which squares are occupied, you get 4 bits per piece to describe each piece. Since there are only 12 pieces, you can use up the extras for side, castling, and enpassant. Have special pieces called king-whose-side-is-to-move, rook-which-can-castle, and pawn-which-can-be-captured-ep -- not necessary to give the colors here, which can be deduced from the location or the color of the other king. In practice, I also compute a standard zorbrist key, and use *that* to get the index into the hash table. I also keep the high 32 bits of the zorbrist key in the table, which helps lookup speed considerably, as you only have to calculate and compare the full 192 bit position if the 32 bits match up. Not sure how helpful this last bit would be for a real hash table -- as you'd need to compute the 192 bits to add a position -- but for something like learning, there are an awful lot more lookups than adds. -paul
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.