Chess - Programming - Pawn Hash Table
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 eventually 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 verification.
Pawn Hash Index
Most simple, common and recommended 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 therefore 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 a la magic bitboards by the difference of the disjoint pawn sets.
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.
A sharper bound on the number of Pawn constellations than 3^48 (which also counts cases like having 48 black Pawns) is 2^64.
(3^48 = (1.5*2)^48 = 1.5^48 * 2^48 = 2.25^24 * 2^48 > 2^24 * 2^48 = 2^72.)
You need 48 bits to indicate Pawn occupation of the 48 Pawn-accessible squares, and that an additional 16 bits are then enough to flag which of the 16 Pawns that can maximally be in there are black.
An even more accurate estimate, which takes account of the fact that you can have at most 8 white and 8 black Pawns, is 2^55.
For exactly 16 Pawns it is 2^54.68 (= 48!/(16!*32!) * 16!/(8!*8!)), but the number decreases very fast when there are fewer Pawns.)
This still does not take account of the fact that most of the Pawn constellations would be unreachable from the initial position.
This can be further reduced by mirroring the board, considering symmetric positions or detecting illegal positions.
Potential Pawn Hash Table
mod(49981), which is an appropriate size for a pawn hash table:
unsigned int mod49981 (unsigned __int64 a)
{
// (2**64 + 49981 - 1) / 49981
// is not exact divisible without remainder
// 369075130023601.0003001140433 ~ 0x14FAC00053EB1
unsigned __int64 m = (0x00014FAC00053EB1 * (a >> 32)
+ 0x00014FAC * (a & 0xffffffff));
int modulus = (int)(a - (__int64)(m>>32)* 49981);
if ( modulus < 0 ) // correct negative results
modulus += 49981; // due to the remainder of 0.0003
return (unsigned int) modulus;
}
Information to store include:
Without king positions in pseudo-C
hash_t RandomIndex[64][2]; // Initialize by Pseudo random numbers.
PawnHashIndex = 0;
for (pos = A1; pos <= H8; pos++)
if (figure[pos] == pawn)
PawnHashIndex ^= RandomIndex[pos][color[pos]];
Probably do not do this after every move.
If you move a pawn , you can update the PawnHashIndex by
// Update the pawn hash for "normal" pawn move.
PawnHashIndex ^= RandomIndex[from][side]; // Clear the old pawn position.
PawnHashIndex ^= RandomIndex[to][side]; // Put in the new pawn position.
Similar code is needed for captures of a pawn and pawn promotions.