Horizon detection

[hgm]

Some kind of moves are ideal for pushing trouble behind the horizon. Checks are the best know. But also 'futile interpositions' on checks, which just throw unprotected material in the path of a distant check to delay an unavoidable mate can make it more difficult to see the mate coming. In both cases the moves are easy to recognize: you know when you are checking, and you know when you are evading a check by interposing a piece.

The problem is, what to do when you get a fail high on such a 'suspect' move when all other moves in that node fail low? Chances are that this is just because you pushed the trouble over the horizon, as it is very unlikely that, say, throwing a piece in the path of a checking Rook, can subsequently be taken by that Rook to renew the check, is going to solve anything. If you would assume that, you might as well have pruned the move before searching it. But you cannot do that, because in occasional situations such a move might help (e.g. because the sacrificed piece opened a path for another piece to come to the rescue), and with hard pruning you would never see that, no matter how deep you search. Of course you could extend the search by the number of ply that the suspect move and its typical refutation would take, but this can be very expensive.

[d]R5k1/5ppp/2n5/1b6/8/8/4rPPP/5RK1 w - - 0 1
So it would be nice if there was a way to know whether there is a danger a suspect move pushes trouble seen by non-suspect moves over the horizon. If the trouble is close enough that a shallower search on the non-suspect moves would have seen it at lower depth, and the suspect move gives you a fail high, you can be confident it really solved the problem. If the non-suspect moves would just barely see the trouble, and any lower depth would make them fail high, it would be better not to search the suspect move at all, and just assume it fails low, as more often than not an actual fail-high result would be in error.

The problem is: how can you know? I was thinking about the following system:

* When you find a cut-move at d=1 that is a capture, you declare that node 'OK'. (Because QS would have searched that move even at d=0.)
* When the cut-move in a d=1 node is a non-capture, but the static eval is >= beta there, you declare that node 'OK'. (Because a d=0 search could have stood pat there, to obtain the same result.)
* When all moves failed low at d=1, and static eval <= alpha, you declare the node OK. (Because QS could not have done any better.)
* In all other cases the move is not OK, as at lower depth it would have given the opposite result.

Then you back up that info toward the root as follows:
* A cut node at d > 1 is OK if any of the daughters searched upto and including its cut-move daughter would be OK.
* An all-node if OK only if all its daughters were OK.

This is not iron clad, but should be pretty good, as the cut-move of the lower-depth search should in principle be available as hash move from the previous root iteration. So this would immediately make any cut nodes at the current depth OK, even if the hash moves now fails low and we eventually found another one that happens to be not OK.

So at any node in the search that upto now hasn't failed high, we would have the information available whether a search at d-1 of that same node would have failed high as well. The interesting case is when one of the unsuspect moves that now fail low is qualified as 'not OK', meaning that any less-deep search would have failed high. Which makes it very likely that the suspect move, which we know will bring us to a position similar to the current, will also fail high, but fail low on deeper search. So we'd better prune it, which will both save us work, and give a more reliable result.

The next iteration, when all the non-suspect moves fail again low, they should all be OK (as failing low is what they did in the current iteration). At that point it would be safe to search the suspect move as well, as a fail high there then would mean that it apparently made some real difference.

[bob]

Chrilly Donninger gave one idea years ago.

when a move fails high, before doing anything else, do a null-move search with a negatively-offset window. If that fails high, all is OK. But if that fails low, you now have a conundrum. Playing the current move fails high and is good. Doing nothing (null-move) fails low and is bad.

The might mean that the current best move is the ONLY move that defends against (or holds off) the opponent's threat. To determine this, extend one ply and search just this move again. If it still fails high, just return beta as always. If it fails low, now you become suspicious and you could try several things, most expensive being search ALL moves here one ply deeper to see if one is better.

I have a version of Crafty that does this, but it, just like the SE version I worked on for such a long time, shows a complete wash in cluster testing. No gain or loss. It shows some pretty cute PVs in the right positions, but it does add some complexity. For no gain, I decided to stick with simple. But I carefully saved both versions so that I can return and test some more if a new idea comes to mind.

I think Chrilly's idea comes closest to addressing your horizon-effect moves. You could restrict this to near the tips, but it does also work inside the tree.

[hgm]

To determine this, extend one ply and search just this move again. If it still fails high, just return beta as always.

The problem is that in the context where I want this most badly (futile interpositions to delay an unavoidable mate enough not to detect it), I am already in a situation where the checks are extended. The suspect moves that fail high are the check evasions. And if I also extend those one ply, checks and interpositions can go on forever for free, and I get a very bad search explosion. (I should add that I am doing this for variants where pieces can be dropped, so typically the checked side has several pieces in hand, which each can be dropped on any square along the check ray.) I already tried a scheme where I only extend the suspected refutation of the interposition, where the former checker just captures to check again, and even that gave me search explosion. (But it could perhaps be ameliorated by more clever move ordering, which I did not do yet.) In addition, doing a null move when in check is not really possible. But I guess I can replace that by capture of the checker and withdrawal of the King all failing low.

