Null Move Pruning

[Hoethe]

Hello everyone,

I was wondering if anyone could help me wrap my head around null move pruning. I think I understand the principle behind it: a position is so strong for one side that, even when they forfeit a turn, the other player can't improve their position enough that an alpha-beta cut off wont be produced.

So in a game: 1. e4 e5 2. Nf3 Nc6 if the engine investigates the (obviously bad) move 3. Nxe5 then, after 3. ... Nxe5, black forfeits his next go. The search depth is reduced (saving computational effort) and the computer discovers that white is still losing no matter what so the whole Nxe5 branch is pruned.

What I don't understand is when null move pruning is applied? When does the engine decide that a player should forfeit a turn? Is this idea somehow investigated at every node or only when one player is winning by a substantial amount?

I'm sorry if what I'm asking is obvious and thanks for taking the time to read this.

[JVMerlino]

Hello everyone,

I was wondering if anyone could help me wrap my head around null move pruning. I think I understand the principle behind it: a position is so strong for one side that, even when they forfeit a turn, the other player can't improve their position enough that an alpha-beta cut off wont be produced.

So in a game: 1. e4 e5 2. Nf3 Nc6 if the engine investigates the (obviously bad) move 3. Nxe5 then, after 3. ... Nxe5, black forfeits his next go. The search depth is reduced (saving computational effort) and the computer discovers that white is still losing no matter what so the whole Nxe5 branch is pruned.

What I don't understand is when null move pruning is applied? When does the engine decide that a player should forfeit a turn? Is this idea somehow investigated at every node or only when one player is winning by a substantial amount?

I'm sorry if what I'm asking is obvious and thanks for taking the time to read this.

Null move can theoretically be used for every node in the search, with the only exceptions being where it would be obviously broken (such as when the side to move is in check and forfeiting the move would be illegal).

It should definitely come after the hash probe, but precisely where to place it in the search may be the subject for debate, but here is where it is in my engine (better programmers of stronger engines will certainly correct me if this is wrong):

hash probe
tablebase probe
check for max depth
check for depth=0 to go to quiescent search
futility pruning
null move
regular search

But there are some situations in which null move would be dangerous, the most common of which is zugzwang. For this reason, many programs put some kind of minimum material check to limit the chances of zugzwang being possible. In my engine, if the side to move has a piece, then null move is ok.

Other possible restrictions are:
-- if you are on a leaf node (remaining depth = 1)
-- if you are in a PV node
-- if alpha is highly negative (meaning the side to move might be in a mate threat)
-- if you've already done several null moves in this branch

Null move is pretty easy to implement, but tweaking can be time-consuming. Good Luck!

jm

[smatovic]

What I don't understand is when null move pruning is applied? When does the engine decide that a player should forfeit a turn? Is this idea somehow investigated at every node or only when one player is winning by a substantial amount?

I do it at every non-PVNode with depth > 2 and when side to move is not in check and there is a king with at least 1 piece. In QSearch i do not apply null-move pruning.

Some engines use a verification search with reduced depth to verify the fail-high of null-move (Zugzwang detection?). The verification search doesnt use null-move pruning itself.

Vincenct Diepeeven posted an idea of double-null-move pruning to avoid the verification search....but i was not able to get a speedup by this...
--
Srdja

[bob]

What I don't understand is when null move pruning is applied? When does the engine decide that a player should forfeit a turn? Is this idea somehow investigated at every node or only when one player is winning by a substantial amount?

I do it at every non-PVNode with depth > 2 and when side to move is not in check and there is a king with at least 1 piece. In QSearch i do not apply null-move pruning.

Some engines use a verification search with reduced depth to verify the fail-high of null-move (Zugzwang detection?). The verification search doesnt use null-move pruning itself.

Vincenct Diepeeven posted an idea of double-null-move pruning to avoid the verification search....but i was not able to get a speedup by this...
--
Srdja

First, why does it work? If I could play a GM in a game of chess, at at a point of my choosing, I could play 2 moves in a row, I would bet money on my chances to win. Now the GM can't leave his queen open to a two-consecutive-move trap, nor leave his king open to a two consecutive move mate. Etc...

