Null move, futility and LMR

[H.G.Muller]

I have been thinking of the various techniques to chop some dead wood off the search tree. The following idea has appeal to me:

Basically I want to get rid of branches where the losing side, playing the all nodes, sacrifices more and more material in his all-attempt to get even. When the losing side is playing his bad captures, null moves are not a very good defence: to prove that the captures are losing I must recapture, and although I gain material I don't benifit from the reduction that the null move would bring. Yet there seems to be every reason to reduce such branches.

It thus sounds more as something where late-move reductions could be of use. Reductions, however, are pruning decisions taken early in the branch, long before you reach the point where you actually do the pruning, and a lot could happen in between. So I'd rather take the decision to prune at the point where you do it, so I can make sure that it is still justified. The justification to terminate the search for branches of the type I am discussing would be some kind of futility argument: the losing side is so much behind, that it is unlikely he will be able to get back in window in the remaining plies. If, against all expectation, the play upto now was a brilliant series of sacrifices, I leave it to a deeper search to find it.

The farther the score is out-of-window, the more plies you can prune. Current evaluation is a bad measure for this, however, since there might be hanging pieces. You wouldn't want to discard a node if the side to move, although behind in current eval, can do a good capture, or make a grave threat that could bring him back in window (e.g. give a check). Such moves are far from futile. It is not so easy to recognize statically if there are moves available that make a threat, though. So pruning simply because the stm has a bad eval seems too early.

One ply later, good captures the losing side might have played are already incorporated in the current eval. The winning side now has the move, and if it still is far above beta, we have a pruning candidate. We still have to worry about the last move being a grave threat with the potential to annihilate our advantage. Typically the first thing we try with eval>=beta is a null move, and if there is such a grave threat, it will detect the threat by failing low. So this is a natural place to take the decision.

Suppose we act on the idea that it is unlikely that the opponent will be able to gain consistently more than a full piece in every one of his remaining plies. Say we are ahead more than 3 pieces (eval > beta + 3PIECES), because he blundered away a Queen somewhere on the road... If a QS after null move shows that he has no threats we could prune this node if there are 6 or fewer ply remaining search depth left. (Perhaps even 8, for the fact that there was no threat proves that he cannot gain anything in his next ply, so he would have only 3 plies to capture three pieces.) For d=6, ordinary null-move pruning would require a d-R-1 = 2-or-3-ply search to achieve the same, quite a bit more expensive than a mere QS. Basically, the whole idea shows up as null-move pruning with an extremely reduced depth for the null-move search.

The downside is that, in order to prove that there is no threat when eval is so much above beta, you would have to enlarge the window for the null-move search to {beta-1, beta+3PIECES}. A QS with this larger window will still be enormously cheaper than a deeper search with the usual null window {beta-1, beta}, though.

If the null move fails low, you know that it will probably be a waste of time to try a deeper null-move search. Apparently he has an immediate threat that is so great that, despite our lead, we cannot afford to ignore it. If we get an in-window score for the null move, we know that he has some threat, but not grave enough to get even. In that case we should choose between a normal null-move search at depth d-R-1, or try a normal move to nullify the threat.

Note that a succesful threat-evasion would preserve our 3-piece lead (or even increase it, if we are dealing with a phantom threat where we can simply capture the hanging attacker). So although it will be formally searched to 6-ply, almost every reply to it that doesn't capture more than a piece will be pruned by the proposed mechanism. So it will be more like a 2-ply search. A reduced null-move search might just start with a marginal advantage (if his threat was to capture a Queen back), and might have to run to its full depth d-R (i.e. 3 or 4 ply).

For a minor threat the null move might start from an advantage so big that it will also be further reduced trough this mechanism. So what the optimal choice is for the refutation move depends on the magnitude of the threat that the 1-ply null-move search revealed, and on the other hand, if the threat can be refuted at a gain, or merely ameliorated to a smaller loss. Basically, you can expect 2 ply to be pruned of the end of every search for every piece difference between ignoring the threat or refuting it, and you would have to weigh that against the R-ply reduction of the null move.

If you have a good capture on the attacker, I would certainly prefer that over null move, since even winning a Pawn versus losing a Pawn above beta is already nearly good for those 2 ply of extra pruning. Letting a piece capture with impunity (even if the material gain itself is futile) is usually a bad idea, since it is likely to create a lot of tactical trouble in the new position, plus that it weakened your own defense.

[Michael Sherwin]

Hi H.G.,

