The devilish fail low

[Ovyron]

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.

In my experience as someone that matches my engine against pretty much the same engine in much faster hardware online, this is a losing strategy. Sometimes my opponent has a fail high and my engine takes another 6 moves before having a fail low. By then there's no saving move because the blunder was played ages ago, so taking time trying to find a saving move is suicide.

I've been able to save -2.00 disadvantage positions against people out-searching me by 10ply, and that would have been impossible without enough time in the clock. If the opponent is superior (only superior opponents cause you a fail low) and you haven't made a decisive blunder yet (if you have what you do makes no difference) you better save enough time on the clock to play the rest of the game, because without it you're going to fail to draw a drawn position because of the rate needed to play your moves (0.00 positions that are lost by the clock.)

[hgm]

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.

All the positions along that 24-ply PV will be in the TT with the disastrous score (bound). You will even hit upon it in a 1-ply search. When you probe the TT after the old PV root move you will get a hit on an entry with d=23, telling you the move is no good.

One must actually be careful to sensibly compare depths from the fixed-depth search with those from the reduced source. There might be a solution through an alternative move that branches from the PV at ply 3 or 5, and you don't want to be shielded from that by taking hash cutoffs until the fixed-depth search reaches 25 ply (which it will of course never do). So you could count the drafts of the TT entries created during the reduced search as (say) 1/6. Then you would no longer accept the TT cutoff after 1 ply when your fixed-depth search reaches d=5 (because 23/6 < 4). But the bad PV score would still not go away, because then it will picked up at ply 2 (because 22/6 > 3). At the tips of your fixed-depth search, where d=0, you would accept any result from the previous search.

That the TT scores are 'not true' is too vague a generalization. A very deep reduced search will likely contain the entire tree of a shallow fixed-depth search, (most reductions only kick in above a certain depth), and will thus be more true.

[Ras]

So you could count the drafts of the TT entries created during the reduced search as (say) 1/6. Then you would no longer accept the TT cutoff after 1 ply when your fixed-depth search reaches d=5 (because 23/6 < 4).

That's reasonable, but it doesn't address my question. The PV with the bad score is at depth 24 in this example because that's how far you need to look ahead to even see the looming problem.

Now if you branch off of the PV let's say at ply depth 3, but now you can only look ahead up to depth 10, then you're back to my question. The issue is that the problem is outside the no-pruning horizon, and therefore, the no-pruning search has no way to tell whether its alternative move choice will really solve the problem, or merely avoid looking far enough to even notice it. The TT is not overly helpful here because the idea is to explore branches that don't have TT entries because they had been pruned previously.

Also, it's not useful to explore along the PV because that is the result of the pruning search we have just decided not to trust. On top of that, if the exploration result is that the previously chosen root move is actually fine after all (which the no-pruning search can't actually tell, see above), then the effort has been in vain because the reply move is the same anyway. Only if the result is another, better root move, we have changed the game.

The final kicker is that the whole reason for the pruning is because looking ahead further (though in less detail) results in stronger play. Given that chess is highly tactical, even 30 good moves will lose the game if followed by a blunder. So "stronger play" means it's consistently stronger throughout whole games. Reducing the pruning would be like a master in trouble considering to ask an amateur for advice on how to continue.

[Dann Corbit]

The tree is not symmetrical. A branch can be pruned (for instance) because of null move or LMR or a number of other reasons. So a depth 24 search may be very shallow along certain branches.
Now, simply switching to pure alpha-beta would have very limited use. For instance, if there was a very close-by improvement that was pruned due to (for example) null move but the position was zugzwang.
That is why I suggested zero window searches.
But I do not really know if either method has any merit.

It stems from observations where very strong engines fail to see (for example) mate in 12 after a lengthy search.
Generally, the strongest engines will find it anyway after enough fail lows cause alternative paths to be searched.
But it would be nice if I did not have to analyze for an hour with 60 cores on a mate in 12.

There is a similar problem with winning positions where a powerful engine finds a draw with material down.
Sometimes, it will never see the mate (or at least not in any sort of reasonable time).

There may be no simple solution for difficult positions of this sort, and I was really just interested to see if anyone has tried these sorts of things.

One approximate analog was the original Rybka Winfinder, which did zero window searches with a quarter pawn above the best score. I extrapolated that by watching the searches, and I believe that Vas confirmed it, but I may remember incorrectly.

[hgm]

That's reasonable, but it doesn't address my question. The PV with the bad score is at depth 24 in this example because that's how far you need to look ahead to even see the looming problem.

The point is that in the reduced search the lines that were reduced to (say) 6 ply can already be seen to be bad at 6 ply. Or they would just have become the new PV move at 24 ply, when the old PV collapsed. You just hope that one of them would be less bad at the 10 ply you can give them now.

It seems a long shot, though, and I think the better strategy would be to just play the PV move of the 23rd iteration without trying to resolve the fail low in the 24th. There is probably a better chance that the opponent will not reach 24 ply on this line, than that one of your alternative lines will recover. If these alterative lines can be seen to be bad at 6 ply already, you can be sure the opponent will know how to punish them. It is the same silly idea as trying to postpone being checkmated one move by a spite check Qxh7+. Even a random mover would most likely reply Kxh7, and after that the checkmate is as close as ever, and the only thing you have achieved is that, now being a Queen down, you have also guaranteed a loss if he doesn't see the mate.

