# Difference between revisions of "Null Move Pruning"

Home * Search * Selectivity * Pruning * Null Move Pruning

Samuel Bak - Signals [1]

Null Move Pruning,
also called Null Move Heuristic (NMH), is a method based on the Null Move Observation to reduce the search space by trying a "null" or "passing" move, then seeing if the score of the subtree search is still high enough to cause a beta cutoff. Nodes are saved by reducing the depth of the subtree under the null move. The value of this depth reduction is known as R.

# History

## Mater II

In computer chess, Null Move was already used in threatening mate in one detection, as elaborated by George Baylor and Herbert Simon in A chess mating combinations program, 1966, the description of Mater II [2] .

```Routine G17 asks if a proposed move threatens mate in one move. It determines the answer by assuming Black does nothing on his turn, that is, by playing a "No Move" and then seeing if White can enforce an immediate checkmate.
```

## Kaissa

Null Move pruning was already used in Kaissa, as described by their authors 1975 in Some Methods of Controlling the Tree Search in Chess Programs [3] , at the end of chapter 2:

```2. The Order of Move Considerations:
A less trivial idea was that sometimes an extension of the game tree by introducing of dummy move can lead to a reduction of the search tree. In positions with material advantage (with respect to limits) it was permitted to try a so-called "blank" move in which ones own pieces are not moved. Certainly in positions with "Zugzwang" (the side to move must weaken his position) this may lead to errors.
```
```However, the standard of the program's play is still such that such errors do not essentially lower it. (We plan to develop in the future a procedure for recognizing "Zugzwang" positions, and to forbid a blank move in them.) The reduction of search takes place in this case, because the blank move proves to be a closing one and furthermore does not generate complex forcing variations.
```

## Beal's NMQS

Null move was further examined by Don Beal, as already elaborated in his Advances in Computer Chess 5 lecture. He proposed a so called Null Move Quiescence Search (NMQS) as a selective layer between a regular full width search and quiescence search, later dubbed Generalized Quiescence Search [4]. The full width search was called with two depth parameters, both considered inside the transposition table, full-depth and q-depth. Full-depth was recursively decremented as usual, but instead of calling quiescence at the full-depth horizon, NMQS with q-depth was called - q-depth recursively decremented in this layer as well. As long as q-depth is greater than zero, the hash move, if any, is searched first regularly. Next, NMQS calls quiescence for the other side to move, to check for a possible null move beta-cutoff, before proceeding the remaining moves in usual manner. As pointed out by Chun Ye in his 1992 thesis [5], NMQS permits more flexible iterative deepening concerning full-depth in an outer and q-depth in an inner loop.

## Schaeffer

In his 1987 ICCA Journal paper Speculative Computing, Jonathan Schaeffer mentioned The Null-Move Algorithm or Don Beal's null-move, and used it non-recursively up to once per search path in his tactical scout solver Minix (Mini-Phoenix), which up and then gave the parallel running Phoenix, which was a less deep searcher than Minix, some tactical hints [6].

## Goetsch and Campbell

Gordon Goetsch and Murray Campbell published the results of some experiments with Null move pruning in 1988 and 1990 [7] [8], already considering recursive NMP with depth reduction of 1, also mentioned in Chun Ye's 1992 thesis with source code as implemented inside the Chinese Chess program Abyss [9] .

## Morsch and Donninger

Null move pruning was used recursively to possibly occur multiple times inside a path of the search by Frans Morsch [10] inside his chess engines Quest and Fritz. Frans exchanged his ideas with Chrilly Donninger, who popularized null move by his Null Move and Deep Search paper in the ICCA Journal 1993 [11] .

# Schemes

Most typical engines use recursive null move with an R value of 2 or 3. Recursive null move pruning is simply allowing more than one null move in one branch of the search. Fruit uses a depth reduction factor R=3, with no null move pruning when down to king and pawns for the side to move, or when in check. The default for Fruit is to try a null search if the static evaluation is greater than beta, or the depth less than four. Newer versions of Fruit as well as Toga default to always doing a null search, as long as there is at least one piece of value greater than a pawn for that side.

Ernst A. Heinz proposed refinements with Adaptive Null Move Pruning [12] . Some programs vary R with depth, or based on evaluation features, such as being in or near the endgame.

## Restrictions on use

Obviously, the null move cannot be used when the side to move is in check, because that would result in an illegal position. But there are more less obvious restrictions on using null move safely. The theoretical basis of null move pruning, as coined by Christophe Théron, is the null move observation. The null move observation is the fact that in chess, in almost every position, the side to move will have a move to play that is better than doing nothing.