I have done a lot of thinking along these lines. I always reach the same conclusion. And that is null move is very cheap and reducing it further does not save much time. Almost all bad lines are pruned by null move. There are millions and millions of good for nothing, do nothing moves that are inside the alpha beta window that should be able to be pruned, however, no one has figured out a way to do that yet. I think that there is some merit to Botvinnik's algorithm for computer chess, if it is adapted to alpha beta. His basic idea was to look at all attacks and negations in an N ply horizon. So, if a piece could be moved to a square that makes a NEW attack it is included or if it can then be moved to another otherwise unreachable square that makes a new attack it is included. This is repeated up to the limit set as the horizon. This is a very simple explanation of his algorithm. It is sort of like giving one side several moves in a row to see if a move can be dangerous when combined with others. If a move is not considered dangerous by this algorithm and has no other redeeming features then it is just simply not included in the main search. Just a thought. The translator of Botvinnik's paper is N. A. Krinitskii. I believe that the title was 'Chess, an Experiment' or something similar. It had a 1961 copyright. I wish that I could be more specific, however, I only posses a couple of copied chapters.

Mike

P.S. The Scope of the Task

"The second principle amounts to saying that we must find an approximate solution by limiting the problem. If we are to consider all possible attacks, the problem becomes impossibly difficult to solve. We have to limit the problem and look at only a few attacks and the corresponding negations. In other words, we must establish a horizon and deal with only those attacks that fall within it. Within the limits of the horizon the problem will be (or should be) solved exactly." -- Botvinnik!

[H.G.Muller]

I am not sure that this couldn't have a significant advantage w.r.t. usual null-move pruning. Because in the latter, you only have the benifit of reduced search depth in the null-move branch, but the cost of getting this benifit is that you have to play a very poor and often non-sensical move for it, that erodes your advantage. (It makes no sense to play null-move in a situation where you can recapture a hanging piece.) So you get the advantage of the reduction, but at the expense of reduced score margin, and a very complicated tactical situation. Leaving pieces of the losing side on the board where you could have avoided this will directly affect his branching ration, and it is the losing side playing the all nodes.

In the scheme above, you can play the natural refutation of non-sense moves: because of the extra material gain compared to a null-move refutation attempt, you will get the reduction anyway (at the end of the tree, and perhaps even a larger one), but in a tree that doesn't branch as much because the opponent is stripped of his pieces, and the pieces he has left are not in super-dangerous positions where they can do moves that might have very non-obvious refutations.

[Michael Sherwin]

I am not sure that this couldn't have a significant advantage w.r.t. usual null-move pruning. Because in the latter, you only have the benifit of reduced search depth in the null-move branch, but the cost of getting this benifit is that you have to play a very poor and often non-sensical move for it, that erodes your advantage. (It makes no sense to play null-move in a situation where you can recapture a hanging piece.) So you get the advantage of the reduction, but at the expense of reduced score margin, and a very complicated tactical situation. Leaving pieces of the losing side on the board where you could have avoided this will directly affect his branching ration, and it is the losing side playing the all nodes.

In the scheme above, you can play the natural refutation of non-sense moves: because of the extra material gain compared to a null-move refutation attempt, you will get the reduction anyway (at the end of the tree, and perhaps even a larger one), but in a tree that doesn't branch as much because the opponent is stripped of his pieces, and the pieces he has left are not in super-dangerous positions where they can do moves that might have very non-obvious refutations.

Then maybe a good idea would be to try the verification search first if there is a winning capture to start it off as that would reduce the tree size and then just accept the score returned without doing a NULL move. Only search to full depth if the returned score was less than beta. You will loose the mate threat extension in most cases. Maybe a search to one ply deeper than the null move would have searched would be good for some extra tactical advantage.

[H.G.Muller]

Yes, if good captures are as least as cheap to search (in terms of reduction) as the null move, there is no reason at all to try the latter first. In fact, a null move in a situation where you have a good capture is very unnatural, and simply asking for trouble. Humans would not try to refute a bad capture by a null move, in the analysis of a position. If you have an obvious way to recapture something, you recapture it, no questions asked...

Playing the natural refutation to silly moves should help to keep your own position sound, i.e. keep your obvious refutations to other moves intact, so that you will almost always immediately identify the cut move on the first try. Trying contrived refutations is bound to make the tree larger. If it seems preferable because your rules for reductions make the tree smaller in such a case, it can only mean that these rules are unsound, that they make you prune parts of the tree that were relevant, or that in the competing case they failed to prune parts of the tree that were irrelevant.

