Reduced depth search after Fail high at the root

[hgm]

LMR is extremely heavily based on move ordering, not only it reduces more for latter moves, but it also takes into account history sum to reduce less/more in basically any strong engine - and this is worth quite a chunk of elo, in fact, continuation histories are worth more in LMR reductions than they are worth in move ordering itself in Stockfish, for example.

Oh, I am sure it is worth some Elo. But the issue was whether it is an absolute necessity to do this to get above 2200 Elo CCRL. And whether it thus can be deduced that all engines rated above this use that technique.

I know for sure that this is not the case. Joker is rated around 2300 on CCRL, and it doesn't use history at all, and reduces by a fixed amount of 1 ply. Considering that it would probably gain significant Elo if it would have King Safety or Mobility in its evaluation (which it doesn't have either), the 'fixed-LMR Elo barrier' should ly significantly higher.

IIRC Fruit 2.1 also only reduces late moves by only a single ply, and it is rated around 2700. It is true that it exempts a few moves with the highest history score from this reduction, but I doubt whether it would really lose much Elo on not doing that.

[Viz]

Stockfish without anything but alphabeta should be smth like 3000 CCRL, so it's indeed not "necessary", but it's simple and good.

[Uri Blass]

LMR is extremely heavily based on move ordering, not only it reduces more for latter moves, but it also takes into account history sum to reduce less/more in basically any strong engine - and this is worth quite a chunk of elo, in fact, continuation histories are worth more in LMR reductions than they are worth in move ordering itself in Stockfish, for example.

Oh, I am sure it is worth some Elo. But the issue was whether it is an absolute necessity to do this to get above 2200 Elo CCRL. And whether it thus can be deduced that all engines rated above this use that technique.

I know for sure that this is not the case. Joker is rated around 2300 on CCRL, and it doesn't use history at all, and reduces by a fixed amount of 1 ply. Considering that it would probably gain significant Elo if it would have King Safety or Mobility in its evaluation (which it doesn't have either), the 'fixed-LMR Elo barrier' should ly significantly higher.

IIRC Fruit 2.1 also only reduces late moves by only a single ply, and it is rated around 2700. It is true that it exempts a few moves with the highest history score from this reduction, but I doubt whether it would really lose much Elo on not doing that.

I guess that with good NNUE evaluation you can get clearly above 2200 even with no extensions and reductions and I agree that the 2200 claim not by me was wrong.

But the discussion is not about that wrong claim.

Even if you take fruit2.1 that today is a relatively weak engine the depth of a line is dependent on the history of the search and not only on the moves of the line so maybe reducing after fail high can help to improve it(did not check it).

[hgm]

It cannot be excluded, but it seems very unlikely. As I said, revoking reductions because a move when a late move is found to be a cut move is usually offset by the preceding ply failing low and becoming a late move. In Fruit LMR is only a single ply. And only three moves won't get that reduction.

[RubiChess]

An example for the meaning of depth:

I did some spsa tuning for all the search parameters in my engine some months ago (thanks to AGE for making this so easy in OpenBench).

The result (measured in 10000 games tc=60+0.6):
Elo: +26
Average depth per move: -3.4 (24.9 for the old version, 21.5 for the tuned version).

Regards, Andreas

[Meesha]

quote="Uri Blass" post_id=964305 time=1715855069 user_id=192]

So it would only make sense in engines for which 'depth' is a rather meaningless concept, not related in a fixed way to the quality of the search?

I guess it would be important to know whether it is pointless to try this for those of us who have an engine that has a more robust interpretation of the depth parameter.

I think that 'depth' is meaningless for majority of programmers or to be more correct it is not meaningless but does not have the meaning that you expect(if you play fixed depth match then bigger depth still wins)

Even engines that only have null move pruning can maybe earn from reduction after fail high.

Imagine you have the following.

depth 9 1.e4 0.32
1.d4 no threat
depth 10 1.e4 0.23
depth 10 1.d4 has a threat(not because you search deeper but because threat is now relative to 0.23
depth 10 1.d4 fail high.
searching 1.d4 to depth 10 to get an exact score is too expensive so you search 1.d4 to depth 9 and get a score of 0.25
now the question is how to continue.
You can do a research at depth 10 for 1.d4 but you can also decide not to do a research and searching other moves at depth 9(you know from previous search that they are not better than 0.32 but you do not know if they are not better than 0.25).
[/quote]

Thank you Uri! This is what I will try:

For simplicity we have 5 possible root moves m1, m2,...m5
Up until depth 9, m1 has been the best move with a score of 0.32. Now on depth 10, m1 scores 0.23 and m2 fails high. Instead of searching m2 with an open window at depth 10, we do a search at depth 9 to ensure that the search can complete in time. As you say we get a score of 0.25 and it becomes the best move. Proceeding with the remaining moves (m3,..m5) I originally thought it would be pointless to search them with a null window at depth 9 since they had already failed low on the previous iteration. But as you point out they failed low when alpha was 0.32. Its now possible that one of them could fail high with alpha 0.25. If not we move on with the depth 10 iteration once again with m2 as the PV move. Thats helpful.

Now the question is, lets say m3 now fails high at depth 9 with alpha 0.25. You would now do a open window search of m3 at depth 8?

Does anyone else do this in their engine and if so, is there ever a need to reduce by more than one ply (perhaps at very high depth)?

[hgm]

An example for the meaning of depth:

I did some spsa tuning for all the search parameters in my engine some months ago (thanks to AGE for making this so easy in OpenBench).

The result (measured in 10000 games tc=60+0.6):
Elo: +26
Average depth per move: -3.4 (24.9 for the old version, 21.5 for the tuned version).

Regards, Andreas

It is pretty obvious that you can also prune too much. I can make an engine that only needs 30 nodes to reach depth 30. It won't be very strong...

[hgm]

For simplicity we have 5 possible root moves m1, m2,...m5
Up until depth 9, m1 has been the best move with a score of 0.32. Now on depth 10, m1 scores 0.23 and m2 fails high. Instead of searching m2 with an open window at depth 10, we do a search at depth 9 to ensure that the search can complete in time. As you say we get a score of 0.25 and it becomes the best move. Proceeding with the remaining moves (m3,..m5) I originally thought it would be pointless to search them with a null window at depth 9 since they had already failed low on the previous iteration. But as you point out they failed low when alpha was 0.32. Its now possible that one of them could fail high with alpha 0.25. If not we move on with the depth 10 iteration once again with m2 as the PV move. Thats helpful.

Now the question is, lets say m3 now fails high at depth 9 with alpha 0.25. You would now do a open window search of m3 at depth 8?

Does anyone else do this in their engine and if so, is there ever a need to reduce by more than one ply (perhaps at very high depth)?

OK, I see. You are not talking about a fail high of the entire iteration due to aspiration, but of the PVS fail high of the pilot search. In most cases this would already have been searched at reduced depth because of LMR. So the first re-search with open window at that LMR'ed depth would already be (perhaps a lot) less deep than 10 ply.

This is normal alpha-beta behavior, which has nothing to do with reductions / extensions or search instability. When the PV move drops in score compared to the previous iteration, there is a good chance another move could become PV, and it could be any move. This applies to the root as well as any other PV node. And all these other moves have been 'inadequately refuted', in the sense that even at the depth they were searched before, the cut moves used to refute them might not be able to do it at the new search window. And you might have to search very many of those before you get the new best.

So it does indeed seem advisable to first search all these moves at the same depth they have already been searched, but now with the new window, to find the best one, and only then search at the depth dictated by the current iteration, starting with that best. I think that would be a safe thing to do in any PV node.