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
Possible pawn hash speed optimization?
Moderators: hgm, Rebel, chrisw
-
- Posts: 1357
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Possible pawn hash speed optimization?
If there are more than two pawns on the board, then a regeneration will cost more than an update/downdate.
-
- Posts: 227
- Joined: Mon Sep 12, 2011 11:27 pm
- Location: Moscow, Russia
Re: Possible pawn hash speed optimization?
But may be it's posible to find some quick bitboard-based pawn hash evaluation tech? Something like:sje wrote:If there are more than two pawns on the board, then a regeneration will cost more than an update/downdate.
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
The Force Be With You!
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Possible pawn hash speed optimization?
I agree to the last sentenceSergei S. Markoff wrote:But may be it's posible to find some quick bitboard-based pawn hash evaluation tech? Something like:sje wrote:If there are more than two pawns on the board, then a regeneration will cost more than an update/downdate.
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
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
-
- Posts: 1357
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
Re: Possible pawn hash speed optimization?
Ok, guys. Thanks for the verification.Sven Schüle wrote:I agree to the last sentenceSergei S. Markoff wrote:But may be it's posible to find some quick bitboard-based pawn hash evaluation tech? Something like:sje wrote:If there are more than two pawns on the board, then a regeneration will cost more than an update/downdate.
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
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
jm
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Possible pawn hash speed optimization?
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...sje wrote:If there are more than two pawns on the board, then a regeneration will cost more than an update/downdate.
-
- Posts: 900
- Joined: Tue Apr 27, 2010 3:48 pm
Re: Possible pawn hash speed optimization?
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.bob wrote: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...sje wrote:If there are more than two pawns on the board, then a regeneration will cost more than an update/downdate.
-
- Posts: 838
- Joined: Thu Jul 05, 2007 5:03 pm
- Location: British Columbia, Canada
Re: Possible pawn hash speed optimization?
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.JVMerlino wrote: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
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Possible pawn hash speed optimization?
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.rbarreira wrote: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.bob wrote: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...sje wrote:If there are more than two pawns on the board, then a regeneration will cost more than an update/downdate.
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...
-
- Posts: 27811
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Possible pawn hash speed optimization?
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.