The idea of the null-move is to quickly dismiss positions where you are way ahead. If I am so far ahead, that after you make a move, I can pass and give you a second consecutive move, and the search still fails high for me, one might call my position "winning". And there is no need to search it as carefully. The power of two consecutive moves is worth way more than a piece or even a rook...

So I give you two consecutive moves, but I reduce the depth of the search significantly, because the two consecutive moves should allow you to win something quickly. If it doesn't your position sucks...

Once you get that idea, the rest is pretty easy...

[mcostalba]

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.

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.

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.

[hgm]

The point is that Chess is a game where you can often delay inevitable losses for quite a number of moves (usually at the expense of coming out worse, eventually). So in positions where you stand to lose something, you need to search deep, or you would just be fooling yourself by pushing the loss over the horizon (e.g. by first trading something valuable, that he has to recapture first, or threatening something valuable, that he has to rescue first). In other words: in the presence of a threat, undeep searches are unreliable.

Now the null move is a quick way to probe if the opponent has such a threat. It won't create any problems (or opportunities) for the opponent, so if he has anything up his sleeve, he can start with it immediately, so a relatively shallow search will already reveal it. So if the null move fails high, you can be pretty sure he has nothing up his sleeve. Especially, since if there would remain something that is yet conceiled at the depth you have searched, you can pre-emptively defend against it, through replacing your null move by a real move that thwarts his plans.

But if there is a threat, making the null move fail low, you must make sure to search for potential defences at a larger depth than you needed to just see the threat after null move. Otherwise you would just find false defences, that delay what might turn out to be inevitable on deeper search.

[tpetzke]

Hi,

this is the rule set I currently use

null_move_ok= (nullMove == NULL_MOVE_OK) &&
!timeCtrl->searchForMate &&
(board->bb.mmPcsCount[board->sideToMove]>1) &&
(depth > 2) &&
!board->inCheck() &&
!avoid_null_move &&
(alpha == beta - 1) &&
(value >= beta);

This reads as
1. The previous move was not a null move
2. We don't search for a mate in X puzzle
3. the side to move has more than 1 piece left (zugzwang)
4. the remaining depth is >2
5. the side to move is not in check
6. we don't see from the hash tbl that a null move is futile for sure
7. we are searching with a 0 window (means we are in a likely CUT node)
8. value is >= beta, means we are doing pretty good already, value is the value from static eval of this node

I always wondered about that last 2 conditions, I've seen other engines that don't have it. It's just my understanding of it, that a 0 move has only a chance to cause pruning if we are already doing good. If we are below beta already I don't see how doing nothing will get us above it, so I have it in and it seems to work ok. Changing those conditions deteriorates the 0 move success rate.

But it might well be that I miss something here.

Thomas...

[Teemu Pudas]

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.

[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."

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.

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]

Hi,

this is the rule set I currently use

null_move_ok= (nullMove == NULL_MOVE_OK) &&
!timeCtrl->searchForMate &&
(board->bb.mmPcsCount[board->sideToMove]>1) &&
(depth > 2) &&
!board->inCheck() &&
!avoid_null_move &&
(alpha == beta - 1) &&
(value >= beta);

This reads as
1. The previous move was not a null move
2. We don't search for a mate in X puzzle
3. the side to move has more than 1 piece left (zugzwang)
4. the remaining depth is >2
5. the side to move is not in check
6. we don't see from the hash tbl that a null move is futile for sure
7. we are searching with a 0 window (means we are in a likely CUT node)
8. value is >= beta, means we are doing pretty good already, value is the value from static eval of this node

I always wondered about that last 2 conditions, I've seen other engines that don't have it. It's just my understanding of it, that a 0 move has only a chance to cause pruning if we are already doing good. If we are below beta already I don't see how doing nothing will get us above it, so I have it in and it seems to work ok. Changing those conditions deteriorates the 0 move success rate.

But it might well be that I miss something here.

Thomas...

The last condition is not a good one. From the opening position, a _lot_ of null-move searches fail high when material is equal and score is equal. The CUT node idea is also wrong. But you can test that for yourself to verify. BTW alpha == beta-1 is -not- always a CUT node. It can also be an ALL node. Just not PV.

See my other post that shows that null-move does fail high even when material is < 0. Just not as often.