Differences

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

--- chess:programming:zobrist_hashing [2021/10/30 21:23] – 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 127: / Line 161: @@
 <code cpp>
-piece*color*square * 8 + 3*8) bits;
+(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
+If a bit boundary is used, the array becomes:
 <code cpp>
-piece*color*square + 63) bits;
+(piece*color*square + 63) bits;
 </code>