The devilish fail low

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 24450
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: The devilish fail low

Post by hgm » Sun Apr 05, 2020 8:00 pm

Ras wrote:
Sun Apr 05, 2020 7:48 pm
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
Posts: 1381
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: The devilish fail low

Post by Ras » Sun Apr 05, 2020 8:06 pm

hgm wrote:
Sun Apr 05, 2020 8:00 pm
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?
Rasmus Althoff
https://www.ct800.net

Ras
Posts: 1381
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: The devilish fail low

Post by Ras » Sun Apr 05, 2020 9:12 pm

Dann Corbit wrote:
Sun Apr 05, 2020 7:54 pm
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.
Rasmus Althoff
https://www.ct800.net

User avatar
hgm
Posts: 24450
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: The devilish fail low

Post by hgm » Sun Apr 05, 2020 9:29 pm

Ras wrote:
Sun Apr 05, 2020 8:06 pm
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
Posts: 20896
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: The devilish fail low

Post by bob » Sun Apr 05, 2020 9:33 pm

Ras wrote:
Sun Apr 05, 2020 2:57 pm
Dann Corbit wrote:
Sun Apr 05, 2020 2:25 am
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
Posts: 20896
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: The devilish fail low

Post by bob » Sun Apr 05, 2020 9:34 pm

Dann Corbit wrote:
Sun Apr 05, 2020 7:26 pm
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
Posts: 20896
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: The devilish fail low

Post by bob » Sun Apr 05, 2020 9:36 pm

Ras wrote:
Sun Apr 05, 2020 7:48 pm
hgm wrote:
Sun Apr 05, 2020 3:37 pm
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
Posts: 1381
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: The devilish fail low

Post by Ras » Sun Apr 05, 2020 10:10 pm

hgm wrote:
Sun Apr 05, 2020 9:29 pm
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.

bob wrote:
Sun Apr 05, 2020 9:33 pm
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.
Rasmus Althoff
https://www.ct800.net

chrisw
Posts: 3114
Joined: Tue Apr 03, 2012 2:28 pm

Re: The devilish fail low

Post by chrisw » Sun Apr 05, 2020 10:49 pm

Ras wrote:
Sun Apr 05, 2020 10:10 pm
hgm wrote:
Sun Apr 05, 2020 9:29 pm
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.

bob wrote:
Sun Apr 05, 2020 9:33 pm
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
Posts: 1381
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: The devilish fail low

Post by Ras » Sun Apr 05, 2020 10:57 pm

chrisw wrote:
Sun Apr 05, 2020 10:49 pm
-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.
Rasmus Althoff
https://www.ct800.net

Post Reply