Reduced depth search after Fail high at the root

[Meesha]

This came up recently when someone noticed a drop in the search depth with Stockfish and it was mentioned that many engines reduce the search depth after a fail high at the root in order to have enough time to complete the search of the move that failed high with an open window and get a score for said move. This was helpful for me in a situation where the search was hanging after the fail high and a new best move wasn't being returned in time. But i just want to make sure i'm implementing this correctly. By way of example. Lets say in an iterative deepening framework we are in the process of a depth 20 search and a move later in the move list fails high. We now do a reduced depth search of this move with an open window. How much of a reduction are we talking about? In my case just doing a depth 19 search was good enough, but what is typical? 1 ply, 2 plies? A reduction based on the depth like depth / 10?

And once we complete this reduced depth search and get a score and a short PV, do we continue searching the remaining moves with a null window at the initial depth....in this case depth 20?

And lastly assuming we were successful with our reduced depth (depth 19) search and all remaining moves fail low and now we go to continue the iterative deepening....are we going to do a depth 20 search again with our new best move or do we continue at depth 21?

[hgm]

I don't get it. You did already search the move at 19 ply, and it did not fail high then. So why would it fail high when you search it again, and not just return the (apparently much too low) score it returned before?

[Uri Blass]

I don't get it. You did already search the move at 19 ply, and it did not fail high then. So why would it fail high when you search it again, and not just return the (apparently much too low) score it returned before?

because earlier you reduced the depth after the move by some plies with LMR(late move reduction) when after the move failed high you do not reduce the depth after the move.

[Meesha]

There was a post titled "Stockfish search question" on May 7 where someone referenced a 2012 thread that ran about 8 pages regarding this search technique. It involved Houdart, Bob, Rebel, Don, Larry etc...which of course meant it would turn into an argument. The point is, while the approach was mentioned, the amount of reduction and how to proceed was not detailed and I was curious how others approach it.

I tried to describe the issue in as much detail as possible, and I really think I was clear. Just trying to save some time, but I will figure it out. Always do.

[Viz]

I don't get it. You did already search the move at 19 ply, and it did not fail high then. So why would it fail high when you search it again, and not just return the (apparently much too low) score it returned before?

because now search will be redone with newly gathered info that will make it different.
For example, you will probably trigger quite some singular extensions in even plies near root that were not present before. So even when you reduce search depth your effective search depth might increase anyway because of this (especially with how aggressive modern engines are with extensions).

[hgm]

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.

[Uri Blass]

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

[AndrewGrant]

Depth stopped being meaningful (between entities) the first time anyone did unsound pruning. Which I imagine is 40+ years ago.

[Viz]

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.

Basically for any engine that does any sort of pruning apart from AB.
Basically for any engine that uses SMP in any sort of efficient way (aka LazySMP of any sort).
Basically for any engine that uses not AB as a core of it search.
Basically for any engine that uses any sort of extensions.
Well, basically for any engine depth is somewhat meaningless concept.
I did write some brief explanation on why it's the case - https://github.com/official-stockfish/S ... t-is-depth

[hgm]

You miss the point. That something might not mean what you think it does, doesn't make it meaningless. None of the techniques you mention would cause a completely different tree to be searched when you search again at the same depth. For 99% of all engines requesting a search at a particular depth determines within a very small margin what tree would be searched (even though alpha-beta pruning might cut of different parts of it for irrelevance).