Salvaging a timed-out iteration

[AndrewShort]

Consider simple iterative deepening from the root.

Suppose after a depth 9 search it finds move 3 of 30 is best.

Now, during a depth 10 search, the iteration times out, say while searching half-way through, through move 15.

My code uses the best move from the depth 9 search (move 3).

but suppose in the depth 10 search, before the time out, it found move 4 of 30 had a better score backed up to the root.

Do I do move 4, or stick with move 3? Seems like a no-brainer to use move 4. Am I missing something?

[hgm]

You are not missing anything; to the best of your knowledge move 4 is better than move 3, as both have been searched to the same depth.

Joker uses the best move found so far from an incomplete iteration. It gives extra time to finish the iteration, though, if the score of this best-so-far move lies significantly below the score of the previous iteration. If you have the coice between having more time left for your remaining moves, so they might be better, or playing a move that you are sure will get you in trouble on the board, it is usually better to avoid playing a bad move now.

Of course you start by searching move 3, so even if no other moves have been searched at all, you won't pick a disastrously wrong move.

[AndrewShort]

ahh, I see. To keep things simple, I could do this:

If a 9 ply search completes and finds Ra1-a5 is the best move, then in the next iteration, a 10 ply search tries Ra1-a5 first (principal variation from previous iteration is sorted first), but then 10 ply iteration times out, I should use the best move from the incomplete 10 ply search (which might not be Ra1-a5 anymore), even if that best move yields a score worse than Ra1-a5 did from the 9 ply search, since the deeper search is more accurate.

I can't believe I didn't think of this. I've been needlessly throwing away the work of incomplete iterations...

[Tord Romstad]

I can't believe I didn't think of this. I've been needlessly throwing away the work of incomplete iterations...

Yes. You just got a lot of Elo points essentially for free. Congratulations!

A somewhat related question I have been thinking about recently: What should we do in case of a timeout during a fail-high re-search at the root? Always playing the move that fails high is far too risky. I've tried it a few times, and not surprisingly, the results are disastrous. But perhaps playing the move that fails high is still a good idea if we are in a sufficiently desperate situation? If the current root score is very bad, the best move found so far is probably losing, so we don't risk all that much by playing another move which shows some evidence of being stronger.

Has anyone tried this?

Tord

[AndrewShort]

and in that case, should the engine report a "depth searched" of 9 (the completed iteration), or 10 (the incomplete iteration). You could argue both, but 10 is a little misleading...what do you do? (assume you do not report any extra depth from Quies(), as I do)

[bob]

Consider simple iterative deepening from the root.

Suppose after a depth 9 search it finds move 3 of 30 is best.

Now, during a depth 10 search, the iteration times out, say while searching half-way through, through move 15.

My code uses the best move from the depth 9 search (move 3).

but suppose in the depth 10 search, before the time out, it found move 4 of 30 had a better score backed up to the root.

Do I do move 4, or stick with move 3? Seems like a no-brainer to use move 4. Am I missing something?

Why would you_not_ use that move? You already know that searching 1 ply deeper, it is better than the move you would play if you played the move from the last complete iteration. So yes, there could be even better moves and you don't have time to discover them, but why would you knowingly play a _worse_ move? And you know that the previous best move is worst than move #4 at the current depth because you searched both.

[bob]

I can't believe I didn't think of this. I've been needlessly throwing away the work of incomplete iterations...

Yes. You just got a lot of Elo points essentially for free. Congratulations!

A somewhat related question I have been thinking about recently: What should we do in case of a timeout during a fail-high re-search at the root? Always playing the move that fails high is far too risky. I've tried it a few times, and not surprisingly, the results are disastrous. But perhaps playing the move that fails high is still a good idea if we are in a sufficiently desperate situation? If the current root score is very bad, the best move found so far is probably losing, so we don't risk all that much by playing another move which shows some evidence of being stronger.

Has anyone tried this?

Tord

Done right, there is no risk. At the root there are two types of fail-high moves, assuming you are doing aspiration search and normal PVS with null-move.

1. You search a move and it fails high on the aspiration search, which means the search is better than your original estimate. Playing this move without completing the re-search has no risk at all.

2. You search any but the first move and get a fail-high on the null-window search. This move is not safe to play until you research and at least get a fail high on the original beta (aspiration) bound. null-window searches can fail high on the null-window search, but the actual move might not have a better score and might well fail low on the re-search. I do not accept a null-window fail-high at the root as a new best move until the research proves this with either a better score or a fail-high on the aspiration window...

And I have had zero problems since I started handling case 2 properly as above. Trusting the null-window fail-high will absolutely wreck you at times, which is troubling but a fact of search.

[bob]

and in that case, should the engine report a "depth searched" of 9 (the completed iteration), or 10 (the incomplete iteration). You could argue both, but 10 is a little misleading...what do you do? (assume you do not report any extra depth from Quies(), as I do)

The move and PV came from depth 10. So it is a 10 ply search...

[hgm]

Done right, there is no risk. At the root there are two types of fail-high moves, assuming you are doing aspiration search and normal PVS with null-move.

1. You search a move and it fails high on the aspiration search, which means the search is better than your original estimate. Playing this move without completing the re-search has no risk at all.

2. You search any but the first move and get a fail-high on the null-window search. This move is not safe to play until you research and at least get a fail high on the original beta (aspiration) bound. null-window searches can fail high on the null-window search, but the actual move might not have a better score and might well fail low on the re-search. I do not accept a null-window fail-high at the root as a new best move until the research proves this with either a better score or a fail-high on the aspiration window...

Something seems to be inconsistent here. You don't specify how much the aspiration beta has to be above alpha. By sheer coincidence you might have picked an aspiration threshold that is only 1 higher than the score of the PV move. Then the two cases become the same.

Why would you trust that failing high above an aspiration threshold would indeed mean the score is above this threshold, and not for a fail high only infinitesimally above the PV score? Should there be a safety margin? If so, how large does it have to be?

It seems to me that a move failing high might have obtained its score from a branch that contains an appriciable number of null moves, and as a consequence might have been reduced so much that it missed arbitrarily bad trouble that was suppressing the PV score. That does not change merely because bound compared to which you fail is different.

[bob]

Done right, there is no risk. At the root there are two types of fail-high moves, assuming you are doing aspiration search and normal PVS with null-move.

1. You search a move and it fails high on the aspiration search, which means the search is better than your original estimate. Playing this move without completing the re-search has no risk at all.

2. You search any but the first move and get a fail-high on the null-window search. This move is not safe to play until you research and at least get a fail high on the original beta (aspiration) bound. null-window searches can fail high on the null-window search, but the actual move might not have a better score and might well fail low on the re-search. I do not accept a null-window fail-high at the root as a new best move until the research proves this with either a better score or a fail-high on the aspiration window...

Something seems to be inconsistent here. You don't specify how much the aspiration beta has to be above alpha. By sheer coincidence you might have picked an aspiration threshold that is only 1 higher than the score of the PV move. Then the two cases become the same.

Why would you trust that failing high above an aspiration threshold would indeed mean the score is above this threshold, and not for a fail high only infinitesimally above the PV score? Should there be a safety margin? If so, how large does it have to be?

It seems to me that a move failing high might have obtained its score from a branch that contains an appriciable number of null moves, and as a consequence might have been reduced so much that it missed arbitrarily bad trouble that was suppressing the PV score. That does not change merely because bound compared to which you fail is different.

My aspiration window is always score +/- N. Where N is roughly 1/2 a pawn... I suppose that circumstance _could_ happen in a rare case, but I hav enot seen it. I have a program to specifically scan logs for that (among other things) since it has been a known issue, and while I don't scan all logs, I did do several thousand and did not find a case where it would be a problem... That is fail high at the root where the previous best score was aspiration-beta - 1...