Differences

This shows you the differences between two versions of the page.

--- chess:programming:zobrist_hashing [2021/10/12 11:04] – peter
+++ chess:programming:zobrist_hashing [2021/10/30 21:41] (current) – [Implementation Consideration] peter
@@ Line 1: / Line 1: @@
 ====== Chess - Programming - Zobrist Hashing ======
-**Zobrist Hashing** is 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.
+**Zobrist Hashing** is a hashing function that is widely used in 2 player board games.
   * 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.
+  * It is the most common hashing function used in transposition tables; and sometimes opening books.
+  * Transposition tables basically store the evaluated values of previous board states, so that if they are encountered again we simply retrieve the stored value from the transposition table.
+  * These index numbers are used for faster and more space efficient Hash tables or databases.
+----
+[[Chess:Programming:Zobrist Hashing:A program to illustrate the Zobrist Hashing Algorithm|A program to illustrate the Zobrist Hashing Algorithm]]
+----
+===== Pseudocode =====
+<code>
+// A matrix with random numbers initialized once.
+Table[#ofBoardCells][#ofPieces]
+// Returns Zobrist hash function for current configuration of board.
+function findhash(board):
+  hash = 0
+  for each cell on the board :
+    if cell is not empty :
+      piece = board[cell]
+      hash ^= table[cell][piece]
+  return hash
+</code>
+<WRAP info>
+**NOTE:**  Explanation :
+  * The idea behind Zobrist Hashing is that for a given board state, if there is a piece on a given cell, we use the random number of that piece from the corresponding cell in the table.
+  * If more bits are there in the random number the lesser chance of a hash collision.
+  * Therefore 64 bit numbers are commonly used as the standard and it is highly unlikely for a hash collision to occur with such large numbers.
+  * The table has to be initialized only once during the programs execution.
+  * Also the reason why Zobrist Hashing is widely used in board games is because when a player makes a move, it is not necessary to recalculate the hash value from scratch.
+  * Due to the nature of XOR operation we can simply use few XOR operations to recalculate the hash value.
+</WRAP>
 ----
@@ Line 64: / Line 102: @@
   * A collision occurs if two positions map the same key.
-  * Usually 64bit are used as a standard size in modern chess programs.
+  * Usually 64 bit is used as a standard size in modern chess programs.
 ----
-==== Collisions ====
+===== Collisions =====
 Using too small a hash code, such as only 32 bits, may result in different positions being assigned the same hash code.
@@ Line 86: / Line 124: @@
     * No, there is not a "modulus" mechanism for vector loads to make this load "wrap around" to the beginning.
+Remember that a table entry contains a "key", score, score type, best move, etc.
+  * This key must EXACTLY match the hash key before we consider this a "hit".
+  * This means that the 64 bit hash key must match completely, even though we only used the low order "n" bits of this key to probe into the table.
+  * In fact, since we used the low order "n" bits to prob into the table, we do not even bother storing them since we "know" what they were already (which saves table space.)
+<WRAP info>
+**NOTE:**  It is highly recommended to use 64-bit keys to not have to deal with collisions.
+  * A value of 48 bits has shown to be just as safe as 64, but 48 is not a reasonable size as 64 bit signatures are the natural signature length for 64 bit processors.
+</WRAP>
+----
+===== Implementation Consideration =====
+<code cpp>
+UINT64 getZoristKey(int piece, int color, int square)
+{
+  int index = piece*color*square;
+  const char *p = ((char *)zorbrist) + index
+  return *(UNIT64 *) p;
+}
+</code>
+This means that the array does not need:
+<code cpp>
+(piece*color*square * 64) bits;
+</code>
+  * The original and well-known implementation.
+but only
+<code cpp>
+(piece*color*square * 8 + 3*8) bits;
+</code>
+  * This will reduce array of about 8th in size.
+If a bit boundary is used, the array becomes:
+<code cpp>
+(piece*color*square + 63) bits;
+</code>
+To use this:  The index to the 64-bit value that is being searched for becomes an index to the first bit of the 64-bits needed.
+  * This gives the shortest possible array.
+  * The access would be 64 + 8 bits; and then shift the results according to the bit index.
+  * An easiest way is to use a byte boundary.
+----
+===== References =====
+http://web.archive.org/web/20111202160335/http://www.cis.uab.edu/hyatt/collisions.html