Threat extension

[hgm]

I have the following conceptual problem:

If at d=1 the null-move search fails low because it is refuted by a capture in QS (as opposed to a stand-pat), we have to do a real search. But most of the time a d=1 real search will be able to find a delaying tactic (e.g. a capture + recapture or threat + evasion on a high piece) to push the problem that made the null move fail low over the horizon. After the 2 ply delay, we can stand pat like there is no worry in the world.

So is it really useful to do the real search when the null move fails low at d=1? It seems doing so invites horizon effect. There seem to be several things one can do here:

1) Skip the real search and fail low. (Probably too pessimistic.)
2) Skip the real search and fail high. (Too optimistic, but at least saves time.)
3) Do the real search, (but will mostly give the same result as (2) even where this result is wrong, and so wastes time.)
4) Give an extention to see beyond the horizon if the threat is really solved. (Expensive and dangerous, as this has to be a two-ply extension to prevent the stand-pat, and thus entails the risk of search explosion. But it might be viable at d=2, where the same problem exists, but now a 1-ply extension would cure it.)
5) Give the 2-ply extension only on some selected tactical moves likely to be a delaying tactic, like captures or attacks of higher or hanging pieces. (Again risk of search explosion, especially for the counter-attacks.)
6) Assume a fail low, except for some moves that are text-book solutions to the threat detected by the null move (capturing attacker, withdrawing the threatened piece, interposing something, defending the attacked piece). This requires some Chess knowledge, though.
7) Introduce some kind of semi-extension, that forbids stand-pat at the end of the tree. I.e. order a d=2+ search (in stead of d=1 and d=2). Two ply deeper a d=0+ search remains, and such a search only searches captures plus null move. (So no stand-pat; the null-move score substitiutes for the stand-pat score.) The null move now checks if the threat is really gone.

Has anyone tried any of the above solutions? (And was this successful?)

[bob]

I have the following conceptual problem:

If at d=1 the null-move search fails low because it is refuted by a capture in QS (as opposed to a stand-pat), we have to do a real search. But most of the time a d=1 real search will be able to find a delaying tactic (e.g. a capture + recapture or threat + evasion on a high piece) to push the problem that made the null move fail low over the horizon. After the 2 ply delay, we can stand pat like there is no worry in the world.

So is it really useful to do the real search when the null move fails low at d=1? It seems doing so invites horizon effect. There seem to be several things one can do here:

1) Skip the real search and fail low. (Probably too pessimistic.)
2) Skip the real search and fail high. (Too optimistic, but at least saves time.)
3) Do the real search, (but will mostly give the same result as (2) even where this result is wrong, and so wastes time.)
4) Give an extention to see beyond the horizon if the threat is really solved. (Expensive and dangerous, as this has to be a two-ply extension to prevent the stand-pat, and thus entails the risk of search explosion. But it might be viable at d=2, where the same problem exists, but now a 1-ply extension would cure it.)
5) Give the 2-ply extension only on some selected tactical moves likely to be a delaying tactic, like captures or attacks of higher or hanging pieces. (Again risk of search explosion, especially for the counter-attacks.)
6) Assume a fail low, except for some moves that are text-book solutions to the threat detected by the null move (capturing attacker, withdrawing the threatened piece, interposing something, defending the attacked piece). This requires some Chess knowledge, though.
7) Introduce some kind of semi-extension, that forbids stand-pat at the end of the tree. I.e. order a d=2+ search (in stead of d=1 and d=2). Two ply deeper a d=0+ search remains, and such a search only searches captures plus null move. (So no stand-pat; the null-move score substitiutes for the stand-pat score.) The null move now checks if the threat is really gone.

Has anyone tried any of the above solutions? (And was this successful?)

This issue was described almost 20 years ago. There are several flavors, including the "null move threat detection which I used it in early versions of Crafty in fact, as you can find mention of this in the comments in main.c... It worked at shallow depths we were seeing, but as hardware got faster, it just burned extra CPU cycles that were better used elsewhere.

The general form of the idea can be applied anywhere. Whenever any move in the tree fails high, do an "offset window" null-move search (window is offset downward). If that fails low (doing nothing fails low, but on a lower window than normal) and this one move fails high, this might be a "single saving move" that is holding off some serious threat. The question is, can it hold it off indefinitely? The solution is to extend the move to give the opponent a chance to refute the move.

Whenever a null-move fails low or fails high, it tells you something. But sometimes, using that information adds greatly to the overhead with out returning an offsetting advantage...

[Harald Johnsen]

I think the usual situation of failing low on NM is when there is an hanging piece.


5) BM extension could help here. The same threat two times in a row. Note that extending one ply only can be enought if you extend on recaptures. I'm using a form of BM in the last Cyrano but frankly this thing can trigger a lot, so i'm not extending, i just search with the normal depth nodes that were reduced with lmr and that triggered BM ext.

7) this is what I am doing on PV nodes in qsearch (so nothing to do with NM, i know). I disalow standing pat when the score > alpha (ie a score that can be backed up to the root), if that happens i do a nm search (to detect threats), if there is threats if go back to search. The problem is that if you do that on non pv nodes this means that you do it when eval() >= beta, so too many times...

