Null Move Pruning

[bob]

Drop the depth > 2. It makes sense to require depth > 1 since the reduction would be zero at depth 1 (but you can still use the result as if it were depth R+1 so it's at least worth testing, particularly with a condition like expectedTotalSearchTime >= currentTime * estimatedBranchingFactor).

8. value is >= beta, means we are doing pretty good already, value is the value from static eval of this node

This condition is theoretically sound for depth <= R + 1 since the opponent will just stand pat. At higher depths, you could have an unstoppable threat. Those are rare, though, and you might want to just let IID find them instead.

Changing those conditions deteriorates the 0 move success rate.

Time to depth is a better metric. Or nodes wasted in nullmove searches that seemed futile vs nodes saved in unexpectedly successful nullmove searches.

There is a danger if you don't do q-search checks. If you let a null-move search take you directly to q-search, it will fail high even if the opponent has a move that mates you instantly...

[tpetzke]

Thanks for your reply. I will do run some additional tests.

I did see some additional fail highs on null moves without the value >= beta condition, so just as you said, I used a similar counting approach.

On the other hand the null move search comes not for free. It might take some time and if it fails low, this time is wasted (even hash table positions stored might only be useful for other 0 moves as they will have the wrong side to move stored in).

So it was just a decision whether to try a null move anyway in positions where I can tell statistically it will most likely fail low (>90%). Does the 1 out of 10 cases saving justify the wasted efforts in the other 9?

As I use a full eval score (not only material) in the comparison I factor also a possible strong positional advantage of the side that does the 0 move already in.

I'm faced with a similar question when it comes to IID. When I enter a node I try to predict what type of node I'm in (ALL, CUT, PV). I measured how good this prediction performs and it's quite accurate (>90%). So do I use expensive IID for better move ordering in a node that is with a >90% probability an ALL node ?

But as stated, I put more tests on that on the ToDo list.

Thanks again

Thomas...

[mcostalba]

Try adding a counter to see how many times null-move fails high when material is equal, vs how many times it fails high when material is anything but equal...

This means nothing because it is obvious, you can run the same test for razoring, stand-pat or any other pruning scheme based on evaluation and get more or less the same numbers.

The real question is: "In what is different null search from other pruning facilities based on evaluation and its distance from beta ?"

The answer is that other schemes are unable to disciminate stable positions from positions where there is still activity and threats or, at least, are unable to discriminate in such a powerful and deep way as null search.

This is the key point. The fact that a stable position, when above beta, can be pruned is a natural and logical _consequence_, but we have to understand the difference between a key fact and its consequences.

[jwes]

The idea of the null-move is to quickly dismiss positions where you are way ahead.

No, this is the idea of, for instance razoring, where if evaluation says we are well ahead then we do a quick qsearch to confirm evaluation score against possible pending threats and then, if still well above beta we dismiss the node.

Sorry. Reread Beal's paper on null-move and the definition of "null-move observation."

But you do not want to try a null move if you are going to prune the node anyway.

Aim of null search is, IMHO, to detect stable positions. As example I can be even a knight ahead but if my queen is under threat then null search _never_ will fail high. Instead, I can be only half a pawn ahead but if position is stable, let's say we are in a close position, then null search will fail high.

Try adding a counter to see how many times null-move fails high when material is equal, vs how many times it fails high when material is anything but equal...

fail high mat good = 924928
fail high mat bad = 5315
fail high mat equal = 67696


good means that material, from the side-to-move's perspective, is > 0, bad is < 0, equal is obvious...

Another normal position, searched a little longer (above is a 10 second search):

fail high mat good = 2389828
fail high mat bad = 203534
fail high mat equal = 65463

and another for 60 seconds:



fail high mat good = 5443847
fail high mat bad = 1357425
fail high mat equal = 498747


over 90% of null-move fail highs occur when the side playing the null-move is winning.

Where are the other half of these numbers, the number of null-move attempts? Obviously, you only want to do null-move if you expect to save nodes by doing it, so you need the probability of a given null-move search failing low and an estimate of the ratio of the cost of the null-move search to the full search to determine if the null-move search is worthwhile.

I think the real plus of null search against a tons of other pruning techniques that are all based on the rule "if I am well ahead then there is no need to continue the search", the real plus is that null search is the only one that is able to discriminate stable positions from dynamic ones, i.e. positions where there is still tension and activity on the board and so need to be searched further.

It does show you which positions can be tossed out with much less effort, as shown above...

[bob]

Try adding a counter to see how many times null-move fails high when material is equal, vs how many times it fails high when material is anything but equal...

This means nothing because it is obvious, you can run the same test for razoring, stand-pat or any other pruning scheme based on evaluation and get more or less the same numbers.

The real question is: "In what is different null search from other pruning facilities based on evaluation and its distance from beta ?"

The answer is that other schemes are unable to disciminate stable positions from positions where there is still activity and threats or, at least, are unable to discriminate in such a powerful and deep way as null search.

This is the key point. The fact that a stable position, when above beta, can be pruned is a natural and logical _consequence_, but we have to understand the difference between a key fact and its consequences.

I will say it again. The _main_ benefit from null-move pruning is that it lets us recognize "winning" positions and spend less effort searching those, so that we can spend more time on the branches that are trouble. It has _always_ been based on that idea. AKA "the null-move observation". If I can let you make two consecutive moves and you can't cause me any problems, your position sucks...

Razoring and such are completely different, only applied near the tips of the tree, while null-move is applied all the way back to just below the root. So I am not sure what you are talking about there.

But my point was that _most_ null-move fail-highs (> 90%) are because we are in a winning position and our opponent can't do anything about it. Such as when he sacs his queen at ply=2 and gets nothing back even if he gets to make two moves in a row...

Yes, it fails high in other cases. But if you saw my data, it fails high in _that_ case the majority of the time, and that's where its significant benefit comes from.

Null-move is not pruning in the traditional sense. Things like futility and other forms of forward pruning just lop off a branch and never even consider the ramifications, while null-move simply reduces the depth but doesn't prune anything away where it could be ignored, except for a couple of plies of effort.

[bob]

The idea of the null-move is to quickly dismiss positions where you are way ahead.

No, this is the idea of, for instance razoring, where if evaluation says we are well ahead then we do a quick qsearch to confirm evaluation score against possible pending threats and then, if still well above beta we dismiss the node.

Sorry. Reread Beal's paper on null-move and the definition of "null-move observation."

But you do not want to try a null move if you are going to prune the node anyway.

I do not understand what you mean. We prune near the tips. We null-move reduce everywhere. You don't do a null-move search on a particular move, you do it on a position before you try anything else, including a normal search which might include forward pruning ideas...

Aim of null search is, IMHO, to detect stable positions. As example I can be even a knight ahead but if my queen is under threat then null search _never_ will fail high. Instead, I can be only half a pawn ahead but if position is stable, let's say we are in a close position, then null search will fail high.

Try adding a counter to see how many times null-move fails high when material is equal, vs how many times it fails high when material is anything but equal...

fail high mat good = 924928
fail high mat bad = 5315
fail high mat equal = 67696


good means that material, from the side-to-move's perspective, is > 0, bad is < 0, equal is obvious...

Another normal position, searched a little longer (above is a 10 second search):

fail high mat good = 2389828
fail high mat bad = 203534
fail high mat equal = 65463

and another for 60 seconds:



fail high mat good = 5443847
fail high mat bad = 1357425
fail high mat equal = 498747


over 90% of null-move fail highs occur when the side playing the null-move is winning.

Where are the other half of these numbers, the number of null-move attempts? Obviously, you only want to do null-move if you expect to save nodes by doing it, so you need the probability of a given null-move search failing low and an estimate of the ratio of the cost of the null-move search to the full search to determine if the null-move search is worthwhile.

Crafty attempts a null-move at _every_ node except where the TT "trick" says don't do it. That is infrequent. That is not another half. I could certainly run it, but I don't see 20% hash hits in these kinds of middlegame positions, so the number of positions where I don't try a null is very small unless you pick a wildly tactical position where there are almost nothing but checks (since I don't do a null while in check)...

