The many faces of Null Move Pruning

[hgm]

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.

It seems to me that this was exactly the point for doing it: if the second null move fails high the position is a Zugzwang. This is indeed searched at much reduced depth. Which seems sufficient for most Zugzwangs. No one forces you to use the same reduction for the second null-move in a row than as for the first. You can even allow an extension, as long as it is not bigger than the reduction by the previous null move, without the risk of a search explosion. But that makes it of course even more expensive, so I would only recommend it if the second null move is searched last. To get the classic verified NMP one would have to give the second null move an extension R-1.

[bob]

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.

It seems to me that this was exactly the point for doing it: if the second null move fails high the position is a Zugzwang.

Not anywhere near "always" unfortunately. At position P (remaining depth = D) you try a null-move which would fail high because you don't want to make a move, as any move worsens your position.. At position P+1, remaining depth = D-nmr (null-move reduction) you reach a position that fails high, not because the other side is also in a position where any move makes it worse, it fails high because the D - nmr -nmr reduces the depth so far that the threats disappear and now this side thinks it is better.

So it is not a cure-all for zugzwang at all. Reducing the search by 2 * NMR really hides a lot of tactics. And double-null concludes "zugzwang" which the truth is simply "horizon effect".

That's the case I have never liked and is why I don't use double-NM.

This is indeed searched at much reduced depth. Which seems sufficient for most Zugzwangs.

I am not convinced just by your making that statement ("sufficient"). The thing that exposes most zugzwang positions is a significant search to show that if I move I lose. Fine 70 is a good example of where white zugs black and wins a pawn. But it takes a _deep_ search to realize that black is zugged and has to give up a pawn on one side or the other. If you hack off 6 plies, the second null-move search might well fail high thinking it can hold everything, when it can't, it just can't see deeply enough to figure that out.

No one forces you to use the same reduction for the second null-move in a row than as for the first. You can even allow an extension, as long as it is not bigger than the reduction by the previous null move, without the risk of a search explosion. But that makes it of course even more expensive, so I would only recommend it if the second null move is searched last. To get the classic verified NMP one would have to give the second null move an extension R-1.

It doesn't matter what reduction you use. But the usual implementation is to use the same R value for all null-move searches. But so long as R != 0, you can find positions where just lopping off one ply makes you think you have a mutual zugzwang position but you don't, and you toss the first NM search out, and do a really big search, and still end up failing high but with way more effort than just the NM search effort...

[Mangar]

Hi,

for Spike verification does not work. It is possible to be better in some test postions but not in "real" games.
For Spike the rule "no nullmove if material is at least one pawn less than beta" works better than doing the evaluation.

Greetings Volker

[hgm]

It doesn't matter what reduction you use. But the usual implementation is to use the same R value for all null-move searches. But so long as R != 0, you can find positions where just lopping off one ply makes you think you have a mutual zugzwang position but you don't, and you toss the first NM search out, and do a really big search, and still end up failing high but with way more effort than just the NM search effort...

Horizon effect doesn't worry me so much. No matter how smartly your tree is shaped, there will always be a horizon, and you won't be able to see what lies behind it. But then you search deeper, and sooner or later it does get within your horizon.

Dodging Zugzwangs by null-moving is another matter. There can be a completely obvious Zugzwang, where your opponent has to move away a defender and lose a Pawn on ply 3. And it will not become PV at _any_ search depth, because it is refuted at ply 2 by null move.

So even if a hefty 8 ply are taken away due to the double null move and the two accompanying R=3 reductions, you would get to see it at d=11 (a depth that is typically easily reached in situations where Zugzwangs occur). And when you finally sees it the moves becomes PV and the full disaster for the opponent unfolds in 11-ply technicolor.

I agree, though, that an 8-ply reduced verification search is probably way to stingy. Having a 4-ply reduction is probably _much_ safer, and still has negligible cost. It would mean that after an R=3 null move, you would have to play the second null move of the pair with R=0. (i.e. without any reduction, making it as expensive as all other moves in this ALL-node).

