Changes

Jump to: navigation, search

Null Move Pruning

36,744 bytes added, 07:05, 29 April 2018
Created page with "'''Home * Search * Selectivity * Pruning * Null Move Pruning''' FILE:SamuelBakSignals.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/ass..."
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Pruning]] * Null Move Pruning'''

[[FILE:SamuelBakSignals.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d77d58ae5574bf8bc5|[[Arts#Bak|Samuel Bak]] - Signals <ref>[http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d77d58ae5574bf8bc5 Chess in the Art of Samuel Bak], [http://www.chgs.umn.edu/ Center for Holocaust & Genocide Studies], [https://en.wikipedia.org/wiki/University_of_Minnesota University of Minnesota]</ref> ]]

'''Null Move Pruning''',<br/>
also called Null Move Heuristic ('''NMH'''), is a method based on the [[Null Move Observation]] to reduce the search space by trying a [[Null Move|"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 [[Reductions|reducing]] the [[Depth|depth]] of the subtree under the null move. The value of this depth reduction is known as [[Depth Reduction R|R]].

=History=
==Mater II==
<span id="History"></span>In computer chess, Null Move was already used in threatening [[Checkmate|mate in one]] detection, as elaborated by [[George Baylor]] and [[Herbert Simon]] in ''A chess mating combinations program'', 1966, the description of [[Mater#MaterII|Mater II]] <ref>[[George Baylor|George W. Baylor]], [[Herbert Simon|Herbert A. Simon]] ('''1966'''). ''[http://dl.acm.org/citation.cfm?id=1464182.1464233&coll=GUIDE&dl=GUIDE A chess mating combinations program]''. [https://en.wikipedia.org/wiki/American_Federation_of_Information_Processing_Societies AFIPS] [https://en.wikipedia.org/wiki/Joint_Computer_Conference Joint Computer Conferences], reprinted 1988 in [[Computer Chess Compendium]]</ref> .
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'' <ref>[[Georgy Adelson-Velsky]], [[Vladimir Arlazarov]], [[Mikhail Donskoy]] ('''1975'''). ''Some Methods of Controlling the Tree Search in Chess Programs''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6, No. 4, pp. 361-371. ISSN 0004-3702. Reprinted ('''1988''') in [[Computer Chess Compendium]]</ref> , 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.

<span id="NMQS"></span>
==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|quiescence search]], later dubbed '''Generalized Quiescence Search''' <ref>[[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''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702.</ref>. The full width search was called with two depth parameters, both considered inside the [[Transposition Table|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|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|beta-cutoff]], before proceeding the remaining moves in usual manner. As pointed out by [[Chun Ye]] in his 1992 thesis <ref>[[Chun Ye]] ('''1992'''). ''Experiments in Selective Search Extensions''. M.Sc. thesis, Department of Computing Science, [[University of Alberta]], [https://era.library.ualberta.ca/public/datastream/get/uuid:e4fbf48d-7603-490f-85cc-5497bbecf5a8/DS1 pdf], pp. 57</ref>, NMQS permits more flexible [[Iterative Deepening|iterative deepening]] concerning full-depth in an outer and q-depth in an inner loop.

==Schaeffer==
In his 1987 [[ICGA Journal|ICCA Journal]] paper ''Speculative Computing'', [[Jonathan Schaeffer]] mentioned ''The Null-Move Algorithm'' or ''Don Beal's null-move'', and used it non-[[Recursion|recursively]] up to once per search path in his tactical [[Scout|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 <ref>[[Jonathan Schaeffer]] ('''1987'''). ''Speculative Computing''. [[ICGA Journal#10_3|ICCA Journal, Vol. 10, No. 3]]</ref>.

==Goetsch and Campbell==
[[Gordon Goetsch]] and [[Murray Campbell]] published the results of some experiments with Null move pruning in 1988 and 1990 <ref>[[Gordon Goetsch]], [[Murray Campbell]] ('''1988'''). ''Experimenting with the Null Move Heuristic in Chess''. AAAI Spring Symposium Proceedings, pp. 14-18</ref> <ref>[[Gordon Goetsch]], [[Murray Campbell]] ('''1990'''). ''[https://link.springer.com/chapter/10.1007/978-1-4613-9080-0_9 Experiments with the Null-Move Heuristic]''. [[Computers, Chess, and Cognition]], pp. 159-168</ref>, already considering [[Recursion|recursive]] NMP with [[Depth Reduction R|depth reduction]] of 1, also mentioned in [[Chun Ye|Chun Ye's]] 1992 thesis with source code as implemented inside the [[Chinese Chess]] program [[Abyss]] <ref>[[Chun Ye]] ('''1992'''). ''Experiments in Selective Search Extensions''. M.Sc. thesis, Department of Computing Science, [[University of Alberta]], [https://era.library.ualberta.ca/public/datastream/get/uuid:e4fbf48d-7603-490f-85cc-5497bbecf5a8/DS1 pdf], pp. 27-29 </ref> .

==Morsch and Donninger==
Null move pruning was used [[Recursion|recursively]] to possibly occur multiple times inside a path of the search by [[Frans Morsch]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=288321&t=28775 Re: SOMA] by [[Ed Schroder|Ed Schröder]], [[CCC]], August 26, 2009</ref> 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 [[ICGA Journal|ICCA Journal]] [[Timeline#1993|1993]] <ref>[[Chrilly Donninger]] ('''1993'''). ''Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs.'' [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]</ref> .
<span id="Schemes"></span>
=Schemes=
Most typical engines use [[Recursion|recursive]] null move with an [[Depth Reduction R|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 [[Reductions|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|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.
<span id="AdaptiveNullMovePruning"></span>
==Adaptive Null Move Pruning==
[[Ernst A. Heinz]] proposed refinements with Adaptive Null Move Pruning <ref>[[Ernst A. Heinz]]. ('''1999'''). ''Adaptive null-move pruning''. [[ICGA Journal#22_3|ICCA Journal, Vol. 22, No. 3]], [http://people.csail.mit.edu/heinz/ps/adpt_null.ps.gz ps]</ref> . Some programs vary R with [[Depth|depth]], or based on [[Evaluation|evaluation]] features, such as being in or near the [[Endgame|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|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|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|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|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:
<span id="ZugzwangVerification"></span>
==Zugzwang Verification==
Concerning null move failures in [[Zugzwang|zugzwang]] <ref>[https://www.stmintz.com/ccc/index.php?id=76352 Position from local chess club] by Bernhard Bauer, [[CCC]], November 05, 1999</ref> , there were proposals by [[Stefan Plenkner]] 1995, <ref>[[Stefan Plenkner]] ('''1995'''). ''A Null-Move Technique Impervious to Zugzwang.'' [[ICGA Journal#18_2|ICCA Journal, Vol. 18, No. 2]]</ref> <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/0840bc8aabd0f6e5# Null-move zugzwang avoidance, Jun '95 ICCAJ] by [[Bruce Moreland]] in [[Computer Chess Forums|rgcc]], December 6, 1996</ref> and later the ''Verified Null-Move Pruning'' approach by [[Omid David]] and [[Nathan S. Netanyahu]] <ref>[[Omid David]], [[Nathan S. Netanyahu]] ('''2002'''). ''Verified null-move pruning.'' [[ICGA Journal#25_3|ICGA Journal, Vol. 25 No. 3]]</ref> . 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]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=28561 verified null move] by [[Robert Hyatt]], [[CCC]], June 21, 2009</ref> similar with [[Null Move Reductions|extended null-move reductions]] <ref>[[Omid David]], [[Nathan S. Netanyahu]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_19 Extended Null-Move Reductions]''. [[CG 2008]], [http://www.oedavid.com/pubs/nmr.pdf pdf]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=367273&t=35841 Re: Extended Null-Move Reductions] by [[Robert Hyatt]], [[CCC]], August 20, 2010</ref> . However, [[Marco Costalba]] states that verification search has almost nothing to do with zugzwang <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=367314&t=35841 Re: Extended Null-Move Reductions] by [[Marco Costalba]], [[CCC]], August 20, 2010</ref> .
<span id="DoubleNullMove"></span>
==Double Null Move==
Widely discussed in [[Computer Chess Forums|computer chess forums]] was the [[Double Null Move]] idea by [[Vincent Diepeveen]] to perform two consecutive null moves to detect zugzwang <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/PrN_AXwYV_4/UXU5x67UaoQJ Re: Null move?] by [[Vincent Diepeveen]], [[Computer Chess Forums|rgcc]], October 11, 1997</ref> .
<span id="VariableNMBound"></span>
==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|tempo]] bonus, was already proposed by [[Gordon Goetsch]] and [[Murray Campbell]] in 1988 as future research idea <ref>[[Gordon Goetsch]], [[Murray Campbell]] ('''1988'''). ''Experimenting with the Null Move Heuristic in Chess''. AAAI Spring Symposium Proceedings, pp. 14-18</ref> . [[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|root]] to the current node as estimated by positive scores of generated moves from the [[History Heuristic|history heuristic]], was used to determine a tempo bonus of 10 or 20 [[Centipawns|centipawns]] - the higher numPGAM, the lower the probability that an erroneous forward pruning decision will propagate up the tree <ref>[[Yngvi Björnsson]], [[Tony Marsland]] ('''2000'''). ''Selective Depth-First Search Methods''. in [[Jaap van den Herik]], [[Hiroyuki Iida]] (eds.) ('''2000'''). ''Games in AI Research''. [[Maastricht University|Universiteit Maastricht]], [http://www.cs.ualberta.ca/%7Etony/RecentPapers/nec97w.pdf pdf preprint]</ref> .
<pre>
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
}
}
</pre>
''For zwSearch, see [[Principal Variation Search#ZWS|Zero Window Search]] inside the [[Principal Variation Search]].''
<span id="ThreatDetection"></span>
=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 Move|threat moves]] by the opponent to improve further [[Move Ordering|move ordering]] and to possibly trigger [[Mate Threat Extensions|mate threat extensions]] <ref>[https://www.stmintz.com/ccc/index.php?id=14259 Deep Search Extension] by [[Stuart Cracraft]], [[CCC]], January 18, 1998</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=57953 Null move mate extension] by [[James Robertson]], [[CCC]], June 25, 1999</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=389013 mate threat extension/null move] by [[Rick Bischoff]], [[CCC]], September 25, 2004</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=390268 Re: mate threat extension/null move] by [[Don Beal]], [[CCC]], October 04, 2004 » [[Mate Threat Extensions]] and [[Win at Chess|WAC]] booster</ref> . However, some kind of [[Fail-Soft|fail-soft]] framework is necessary to recognize "I get mated, if I do nothing", otherwise the hard bound of a [[Null Window|null window]] null-move search around [[Beta|beta]] will limit the [[Upper Bound|upper bound]] to beta-1 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=24543 null move threat extension] by [[Andrew Short]], [[CCC]], October 23, 2008</ref> . Another, possibly too expensive solution with a [[Fail-Hard|fail-hard]] framework, is to play a bit with the search window, if the null move doesn't fail high:
<pre>
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();
}
}
</pre>

==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 [https://en.wikipedia.org/wiki/World_Chess_Championship World Chess Champion] [[Mikhail Botvinnik]], who addressed related issues in his publications <ref>[https://www.stmintz.com/ccc/index.php?id=318833 The "same threat extension" as effective way to resolve horizon problem] by [[Sergei Markoff]], [[CCC]], October 01, 2003</ref> .

==Influence on Move Ordering==
Most of the time, null move is refuted by a [[Captures|capture]]. Therefore it makes sense to extract a move that refuted null move from the [[Transposition Table|transposition table]], record the [[Target Square|target square]] of such a move, to give a [[Move Ordering|move ordering]] boost for escaping from that square. Also, there is a strong conjecture that in programs using [[History Heuristic|history move ordering]], even a failed null move search helps by filling the history tables faster.

=Test Results=
* [[Null Move Pruning Test Results]] - various experimental test results of null move pruning
* [[Null Move Test-Positions]], where Null Move may fail due to zugzwang

=See also=
* [[Enhanced Forward Pruning]]
* [[Extensions]]
* [[Fail-High Reductions]]
* [[Knowledge#SearchVersusEvaluation|Knowledge | Search versus Evaluation]]
* [[Multi-Cut]]
* [[Null Move Observation]]
* [[Null Move Reductions]]
* [[ProbCut]]
* [[Reductions]]
* [[Reverse Futility Pruning]] (Static Null Move Pruning)

=Publications=
==1966==
* [[George Baylor|George W. Baylor]], [[Herbert Simon|Herbert A. Simon]] ('''1966'''). ''[http://dl.acm.org/citation.cfm?id=1464182.1464233&coll=GUIDE&dl=GUIDE A chess mating combinations program]''. AFIPS Joint Computer Conferences, reprinted 1988 in [[Computer Chess Compendium]]
==1975==
* [[Georgy Adelson-Velsky]], [[Vladimir Arlazarov]], [[Mikhail Donskoy]] ('''1975'''). ''Some Methods of Controlling the Tree Search in Chess Programs''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6, No. 4, pp. 361-371. ISSN 0004-3702. Reprinted ('''1988''') in [[Computer Chess Compendium]]
==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''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 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 ...==
* [[Don Beal]] ('''1990'''). ''A Generalized Quiescence Search Algorithm''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702
* [[Gordon Goetsch]], [[Murray Campbell]] ('''1990'''). ''[https://link.springer.com/chapter/10.1007/978-1-4613-9080-0_9 Experiments with the Null-Move Heuristic]''. [[Computers, Chess, and Cognition]], pp. 159-168
* [[Chun Ye]] ('''1992'''). ''Experiments in Selective Search Extensions''. M.Sc. thesis, Department of Computing Science, [[University of Alberta]], [https://era.library.ualberta.ca/public/datastream/get/uuid:e4fbf48d-7603-490f-85cc-5497bbecf5a8/DS1 pdf]
* [[Chrilly Donninger]] ('''1993'''). ''Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs.'' [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]
* [[Stefan Plenkner]] ('''1995'''). ''A Null-Move Technique Impervious to Zugzwang.'' [[ICGA Journal#18_2|ICCA Journal, Vol. 18, No. 2]]
* [[Ernst A. Heinz]]. ('''1999'''). ''Adaptive null-move pruning''. [[ICGA Journal#22_3|ICCA Journal, Vol. 22, No. 3]], [http://people.csail.mit.edu/heinz/ps/adpt_null.ps.gz ps]
==2000 ...==
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''2000'''). ''Selective Depth-First Search Methods''. in [[Jaap van den Herik]], [[Hiroyuki Iida]] (eds.) ('''2000'''). ''Games in AI Research''. [[Maastricht University|Universiteit Maastricht]], [http://www.cs.ualberta.ca/%7Etony/RecentPapers/nec97w.pdf pdf preprint]
* [[Omid David]], [[Nathan S. Netanyahu]] ('''2002'''). ''Verified null-move pruning.'' [[ICGA Journal#25_3|ICGA Journal, Vol. 25 No. 3]] <ref>[https://www.stmintz.com/ccc/index.php?id=266356 Verified Null-Move Pruning, ICGA 25(3)] by [[Omid David]], [[CCC]], November 20, 2002</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=271270 Proving something is better] by [[Bruce Moreland]], [[CCC]], December 17, 2002</ref>
* [[Don Beal]] ('''2006'''). ''[[File:alg1986review.txt|Review of a nullmove-quiescence search mechanism from 1986]]''. (Draft) <ref>courtesy of [[Don Beal]] and [[Carey Bloodworth]], [http://www.talkchess.com/forum/viewtopic.php?t=58603&start=13 Re: Antique chess programs] by [[Carey Bloodworth|Carey]], [[CCC]], December 16, 2015</ref>
* [[Omid David]], [[Nathan S. Netanyahu]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_19 Extended Null-Move Reductions]''. [[CG 2008]], [http://www.oedavid.com/pubs/nmr.pdf pdf]
* [[Daniel Shawul|Daniel S. Abdi]] ('''2013'''). ''Analysis of pruned minimax trees''. [https://dl.dropboxusercontent.com/u/55295461/analysis/pruning.pdf pdf] » [[Alpha-Beta]], [[Late Move Reductions]]

=Forum Posts=
==1995 ...==
* [http://groups.google.com/group/rec.games.chess/browse_frm/thread/4240e92cca890050 Null Move heuristic] by [[Valavan Manohararajah]], [[Computer Chess Forums|rec.games.chess]], July 28, 1995
'''1997'''
* [https://groups.google.com/d/msg/rec.games.chess.computer/JJTEBafyuYM/hRTys0ZxcUIJ Null move depth reductions] by [[Tom King]], [[Computer Chess Forums|rgcc]], February 02, 1997 » [[Depth Reduction R]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/3eb37f017c1857fe Null move?] by MLC, [[Computer Chess Forums|rgcc]], October 07, 1997
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/8b835621f7790967 Searching correctly with the Nullmove ==> no zugzwang problems anymore] by [[Vincent Diepeveen]], [[Computer Chess Forums|rgcc]], October 23, 1997
'''1998'''
* [https://www.stmintz.com/ccc/index.php?id=19827 During Null Move search] by [[Peter Fendrich]], [[CCC]], June 02, 1998
* [https://www.stmintz.com/ccc/index.php?id=20167 Extend or not extend in a nullmove tree] by [[Roland Pfister]], [[CCC]], June 08, 1998 » [[Extensions]]
* [https://www.stmintz.com/ccc/index.php?id=20596 Zero-width Window Null Move Search] by [[Dezhi Zhao]], [[CCC]], June 15, 1998 » [[Null Window]]
* [https://www.stmintz.com/ccc/index.php?id=21888 search extension] by [[Werner Inmann]], [[CCC]], July 08, 1998
* [https://www.stmintz.com/ccc/index.php?id=28772 Null move reductions] by [[Roberto Waldteufel]], [[CCC]], October 04, 1998
'''1999'''
* [https://www.stmintz.com/ccc/index.php?id=43328 Singular Extensions, Nullmove deepsearch] by [[Frank Schneider]], [[CCC]], February 16, 1999 » [[Singular Extensions]]
* [https://www.stmintz.com/ccc/index.php?id=44363 NULL MOVE] by Sylvain Lacombe, [[CCC]], February 24, 1999
: [https://www.stmintz.com/ccc/index.php?id=44497 To skin a cat (was Re: NULL MOVE)] by [[Don Dailey]], [[CCC]], February 24, 1999
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/0e56bda426a70a22# Null move around (beta-1, beta)] by [[Tom King]], [[Computer Chess Forums|rgcc]], March 05, 1999
* [https://www.stmintz.com/ccc/index.php?id=57953 Null move mate extension] by [[James Robertson]], [[CCC]], June 25, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=123156 Pseudo C code for double nullmove + PVS] by [[Vincent Diepeveen]], [[CCC]], August 06, 2000
* [https://www.stmintz.com/ccc/index.php?id=129985 is this nullmove? problems in pulsar algorithm] by [[Mike Adams]], [[CCC]], September 20, 2000 » [[Pulsar]]
'''2001'''
* [https://www.stmintz.com/ccc/index.php?id=148745 Can nullmoves behave like this?] by [[Severi Salminen]], [[CCC]], January 08, 2001
* [https://www.stmintz.com/ccc/index.php?id=156376 Nullmove: when to avoid it?] by [[Leen Ammeraal]], [[CCC]], February 28, 2001
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=33381&p=126413 An idea for all you chess programmers.] by Paul, [[Computer Chess Forums|Winboard Forum]], March 16, 2001
* [https://www.stmintz.com/ccc/index.php?id=160954 Double Nullmove] by [[David Rasmussen]], [[CCC]], March 30, 2001
* [https://www.stmintz.com/ccc/index.php?id=179604 Double Null move?] by [[Steve Maughan]], [[CCC]], July 13, 2001
* [https://www.stmintz.com/ccc/index.php?id=183089 Null move R=2 vs Null move R=2/3] by [[Tom King]], [[CCC]], August 09, 2001 » [[Depth Reduction R]]
'''2002'''
* [https://www.stmintz.com/ccc/index.php?id=210702 Crafty-IsiChess,CCT4,r11 ==> A move to avoid?] by [[José Antônio Fabiano Mendes]], [[CCC]], January 29, 2002
* [https://www.stmintz.com/ccc/index.php?id=225990 Double Nullmove] by [[Andreas Herrmann]], [[CCC]], April 25, 2002
* [https://www.stmintz.com/ccc/index.php?id=239907 Null-Move: Difference between R = 2 and R = 3 in action] by [[Omid David]], [[CCC]], July 11, 2002
* [https://www.stmintz.com/ccc/index.php?id=266356 Verified Null-Move Pruning, ICGA 25(3)] by [[Omid David]], [[CCC]], November 20, 2002
* [https://www.stmintz.com/ccc/index.php?id=267039 new thoughts on verified null move] by [[Scott Farrell]], [[CCC]], November 23, 2002
'''2003'''
* [https://groups.google.com/d/msg/rec.games.chess.computer/iECalt6Tzug/GWNOLzFQyk8J An interesting forward pruning experiment - with pseudo description] by [[Vincent Diepeveen]], [[Computer Chess Forums|rgcc]], February 08, 2003
* [https://www.stmintz.com/ccc/index.php?id=318833 The "same threat extension" as effective way to resolve horizon problem] by [[Sergei Markoff]], [[CCC]], October 01, 2003 » [[Botvinnik-Markoff Extension]]
* [https://www.stmintz.com/ccc/index.php?id=319187 a question to Tord about detecting threats in null move] by [[Uri Blass]], [[CCC]], October 03, 2003
'''2004'''
* [https://www.stmintz.com/ccc/index.php?id=348841 Re: not using nullmove?] by [[Tord Romstad]], [[CCC]], February 13, 2004
* [https://www.stmintz.com/ccc/index.php?id=354078 mtd(f) and null move] by [[Peter Aloysius Harjanto|Peter Alloysius]], [[CCC]], March 11, 2004 » [[MTD(f)]]
* [https://www.stmintz.com/ccc/index.php?id=373804 double null move help] by [[Daniel Shawul]], [[CCC]], July 04, 2004
* [https://www.stmintz.com/ccc/index.php?id=377240 An MTD(f) question about NULL MOVE searching] by [[Dann Corbit]], [[CCC]], July 16, 2004 » [[MTD(f)]]
* [https://www.stmintz.com/ccc/index.php?id=378541 null move question(Fruit)] by [[Jan Kaan|Jan K.]], [[CCC]], July 22, 2004
* [https://www.stmintz.com/ccc/index.php?id=389013 mate threat extension/null move] by [[Rick Bischoff]], [[CCC]], September 25, 2004
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=2071 recusive null move in iterative search] by [[Daniel Shawul]], [[Computer Chess Forums|Winboard Forum]], March 25, 2005 » [[Iterative Search]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?t=2300 Reductions and null move refutations] by [[Tord Romstad]], [[Computer Chess Forums|Winboard Forum]], April 18, 2005 » [[Reductions]], [[Late Move Reductions]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=3004&p=14559 depthnull] by [[Pedro Castro]], [[Computer Chess Forums|Winboard Programming Forum]], July 04, 2005
'''2006'''
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4480&p=23303 Verified null-move pruning] by [[Tom King]], [[Computer Chess Forums|Winboard Programming Forum]], March 09, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4660&start=0 Simple NULL move enhancement, checks in qsearch] by [[Mark Lefler]], [[Computer Chess Forums|Winboard Programming Forum]], April 14, 2006
'''2007'''
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6392 NMP on ALL nodes] by [[Onno Garms]], [[Computer Chess Forums|Winboard Programming Forum]], April 15, 2007 » [[Node Types#ALL|All Nodes]]
* [http://www.hiarcs.net/forums/viewtopic.php?p=2944 Re: Search or Evaluation?] by [[Mark Uniacke]], [[Computer Chess Forums|Hiarcs Forum]], October 14, 2007
* [http://www.talkchess.com/forum/viewtopic.php?p=160677 Null Move] by [[Stuart Cracraft]], [[CCC]], November 23, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=18081 fractal null move] by [[Pawel Koziol]], [[CCC]], November 28, 2007
'''2008'''
* [http://www.talkchess.com/forum/viewtopic.php?t=24543 null move threat extension] by [[Andrew Short]], [[CCC]], October 23, 2008
'''2009'''
* [http://www.talkchess.com/forum/viewtopic.php?t=29439 Null move in quiescence search idea from Don Beal, 1986] by [[Eelco de Groot]], [[CCC]], Aug 17, 2009 » [[Quiescence Search]], [[Don Beal]]
* [http://www.talkchess.com/forum/viewtopic.php?t=28561 verified null move] by [[Robert Hyatt]], [[CCC]], June 21, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=29873 Null-moves and zugzwang] by [[Luca Hemmerich]], [[CCC]], September 25, 2009 » [[Zugzwang]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=314332&t=31413 Using Heinz in 2010 is not optimal] by [[Milos Stanisavljevic]], [[CCC]], January 01, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=33514 Null-move pruning and the hash table] by [[Robert Purves]], [[CCC]], March 28, 2010 » [[Transposition Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=35052 nullmove and repetitive draw detection] by [[Edward Yu]], [[CCC]], June 20, 2010 » [[Repetitions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=35543 Stockfish null move pre-condition] by [[Rein Halbersma]], [[CCC]], July 22, 2010 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?p=367283 Extended Null-Move Reductions] by [[Alvaro Cardoso]], [[CCC]], August 20, 2010
'''2011'''
* [http://www.talkchess.com/forum/viewtopic.php?t=38409 Less null move pruning by trans map] by [[Onno Garms]], [[CCC]], March 13, 2011 » [[Onno]]
* [http://www.talkchess.com/forum/viewtopic.php?t=38640 Null Move Pruning] by Alex Farley, [[CCC]], April 03, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=41104 Null move alternative in endgames] by [[Aleks Peshkov]], [[CCC]], November 16, 2011
'''2012'''
* [http://www.talkchess.com/forum/viewtopic.php?t=44666 TT avoid nullmove flag] by [[Matthew R. Brades]], [[CCC]], August 02, 2012 » [[Transposition Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=44686 Nullmove vs classic selective search] by [[Ed Schroder|Ed Schröder]], [[CCC]], August 04, 2012 <ref>[http://www.top-5000.nl/authors/rebel/chess840.htm#SELECTIVE%20SEARCH Selective Search Techniques in REBEL (introduction)] from [http://www.top-5000.nl/authors/rebel/chess840.htm Programmer Corner] by [[Ed Schroder|Ed Schröder]]</ref>
'''2013'''
* [http://www.open-chess.org/viewtopic.php?f=5&t=2210 Null Move Fail] by [[Christian Daley|CDaley11]], [[Computer Chess Forums|OpenChess Forum]], January 10, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47189 Two questions] by [[Jerry Donald]], [[CCC]], February 11, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=49351 nullmove verification vs avoid null] by [[Martin Sedlak]], [[CCC]], September 14, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=49863 Null move, razoring and mate threats] by [[Jon Dart]], [[CCC]], October 28, 2013 » [[Razoring]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50587 Is SF DD greater efficiency would be null move pruning?] by Jonathan Lee, [[CCC]], December 22, 2013 » [[Stockfish]]
'''2014'''
* [http://www.talkchess.com/forum/viewtopic.php?t=51129 fixing the null move search "bug"] by [[Uri Blass]], [[CCC]], February 01, 2014 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=51291 Disabling Null Move Pruning in Stockfish] by [[Louis Zulli]], [[CCC]], February 15, 2014 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=51578 Null move and LMR] by [[Laurie Tunnicliffe]], [[CCC]], March 12, 2014 » [[Late Move Reductions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=53049 Null move pruning on PV nodes] by [[Eric Oldre]], [[CCC]], July 22, 2014 » [[Node Types#PV|PV-Nodes]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=56272 Why not two consecutive null moves ?] by [[Henk van den Belt]], [[CCC]], May 07, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56672 thoughts on null-move reduction] by [[Youri Matiounine]], [[CCC]], June 14, 2015 » [[Null Move Reductions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=57638 Null move: minimum depth] by [[Henk van den Belt]], [[CCC]], September 14, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58527 Null Move in Quiescent search] by [[Laurie Tunnicliffe]], [[CCC]], December 09, 2015 » [[Quiescence Search]], [[Search Pathology]]
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=60366 When to do null move] by [[J. Wesley Cleveland]], [[CCC]], June 05, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=60561 Calculating R value for Null Move] by [[Andrew Grant]], [[CCC]], June 23, 2016 » [[Depth Reduction R]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2994 Null Move recommendations] by kickstone, [[Computer Chess Forums|OpenChess Forum]], July 29, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61086 Null Move in LMR] by [[Laurie Tunnicliffe]], [[CCC]], August 10, 2016 » [[Late Move Reductions]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61257 Nullmove bugs] by [[Matthew R. Brades]], [[CCC]], August 28, 2016
'''2017'''
* [http://www.talkchess.com/forum/viewtopic.php?t=62890 What is wrong with doing Nulls & ttcuts in a pv node ?] by [[Mahmoud Uthman]], [[CCC]], January 21, 2017 » [[Node Types#PV|PV-Nodes]], [[Transposition Table]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=3074 NULL Move code question] by thevinenator, [[Computer Chess Forums|OpenChess Forum]], January 27, 2017 » [[CPW-Engine_search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=63737 null move] by [[Folkert van Heusden]], [[CCC]], April 14, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64093 tt move vs null move] by [[Erin Dame]], [[CCC]], May 27, 2017 » [[Hash Move]], [[Null Move]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64266 End game and Null move] by [[Laurie Tunnicliffe]], [[CCC]], June 12, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64853 Fifty move counter and Null move] by Tamás Kuzmics, [[CCC]], August 09, 2017 » [[Fifty-move Rule]], [[Halfmove Clock]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64927 Rethinking r in null move] by [[Michael Sherwin]], [[CCC]], August 18, 2017 » [[Depth Reduction R]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65024 Question on Null Move Pruning] by [[Jason Fernandez]], [[CCC]], August 29, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=65121 Threat detection] by [[Harm Geert Muller]], [[CCC]], September 09, 2017 » [[Null Move Pruning#ThreatDetection|Threat Detection]], [[Threat Move]]

=External Links=
* [http://www.top-5000.nl/authors/rebel/chess840.htm#NULLMOVE Selective Search Techniques in REBEL (null-move)] from [http://www.top-5000.nl/authors/rebel/chess840.htm Programmer Corner] by [[Ed Schroder|Ed Schröder]] <ref>How Rebel Plays Chess is also available as [http://members.home.nl/matador/Inside%20Rebel.pdf pdf]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=44686 Nullmove vs classic selective search] by [[Ed Schroder|Ed Schröder]], [[CCC]], August 04, 2012</ref> » [[Rebel]]
* A presentation describing the power and flaws in null move pruning: [http://www.csse.uwa.edu.au/%7Elucas/files/411_null_move_heuristic_seminar.pdf Null Move pruning] (pdf) Slides by [http://www.csse.uwa.edu.au/%7Elucas/template.php?content=index Lucas Bradstreet]
* [https://en.wikipedia.org/wiki/Null-move_heuristic Null-move heuristic from Wikipedia]

=References=
<references />

'''[[Pruning|Up one level]]'''

Navigation menu