The many faces of Null Move Pruning

[Pradu]

Should I understand from this that you would do the null-move search itself with an open window, if the node from which you start it has an open window?

Arrg forgot that I do null move searches with zero-windows regardless of the current bounds. Forgive my stupidity. But yes, for my implementation it seems to help doing nullmove even on ALL nodes.

[bob]

I use IID, but doing null-move _everywhere_ has always been more efficient in Crafty...

[bob]

Should I understand from this that you would do the null-move search itself with an open window, if the node from which you start it has an open window?

Arrg forgot that I do null move searches with zero-windows regardless of the current bounds. Forgive my stupidity. But yes, for my implementation it seems to help doing nullmove even on ALL nodes.

I agree. Once upon a time in Crafty, I didn't do null-move on non-zero window (PV) nodes. When I went back and tried doing them everywhere, it was faster, and significantly so in fact. There is not a single node I don't do a null-search on, except for those where the transposition table entry proves that a null-move search will fail low... I don't do them there, but that is the only place. Even when going down the left-hand side of the tree (assuming left-to-right search traversal order) I try a null before any move at every node.

[jesper_nielsen]

I use a null move verification search and it works for me. NMV search overhead slows down my search by about 4%, but in actual games it plays stronger than plain null move. My null move and NMV search are not "standard".

my null move:

• * Up to 3 null moves allowed per search line (mostly twice) depending on search depth and game stage
  * Null-move reduction range R = 2->4.5 plies, depending on material and zugswang danger

my null-move verification search :

• * NMV search done to depth: (depth - R), where R is same as null move R
  * NMV search allowed to use null-move
  * for cutoffs, stores actual NMV search score into the hash
  * for cutoffs returns actual NMV search score, not beta

Warning: I have not compared my weird null-move/NMV search to standard null move in a long time...

Ron

I gained about 3/4 ply depth consistantly in 1+1 games.

My rules are:
* Not in check. Of course.
* Not two null moves in a row.
* Side to move has at least five pieces.

I am considering changing the last condition to
* Side to move has at least one slider.

... since it appears that i lost a couple of pawn endgames, that might be because a null move was actually a zugzwang position. But I am investigating this further.

Kind regards,
Jesper

[Ron Murawski]

Hi Jesper,

I forgot to mention that I don't null-move on the first two plies of the search, not if there is a danger of mate (from the hashtable), and not if in check.

Ron

[hgm]

... since it appears that i lost a couple of pawn endgames, that might be because a null move was actually a zugzwang position. But I am investigating this further.

Never do NMP in pawn endings. Not only because of the Zugzwang problem, but also not to push promotions over the horizon. In a pawn ending therer is rarely any immediate tactical danger, the danger mostly comes from not being able to catch a running passer. If you would allow the defending side to defend with null moves, a promotion in 7 ply might take 16 ply to see it. So you would be practically blind against combinations where one side sacs a Pawn to lure the opponent's King out of the square of a passer.

Even the one-slider rule is not without danger. Joker once lost a game because its Bishop had to defend two squares not on the same diagonal, and of course it overlooked the Zugzwang at any search depth. For this reason it migh be benificial to verify null-move searches by even more reduced real searches. e.g. if you do R=3 null-move pruning, do an R=5 verify when d>5. Then at least you will see the Zugzwangs eventually, and it does take only very little time. But still never in endings with only Pawns + leapers.

[jesper_nielsen]

... since it appears that i lost a couple of pawn endgames, that might be because a null move was actually a zugzwang position. But I am investigating this further.

Never do NMP in pawn endings. Not only because of the Zugzwang problem, but also not to push promotions over the horizon. In a pawn ending therer is rarely any immediate tactical danger, the danger mostly comes from not being able to catch a running passer. If you would allow the defending side to defend with null moves, a promotion in 7 ply might take 16 ply to see it. So you would be practically blind against combinations where one side sacs a Pawn to lure the opponent's King out of the square of a passer.

Even the one-slider rule is not without danger. Joker once lost a game because its Bishop had to defend two squares not on the same diagonal, and of course it overlooked the Zugzwang at any search depth. For this reason it migh be benificial to verify null-move searches by even more reduced real searches. e.g. if you do R=3 null-move pruning, do an R=5 verify when d>5. Then at least you will see the Zugzwangs eventually, and it does take only very little time. But still never in endings with only Pawns + leapers.

Agreed!

I also recently saw a position where a rook was defending two pawns, but because of zugzwang was forced to move away from one of them.

I think this could be a symptom of not allowing two null moves in a row.

With the rook in position, we try a null move. Now the opponent HAS to move, and after that we can still leave the rook in place, because the next move again is allowed to be a null move.

I am wondering if allowing exactly two null moves in a row will catch this situation?

More testing is needed!

- Jesper

[hgm]

I am wondering if allowing exactly two null moves in a row will catch this situation?

Well, Vincent is the expert on this.

Note, however, that depending on your move ordering and the reductions you apply, using two null moves in a row can be either logically equivalent to Internal Iterative Deepening of Verified NMP.

