The devilish fail low

[Dann Corbit]

Watching chess programs analyze positions, I noticed something strange. When a program gets a fail low, it simply plows forward, no matter what the cost, to find out how truly terrible the current move is.

So, for instance, it might find it drops from +24 centipawns to -200 in two or three seconds. But then it will pound on and on, perhaps for ten minutes until it finally sees that the current move choice is going to be checkmated.

I am wondering if anyone has tried something like this:
If I drop (some margin such as) 450 centipawns, instead of pounding away to see how badly I am going to be sliced to pieces, switch to a zero window search at half your loss and do several plies looking for an improvement. I know mathematically it is not sound. But once you are down -450 centipawns you are going to lose anyway (SF wins less than one game in 30,000 after being down 450 centipawns). So why not hit the panic button and look for a way out of the hole?

I guess that someone has already tried this since it is a relatively obvious idea.

[Dann Corbit]

A related idea is to try +1 pawn (or some such margin) zero window searches after a long series of approximately stalemented searches. You are probably going to draw, so why not search for an elusive win. I have more qualms about this idea, and I imagine it has been tried too

[bob]

First "half your loss" is hard to define, since all you know is score is <= alpha.

Second, this is a question that has been asked for 40 years. There are several schools of thought:

(1) resolve the fail low so that you have a good score which gives you information you can use to adjust your time limit. Bigger loss == more time allowed.

(2) continue searching the root move list with the same window hoping something will be better and you avoid the fail low. If everything fails low, you have wasted all the search time and still know nothing.

(3) start the search again from scratch, and back up a few plies. Since you know that this move failed low at depth = D, it should fail low at earlier depths now since the fail low is recorded in the hash table. Hopefully. Hopefully not overwritten. There's an opportunity for a nice loop here, if that hash entry doesn't survive long enough.

Etc.

Which is best? Hard to say. My testing has always shown it is best to get a score for the move that has been best all along, before working on the others. Here is one possible scenario that fits. Your opponent leaves a piece hanging. When you start your search, you get +3.x scores. Until you get to the last iteration you can afford, and suddenly you figure out it is not hanging. And you get a fail low and the score drops back to around zero. If this move is best, then you really do want to get its true score before continuing. If not, you don't. But how to tell the difference.

I used to have some data from older games about how often the first move fails low but remains the best move. It was actually a lot higher percentage than I thought.

Never wrong to try something new, nobody knows what new approach will suddenly look much better.

[Dann Corbit]

I think I did not explain myself very well.
I agree that almost all of the time, it is best to simply complete the search.
But I am talking about the root score when you finish an iteration.
If the root score is losing (I gave the example of -450 centipawns) that is the scenario I was trying to describe. Since you are most likely going to lose anyway, you might as well hit the panic button.

More precisely,
If I have exceeded some guard depth (e.g 12 plies) and my root move score drops to an almost certain loss when the iteration completes, then try quick zero window searches with a hoped for gain to try to escape the dire situation. What I see programs do is add bigger and bigger negative windows and keep searching again and again with bigger and bigger fail lows. Now, you have probably lost anyway, so that is why my idea is probably a fly covered hot dog on a stick, but I was wondering if there are measurements for it.

If you go from +3 to 0, I don't think it is time to panic.

[chrisw]

I think I did not explain myself very well.
I agree that almost all of the time, it is best to simply complete the search.
But I am talking about the root score when you finish an iteration.
If the root score is losing (I gave the example of -450 centipawns) that is the scenario I was trying to describe. Since you are most likely going to lose anyway, you might as well hit the panic button.

More precisely,
If I have exceeded some guard depth (e.g 12 plies) and my root move score drops to an almost certain loss when the iteration completes, then try quick zero window searches with a hoped for gain to try to escape the dire situation. What I see programs do is add bigger and bigger negative windows and keep searching again and again with bigger and bigger fail lows. Now, you have probably lost anyway, so that is why my idea is probably a fly covered hot dog on a stick, but I was wondering if there are measurements for it.

If you go from +3 to 0, I don't think it is time to panic.

Not sure if it still does, but when I used to take a close interest in what other engines did, Hiarcs was noticeable for sometimes taking a humongous amount of time (I’m talking 90% of total time left for the entire game) on one move. I think I saw a quote from Uniacke to the effect that if a score fell, the engine would then do everything it could to try (eg extend the search) and find a better root move, even at the cost of playing the rest of the game with way less time. Makes sense, if a move is really bad, you lose whatever, so best to avoid if possible.