And the opponent might be pondering. So the longer you spend on figuring out exactly how he can best demolish you, the larger the chances that he will see it too!

[Ras]

The tree is not symmetrical. A branch can be pruned (for instance) because of null move or LMR or a number of other reasons. So a depth 24 search may be very shallow along certain branches.

Sure, HGM pointed that one out. But the thing is, if you see a problem at the main 24 horizon, you have no way to tell at the depth 10 horizon of less explored branches that the 24 horizon problem has gone away in that branch. And if you switch off the pruning, you can't tell that for any branch anymore.

That's why switching off pruning would be like "if I close my eyes, I can't see the problem anymore, so I'm happy now".

For instance, if there was a very close-by improvement that was pruned due to (for example) null move but the position was zugzwang.

You don't do nullmove in endgame positions, i.e. when the number of pieces other than kings and pawns is low. True, there are positions like the final one in Nimzowitsch's famous zugzwang game from 1923 against Sämisch with zugzwang despite a lot of pieces, but that's so rare that caring about that would be a net Elo loss.

That is why I suggested zero window searches.

But that's what the scouting does anyway, zero window search with alpha/alpha+1.

But it would be nice if I did not have to analyze for an hour with 60 cores on a mate in 12.

With a non-pruning engine, you wouldn't reach 12 moves, i.e. 24 plies anyway. Except if said mate is basically a series of checks that are extended - but that's what pruning engines do, too. Extending is really just the other side of the coin from reducing. The search tree is the same.

[Dann Corbit]

That is why I suggested zero window searches.

But that's what the scouting does anyway, zero window search with alpha/alpha+1.

I was suggesting zero window searches with alpha + margin/ alpha + margin + 1
Margin might be a fixed quantity, or it might be a goal.

[Ras]

You just hope that one of them would be less bad at the 10 ply you can give them now.

I see, but there are so many lines that might fit this bill that we can't verify even a fraction of them at the required depth without going back to pruning again. It's the worst kind of ignorance that an entity can suffer from - not even knowing what it doesn't know.

I think the better strategy would be to just play the PV move of the 23rd iteration without trying to resolve the fail low in the 24th.

That's what I do. If time is up, then it is up. The very least thing is that my engine is never losing on time because it would invest an insane amount of time just to resolve a fail low at high depth that might be only a pawn. Instead, I try to avoid the whole situation by giving more time in the crucial phase of the game, mainly from moves 12 to 22 or so.

There is probably a better chance that the opponent will not reach 24 ply on this line

That's also possible. Or that winning the endgame turns out to be too hard if the opponent isn't Stockfish with 7-man.

And the opponent might be pondering.

Good point, though not for the CCRL ranking list.

[Ras]

I was suggesting zero window searches with alpha + margin/ alpha + margin + 1

I tried that, and it didn't work well. Neither if you do that in all nodes in the tree nor for root moves only. What I wanted to resolve when I tried that is that the engine wastes a lot of time on improving the PV by 5 centipawns at the same main depth instead of going to the next main depth, as observed by oscillating PVs. Interestingly, this problem went away by itself with more pruning.

[Pio]

That's reasonable, but it doesn't address my question. The PV with the bad score is at depth 24 in this example because that's how far you need to look ahead to even see the looming problem.

The point is that in the reduced search the lines that were reduced to (say) 6 ply can already be seen to be bad at 6 ply. Or they would just have become the new PV move at 24 ply, when the old PV collapsed. You just hope that one of them would be less bad at the 10 ply you can give them now.

It seems a long shot, though, and I think the better strategy would be to just play the PV move of the 23rd iteration without trying to resolve the fail low in the 24th. There is probably a better chance that the opponent will not reach 24 ply on this line, than that one of your alternative lines will recover. If these alterative lines can be seen to be bad at 6 ply already, you can be sure the opponent will know how to punish them. It is the same silly idea as trying to postpone being checkmated one move by a spite check Qxh7+. Even a random mover would most likely reply Kxh7, and after that the checkmate is as close as ever, and the only thing you have achieved is that, now being a Queen down, you have also guaranteed a loss if he doesn't see the mate.

And the opponent might be pondering. So the longer you spend on figuring out exactly how he can best demolish you, the larger the chances that he will see it too!

Hi HGM

I Also thought about the time issue yesterday or the day before. One thing that I thought about is the reverse. What happens if the opponent suddenly uses a lot of time? Probably he has seen that he is in trouble. So if you have not seen something good you should probably spend more time when it is your turn.

I think you can make the problem less severe if you reduce asymmetrically. The more behind you are by evaluating an inner node the less you should reduce on your moves and the better you are in an inner node the more you should reduce. The reason is that if you are really good you do not have to find the best moves you just have to be sure the moves you do is good enough. This will also reduce the problem of that the history heuristics being self fulfilling.

Another thing that I do when I play chess and see that I am in trouble is that I look much deeper on checks, pawn storms and captures close to the opponent king to try forcing a threefold repetition.

/Pio