There are a few situations in which this assumption does not hold. The null move will produce very bad results in zugzwang positions - positions in which not moving would be the best move, if it were legal. For this reason, some conditions must be used for when the null move is tried in search. Most engines do not try the null move in the endgame, because that is where zugzwang positions are most likely to occur, because there are fewer pieces to move. It is debatable whether a programmer should allow the null move search descend directly to the quiescence search. Most probably it is worthwile only with more tactically aware versions of quiescence.

Some other ways to combat the negative effect of the null move observation are listed here:

## Zugzwang Verification

Concerning null move failures in zugzwang [13] , there were proposals by Stefan Plenkner 1995, [14] [15] and later the Verified Null-Move Pruning approach by Eli David and Nathan S. Netanyahu [16] . Recently Robert Hyatt tested Verified Null-Move Pruning extensively with a lot of variations and depth reductions for the verified search, and concluded it does not help at all in Crafty [17] similar with extended null-move reductions [18] [19] . However, Marco Costalba states that verification search has almost nothing to do with zugzwang [20] .

## Double Null Move

Widely discussed in computer chess forums was the Double Null Move idea by Vincent Diepeveen to perform two consecutive null moves to detect zugzwang [21] .

## Variable NM Bound

The idea to permit a null move cutoff not only if the null move search returns a value greater than or equal to beta, but also if the value is slightly less - that is using a bound of beta minus some tempo bonus, was already proposed by Gordon Goetsch and Murray Campbell in 1988 as future research idea [22] . Yngvi Björnsson and Tony Marsland substantiated the idea as implemeted in The Turk, where the number of potentially good alternative moves (numPGAM) per side in the path from the root to the current node as estimated by positive scores of generated moves from the history heuristic, was used to determine a tempo bonus of 10 or 20 centipawns - the higher numPGAM, the lower the probability that an erroneous forward pruning decision will propagate up the tree [23] .

```if ( nullMoveAllowed &&  ...) {
int bound = beta;
if ( inNullMoveSearch == 0 ) {
tempo = 10*(numPGAM > 0) + 10* numPGAM > 15);
bound -= tempo; // variable bound
}
makeNullMove(); ++inNullMoveSearch;
score = -zwSearch(1-bound, depth-R-1)
unmakeNullMove(); --inNullMoveSearch;
if ( score >= bound ) {
return beta; // null move pruning
}
}
```

For zwSearch, see Zero Window Search inside the Principal Variation Search.

# Threat Detection

## Mate Threats

As suggested in Donninger's paper, concerning the deep search, null move is not only about pruning, but also about detecting threat moves by the opponent to improve further move ordering and to possibly trigger mate threat extensions [24] [25] [26] [27] . However, some kind of fail-soft framework is necessary to recognize "I get mated, if I do nothing", otherwise the hard bound of a null window null-move search around beta will limit the upper bound to beta-1 [28] . Another, possibly too expensive solution with a fail-hard framework, is to play a bit with the search window, if the null move doesn't fail high:

```if ( nullMoveAllowed && depth >= X && ...) {
makeNullMove()
score = -zwSearch(1-beta, depth-R-1) // -AlphaBeta (0-beta, 1-beta, depth-R-1)
if (score >= beta ) {
// fail high on null move
unmakeNullMove();
return beta; // null move pruning
} else {
if ( zwSearch( VALUE_MATE/2, depth-R-1) > VALUE_MATE/2 )
extend; // mate threat extension inside a fail hard framework
unmakeNullMove();
}
}
```

## Botvinnik-Markoff Extension

Null move is also the base of the Botvinnik-Markoff Extension, as proposed by Sergei Markoff - as a tribute to the computer chess pioneer and former World Chess Champion Mikhail Botvinnik, who addressed related issues in his publications [29] .

## Influence on Move Ordering

Most of the time, null move is refuted by a capture. Therefore it makes sense to extract a move that refuted null move from the transposition table, record the target square of such a move, to give a move ordering boost for escaping from that square. Also, there is a strong conjecture that in programs using history move ordering, even a failed null move search helps by filling the history tables faster.

# Publications

## 1980 ...

• Gordon Goetsch, Murray Campbell (1988). Experimenting with the Null Move Heuristic in Chess. AAAI Spring Symposium Proceedings, pp. 14-18.
• Don Beal (1989). Experiments with the Null Move. Advances in Computer Chess 5, a revised version is published (1990) under the title A Generalized Quiescence Search Algorithm. Artificial Intelligence, Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702, edited version in (1999). The Nature of MINIMAX Search. Ph.D. thesis, IKAT, ISBN 90-62-16-6348. Chapter 10, pp. 101-116

# Forum Posts

## 1995 ...

1997

1998

1999

To skin a cat (was Re: NULL MOVE) by Don Dailey, CCC, February 24, 1999

2001

2002

2003

2004

2006

2007

2008

2009

2011

2012

2013

2014

2016

2017