Implementation of pawn hash table

[OliveriQ]

Could someone point out any issues in my implementation of pawns hash table? I couldn't really find any resources on it so I really just came up with it myself and did something similar to a transposition table, where I only hash the pawns and the side to move. Then in the evaluation function, if there is no entry that matches the current pawn hash key of the position, I perform the pawns evaluation and then store them in the hash table. And of course if there is an entry I simply retrieve the evaluation scores. The source files can be found here https://github.com/OliveriQ/Horowitz/tree/dev/src. The implementation is in pawns.h and pawns.cpp, and the evaluation function is in evaluate.h. I appreciate any advice.

[dangi12012]

The Discs of Tzeentch are large, sentient creatures that were transformed from an ordinary Screamer into large, disc-like shapes to better suit the Sorcerers who bind them into swift mounts. They float in the clouds of swirling energy that makes up the Realm of Chaos, drifting through the Aethyr, feasting on lower Daemons and the souls of the damned.



The question at hand:
"Could someone point out any issues in my implementation of pawns hash table".

Well are you experiencing some issues? It looks good from a coding perspective. Except that you should put the color into a template parameter since you have it at compiletime in eval too. So if it increases strength and is not buggy then there are no issues.

Also this is expensive in your code:

Code: Select all

entries[hashKey % hashTableEntries];

So I strongly recommend making hashTableEntries constexpr. If you can tell the compiler that hashTableEntries is a power of two then
MOD = x & (pow2 - 1)
You could also do it by hand

Code: Select all

entries[hashKey & 16777215]

There are not too many pawn structures per color to begin with: NCR(48,8) = 377348994
So with a magic hash and around 4E8 slots (memory mapped file) you could store everything there is to know about pawns before runtime.

[dangi12012]

What I meant above:
A single uin64_t *magic* that satisfies this condition without overlap and not too much overhead:

uint64_t wpawn = white & pawn;
PawnInformation info = PawnMap[(wpawn * magic) >> 35];

In that information you could store anything you want to. Count of Pawns, Aggregate Zobrist, Piece Square Value, etc..
Since pawns can only exist in 48/64 squares that is possible to do for 0 up to including 8.

That moves you hashing idea from runtime into compiletime.

The same idea can be used to store kings in 11 bits (not 12 like usually) because lb(ncr(64,2)) == 10.9
Even less than that since many of those positions are not legal.

[hgm]

The key has to depend on the location of both the white and the black pawns, right? Your code seems to ignore the black pawns.

I also don't understand your King trick. You can encode the location of 2 kings in 11 bit alright, but you would not know which is the white one.

[dangi12012]

The key has to depend on the location of both the white and the black pawns, right? Your code seems to ignore the black pawns.

I also don't understand your King trick. You can encode the location of 2 kings in 11 bit alright, but you would not know which is the white one.

All the information for up to 8 pawns can be stored - the aggregate zobrist (per color) - the aggregate piece square value and so on. So the color is there too because you know which color you are looking up currently and you have two members per slot and information item - and you can select the right member.


The king trick there is to decompress the *nth permutation* into the king bitboard. This its the same as normal Bitboards where the 64bits are the occupancy of a piece. The color is stored in another bitboard.
You are correct its a 64bit compression by converting into the nth permutation - so its not really the same as two 6 bit numbers.
Its a way to compress 64 bits into less bits just by knowing the maximum number of set bits.

[hgm]

Pawn hash is not used for storing PST scores; this would be pointless, because those can be incorporated for free in the total incremental evalution. It serves for storing terms that require complex calculation. Such as which pawns are passers, and how much bonus you get for their current advance. None of which you can calculate without knowing where the opponent pawns are.