So I am looking for ways to improve the accuracy by pruning moves, rather than extending them. Then you win both ways. But at some depth you would have to stop pruning, or you would have made yourself permanently blind to some rare, tactics. The problem is how to figure out at what depth it becomes safe to search the suspect moves without extension (or even with reduction). The problem is that these are moves that intrinsically have a low probability to be good, (like negative-SEE captures). So extending them is really the last thing you would like to do.

The same thing always bothered me about 'spite checks' (i.e. checks with negative SEE): non-sensical moves, that tend to eat large amounts of your nodes budget.

[bob]

To determine this, extend one ply and search just this move again. If it still fails high, just return beta as always.

The problem is that in the context where I want this most badly (futile interpositions to delay an unavoidable mate enough not to detect it), I am already in a situation where the checks are extended. The suspect moves that fail high are the check evasions. And if I also extend those one ply, checks and interpositions can go on forever for free, and I get a very bad search explosion. (I should add that I am doing this for variants where pieces can be dropped, so typically the checked side has several pieces in hand, which each can be dropped on any square along the check ray.) I already tried a scheme where I only extend the suspected refutation of the interposition, where the former checker just captures to check again, and even that gave me search explosion. (But it could perhaps be ameliorated by more clever move ordering, which I did not do yet.) In addition, doing a null move when in check is not really possible. But I guess I can replace that by capture of the checker and withdrawal of the King all failing low.

So I am looking for ways to improve the accuracy by pruning moves, rather than extending them. Then you win both ways. But at some depth you would have to stop pruning, or you would have made yourself permanently blind to some rare, tactics. The problem is how to figure out at what depth it becomes safe to search the suspect moves without extension (or even with reduction). The problem is that these are moves that intrinsically have a low probability to be good, (like negative-SEE captures). So extending them is really the last thing you would like to do.

The same thing always bothered me about 'spite checks' (i.e. checks with negative SEE): non-sensical moves, that tend to eat large amounts of your nodes budget.

When I did this (I think back around the 8.x versions, circa 1995) I used the deep thought approach of (two plies of extensions for every two plies of search) as opposed to just one ply of extensions per ply of search. So I could extend twice, once because of the check, second because the threat test says "be careful here".

I will add I don't do it today. And when I was testing it last year, I didn't do that either. If a move was already extended, the test was skipped completely. To limit explosion.

[zd3nik]

I'm also very interested in finding a cheep solution (even if it's not 100% fool proof) to horizon effect.

I'm having a little trouble following you're explanation though:

* When you find a cut-move at d=1 that is a capture, you declare that node 'OK'. (Because QS would have searched that move even at d=0.)
* When the cut-move in a d=1 node is a non-capture, but the static eval is >= beta there, you declare that node 'OK'. (Because a d=0 search could have stood pat there, to obtain the same result.)
* When all moves failed low at d=1, and static eval <= alpha, you declare the node OK. (Because QS could not have done any better.)
* In all other cases the move is not OK, as at lower depth it would have given the opposite result.

Then you back up that info toward the root as follows:
* A cut node at d > 1 is OK if any of the daughters searched upto and including its cut-move daughter would be OK.
* An all-node if OK only if all its daughters were OK.

When you determine your best move at d=1 is not OK that's where I get lost. Are you just setting a bit/flag on the move and continue to back it up the tree anyway? And then using this info to discard not OK lines in d>1 nodes when there are other lines that are OK? I'm guessing that's what you're saying but I can't seem to make the connection. Sorry, I can be dense as a brick wall some times. Could you perhaps provide some minimal psuedo-code?

[hgm]

'OK' here means that the move would have gotten the same fail (high or low) at depth d-1 as it got now, at depth d.

And I think you are right in not understanding it, because I seem to have it written down wrong. The condition in all-nodes is correct: an all-node is only all-node if all moves fail low. So if any of its daughters would change in the shallower search, it is enough to turn it into a cut-node, and thus is not OK.

But cut-nodes stay cut-nodes if they have one cut-move, and it does not have to be the same cut move as in the shallower search. In the current search we will search moves that fail low, until we find one that fails high, and then we take the beta cutoff and the entire node fails high. If that cut move was 'not OK', it would not have been a cut move in the shallower search. But if any of the moves that now failed low would have failed high in the shallower search (i.e. would be qualified as 'not OK' now), we would still have had our cut move, and the node would have still be a cut node. So a d>1 cut node is OK when the cut move is OK, or when any of the moves that failed low before we found the cut move was not OK. In my previous description I left out that 'not'.