The reason SF, and most nearly everybody else, I assume searches over and over with increasingly negative windows, is that they are trying to not just evaluate the (bad) move, but trying to fill the hash with sensible continuation lines that are going to be lacking in the fail low searches. In a fail low search, just about any old junk moves by the opponent in the tree will give cutoffs, and your engine is going to fail low continuously in the tree and not find cutoffs, with result hash continuation lines will be full of the any old junk, with negative effect on search efficiency.

[Ras]

Watching chess programs analyze positions, I noticed something strange. When a program gets a fail low, it simply plows forward, no matter what the cost, to find out how truly terrible the current move is.

I have never seen an engine that does it this way because it wouldn't even make sense, defeating the whole point of alpha-beta search. The current move fails low, OK, so forget about it, that's how engines implement this. Even if a whole node fails low - don't care, this just means the move leading to this node will fail high one depth level further up. The only problem is at root level because there is no "one level further up", and then engines don't invest time to figure out how bad the currently tried root move is, but to find ANY root move that doesn't fail low.

If all fails low at root, then and only then the root aspiration window is widened. Most engines widen by a certain factor, and there's a compromise: the smaller you make the factor, the faster the re-search is done in many cases, but the more re-search tries you need in exceptional cases. This is especially bad if the actual problem is that the engine will be mated because that's a very large negative value where it can take many widenings to arrive.

A possible solution is that if things still fail low after let's say widening the aspiration window three times, you set root alpha to -MATE and search with half-open window.

[hgm]

It is a good question whether one should spend a lot of time to figure out how low the score of a certain iteration is, or spend that time instead to figure out whether there isn't some miraculous recovery in the next iteration that would lift you above the 'certain loss'.

One problem is that you would not have much to go on in this next iteration when the previous one was abandoned after a too-low fail-low. But perhaps the size of the search tree would still be some measure for how close to alpha the real score was.

Another panic mode could be to search wider instead of deeper; modern top engines reduce so aggressively that it is very hard to get more depth in the side branches, and you have to increase the nominal search depth enormously to even get one extra ply there. Often the reason for their heavy reduction is nothing else than that they happened to be later than other moves in the initial move ordering determined by the move generator. History is often a self-fulfilling prophecy; those moves that you hardly ever try will never be able to get a high history score even when they are good, and will thus hardly ever be tried. If you are dependent on a miracle, it might be cheapest to search it in those moves. Apparently your intuition for deciding what moves were worth following proved wrong, or it would not have led you to this failing PV. So better drop it, and treat all moves more equally.

[Dann Corbit]

That is an interesting idea and one I have never thought of as a solution, switch to pure alpha-beta.

[Ras]

Another panic mode could be to search wider instead of deeper

The engine hadn't been seeing the problem in the move turn before, or else it would have avoided it already. So if the current iteration of pruning search found the engine is in trouble, then this will probably be in one of the last two depth iterations, assuming that the thinking time for the current move is similar to the turn before.

Going for less aggressive pruning would by far not reach this depth - after all, that's why we prune in the first place. So you'd also have to reduce the search depth, but then the bad things are beyond the horizon, at which point you can just take the PV from the depth iteration before the fail low happened.

I think that the "panic mode" stuff is in vain anyway. Once this happens, it's already too late.

[Dann Corbit]

Another panic mode could be to search wider instead of deeper

The engine hadn't been seeing the problem in the move turn before, or else it would have avoided it already. So if the current iteration of pruning search found the engine is in trouble, then this will probably be in one of the last two depth iterations, assuming that the thinking time for the current move is similar to the turn before.

Going for less aggressive pruning would by far not reach this depth - after all, that's why we prune in the first place. So you'd also have to reduce the search depth, but then the bad things are beyond the horizon, at which point you can just take the PV from the depth iteration before the fail low happened.

I think that the "panic mode" stuff is in vain anyway. Once this happens, it's already too late.

I guess that the chances of a kick save are really low, but if there is a solution and we did not find it, chances are good that it got pruned away.
On the other hand, a branching factor of 6 is going to severely limit depth.
Stoically accepting a death dealing outcome seems rather British
Another thing to try is Amir Ban's verification search, with a more aggressive verification.