If the second null move is searched as deep as the all other null-move replies, and fails high by pushing your original threat over the horizon, one of the real replies would have been even more likely to do that. So it seems you won't subvert the usefulness of NMP in any way. The chances that the second null move will delay the gain you are dependent on more than a real move could delay it are truly low.

That most people take the same R for first and second null move is of no importance. One should do what works best, not what is done most...

[bob]

It doesn't matter what reduction you use. But the usual implementation is to use the same R value for all null-move searches. But so long as R != 0, you can find positions where just lopping off one ply makes you think you have a mutual zugzwang position but you don't, and you toss the first NM search out, and do a really big search, and still end up failing high but with way more effort than just the NM search effort...

Horizon effect doesn't worry me so much. No matter how smartly your tree is shaped, there will always be a horizon, and you won't be able to see what lies behind it. But then you search deeper, and sooner or later it does get within your horizon.

Dodging Zugzwangs by null-moving is another matter. There can be a completely obvious Zugzwang, where your opponent has to move away a defender and lose a Pawn on ply 3. And it will not become PV at _any_ search depth, because it is refuted at ply 2 by null move.

So even if a hefty 8 ply are taken away due to the double null move and the two accompanying R=3 reductions, you would get to see it at d=11 (a depth that is typically easily reached in situations where Zugzwangs occur). And when you finally sees it the moves becomes PV and the full disaster for the opponent unfolds in 11-ply technicolor.

I agree, though, that an 8-ply reduced verification search is probably way to stingy. Having a 4-ply reduction is probably _much_ safer, and still has negligible cost. It would mean that after an R=3 null move, you would have to play the second null move of the pair with R=0. (i.e. without any reduction, making it as expensive as all other moves in this ALL-node).

If the second null move is searched as deep as the all other null-move replies, and fails high by pushing your original threat over the horizon, one of the real replies would have been even more likely to do that. So it seems you won't subvert the usefulness of NMP in any way. The chances that the second null move will delay the gain you are dependent on more than a real move could delay it are truly low.

That most people take the same R for first and second null move is of no importance. One should do what works best, not what is done most...

Did you ever stop to think that maybe we are not all a bunch of lemmings, and that instead of playing follow-the-leader off the cliff, we actually test to see what works best? I know I do... I don't guess. I don't hypothesize. I actually find out... My search extensions are not the result of guesswork. Ditto for other eval things. And search extensions. And reductions. Etc. All tested to discover what works best... I don't use R=3 everywhere. Everyone that has read posts by me or looked at crafty knows it has been using "adaptive R" for 10+ years now...

[hgm]

So how much better / worse is it to do double null move in stead, with R=0 for the second of the pair?

[bob]

So how much better / worse is it to do double null move in stead, with R=0 for the second of the pair?