The 'not iron-clad' part is that when all low-failing moves we searched before the cut-move would have been 'OK', and the cut move would have been 'not OK', we have not find a move yet that could have been cut-move for the shallower search, but that there still could have been a cut move for that search in the moves we now do not search, because we already took the beta cutoff that the shallower search did not have. So we cannot be sure the shallower search would have seen an all-node here. The assumption, however, is that if the shallower search would have had any cut move at all, it would have been promoted to hash move, and the current search would have searched it first. So that means we have already seen it in the current search, and thus also noticed it as a not-OK fail low, good enough declare the current node as cut-node both in the current and the shallower search, and thus 'OK'. This assumes the previous root iteration would have searched the current sub-tree at one-ply-lower depth, or that IID would have done that.

If that cannot be relied on, I guess the only certain way would be to not immediately take a beta cutoff, but continue searching moves at the lower depth after you found the cut move for the current depth. That would no longer be free, though. And it would probably be simpler in that case to first do a normal search at d-1 as a pilot search.

[hgm]

Perhaps trying to get this information for free is a bad idea. In a node where you are in check, if there is a hash hit on an entry from the previous root iteration, you would already know if at that depth it would fail low or high, from the score bound type. You could then search the all the non-suspect evasions at the current depth, and if they all failed low, while the hash hit was a fail high through one of the non-suspect moves, you know you are in trouble. Apparently there is tactics just at the horizon that could not be seen at a one-lower depth, so the suspect evasion will delay it enough to push it over the horizon. Thus you prune it.

If the hash hit would indicate a fail low, you would not mind searching the suspect evasion at the nominal depth, as enough depth would remain in the position after the two delaying ply, (expected to be essentially the same as the curent position), to make that fail low too. So if it doesn't fail low it must not be so similar as you thought, and the seemingly pointless sacrifice must have had an unexpected side effect that saved the day.

If one of the non-suspect evasions fails high at nominal depth, you of course never get to the suspect evasions, as you take the beta cutoff.

If there is no hash hit, you could first search the non-suspect evasions at one-lower depth. If that provides a cut-move you would immediately start searching the non-suspect evasions at the nominal depth, starting with that cut move (as usual in IID), remembering that you failed high at lowered depth, and pruning the suspect evasions (if you still get to them). If the pilot search would have failed low, you would normally search the suspect evasions, and believe any fail-high they produce, taking it as evidence that the suspect evasion somehow breaks the equivalence with the current position.

That leaves the case where the hash hit indicated a fail high on the previous iteration, with a suspect move as hash move. The move could only have become hash move when it was first cleared by the above procedure, because non-cleared suspect moves would be pruned, amaking it impossible for them to become hash move. So it would be safe enough to trusts its fail-high.

What to do if a suspect hash move fails low? The move must have been 'cleared' in the in-check position when the latter was searched at depth d, by showing that all non-suspect evasions failed low at d-1, so that suspect evasions are still expected to fail low at d. That did not only hold for the evasion that happened to fail high against expectation, and thus became hash move, but for all suspect evasions. So the fact that a suspect evasion has become hash move implies that all suspect evasions have in fact been cleared, and are not expected to delay matters enough to make their search at nominal depth unreliable. So there is no need to treat the node in a special way.

The cost of this scheme is an extra d-1 iteration from the in-check moves for which you have no hash hit. A partial one, because you only have to do it for the non-suspect evasions. And you only have to do it when there are suspect evasions as well. This is still not more expensive than doing an extension on the suspect evasions (which would be a d+1 search on the position after them, as the evasion is free), and even than the scheme that would just extends the expected refutation of that suspect evasion (which would be a search of depth d for every suspect evasion).

It is a pity you cannot do that d-1 iteration only in cases that the d iteration on the non-suspect evasions failed low, so that you know it became relevant. Because hash hits would then just return you the result of the d iteration. Of course you could temporarily spoil the hash key to prevent such hash hits. OTOH the d-1 iteration might prime the d iteration in a useful way, providing hash moves and killers, so it isn't really clear it would cost you anything at all.

[PK]

If You think about games like Shogi, perhaps You may check whether several drops of different pieces on the same undefended square, including at least one non-metal piece, fail high in a reduced depth search. Only if it is the case, apply more expensive routine.

[hgm]

Well, I am thinking of Shogi, but I am not sure what you mean. Futile interpositions will delay the original trouble you would see without them even at the original depth. At reduced depth that will only be worse. It could be that despite of pushing the original trouble (usually that you get mated) beyond the horizon, the suspect evasion would still fail low, because such drops are an immediate sacrifice of the dropped piece. And perhaps that sacrifice already pushes you below alpha. But usually it doesn't, because the opponent started the branch by sacrificing lots of material to break open our King fortress, which we all got in hand, and are now merely feeding back to him, so it would take a long time before he again breaks even compared to a branch where nothing happened.

I guess in principle it should be easy to see in advance whether unprotected drop + capture would push us below alpha (while in check). But when that is the case searching at nominal depth will not be much more expensive, because after the opponent pushed us below alpha and we evaded the check in the first 3 ply, he can start to null move, quickly eating away the depth.