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.

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.

Collision = two positions that are not the same having the same hash signature.

Calculate the collision rate.

P = 1 - (1-p)^T

The rate R of collisions is:

R = NP

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.