Differences

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

--- chess:programming:evaluation_hash_table [2021/10/12 12:22] – created peter
+++ chess:programming:evaluation_hash_table [2022/01/06 21:46] (current) – peter
@@ Line 4: / Line 4: @@
   * Despite the fact that the transposition table entries may contain evaluation scores as well, a tighter, dedicated evaluation hash table with its own replacement policy may gain a considerable amount of additional hits.
+----
+Implement a simple evaluation hash table that keeps track of passed evaluations so if the same position occurs again that work does not have to be repeated.
+----
+What sizes should these have?
+  * The UCI protocol comes with a command where the hash size can be set.
+----
+===== Pawn Hash Table =====
+Since the pawn structure changes very rarely it should be a nice boost as long as it gets implemented smoothly.
+Needs to store information about passed pawns so we do not have to find them every time.
+The zobrist key for the pawns will have to be updated every time a pawn is moved, and also the current pawn evaluation uses the king positions as well.
+----
+===== Collisions =====
+Collision = two positions that are not the same having the same hash signature.
+<WRAP info>
+**NOTE:** An assumption is that the hash table is full of entries that do not match the position being searched.
+Factors used:
+  * P = Probability of a collision on a given table lookup.
+  * T = Total number of table entries.
+  * p = Probability of two positions having the same hash signature (= 1/2^n , with n = number of bits in hash).
+  * N = Nodes searched per second (assume one table lookup at each node).
+  * R = Rate of collisions.
+</WRAP>
+Calculate the collision rate.
+<code>
+P = 1 - (1-p)^T
+</code>
+<WRAP info>
+**NOTE:**  This is just 1 minus the probability of no collision.
+</WRAP>
+The rate R of collisions is:
+<code>
+R = NP
+</code>
+<WRAP info>  A standard hash table setup example:
+For a 256K entry table, 32 bit hash code, 30K nodes/sec (i.e.  T = 256000, n = 32, N = 100000/sec.)
+  * R = 6 collisions/sec
+    * for a 48 bit hash code: R ~ 1E-4 collisions/sec
+    * for a 64 bit hash code: R ~ 1E-9 collisions/sec
+</WRAP>
+----
+Could a 24-bit Hash be sufficient for a Pawn Hash Table?
+If 24 bits are used for the hash signature, a rather high collision rate would be expected on Pawn table lookups (a few per second).
+  * The assumption is that entries that do not match the position being searched may break down.... so the collision rate might be less...
+  * With a 24 bit key about 1/128 times less collisions are expected, so you would get a pawn hash collision in about 1 of every 10,000 positions evaluated using a 24 bit key.
+So, no, more bits would be needed.
+Pawns make up about half the pieces on the board, and a little less than half the information content (because there are 2 sorts of pawns and 10 sorts of other pieces), so a guess is that about 24 to 30 bits for the pawns is the right proportion.
+----