the idea of R=0 sounds like a verification search with a high cost. Rather than trying the null-move-observation (my position is so good even if I do nothing my opponent can't hurt me). I didn't personally try R=0 because R=1 and R=2 wore worse for every case I tried except for the set of positions where zugzwang is a known problem.

You can probably dig all of this discussion up from r.g.c.c back in the early to middle 90's. I think Vincent started the discussion...

[hgm]

Just to make sure:

You say you have not tried R=0... So you must be guessing or hypothesyzing this?

My guess would be that R=1 etc. would perform poorly because you run into the horizon-effect problem that you pointed out before. R=0 should not have that, if the first null move would not already do it (in which case it would make little difference if you did the second one or not, as the other moves will suffer from this horizon effect even worse).

I think an R=0 verification search would be extremely cheap! If the first null move is going to fail high, all real moves in the null-move-reply node must also be searched to this depth, and there are likely to be many. So adding one is not that expensive. Compared to the Taibibi verified NMP you would have R more plies of reduction in the verification search. (In other words, to mimic usual verified NMP you would have to set R=-4 for the second null move, i.e. give a 4-ply extension).

[bob]

Just to make sure:

You say you have not tried R=0... So you must be guessing or hypothesyzing this?

I tried R=3. R=2 was worse. R=1 was much worse. I suppose one needs to try R=0 and R=-1 and R=-2 to be thorough? Or one can logically infer that 2 is worse than 3, 1 is worse than 2, so there is no point in continuing?

My guess would be that R=1 etc. would perform poorly because you run into the horizon-effect problem that you pointed out before. R=0 should not have that, if the first null move would not already do it (in which case it would make little difference if you did the second one or not, as the other moves will suffer from this horizon effect even worse).

No. The reason they were worse as R was reduced was that the size of the tree increased. Again, double-null absolutely does detect most zugzwangs. It also detects non-zugzwangs and calls them zugzwangs, which causes the important null-move search to fail low and both the original null-move search and the second end up wasted effort. And now I have to do a real (expensive) search rather than the cheaper null-search that really should have worked.

My testing was based on the size of the tree, and it went up in almost every case. Significantly. Which is the same as slowing the thing down. Significantly. I couldn't play as many games back then as I can today, but testing both on positions, and in real games produced worse results for me. Vincent swears by it. Perhaps for him it works well. But then again, I have seen this happen many times over the years. Programs are different. So they sometimes respond differently to a new idea.

I think an R=0 verification search would be extremely cheap! If the first null move is going to fail high, all real moves in the null-move-reply node must also be searched to this depth, and there are likely to be many. So adding one is not that expensive. Compared to the Taibibi verified NMP you would have R more plies of reduction in the verification search. (In other words, to mimic usual verified NMP you would have to set R=-4 for the second null move, i.e. give a 4-ply extension).

The problem is that the second R=0 search _must_ fail low most of the time, else the original NM search is worthless. That means you are just doing work for no gain, unless null-move is a bad idea everywhere.

[hgm]

I tried R=3. R=2 was worse. R=1 was much worse. I suppose one needs to try R=0 and R=-1 and R=-2 to be thorough? Or one can logically infer that 2 is worse than 3, 1 is worse than 2, so there is no point in continuing?

Well, I was just a bit surprised by this sudden relaxing of standards, as you were so emphatically arguing you never assumed anything without testing it. If ther would be a theoretical expectation that R=0 avoids some problems that R>0 might encounter, it could be an incentive. But let's discuss that below.

My guess would be that R=1 etc. would perform poorly because you run into the horizon-effect problem that you pointed out before. R=0 should not have that, if the first null move would not already do it (in which case it would make little difference if you did the second one or not, as the other moves will suffer from this horizon effect even worse).

No. The reason they were worse as R was reduced was that the size of the tree increased. Again, double-null absolutely does detect most zugzwangs. It also detects non-zugzwangs and calls them zugzwangs, which causes the important null-move search to fail low and both the original null-move search and the second end up wasted effort. And now I have to do a real (expensive) search rather than the cheaper null-search that really should have worked.

Could you give me an example of a non-Zugzwang position where a null-move would fail high, but a double null move with R=0 on the second null move, would fail low?

My testing was based on the size of the tree, and it went up in almost every case. Significantly. Which is the same as slowing the thing down. Significantly. I couldn't play as many games back then as I can today, but testing both on positions, and in real games produced worse results for me. Vincent swears by it. Perhaps for him it works well. But then again, I have seen this happen many times over the years. Programs are different. So they sometimes respond differently to a new idea.

So if I understand you correctly, this size increase was mainly due to the need for doing extra real searches when the first null move failed low. Not because of the size of the second null-move searches themselves/

The problem is that the second R=0 search _must_ fail low most of the time, else the original NM search is worthless. That means you are just doing work for no gain, unless null-move is a bad idea everywhere.

Well, this is inherent in verification. Most of the time it is a waste of time. It must be justified from the rare cases when it comes up with something.