chess:programming:hash_functions
Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| chess:programming:hash_functions [2021/10/12 10:48] – peter | chess:programming:hash_functions [2022/01/06 21:55] (current) – peter | ||
|---|---|---|---|
| Line 5: | Line 5: | ||
| Common Hash Functions are: | Common Hash Functions are: | ||
| - | * [[Chess: | + | * [[Chess: |
| - | * [[Chess: | + | * [[Chess: |
| <WRAP info> | <WRAP info> | ||
| Line 17: | Line 17: | ||
| ---- | ---- | ||
| - | ===== Zobrist Hashing | + | ===== References |
| - | + | ||
| - | A technique to transform a board position of arbitrary size into a number of a set length, with an equal distribution over all possible numbers. | + | |
| - | + | ||
| - | The main purpose of Zobrist hash codes in chess programming is to get an almost unique index number for any chess position, with a very important requirement that two similar positions generate entirely different indices. | + | |
| - | + | ||
| - | These index numbers are used for faster and more space efficient Hash tables or databases, e.g. transposition tables and opening books. | + | |
| - | + | ||
| - | ==== Initialization ==== | + | |
| - | + | ||
| - | At program initialization, | + | |
| - | + | ||
| - | * One number for each piece at each square. | + | |
| - | * One number to indicate the side to move is black. | + | |
| - | * Four numbers to indicate the castling rights, though usually 16 (2^4) are used for speed. | + | |
| - | * Eight numbers to indicate the file of a valid En Passant square, if any. | + | |
| - | + | ||
| - | This results in an array with 781 (12*64 + 1 + 4 + 8) random numbers. | + | |
| - | + | ||
| - | * Since pawns do not occur on first and eighth rank, one might be fine with 12*64 though. | + | |
| - | * 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. | + | |
| - | + | ||
| - | Programs usually implement their own Pseudorandom number generator (PRNG), both for better quality random numbers than standard library functions, and also for reproducibility. | + | |
| - | + | ||
| - | * This means that whatever platform the program is run on, it will use the exact same set of Zobrist keys. | + | |
| - | * 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 endianess. | + | |
| - | + | ||
| - | ---- | + | |
| + | https:// | ||
chess/programming/hash_functions.1634035682.txt.gz · Last modified: 2021/10/12 10:48 by peter