Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Chess - Programming - Evaluation Hash Table ======

An Evaluation Hash Table may be used in a similar fashion as a transposition table, that is using Zobrist or BCH hashing, to cache various computational expensive positional evaluation scores and flags.

  * 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.

----