The effect of two null moves in a row is just that you search the same position with the same side to move again, at lower depth. If both null moves are searched as first move of their node, this means that you search the same position at reduced depth before searching it at full depth. This is implicit IID.

OTOH, if you search the second null move in a row not as first move, but as last move (i.e. you don't search it for the purpose of pruning, but to make sure that the previous null move did not fail high because it dodged a Zugzwang), you reproduce the search pattern of verified null-move pruning. First you search the null move with all non-null replies, and after all these replies have failed low, you know that the underlyng null move is going to fail high. So you go "back" to the parent position by doing a second null move, where you do the verification search, the result of which is then passed back through the line of 2 null moves. You only get a fail high of the first null move when both null-move search and verification search have failed high. If one of those fails low, the first null move fails low, and you would do the full-depth search. Note that the second null move in a row would be treated as a normal move; its score would contribute to the node score.

Of course you can change the order of the moves, and try the second null move as first move in its node. This gives the search pattern you would have when you did the verification search first, and the normal null move (without null-move reply) after it only if the verification search failed high (meaning we are not dependent on Zugzwang to win this position at reduced depth). This is only competative for very much reduced verification searches.

Note that uMax starts every iteration after d=0 (=QS) of its explicit IID always with a null move (mainly to save the characters it would take to find out if you would like to do one based on CurEval vs Beta or previous moves). So in principle it tries an unlimited number of null moves in a row. This is not really useful, but also not harmful, as the reduction for 3 null moves is already quite large. In addition, the nodes that are actually searched go into the hash table, and are exactly the nodes that will have to be searched after the null move two levels below fails low. So it hardly causes any time to be wasted.

[jesper_nielsen]

Also i gathered some statistics regarding only doing null moves, when eval() is above beta. The test showed that only about 1 in 1000 null moves with eval() below beta actually resultet in a cutoff. (Too bad if that one is the one you reallly need! )

How many of you requires the evaluation to be above beta before doing a null move search?

I don't do null move if CurEval < Beta. It can only fail high if you have some irrefutable threat on the board, like a fork. This is very rare, and if you worry about missing that, it would probably pay off much more if you would recognize such threats in Eval. (In which case CurEval would be >= Beta, so you would automatically try the null move as well.)

Doing nullmove on ALL nodes is not always bad. You will get good move ordering on CUT nodes from the "null-killers". For Buzz the improved move ordering gives a bigger boost to search than the extra overhead of the nullmove search. I'm also not doing IID, so perhaps for engines with IID this won't be as big an issue.

My tests indicate a slightly worse performance when requiring curEval < beta.
So it looks like it doesn't work for me.

- Jesper

[bob]

I am wondering if allowing exactly two null moves in a row will catch this situation?

Well, Vincent is the expert on this.

Note, however, that depending on your move ordering and the reductions you apply, using two null moves in a row can be either logically equivalent to Internal Iterative Deepening of Verified NMP.

The effect of two null moves in a row is just that you search the same position with the same side to move again, at lower depth. If both null moves are searched as first move of their node, this means that you search the same position at reduced depth before searching it at full depth. This is implicit IID.

It is a bit more complicated than that. If the second null-move fails high, the first must fail low and so it is not going to affect the search at all. The idea is to catch zugzwangs. There is a big cost, in that doing the double R=3 eats a bunch of plies and can hide interesting tactics that you don't need to miss, which can cause null-move issues. The problem is what about positions where the second one fails high which prevents the previous null-move search from producing a low-effort cutoff, and you lose efficiency.

OTOH, if you search the second null move in a row not as first move, but as last move (i.e. you don't search it for the purpose of pruning, but to make sure that the previous null move did not fail high because it dodged a Zugzwang), you reproduce the search pattern of verified null-move pruning. First you search the null move with all non-null replies, and after all these replies have failed low, you know that the underlyng null move is going to fail high. So you go "back" to the parent position by doing a second null move, where you do the verification search, the result of which is then passed back through the line of 2 null moves. You only get a fail high of the first null move when both null-move search and verification search have failed high. If one of those fails low, the first null move fails low, and you would do the full-depth search. Note that the second null move in a row would be treated as a normal move; its score would contribute to the node score.

Of course you can change the order of the moves, and try the second null move as first move in its node. This gives the search pattern you would have when you did the verification search first, and the normal null move (without null-move reply) after it only if the verification search failed high (meaning we are not dependent on Zugzwang to win this position at reduced depth). This is only competative for very much reduced verification searches.

Note that uMax starts every iteration after d=0 (=QS) of its explicit IID always with a null move (mainly to save the characters it would take to find out if you would like to do one based on CurEval vs Beta or previous moves). So in principle it tries an unlimited number of null moves in a row. This is not really useful, but also not harmful, as the reduction for 3 null moves is already quite large. In addition, the nodes that are actually searched go into the hash table, and are exactly the nodes that will have to be searched after the null move two levels below fails low. So it hardly causes any time to be wasted.