NMP seems to suffer from this: the null move in a highly tactical situation is not necessarily the move that most simplifies the position (unlike in quiet situations, where it is guaranteed not to introduce new tactic, and thus preserves the quiescence). Yet you award a reduction to the null-move search, and search the much simpler position after recapture (or other obvious refutations, such as withdrawing, defending or interposing on a threat) is done to full depth. This can't be optimal. The score of a position is only as reliable as the search quality of the worst searched move; extra effort going into the search of other moves is then largely a waste of time...

[Edsel Apostol]

Hi H.G.,

Your ideas are often good but we can't grasp it solidly. Can you provide maybe a pseudocode? Because in my case that's how I can understand better. I know a lot of people reading your posts would appreciate it.

Edsel Apostol

[H.G.Muller]

Code: Select all

#define MARGIN (3*PAWN_VAL)
#define R  2

Search(Alpha, Beta, Depth)
{
    if(eval >= Beta && Depth >= 3)
    {
        Val = -Search(-eval, 1-Beta, 0); /* QS-level search of reply */
        if(Val >= Beta + MARGIN*((Depth-3)/2) ) /* integer division! */
            return Beta;         /* hyper NMP (= verified razoring?) */

        Val = -Search(-Beta, 1-Beta, Depth-R-1);
        if(Val >= Beta)
            return Beta;  /* normal NMP */
    }

    for (ALL_MOVES)
    {
        Make();
        Val = -Search(-Beta, -Alpha, Depth-1);
        UnMake();
        if(Val > Alpha) {...}
    }
}


Note that the integer division rounds down (and can be implemented as >>1, which normally the compiler would do). Thus 3 and 4-ply searches will only be pruned by a null-move + QS reply (i.e. a 1-ply search of the null move) if they score above Beta. But 5- and 6-ply searches will be pruned by this 1-ply null-move search if they score above Beta+MARGIN, 7- and 8-ply searches if they score above Beta+2*MARGIN, etc.

If you don't score high enough to prune a very deep search, try normal NMP on a null-move search of the normal depth (=Depth-R). If, say, Depth=10, you would need to be a Queen ahead to savely prune. If it turns out you are only two Pieces ahead, don't try to get extra benifits at this point, search the null move to Depth=8 as always. Because in practice, for most replies to it, you will still be two Pieces ahead two ply later. The 1-ply null-move search you will do in that node will tell you so, and it will be enough to prune the 6-ply search that was left. So in practice, you won't have done an 8-ply null-move search, but only a 3-ply null-move search. Except, of course, if his reply to your first null move is a grave threat that he couldn't do in QS. Then in that node your 1-ply null-move search will not fail high enough to get pruning. Which is just as well, for in the case of a threat you wouldn't want to prune. You will complete that branch of the null-move search to make sure he is not on the way to get even.

Note that in the pseudo-code I assumed you would only do null-move pruning on nodes with Depth=3 or more. If you want to prune for even lower depth, you could do that too. Just make sure that the if(Depth>=3) only affects the first null-move search.

[Edsel Apostol]

Hi H.G.,

I tried your method on my program. I performed a fixed depth search at depth 12 on the starting position. I noticed an increase in number of nodes searched by 4.57 percent. I test it against the previous version where your method was not supported and the result is a 220 elo points decrease in strenght. I need more tests but the preliminary testing seems enough for me to conclude that it is not working for my program.

Best Regards,
Edsel Apostol

[H.G.Muller]

Amazing. I am very surprised that is could increase the number of nodes, since it always prunes when null-move pruning would prune, and very drastically prunes in some other situations as well. It is hard to imagine that the few extra quiescence searches that you do in nodes with a depth_left >= 3 would significantly add to the node count.

Perhaps it is because the pseudo-code I gave contains a not-so-smart inefficiency: if Depth==3 it would do the null move + QS pruning attempt, which is OK if it works. But if it fails low, it then repeats exactly the same null-move search with smaller window, which is simply a waste of time. It could have simply used the Val it already had. So it should do the hyper pruning attempt only if Depth >= 4, since for Depth==3 it simply degenerates to ordinary NMP with a needlessly inefficient search window.

I should experiment some with it: the whole idea was that this would cut branches where one side is so much behind that he can never get back in window. If it only does that, it should not affect the move that is played. If it gets weaker, it must obviously be so because it does play other (poorer) moves in some situations. So I should simply find such a case, and figure out which score-determining branch was cut off, to get an idea what the problem is.

[Edsel Apostol]

I will try to experiment with it further. I remembered I have read a similar idea from the old posts on CCC by the author of Rybka. I think it is worth the effort. Some ideas are just simply not working on a first try.