HJ.

[hgm]

I have thought some more about this problem, and I think my preference would go out to declaring moves that do not satisfy the criteria for a threat evasion (against the threat posed by the null-move refutation) futile at d=1 and d=2. So if at d=2 the null move fails low because it was refuted by an opponent move (From, To), I only allow searching of moves that have ToSqr == From, FromSqr == To, ToSqr on the ray From -> To, or the moved piece attacks To from its ToSqr. If none of those moves tops alpha, the d=2 node is declared a fail-low without further search.

Nice thing is that this does not interfere with depth If eval>=beta, d=0 (QS) nodes have a stand-pat cutoff. So a QS node can only find a cut-move when eval<beta. Even in the new scheme we can then upgrade the node to d=1, without actually doing a null-move search: we know that this null-move search would fail low on a stand-pat reply, and would thus not be refuted by a move. Hence, no threat would have been recognized even in a d=1 search, and all moves would have been searched. So in particlar the cut-move capture we found in QS would be a valid move at d=1 or d=2, and also cause a beta cutoff there. We thus can upgrade the QS result accordingly before committing it to the hash or passing it on towards the root.

Only at d>=3 we would search all moves after a null-move fail low. There is no danger of horizon effect then, as we will try another null move two ply later, and cannot fail high unless our move really solved the threat.

[Martin]

Perhaps I misunderstand something but I think this can easily go wrong because of multiple threats.
Suppose the nullmove is refuted by move A that wins some material but there is also another move B that leads to mate. Because move A already gives a cutoff this threat is not detected.
Now you will only do moves that defend against threat A but what about threat B?
It is possible that all defending moves allow mate and then you could end up with a way too low score for this node (if alpha is low).
If that score backs up to the root the engine might suddenly resign in a won position ..

[Tord Romstad]

6) Assume a fail low, except for some moves that are text-book solutions to the threat detected by the null move (capturing attacker, withdrawing the threatened piece, interposing something, defending the attacked piece). This requires some Chess knowledge, though.

Has anyone tried any of the above solutions? (And was this successful?)

Yes, I use solution 6, and it seems quite successful. I have an intermediate phase between the main search and the quiescence search where I only search a small number of moves at every node. I begin by trying a null move. If the null move fails low, I remember the refutation move. I proceed to search all captures, checks, passed pawn pushes, killer moves, moves that have performed particularly well in the past (I use history counters for this), and moves which have a good probability of defending against the null move refutation move (like moving or defending the piece captured by the refutation move). In addition to all this, I always search the first N moves, where N is a number which gets smaller and smaller when I get closer to the real quiescence search. In other words, I have a gradual, tapered transition from the main search to the quiescence search rather than a sharp border at depth == 0.

By default, this intermediate phase lasts 7 plies, but I have a UCI parameter for configuring it.

Tord

[hgm]

Suppose the nullmove is refuted by move A that wins some material but there is also another move B that leads to mate. Because move A already gives a cutoff this threat is not detected.
Now you will only do moves that defend against threat A but what about threat B?

The idea is this:

If threat A is already enough to make you fail low, defending against threat B alone will be futile as long as threat A still exists. Even if you find a way to prevent the mate, in your example, the opponent would still cash in on threat A, and that was enough to make you fail low.

You only have a chance to save your skin if you can solve both threat A and B with the same move. But that means it must be a move that solves A. So trying all moves that solve A, should find that move. When you start searching it, the search will discover that threat B no longer exists, and you get a good score.

[Martin]

Yes, you are right, after some staring I see it.

[hgm]

I guess only searching the evasions for the recognized threat is a bit too restrictive: You might have a good capture that makes the threat insignificant.

Ordinary futility arguments would lead you to search every capture with a victim more valuable than what you will lose after null move. (Or at least what is proven you will lose; the low-failing null move will only provide you with an upper bound.) But if, say, I stand to lose the exchange (-2), just capturing anything worth >= 3 is exactly what I want to avoid, as this will almost certainly seem to help, but, equally certainly, only by pushing the detected threat over the horizon (at d=1 or d=2).

But if I try a capture which has SEE >= 3, it is very likely to be a sufficient cure (or, more accurately, compensation) for the expected loss. So I should certainly search moves with SEE > pendingThreat.

Perhaps I should even do a re-search of the null move with window opened (by lowering alpha) far enough to be sure of the magnitude of the threat. As I only need this score for comparison with the SEE values of my good captures, I could defer that until after move sorting. I will have to sort the moves by SEE in this case, in stead of victim value, as the LxH or equal captures of a high victim, which I would normally search first, will now not be searched at all if SEE is not sufficiently positive (for LxH this might still be predictable from H-L, though). After this sort I know what my best SEE is, say +S. At that point I can then re-search the null move with lower window limit alpha-S in stead of beta-1. (This will only be a QS, so opening up the window is not extremely expensive.) The obtained score will then tell me which captures to search, and which to prune (if they are not at the same time recognized as threat evasion).