Pawn Hash Table

From Chessprogramming wiki
Jump to: navigation, search

Home * Evaluation * Pawn Structure * Pawn Hash Table

Pawns threaten the King [1]

A Pawn Hash Table is often used inside a chess programs to cache purely pawn related pattern and evaluation stuff. Compared to the main transposition table, since the pawn structure inside the search changes rarely or transpose, the number of cached entries required might be quite low (a few K) to get a sufficient hit rate above 95% or even 99% for most positions, specially if the pawn structure is settled or relatively fixed after the opening. On the other hand, most programmers store not only pure aggregated pawn evaluation scores, but other computation expensive pawn structure stuff which is used in second pass evaluation considering pieces and king. Terms for various game phases and king origins for all possible wings/center per side are often calculated speculatively, i.e. pawn shield or pawn storm stuff later used by king safety.

While the content of the pawn hash table entry varies a lot between different chess programs and their implementation, it is not uncommon that one entry exceeds 1/2 K-Byte. Some programs store sets or bitboards of strong pawns (passers, candidates), square of most advanced passer, different kind of weak pawn sets and whatever else. Despite, some programs cache pawn-king stuff separately which requires king squares included inside the index calculation as well table entry for verifications.

Pawn Hash Index

Most simple, common and recommend is to keep an incremental updated, dedicated Zobrist- or BCH-keys similar to the main transposition table, initialized from all squares occupied by pawns only, side to move does not matter. The update of that key is therefor only necessary for the relative rare pawn moves or captures with pawns as aggressor or victim. The hash table index is computed by key modulo number of entries, which might be a cheap and-instruction from the key for power of two sized tables.

Alternatively, considering hits from the transposition table, or a dedicated evaluation hash table, one may use a fast hash function to compute an index from the white and black pawn bitboards on the fly, i.e. either a modulo or a multiplication and shift à la magic bitboards by the difference of the disjoint pawn sets [2] . To verify correct entries while probing, one needs either to store (a part) of the dedicated Zobrist/BCH key, or for 100% correctness 2*48 bits from the pawn occupancy bitboards. This value could be further compressed with the expense of more calculation overhead by means of n-like men:

PawnHashFormla.jpg

This can be further reduced by mirroring the board, considering symmetric positions or detecting illegal positions.

See also

Forum Posts

1999

2000 ...

2005 ...

2010 ...

2015 ...

External Links

References

Up one level