Null Move Pruning

From Chessprogramming wiki
Revision as of 11:54, 4 March 2019 by GerdIsenberg (talk | contribs)
Jump to: navigation, search

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.

Adaptive Null Move Pruning

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.

Test Results

See also

Publications

1966

1975

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

1990 ...

2000 ...

2010 ...

Forum Posts

1995 ...

1997

1998

1999

A Null Move Enhancement? by Daniel Homan, CCC, February 10, 1999
To skin a cat (was Re: NULL MOVE) by Don Dailey, CCC, February 24, 1999

2000 ...

2001

2002

2003

2004

2005 ...

2006

2007

2008

2009

2010 ...

2011

2012

2013

2014

2015 ...

2016

2017

2018

2019

External Links

feat. Terumasa Hino, Gerry Brown, John Lee, Mike Mandel, and guests ... Michael Brecker, Randy Brecker, James Mtume et al.

References

  1. Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
  2. George W. Baylor, Herbert A. Simon (1966). A chess mating combinations program. AFIPS Joint Computer Conferences, reprinted 1988 in Computer Chess Compendium
  3. Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (1975). Some Methods of Controlling the Tree Search in Chess Programs. Artificial Intelligence, Vol. 6, No. 4, pp. 361-371. ISSN 0004-3702. Reprinted (1988) in Computer Chess Compendium
  4. 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.
  5. Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf, pp. 57
  6. Jonathan Schaeffer (1987). Speculative Computing. ICCA Journal, Vol. 10, No. 3
  7. Gordon Goetsch, Murray Campbell (1988). Experimenting with the Null Move Heuristic in Chess. AAAI Spring Symposium Proceedings, pp. 14-18
  8. Gordon Goetsch, Murray Campbell (1990). Experiments with the Null-Move Heuristic. Computers, Chess, and Cognition, pp. 159-168
  9. Chun Ye (1992). Experiments in Selective Search Extensions. M.Sc. thesis, Department of Computing Science, University of Alberta, pdf, pp. 27-29
  10. Re: SOMA by Ed Schröder, CCC, August 26, 2009
  11. Chrilly Donninger (1993). Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs. ICCA Journal, Vol. 16, No. 3
  12. Ernst A. Heinz. (1999). Adaptive null-move pruning. ICCA Journal, Vol. 22, No. 3, ps
  13. Position from local chess club by Bernhard Bauer, CCC, November 05, 1999
  14. Stefan Plenkner (1995). A Null-Move Technique Impervious to Zugzwang. ICCA Journal, Vol. 18, No. 2
  15. Null-move zugzwang avoidance, Jun '95 ICCAJ by Bruce Moreland in rgcc, December 6, 1996
  16. Omid David, Nathan S. Netanyahu (2002). Verified null-move pruning. ICGA Journal, Vol. 25 No. 3
  17. verified null move by Robert Hyatt, CCC, June 21, 2009
  18. Omid David, Nathan S. Netanyahu (2008). Extended Null-Move Reductions. CG 2008, pdf
  19. Re: Extended Null-Move Reductions by Robert Hyatt, CCC, August 20, 2010
  20. Re: Extended Null-Move Reductions by Marco Costalba, CCC, August 20, 2010
  21. Re: Null move? by Vincent Diepeveen, rgcc, October 11, 1997
  22. Gordon Goetsch, Murray Campbell (1988). Experimenting with the Null Move Heuristic in Chess. AAAI Spring Symposium Proceedings, pp. 14-18
  23. Yngvi Björnsson, Tony Marsland (2000). Selective Depth-First Search Methods. in Jaap van den Herik, Hiroyuki Iida (eds.) (2000). Games in AI Research. Universiteit Maastricht, pdf preprint
  24. Deep Search Extension by Stuart Cracraft, CCC, January 18, 1998
  25. Null move mate extension by James Robertson, CCC, June 25, 1999
  26. mate threat extension/null move by Rick Bischoff, CCC, September 25, 2004
  27. Re: mate threat extension/null move by Don Beal, CCC, October 04, 2004 » Mate Threat Extensions and WAC booster
  28. null move threat extension by Andrew Short, CCC, October 23, 2008
  29. The "same threat extension" as effective way to resolve horizon problem by Sergei Markoff, CCC, October 01, 2003
  30. Verified Null-Move Pruning, ICGA 25(3) by Omid David, CCC, November 20, 2002
  31. Proving something is better by Bruce Moreland, CCC, December 17, 2002
  32. courtesy of Don Beal and Carey Bloodworth, Re: Antique chess programs by Carey, CCC, December 16, 2015
  33. Selective Search Techniques in REBEL (introduction) from Programmer Corner by Ed Schröder
  34. How Rebel Plays Chess is also available as pdf
  35. Nullmove vs classic selective search by Ed Schröder, CCC, August 04, 2012

Up one level