Shifting alpha/beta on hash hit

[fierz]

Dear all,

I have always been programming my hashtable lookups that they could either (1) produce a direct cutoff and (2) if they are not sufficient to create a cutoff, that they can at least shift the current alpha and beta bounds at pv nodes. Like so in my negamax function

(1)
if (table.depth >= depth && table.value-is-lowerbound && value >= beta)
return table.value;
...same for alpha and

(2)
if (table.depth >= depth && table.value-is-lowerbound && value > alpha)
alpha = table.value;


I recently found a position where my engine blunders a piece that takes only a few ply (8 to be exact), even at depth 20. If I turn off hashing, it sees the problem at 8 ply as expected. If I turn on hashing, but turn off this shifting of bounds, it still plays the correct move. So I am wondering if I am making a mistake in shifting the window bounds in pv nodes - can you tell me whether that is the case, and whether you shift window bounds or not?

For the record, my engine uses PVS and aspiration windows at the root, and in the position where this happens, a fail low on the first search at 8ply is followed by a research at same depth, which may be part of the problem.

best regards
Martin

[hgm]

I guess it depends on how you handle the search instability. E.g. if your current window is {10, 80}, and you get a hash hit of sufficient depth that gives a lower bound of 50. That is not above the window, so you reduce the window to {50, 80}. Now suppose you fail low, with an upper bound of 40. What do you do? True score could be -800...

[fierz]

Hmm, I have tried enabling and disabling other options in my engine, and it appears that it's not as clearcut as I thought, other things (like less aggressive null move) can also affect this mistake of my engine.

Nevertheless, can anyone tell me whether shifting alpha/beta bounds on hash hits is a good idea or not? I always thought it was, but I also checked and saw that neither Crafty nor Stockfish are doing it...!?

cheers
Martin

[hgm]

Without special handling of the case where the score ends between the original and the shifted limits (e.g. by doing a re-search), it seems a bad idea. But only testing can show that for sure. (And also whether it still pays if you do a re-search. Aspiration of the window is always a risk; it speeds you up a little most of the time, but backfires badly in other cases.

[Evert]

For my own understanding: Once you find a move that improves on raised_alpha you're fine, but a move that fails low against raised_alpha and high against alpha is suspect and due for a re-search (possibly against [alpha, raised_alpha], but that may in turn trigger other re-searches).

In a fail-hard framework not doing the re-search is inconcistent, in fail-soft it is perhaps tolerable to skip it, but that needs testing.

Since most nodes (in a standard PVS framework) have a null-window though, I don't think this type of transposition table based aspiration will gain much. If I recall correctly, aspiration windows at the root aren't worth that much either (in PVS, plain alpha-beta may be another matter).

[bob]

Hmm, I have tried enabling and disabling other options in my engine, and it appears that it's not as clearcut as I thought, other things (like less aggressive null move) can also affect this mistake of my engine.

Nevertheless, can anyone tell me whether shifting alpha/beta bounds on hash hits is a good idea or not? I always thought it was, but I also checked and saw that neither Crafty nor Stockfish are doing it...!?

cheers
Martin

I did this from the 70's. But removed it when CB moved to PVS. I then did it again in early Crafty's, but it was removed (according to comments in main.c) in version 19.18.

I doubt it is worth anything since there is no way to improve alpha in way over 99% of the tree since PVS searches most everything with a null-window. Improving alpha would produce an instant beta cutoff, which should already have been taken when checking the bounds...

[fierz]

I did this from the 70's. But removed it when CB moved to PVS. I then did it again in early Crafty's, but it was removed (according to comments in main.c) in version 19.18.

I doubt it is worth anything since there is no way to improve alpha in way over 99% of the tree since PVS searches most everything with a null-window. Improving alpha would produce an instant beta cutoff, which should already have been taken when checking the bounds...

I agree completely that it's only a very small effect, the number of nodes I need to search for a fixed depth goes down by 1% or so if I enable this. I just wondered if there was a theoretical reason for not shifting the bounds. I guess the answer would have to be there is no reason not to do it, but also no real reason to do it

best regards
Martin

[Mincho Georgiev]

I did this from the 70's. But removed it when CB moved to PVS. I then did it again in early Crafty's, but it was removed (according to comments in main.c) in version 19.18.

I doubt it is worth anything since there is no way to improve alpha in way over 99% of the tree since PVS searches most everything with a null-window. Improving alpha would produce an instant beta cutoff, which should already have been taken when checking the bounds...

I agree completely that it's only a very small effect, the number of nodes I need to search for a fixed depth goes down by 1% or so if I enable this. I just wondered if there was a theoretical reason for not shifting the bounds. I guess the answer would have to be there is no reason not to do it, but also no real reason to do it

best regards
Martin

I was doing this for years with the wrong impression that it's working. I removed it last year. Here are some numbers from a fixed depth 19 search:

Code: Select all

19 163910458   0.24 e2e4 e7e6 g1f3 d7d5 e4d5 e6d5 d2d4 g8f6 f1d3 f8d6 d1e2 c8e6 d3f5 d8e7 f5e6 e7e6 e2e6 f7e6 b1c3
   952 Kn/s,  105.94 sec

move e2e4

fwnodes: 139475, nwsnodes: 198005039,  percentage: 0.07%

Keep in mind I don't prune on fw nodes. There's no way with that percentage this would have an effect. I my case, it was definitely placebo...
Edit: I'm sharing my impression with Evert, again with fail hard. Inconsistency/worse pv line IMO. But this is just a side note, I removed it mainly because of the above ratio.