Pawn Hash

[hgm]

I decided to put a Pawn hash in my new engine, so that I can quickly hack in some passer recognition through a dumb algorithm, without having to worry about efficiency. I never used Pawn hash before. Does the following seem a reasonable implemetation:

I keep an extra 32-bit hash key, which uses the same randoms as the main hash key for Pawns, but zero keys for all other pieces. (In fact I derive them by ANDing the randoms fetched for the main hash with -IS_PAWN(piece), which seemed faster than setting up seprate tables.)

The Pawn hash itself is an array of integers, indexed by the low-order 18 bits of the key. It stores the hashed evaluation score in the 10 low-order bits, and the 22 high-order key bits in the rest, as signature.

In this scheme bits 10-17 are redundant, and do not contribute to avoiding collisions, as they were already implied by the address. I guess I could XOR these with 8 corresponding bits from my main hash key, if I make those bits only depend on Pawns there too (i.e. zero them for all other pieces). Would this degrade the opertion of the main hash table? I guess it would if I take bits for it that are used drectly in the index, but I could use bits from the signature. As I store only a 32-bits signature in the main hash, I guess there are some unused bits, which I could shift to the proper location for this purpose.

Would this be worth it, or would an 18-bit address and (effectively) a 14-bit signature be good enough?

[wgarvin]

I decided to put a Pawn hash in my new engine, so that I can quickly hack in some passer recognition through a dumb algorithm, without having to worry about efficiency. I never used Pawn hash before. Does the following seem a reasonable implemetation:

I keep an extra 32-bit hash key, which uses the same randoms as the main hash key for Pawns, but zero keys for all other pieces. (In fact I derive them by ANDing the randoms fetched for the main hash with -IS_PAWN(piece), which seemed faster than setting up seprate tables.)

The Pawn hash itself is an array of integers, indexed by the low-order 18 bits of the key. It stores the hashed evaluation score in the 10 low-order bits, and the 22 high-order key bits in the rest, as signature.

In this scheme bits 10-17 are redundant, and do not contribute to avoiding collisions, as they were already implied by the address. I guess I could XOR these with 8 corresponding bits from my main hash key, if I make those bits only depend on Pawns there too (i.e. zero them for all other pieces). Would this degrade the opertion of the main hash table? I guess it would if I take bits for it that are used drectly in the index, but I could use bits from the signature. As I store only a 32-bits signature in the main hash, I guess there are some unused bits, which I could shift to the proper location for this purpose.

Would this be worth it, or would an 18-bit address and (effectively) a 14-bit signature be good enough?

I'm not understanding why you'd want to XOR in bits from the main key? Especially if you would need to weaken your main hash keys... Isn't that very undesirable?

It would be simpler to not worry about the duplication of key bits. If in the future, you decide to shrink the size of your pawn hash, then some of the "redundant" key bits would become relevant again.

[bob]

I decided to put a Pawn hash in my new engine, so that I can quickly hack in some passer recognition through a dumb algorithm, without having to worry about efficiency. I never used Pawn hash before. Does the following seem a reasonable implemetation:

I keep an extra 32-bit hash key, which uses the same randoms as the main hash key for Pawns, but zero keys for all other pieces. (In fact I derive them by ANDing the randoms fetched for the main hash with -IS_PAWN(piece), which seemed faster than setting up seprate tables.)

The Pawn hash itself is an array of integers, indexed by the low-order 18 bits of the key. It stores the hashed evaluation score in the 10 low-order bits, and the 22 high-order key bits in the rest, as signature.

In this scheme bits 10-17 are redundant, and do not contribute to avoiding collisions, as they were already implied by the address. I guess I could XOR these with 8 corresponding bits from my main hash key, if I make those bits only depend on Pawns there too (i.e. zero them for all other pieces). Would this degrade the opertion of the main hash table? I guess it would if I take bits for it that are used drectly in the index, but I could use bits from the signature. As I store only a 32-bits signature in the main hash, I guess there are some unused bits, which I could shift to the proper location for this purpose.

Would this be worth it, or would an 18-bit address and (effectively) a 14-bit signature be good enough?

1. why not just use a 64 bit signature. Same random values as normal hash signature. Pawn hash will almost certainly grow beyond "just a score" anyway, so trying to squeeze everything into an array of ints will be wasted effort.

2. If you do that, then the other question becomes moot. You can use the rightmost N bits for index, leftmost M bits (32 for me) for the "lock" to verify a match, and you get good protection.

[Gerd Isenberg]

I decided to put a Pawn hash in my new engine, so that I can quickly hack in some passer recognition through a dumb algorithm, without having to worry about efficiency. I never used Pawn hash before. Does the following seem a reasonable implemetation:

I keep an extra 32-bit hash key, which uses the same randoms as the main hash key for Pawns, but zero keys for all other pieces. (In fact I derive them by ANDing the randoms fetched for the main hash with -IS_PAWN(piece), which seemed faster than setting up seprate tables.)

The Pawn hash itself is an array of integers, indexed by the low-order 18 bits of the key. It stores the hashed evaluation score in the 10 low-order bits, and the 22 high-order key bits in the rest, as signature.

In this scheme bits 10-17 are redundant, and do not contribute to avoiding collisions, as they were already implied by the address. I guess I could XOR these with 8 corresponding bits from my main hash key, if I make those bits only depend on Pawns there too (i.e. zero them for all other pieces). Would this degrade the opertion of the main hash table? I guess it would if I take bits for it that are used drectly in the index, but I could use bits from the signature. As I store only a 32-bits signature in the main hash, I guess there are some unused bits, which I could shift to the proper location for this purpose.

Would this be worth it, or would an 18-bit address and (effectively) a 14-bit signature be good enough?

Even with only a few K entries, you'll already get a sufficient hit-rate, so (much) bigger entries to store and utilize once calculated stuff for pawn-piece or pawn-king interactions are more common. Pawn shields and (extended) pawn center stuff , i.e. as index for dedicated piece square tables, bitboards or file-sets for passers, candidates, "weak" pawns and all kind of other properties, half-open and open file-sets, pawn mobility issues like rams and backward and various lever-options and whatever else. I agree with Bob to store at least the upper 32-bit of a dedicated 64-bit pawn hashkey.

[Sven]

If you store just a value in the pawn hash table then you would have to recalculate quite a lot of information that is needed for evaluation parts which do not depend on pawn structure only, like "rook on open file" (needs "open file" info based on pawn structure but depends also on rook position) or "unstoppable passed pawn" (needs "passed pawn" info but also knowledge about other pieces).

And having to recalculate pawn structure parts although you maintain a pawn hash seems quite ineffective. You could skip these eval parts to avoid it but I don't believe that this is what you wish to do.

So I think you should store much more data than just the score, e.g. one bit per file and color to indicate presence of at least one pawn of that color on a file, or the same again for presence of at least one passer of that color on a file. You have quite a lot of options here.

Including also pawn shield calculation into the pawn hash would IMO require to include the king positions into the pawn hash key, too. Don't know if that makes sense, I have never tried that.

Sven

[hgm]

Well, I don't have an open-file term in my eval yet. Wouldn't it be more logical to include the Rook files in the pawn hash key? The bonus can then be incuded in the score. The same could be done for the King location, if you wanted to put pawn-shield bonus or stoppable passers in the score.

[Sven]

Well, I don't have an open-file term in my eval yet. Wouldn't it be more logical to include the Rook files in the pawn hash key? The bonus can then be incuded in the score. The same could be done for the King location, if you wanted to put pawn-shield bonus or stoppable passers in the score.

Possible. But the amount of a pawn shield bonus may or may not depend on the presence of other pieces, i.e. the same pawn shield will probably get different bonuses in a bishop ending vs. in the opening. And whether or not a passer is unstoppable depends on the existence and maybe position of enemy pieces, not only on the enemy king. But for the pawn hash you only maintain the hash key covering all pawns and (in your proposal) kings (possibly also rook files), and a score directly derived from these, and you get the same value returned regardless whether you are in a bishop ending or in the opening. That tends to go wrong somehow.

Sven

[Daniel Shawul]

Including also pawn shield calculation into the pawn hash would IMO require to include the king positions into the pawn hash key, too. Don't know if that makes sense, I have never tried that.

I started using this recently and it was a good improvement. I do not xor the king location in to the zobrist key though. It reduces the hit rate from 97% to 50 something IIRC. I just store the two king locations along with other data in the pawn hash entry. So with this i calculate pawn scores which depend on king locations such as pawn shield, pawn storm, penalty for open files around king and bad king location by itself.
May be xor-ing king locations may be a good idea in king-pawn endings but i doubt it matters much.

[mathmoi]

Including also pawn shield calculation into the pawn hash would IMO require to include the king positions into the pawn hash key, too. Don't know if that makes sense, I have never tried that.

I started using this recently and it was a good improvement. I do not xor the king location in to the zobrist key though. It reduces the hit rate from 97% to 50 something IIRC. I just store the two king locations along with other data in the pawn hash entry. So with this i calculate pawn scores which depend on king locations such as pawn shield, pawn storm, penalty for open files around king and bad king location by itself.
May be xor-ing king locations may be a good idea in king-pawn endings but i doubt it matters much.

Hi Daniel,

Are you telling that you don't include the positions of the kings in the hash key, but you store informations/evaluation that are dependent on the kings position in the hash entry? How can that work?

[wgarvin]

Including also pawn shield calculation into the pawn hash would IMO require to include the king positions into the pawn hash key, too. Don't know if that makes sense, I have never tried that.

I started using this recently and it was a good improvement. I do not xor the king location in to the zobrist key though. It reduces the hit rate from 97% to 50 something IIRC. I just store the two king locations along with other data in the pawn hash entry. So with this i calculate pawn scores which depend on king locations such as pawn shield, pawn storm, penalty for open files around king and bad king location by itself.
May be xor-ing king locations may be a good idea in king-pawn endings but i doubt it matters much.

Hi Daniel,

Are you telling that you don't include the positions of the kings in the hash key, but you store informations/evaluation that are dependent on the kings position in the hash entry? How can that work?

It sounds like he also stores the kings positions in the entry, and only uses the cached pawn shield, pawn storm info if the king is still in the same position. I guess until you get to the endgame, your king is probably hiding behind some pawns and neither the king nor the pawns is very active, so you'll still be able to re-use this information in a lot of nodes.