As far as determining whether it is worthwhile or not, already done that. I ran the null-move-off test last year and posted the results, so it clearly is a win...

I think the real plus of null search against a tons of other pruning techniques that are all based on the rule "if I am well ahead then there is no need to continue the search", the real plus is that null search is the only one that is able to discriminate stable positions from dynamic ones, i.e. positions where there is still tension and activity on the board and so need to be searched further.

All it will do in that regard is (hopefully) find that if you play QxN and I reply PxQ, then giving you two moves in a row will give me a hint of whether you have any tactics you might spring because of the knight you removed. But the big savings is to recognize lost positions due to being down far enough that two consecutive moves won't help you, so that the search can be terminated with less effort.

It does show you which positions can be tossed out with much less effort, as shown above...

Yes. And the majority of those positions are where your opponent is lost, and can't recover anything with two consecutive moves, which is a lousy position for him to have to play from.

[bob]

Thanks for your reply. I will do run some additional tests.

I did see some additional fail highs on null moves without the value >= beta condition, so just as you said, I used a similar counting approach.

On the other hand the null move search comes not for free. It might take some time and if it fails low, this time is wasted (even hash table positions stored might only be useful for other 0 moves as they will have the wrong side to move stored in).

So it was just a decision whether to try a null move anyway in positions where I can tell statistically it will most likely fail low (>90%). Does the 1 out of 10 cases saving justify the wasted efforts in the other 9?

