Possible pawn hash speed optimization?

[JVMerlino]

I'm sure somebody's thought of this before, but I don't recall any conversations about it. So I'll toss it up here and then duck and cover.

The source for all engines I have looked at that have pawn hash update the pawn hash key incrementally during make/unmake, same as with the tt key. To me, this makes perfect sense in the opening and middlegame, when most moves do not affect the pawn structure (or whatever else you decide to put in the pawn key -- King position seems to be fairly common).

Anyway, as you near the endgame, particularly an endgame in which most of the pieces are pawns, it seems that this incremental update would actually be slower than simply calculating the pawn key from scratch at the leaves and then probing as normal in evaluation. I would think that the make/unmake option is worse in this case because the percentage of moves that require this update becomes higher AND you're searching deeper, so more makes/unmakes in the branch leading to the evaluation.

Does this make sense? Has anybody tried this?

Many thanks for your indulgences....

jm

[sje]

If there are more than two pawns on the board, then a regeneration will cost more than an update/downdate.

[Sergei S. Markoff]

If there are more than two pawns on the board, then a regeneration will cost more than an update/downdate.

But may be it's posible to find some quick bitboard-based pawn hash evaluation tech? Something like:

PawnHash = pawnZobristB1[(int16)Pawns[BLACK]] ^ pawnZobristB2[(int16)(Pawns[BLACK] >> 16)] ^ pawnZobristB3[(int16)(Pawns[BLACK] >> 32)] ^ pawnZobristB4[(int16)(Pawns[BLACK] >> 48)] ^ pawnZobristW1[(int16)Pawns[WHITE]] ^ pawnZobristW2[(int16)(Pawns[WHITE] >> 16)] ^ pawnZobristW3[(int16)(Pawns[WHITE] >> 32)] ^ pawnZobristW4[(int16)(Pawns[WHITE] >> 48)]

And use this way when pawns count exceeds some number?

Anyway, I think all that optimization shouldn't help a lot

[Sven]

If there are more than two pawns on the board, then a regeneration will cost more than an update/downdate.

But may be it's posible to find some quick bitboard-based pawn hash evaluation tech? Something like:

PawnHash = pawnZobristB1[(int16)Pawns[BLACK]] ^ pawnZobristB2[(int16)(Pawns[BLACK] >> 16)] ^ pawnZobristB3[(int16)(Pawns[BLACK] >> 32)] ^ pawnZobristB4[(int16)(Pawns[BLACK] >> 48)] ^ pawnZobristW1[(int16)Pawns[WHITE]] ^ pawnZobristW2[(int16)(Pawns[WHITE] >> 16)] ^ pawnZobristW3[(int16)(Pawns[WHITE] >> 32)] ^ pawnZobristW4[(int16)(Pawns[WHITE] >> 48)]

And use this way when pawns count exceeds some number?

Anyway, I think all that optimization shouldn't help a lot

I agree to the last sentence

Eight tables of 65536 64-bit entries = 4 MB, that's quite a lot for a solution that has no real potential for optimization. One might certainly reduce that to 3 MB by using knowledge that pawns never occupy rank 1+8 but even that would not help much. I think the obvious solution (incremental update when making a move) is also the best one in this case.

Sven

[JVMerlino]

If there are more than two pawns on the board, then a regeneration will cost more than an update/downdate.

But may be it's posible to find some quick bitboard-based pawn hash evaluation tech? Something like:

PawnHash = pawnZobristB1[(int16)Pawns[BLACK]] ^ pawnZobristB2[(int16)(Pawns[BLACK] >> 16)] ^ pawnZobristB3[(int16)(Pawns[BLACK] >> 32)] ^ pawnZobristB4[(int16)(Pawns[BLACK] >> 48)] ^ pawnZobristW1[(int16)Pawns[WHITE]] ^ pawnZobristW2[(int16)(Pawns[WHITE] >> 16)] ^ pawnZobristW3[(int16)(Pawns[WHITE] >> 32)] ^ pawnZobristW4[(int16)(Pawns[WHITE] >> 48)]

And use this way when pawns count exceeds some number?

Anyway, I think all that optimization shouldn't help a lot

I agree to the last sentence

Eight tables of 65536 64-bit entries = 4 MB, that's quite a lot for a solution that has no real potential for optimization. One might certainly reduce that to 3 MB by using knowledge that pawns never occupy rank 1+8 but even that would not help much. I think the obvious solution (incremental update when making a move) is also the best one in this case.

