8/11/2023 0 Comments Enpass in chessAnother, which p4wn used at one stage, is to use 47 or 48 bit additive hashes. One way to get a 64 bit hash is to use two 32 bit numbers in parallel, as Garbochess-JS does. In JavaScript, this type breaks down into a 32 bit integer when bitwise operators are used. Some languages (such as JavaScript and Lua) only have a 64-bit floating point "Number" type. All randomly generated numbers are not the same! With this better seed, it became very, very rare to see a hash error. I changed my seed to another number and the error rate dropped dramatically. To my surprise, there were lots of errors. A few years later I put code in to detect when my 32-bit hash key matched the wrong position. In the early versions of my chess program Phoenix, I generated my Zobrist hash numbers using my student id number as a seed, naively thinking the random numbers generated by this seed would be good enough. With a 64 bit hash, you can expect a collision after about 2 ^ 32 or 4 billion positions. You can expect to encounter a collision in a 32 bit hash when you have evaluated sqrt(2 ^ 32) = 2 ^ 16 or around 65 thousand positions. Hash collisions demonstrate the birthday "paradox", which is to say the chance of collisions approaches certainty at around the square root of the number of possible keys, contrary to some people's expectations. Usually 64bit are used as a standard size in modern chess programs. The dangers of which were well assessed by Robert Hyatt and Anthony Cozzie in their paper Hash Collisions Effect. A collision occurs if two positions map the same key. Smaller hash keys are faster and more space efficient, while larger ones reduce the risk of a hash collision. Key collisions or type-1 errors are inherent in using Zobrist keys with far less bits than required to encode all reachable chess positions.Īn important issue is the question of what size the hash keys should have. xor ( placing the knight on the new square ) xor ( removing the captured bishop from c3 ) E.g., for a White Knight that jumps from b1 to c3 capturing a Black Bishop, these operations are performed: It allows a fast incremental update of the hash key during make or unmake moves. The fact that xor-operation is own inverse and can be undone by using the same xor-operation again, is often used by chess engines. If we now want to get the Zobrist hash code of a certain position, we initialize the hash key by xoring all random numbers linked to the given feature, e.g. This is also useful for things like opening books, where the positions in the book can be stored by hash key and be used portably across machines, considering endianness. This means that whatever platform the program is run on, it will use the exact same set of Zobrist keys. Programs usually implement their own Pseudorandom number generator (PRNG), both for better quality random numbers than standard library functions, and also for reproducibility. There are even proposals and implementations to use overlapping keys from unaligned access up to an array of only 12 numbers for every piece and to rotate that number by square. Since pawns don't happen on first and eighth rank, one might be fine with 12*64 though. This leaves us with an array with 781 (12*64 + 1 + 4 + 8) random numbers.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |