Horizon effect

[hgm]

I am getting a bit tired of the following pattern, during interactive analysis: I have a nice PV, and at some high depth D it turns sour, and the score plumets. In the same iteration it then gets replaced by a bad capture. Because if the opponent 'wastes time' on the recapture, it can re-play the old PV after it, and because two ply where burned in the exchage, it now doesn't get to the depth where the score collapses. So you only lose the material sacrificed in the first two ply, rather than experiencing the score drop of the PV. And when the opponent just ignores the capture, and goes on with his plan that crushed your previous PV, you do experience the score drop, but get the value of the piece you captured without retaliation as consolation. So whether the opponent recaptures or not, the losing capture looks better than your old PV at this new depth, and becomes the new PV. And if you don't find any move that truly pre-empts the problem to supercede it, it will end as best move for the iteration.

Of course two iterations later that new PV will experience the same score drop as the previous one, the pointless sacrifice it started with just adding to the misery. Humans, who do not search fixed-depth, immediately understand such things. So when I see such a thing happen, I know I have to let the analysis run two more ply to get a realistic score. If it happens at a time where my patience was already running out, this is very inconvenient, though. Of course I can intervene here, and force the sacrifice and its recapture, in order to analyze the position after those to depth D, (to verify the sac was indeed pointless, and that the score eventually plummets the same way), and then back-propagate this score to the original position, and only then start the analysis there. This would in general be faster even that analyzing the original position to depth D+1, where I probably still would get the silly sac. Or I can, when I am confident the move is bogus, exclude it from analysis to begin with. (Which saves time, but entails the risk that my judgement was wrong.)

I wonder if it would not be beneficial to automate this procedure. In any PV node. Normally you would already sort bad captures to the very end of the move list. So if you are in a situation where
1) The score of the hash move is far below the score of the node for the previous depth (as seen from the hash score or through IID)
2) None of the moves that were not bad captures did much better
3) We get to a bad capture that superficially (e.g. SEE-based) loses less than the score drop
We could then extend the line of that bad capture plus following recapture by 2 ply. For each bad (but not too bad) capture this would be about as expensive as the search of the node itself would have been without such extension, (we search another node at the same depth). So if we have three bad captures fitting the profile, it quadruples the cost of the node. It might still be a bit cheaper than searching the bad capture itself with an extension of 2 ply, because when the recapture fails low against expectation, you would not extend other possible refutations. (If the recapture does not refute it, the qualification as SEE-wise bad capture is apparently undeserved, and there is no reason to treat it any different from the other moves.)

Of course it is somewhat unsatisfactory having to spend lots of nodes on (suspected) bad moves, just to reject those. The normal procedure would be to reduce suspected bad moves. But in this situation that would almost never work, as the reduction only helps to make the search blind for the trouble that lays ahead, and thus fail high. (After which it would be re-searched at full depth, and still fail high, because the delaying tactics effectively reduced the depth as well.)

It seems much cheaper to do this extension, than to allow the worse-than-pointless delaying tactic to become PV, though. The extension should be considered a partial look-ahead to the next two iterations, and is a one-time event. In the next iteration the old PV (which now stayed PV) would normally not experiece a new score drop, so the bad capture would not be treated in a non-standard way. It might even get reduced, but that doesn't matter, because it will hit upon the hash entry from the previous iteration, which is of higher depth than requested (and of sufficient depth to see the trouble). So you will earn the invested time back in the next two iterations. And if there are no such iterations, it would usually have prevented you from playing a blunder.

The alternative would be to prune the move for this iteration and the next. This of course makes the search cheaper, but it is a bit more risky. Perhaps the classification as 'bad capture' in this case should not be based merely on SEE, but on a shallow search that proves it loses material compared to the current evaluation (e.g. with a null window 1 Pawn below the current evaluation). SEE-wise bad captures can sometimes gain material, by destroying a protector, or luring away an overloaded one. And it would be bad if such profitable moves were pruned. Making sure the move will also be pruned when you revisit the node in the next (root) iteration is tricky. The best way to achieve this is probably to fake a hash entry for the position after the pruned move, with draft D, and a -INFINITE score, so that it will fail low in the next iteration.

[Evert]

This only helps with a particular type of delaying tactic though. What about spite checks? I guess the check extension helps a bit there.
The idea I thought you were going to go for is to try to "graft" the old PV (which you know or can store in some datastructure) after the recapture (or after whatever reply you get to your delaying move).

[cdani]

In Andscacs I have a capture extension only for the main pv, that probably helps a bit to solve this. I cannot get rid of it withouth losing strenght, probably because all the other search stuff is accomodated to it. I have the feeling also that helps specially in long time control games. In stc is clearly bad against other engines because this extension forces Andscacs to see and reject a lot of stuff in the first iterations.

[Evert]

Interesting. Just what constitutes "long" and "short" time control here?

[cdani]

Interesting. Just what constitutes "long" and "short" time control here?

For a few seconds games this extension is definitely bad, it will never pass Stockfish stc nor even ltc testing.
Probably this "badness" extends to games of a few minutes, but just a feeling.

[hgm]

This only helps with a particular type of delaying tactic though. What about spite checks? I guess the check extension helps a bit there.
The idea I thought you were going to go for is to try to "graft" the old PV (which you know or can store in some datastructure) after the recapture (or after whatever reply you get to your delaying move).

For checks the check extension ameliorates things a bit, but not completely. You would recover in the next iteration, but still it would switch PV to the check, and then back, which also represents a lot of wasted search.

But you are right, other delaying tactics, like an attack on a high piece with a low one, or on an unprotected piece, could cause the same problem. But unlike bad captures, they don't necessarily commit you to a material loss. Only when they are unsafe, e.g. you attack a Queen with a Knight that can be immediately taken by a Pawn. So the criterion would actually be SEE < 0, whether they are captures or non-captures.

Grafting the tree is still an idea that I like, but I haven't had much success with that yet. The idea was to graft the undelayed 2-ply search results in the leaves of the sub-tree after the delaying tactic. But is is apparently difficult to make the 2-ply results survive in the hash table, when the search gets deep and the delaying tactic takes place close to the root. And if some of the leaves are not grafted, the search seeks shelter there. (And the side that plays the cut-nodes cannot steer away from it, because altering its moves brings it in uncharted territory, where it cannot fine any grafts at all.) It is also cumbersome to avoid the side that caused the delay breaks the analogy by a move with the piece involved in the delaying tactic. Forcing the search to go 2 ply deeper would work in all the leaves. And although expensive, it would be earned back in later iterations; it is just work moved up-front, and thus eventually free. (It just delays the completion of the iteration where the problem occurred, but probably causes the result of later iterations to be available faster, bcause you saved work on needles PV switching.) The result of it is saved at the root of the sub-tree, which survives quite easily until when it is needed again. The analogous tree that was the source of the grafts can still be used to probe for supplying cut-move candidates.

[cdani]

Another generic way to help on this is using tables of refutation moves related to sequences of moves, as they are independent of the previous moves of the sequence.
Normally they are about short sequences, but something larger can be tried.

[hgm]

Yes, this can be useful for finding cut moves. But it won't help to get extra depth. While the cut moves of the tree that did not suffer the delaying tactics would only work as cut moves if they are searched to the same depth (i.e. without deducting the plies in the delaying tactics).

[Rebel]

Regarding the horizon effect, anyone ever tried to jump back into the main search (taking an extra ply) after the return from QS for specific (tactical) situations?

[Nordlandia]

Show an position were horizon effect is still present today.

Example position.