Sven

Ok, guys. Thanks for the verification.

jm

[bob]

If there are more than two pawns on the board, then a regeneration will cost more than an update/downdate.

I think he is talking about the search path. If you search 40 plies deep, you update the pawn hash signature 40 times, and then do one probe (which uses that). It would be more efficient to recalculate. But it is probably a 0.1% improvement overall since the pawn hash stays in cache because it is updated so often. Hanging on to it might actually make it faster if the memory layout is such that it gets displaced before it is used in eval, and you burn a few thousand cycles waiting to get it back...

[rbarreira]

If there are more than two pawns on the board, then a regeneration will cost more than an update/downdate.

I think he is talking about the search path. If you search 40 plies deep, you update the pawn hash signature 40 times, and then do one probe (which uses that). It would be more efficient to recalculate. But it is probably a 0.1% improvement overall since the pawn hash stays in cache because it is updated so often. Hanging on to it might actually make it faster if the memory layout is such that it gets displaced before it is used in eval, and you burn a few thousand cycles waiting to get it back...

But a 40-ply search path probably calls the evaluation much more than once, with the null-move searches, several evals on each quiescence etc.

[wgarvin]

I'm sure somebody's thought of this before, but I don't recall any conversations about it. So I'll toss it up here and then duck and cover.

The source for all engines I have looked at that have pawn hash update the pawn hash key incrementally during make/unmake, same as with the tt key. To me, this makes perfect sense in the opening and middlegame, when most moves do not affect the pawn structure (or whatever else you decide to put in the pawn key -- King position seems to be fairly common).

Anyway, as you near the endgame, particularly an endgame in which most of the pieces are pawns, it seems that this incremental update would actually be slower than simply calculating the pawn key from scratch at the leaves and then probing as normal in evaluation. I would think that the make/unmake option is worse in this case because the percentage of moves that require this update becomes higher AND you're searching deeper, so more makes/unmakes in the branch leading to the evaluation.

Does this make sense? Has anybody tried this?

Many thanks for your indulgences....

jm

I'm sure incremental pawn hash key updates can be done in a branchless manner so that they cost next to nothing. Especially since your pawn hash key probably lives in the same cache line of your board structure as other critical stuff updated by MakeMove (such as the main hash key). You already have to look up some 64-bit zobrist keys and xor them into the main hash key; after each step of that all that's needed is a conditional instruction to zero the register if the piece being moved or captured is not a pawn, and then xor the result into the pawn hash key. Those reads and writes will hit the same cache line and cost pretty much nothing.

It might also make sense to do these incremental updates of the pawn hash key, but not actually access the pawn hash entry until you reach a leaf node. That way, if your tree contains lots of pawn moves, you don't pollute your caches with accesses to all of the intermediate pawn configurations -- only the ones you end up evaluating. The pawn hash table entries could also probably be prefetched, but I'd be surprised if it had any benefit. It seems like a hit in the pawn hash probably means we've touched this entry recently and it will still be in the processor's L2/L3 cache anyway.

[bob]

If there are more than two pawns on the board, then a regeneration will cost more than an update/downdate.

I think he is talking about the search path. If you search 40 plies deep, you update the pawn hash signature 40 times, and then do one probe (which uses that). It would be more efficient to recalculate. But it is probably a 0.1% improvement overall since the pawn hash stays in cache because it is updated so often. Hanging on to it might actually make it faster if the memory layout is such that it gets displaced before it is used in eval, and you burn a few thousand cycles waiting to get it back...

But a 40-ply search path probably calls the evaluation much more than once, with the null-move searches, several evals on each quiescence etc.

That 40 ply search requires 80 signature updates. If you have king + 5 pawns per side, that is 10 iterations to factor in the pawns, + 2 for the kings. 12 total. Do I use eval enough along that path to make that more expensive? Not so clear. I need to do more than 6 evals to break even. Along a single path, I don't think I will do that. Null-move doesn't count, that starts a different path.

Whether it wins or not, I don't know. I don't do it, because I was never convinced that it did. I was just explaining what I though John's reasoning was...

[hgm]

How many un-branched 40-ply paths do occur in your tree? Because when the tree is branched, even with an EBF as low as 2, your calculation would be totally off-base, and the effective number of updates to reach the node (taking account of sharing) would only be 2, not 40.