Importance of Null Move Pruning

[rdhoffmann]

I just realized how important Null Move Pruning (NMP) is when writing a chess engine, and thought this could be useful for other fellow newbies/hobby chess engine coders to know.

If you take Stockfish and strip out all pruning and all those little hand-crafted details in the main search routine, leaving only NMP, SF is still an absolute beast, seemingly competitive vs engines close to a 3000 rating.

So this might be a hint to focus on NMP very carefully when writing a new chess engine from scratch. One mistake I made in my own engine is to not realize that I have to increase the reduction as the search goes deeper. I had fixed it to R=2 as this is suggested in many online resources.

[mvanthoor]

I just realized how important Null Move Pruning (NMP) is when writing a chess engine, and thought this could be useful for other fellow newbies/hobby chess engine coders to know.

Null move pruning is typically the first pruning technique that is implemented because it is so powerful. What it does is basically saying: You have just moved, and I'm still better. If I give you ANOTHER move (so I skip mine) and I'm STILL better, the entire branch coming from the extra move you just made can be pruned." The reason is: if you're still better after skipping a move, you would certainly be better if you DIDN'T skip your move.

The one caveat is that, in the late endgame, you should disable NMP, because if you skip your move while in zugzwang, it LOOKS like you're better in that line, but you actually aren't.

Depending on the engine NMP can gain around 100 Elo (if added as the first search optimization).

[chrisw]

I just realized how important Null Move Pruning (NMP) is when writing a chess engine, and thought this could be useful for other fellow newbies/hobby chess engine coders to know.

If you take Stockfish and strip out all pruning and all those little hand-crafted details in the main search routine, leaving only NMP, SF is still an absolute beast, seemingly competitive vs engines close to a 3000 rating.

So this might be a hint to focus on NMP very carefully when writing a new chess engine from scratch. One mistake I made in my own engine is to not realize that I have to increase the reduction as the search goes deeper. I had fixed it to R=2 as this is suggested in many online resources.

Did you also try the inverse hypothesis? Take SF, strip out NM, leaving everything else and test.

[rdhoffmann]

Did you also try the inverse hypothesis? Take SF, strip out NM, leaving everything else and test.

Not yet, but yes good idea, that will be interesting as well! What I did test though is stripping out NMP alongside the rest (leaving no pruning whatsoever). Then SF finally collapses, such that my engine can beat it

So it appears that for a chess engine hobbyist developer, spending enough time on NMP seems like a good idea.

[chrisw]

Did you also try the inverse hypothesis? Take SF, strip out NM, leaving everything else and test.

Not yet, but yes good idea, that will be interesting as well! What I did test though is stripping out NMP alongside the rest (leaving no pruning whatsoever). Then SF finally collapses, such that my engine can beat it

So it appears that for a chess engine hobbyist developer, spending enough time on NMP seems like a good idea.

[chrisw]

Did you also try the inverse hypothesis? Take SF, strip out NM, leaving everything else and test.

Not yet, but yes good idea, that will be interesting as well! What I did test though is stripping out NMP alongside the rest (leaving no pruning whatsoever). Then SF finally collapses, such that my engine can beat it

So it appears that for a chess engine hobbyist developer, spending enough time on NMP seems like a good idea.

Last attempt at a reply got hit by the security check losing the reply text.

There's heavy redundancy in the pruning functions, if you kill one off, it won't make a huge amount of difference, the opposite to killing all off and leaving just one. The latter method falsely emphasises the Elo gain of a prune function.

[rdhoffmann]

I see what you mean.

But look e.g. at step 14 of the pruning code in SF. This is about 50 lines of code with very precise conditions, lots of hand-crafted values etc. There is no way anyone can come up with precisely that code on their own. Not in a million years.

Contrast this to NMP, which is almost trivial in comparison. So my argument is more of a practical one for beginners

[syzygy]

Not yet, but yes good idea, that will be interesting as well! What I did test though is stripping out NMP alongside the rest (leaving no pruning whatsoever). Then SF finally collapses, such that my engine can beat it

I tried this some years ago. SF's NPS went sky high, but it lost 800 Elo.

[hgm]

Last attempt at a reply got hit by the security check losing the reply text.

It is infuriating when that happens. But I have discovered you can often retrieve the lost text by backing up to a previous page with the browser. At least for FireFox this usually works: you first reply to the security check, and when you confired you get back to the entry form, but your text has disappeared. Hitting the 'back' button a few times to get you past the recalled security check then gives me the same entry form, but now with the text still in it. Then you can hit 'Submit' there.

[looa]

All this relies on you having a good evaluation function though, null move pruning won't help you if your evaluation is out of whack. So should you put effort into your evaluation or implement these additional search optimizations? I'm currently weighing these options for my own engine, should I spend more time figuring out optimizing my search or should I add more data to my evaluation?