Differences

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

--- chess:programming:zobrist_hashing [2021/10/12 11:15] – 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 98: / Line 136: @@
 </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.
 ----