The devilish fail low

[hgm]

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.

But you might not need to reach the same depth with the less aggressive pruning. You just need higher depth in all those extremely reduced side branches. Which you might already have for a much lower nominal depth. The bad score of the PV won't go away: it will still be in the TT, for any node along it. Everything you will search to lower depth due to the less aggressive pruning will still get the score of the high-depths search that was left in the TT. But the nodes originally in those grafted searches now will be added to the branches that were very short.

[Ras]

But you might not need to reach the same depth with the less aggressive pruning.

How will you find the solution to a problem that you don't even see anymore at reduced depth?

[Ras]

On the other hand, a branching factor of 6 is going to severely limit depth.

Even that is overly optimistic because alpha-beta only reduces the EBF to the square root of moves per position if the move ordering is perfect - but the assumption was that the pruning has taken away good moves precisely because the move ordering wasn't good in that situation.

[hgm]

How will you find the solution to a problem that you don't even see anymore at reduced depth?

But you will continue to see the problem. Because it is grafted from the TT.

Say you have enough nodes to do a 10-ply fixed-depth search. So initially you search to 24 ply, and at 23-ply everything still looked fine, but at 24-ply you get a disastrous fail low, not only of the PV move, but of every other move as well. But the 24-ply was of course a lie, only the PV was searched to that depth, and most branches did not even reach 6 ply. The nodes needed to extend the PV that much had to come from somewhere.

So you try the fixed-depth 10-ply search, in the hope that in the 4 ply that these branches now get extra one of them bounces back to an acceptable score. Something has to bounce back, or you are toast. Perhaps there was some sacrifice that you earlier classified as a pure loss, but which gives you some counter-attack. Every branch that originally was searched deeper than 10 ply will retain its (very bad) score (bound), as these will experience a sufficient-depth hash hit.

[bob]

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.

He's talking about the FIRST move at the root. If it fails low, what do you do? Try to resolve the score or continue searching to see if another move will bring the root score to > alpha??

[bob]

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

That is likely NOT going to work. If you are at depth=30 with a typically pruned search, trying to search at depth=30 with alpha/beta is going to burn the cpu and give you absolutely nothing back.

[bob]

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 can't count the number of times when the first move failed low, and an extended-time search found a move that kept the root score reasonable. That's the whole point for using extra time on some moves.

[Ras]

But you will continue to see the problem. Because it is grafted from the TT.

You won't see the problem because you don't reach the depth where the positions even arise. Reusing the TT for the scores is pointless because the assumption is that they aren't true.

But the 24-ply was of course a lie, only the PV was searched to that depth

Correct, and the problem showed only up at depth 24. The new branches don't show a problem at depth 10, fine - but the original PV didn't show problems either at depth 10. There's just no way that a depth 10 search can figure out how to solve a problem that only becomes evident from depth 24.

He's talking about the FIRST move at the root. If it fails low, what do you do? Try to resolve the score or continue searching to see if another move will bring the root score to > alpha??

Up to depth 4, I search with full window at root. From that point on, I'm using a +/-50 centipawns window relative to the score of the previous root depth iteration. If the first move fails on the low side, I keep on searching the other root moves. The idea is to first try finding a better move than figuring out how bad exactly the first root move is. But if that fails, I open alpha to -infinity and see what my least bad choice is.

[chrisw]

But you will continue to see the problem. Because it is grafted from the TT.

You won't see the problem because you don't reach the depth where the positions even arise. Reusing the TT for the scores is pointless because the assumption is that they aren't true.

But the 24-ply was of course a lie, only the PV was searched to that depth

Correct, and the problem showed only up at depth 24. The new branches don't show a problem at depth 10, fine - but the original PV didn't show problems either at depth 10. There's just no way that a depth 10 search can figure out how to solve a problem that only becomes evident from depth 24.

He's talking about the FIRST move at the root. If it fails low, what do you do? Try to resolve the score or continue searching to see if another move will bring the root score to > alpha??

Up to depth 4, I search with full window at root. From that point on, I'm using a +/-50 centipawns window relative to the score of the previous root depth iteration. If the first move fails on the low side, I keep on searching the other root moves. The idea is to first try finding a better move than figuring out how bad exactly the first root move is. But if that fails, I open alpha to -infinity and see what my least bad choice is.

If you assume the opponent is a senseful entity (which is a good assumption, since your engine ought to be senseful, yet it just found it was playing towards a step downhill), then your policy should depend on absolute score. Eg, if alpha is positive queen, then it probably won’t matter if the downhill step is negative rook. Whereas fail lows off alpha negative rook, you’re just losing, not much point in investing in strategies of saving a lost game. So, for example, if your alpha is positive and you fail low, it could be sensible to set alpha to zero and research, rather than -MATE. -MATE searches are time expensive, and if you’re losing, who cares by how much. Fail lows when alpha is in the region of equality plus/minus are the critical ones, in those cases you need to find something that at least “draws” or goes to minus pawn or whatever, anyway, you get the idea, reset of alpha kind of depends on absolute score, seen from a whole game perspective

[Ras]

-MATE searches are time expensive

Not that much because I start out with the PV from the previous depth iteration as left-most search path so that I will quickly get the associated score as new alpha. I found that several retries with increasingly widened window take more time than one re-search with half-open window.