As I use a full eval score (not only material) in the comparison I factor also a possible strong positional advantage of the side that does the 0 move already in.

I'm faced with a similar question when it comes to IID. When I enter a node I try to predict what type of node I'm in (ALL, CUT, PV). I measured how good this prediction performs and it's quite accurate (>90%). So do I use expensive IID for better move ordering in a node that is with a >90% probability an ALL node ?

But as stated, I put more tests on that on the ToDo list.

Thanks again

Thomas...

I only use IID where alpha != beta - 1. It is too expensive, normally, but along the PV it can make a difference. In many positions, I can turn it off or leave it on and the node count does not change. I certainly would not do it in an ALL node since ordering is completely irrelevant in such positions anyway and any effort expended to order the moves better is 100% wasted.

[Hoethe]

Sorry for replying so slowly, I've been trying to keep up with everything that's been said. Thank you for such detailed responses. I think I understand null move pruning well enough now.

[Don]

Marco,

Your explanation is great! Concise and to the point and what null move pruning is all about.

Don

Try adding a counter to see how many times null-move fails high when material is equal, vs how many times it fails high when material is anything but equal...

This means nothing because it is obvious, you can run the same test for razoring, stand-pat or any other pruning scheme based on evaluation and get more or less the same numbers.

The real question is: "In what is different null search from other pruning facilities based on evaluation and its distance from beta ?"

The answer is that other schemes are unable to disciminate stable positions from positions where there is still activity and threats or, at least, are unable to discriminate in such a powerful and deep way as null search.

This is the key point. The fact that a stable position, when above beta, can be pruned is a natural and logical _consequence_, but we have to understand the difference between a key fact and its consequences.

[bob]

Marco,

Your explanation is great! Concise and to the point and what null move pruning is all about.

Don

Unfortunately, what it is about, and how it works so effectively are two different things. It is specifically most useful to recognize positions where one side is so far ahead in material that giving the opponent 2 consecutive moves is not enough to lose that advantage. If you look at the test data I provided, it clearly shows that. It is not nearly so effective in equal-material or down-in-material positions. Just in ones where we are significantly ahead, such as where you sac the queen at ply 1 and you can't recover anything quickly...

Try adding a counter to see how many times null-move fails high when material is equal, vs how many times it fails high when material is anything but equal...

This means nothing because it is obvious, you can run the same test for razoring, stand-pat or any other pruning scheme based on evaluation and get more or less the same numbers.

The real question is: "In what is different null search from other pruning facilities based on evaluation and its distance from beta ?"

The answer is that other schemes are unable to disciminate stable positions from positions where there is still activity and threats or, at least, are unable to discriminate in such a powerful and deep way as null search.

This is the key point. The fact that a stable position, when above beta, can be pruned is a natural and logical _consequence_, but we have to understand the difference between a key fact and its consequences.