Possible pawn hash speed optimization?

[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.

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...

When I said null-move, I was thinking of the typical eval(cur_state) >= beta pre-condition for null-move, that's part of the 40-ply search path and not the null-move path that gets branched off...

[JVMerlino]

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...

Indeed, that was where I was going with this. However, I wasn't taking into consideration the cache. Obviously the pawn hash key will be right there in the same structure as the tt key, so probably not as expensive as calculating from scratch at every eval.

And, when all is said and done, even if it is a very minor speed boost in some types of endgames, I'm sure the ELO increase will be unmeasurable. And I imagine it will be even harder to see any improvement in today's method of hyperbullet testing; it's may only be useful (if at all) in longer tc.

Anyway, again, thanks for the discussion.

jm

[bob]

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.

I use eval at endpoints. Not at interior nodes. Therefore, for each eval call in a 40 ply search, there are 40 moves to be made. Yes, some branches will be reduced. Which makes the average less than that. But at the same time, I then go deeper as well along some. I'm not saying I gave a lot of thought to this, as before I decided to go that route, I would instrument Crafty and get some real numbers, such as "how many consecutive moves are made for each call to eval?"

But I have noticed, for years, that incremental stuff becomes less effective as the depth climbs. I removed some even in Cray Blitz, because some of the incremental stuff we did was effective at shallow depths, but when the trees stretched out after I had added singular extensions, it became faster to just compute at need, rather than incrementally update the same things over and over before they were used once.

Note this was not talking about hashing in the above case, it was keeping up with which pawns were passed and such...

[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...

When I said null-move, I was thinking of the typical eval(cur_state) >= beta pre-condition for null-move, that's part of the 40-ply search path and not the null-move path that gets branched off...

I don't use that restriction. Never helped in my testing, and actually hurt a little on cluster runs...

[rbarreira]

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.

I use eval at endpoints. Not at interior nodes. Therefore, for each eval call in a 40 ply search, there are 40 moves to be made.

The 40-ply paths ending up in an eval have many common parts, you don't do 40 make_moves for each eval. I think that's what HGM was saying.

[bob]

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.

I use eval at endpoints. Not at interior nodes. Therefore, for each eval call in a 40 ply search, there are 40 moves to be made.

The 40-ply paths ending up in an eval have many common parts, you don't do 40 make_moves for each eval. I think that's what HGM was saying.

As I said, that was too complicated to think about, and I didn't test to measure. But I have seen the effect in years past, not specifically with incremental pawn hash updating, but with incremental updating of scoring ideas...

[Edmund]

If you don't mind the slightly higher rate of collision, why not combine the pawn-hash-key and normal-hash-key into one. Just make the first n-bits of every non-pawn piece hash-key zero.

regards

Edmund

[hgm]

I though about that,but with 64 bits total the key would be too short. But usually you have a material key too If youhave separate Pawns and piece bits in that, you could make the Pawn-counting bits part of the Pawn key, and the total material key part of the hash key.

[Edmund]

I though about that,but with 64 bits total the key would be too short. But usually you have a material key too If youhave separate Pawns and piece bits in that, you could make the Pawn-counting bits part of the Pawn key, and the total material key part of the hash key.

Quoting the paper written by Robert M. Hyatt, PhD. and Anthony E. Cozzie "The effect of hash collisions in a Computer Chess program"

One other simple experiment was run, attempting to define the minimum hash signature length necessary to avoid problems. In summary, 32 bit signatures produced wrong moves and scores, while 64 bits did not. An “in-between” value of 48 bits also proved to be just as safe as 64, but 48 is not a reasonable size since either 32 bit or 64 bit values are the natural signature lengths for 32 bit processors, and 64 bit signatures are the natural signature length for 64 bit processors.

I wonder whether 16 bits for the pawn-hash would be enough.

[sje]

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...

If you search 40 plies deep, you update the pawn hash signature 40 times only if all 40 moves are pawn moves.