Difference between revisions of "Null Move Pruning"

From Chessprogramming wiki
Jump to: navigation, search
(Created page with "'''Home * Search * Selectivity * Pruning * Null Move Pruning''' FILE:SamuelBakSignals.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/ass...")
 
(28 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Search]] * [[Selectivity]] * [[Pruning]] * Null Move Pruning'''
 
'''[[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> ]]  
+
[[FILE:SamuelBakSignals.jpg|border|right|thumb|link=http://chgs.elevator.umn.edu/asset/viewAsset/57f3b6787d58ae5f74bf8ba9#57f3b6d77d58ae5574bf8bc5|[[:Category:Samuel 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], [[University of Minnesota]]</ref> ]]  
  
 
'''Null Move Pruning''',<br/>
 
'''Null Move Pruning''',<br/>
Line 45: Line 45:
 
<span id="ZugzwangVerification"></span>
 
<span id="ZugzwangVerification"></span>
 
==Zugzwang Verification==  
 
==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> .
+
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 [[Eli David]] and [[Nathan S. Netanyahu]] <ref>[[Eli David|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>[[Eli David|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>
 
<span id="DoubleNullMove"></span>
 
==Double Null Move==  
 
==Double Null Move==  
Line 127: Line 127:
 
==2000 ...==  
 
==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]
 
* [[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>
+
* [[Eli David|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 [[Eli David|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>
+
* [[Don Beal]] ('''2006'''). ''Review of a nullmove-quiescence search mechanism from 1986''. [[FILE:alg1986review.txt]] (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]
+
* [[Eli David|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]
 +
==2010 ...==
 +
* [[Kunihito Hoki]], [[Masakazu Muramatsu]]  ('''2012'''). ''[https://www.semanticscholar.org/paper/Efficiency-of-three-forward-pruning-techniques-in-Hoki-Muramatsu/206099961f401c8693e071c2b739f164ae5ffa6c Efficiency of three Forward-Pruning Techniques in Shogi: Futility Pruning, Null-move Pruning, and Late Move Reduction (LMR)]''. [https://www.journals.elsevier.com/entertainment-computing Entertainment Computing], Vol. 3, No. 3
 
* [[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]]
 
* [[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]]
  
Line 143: Line 145:
 
* [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=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=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=21888 search extension] by [[Werner Inmann]], [[CCC]], July 08, 1998 » [[#ThreatDetection|Threat Detection]]
 
* [https://www.stmintz.com/ccc/index.php?id=28772 Null move reductions] by [[Roberto Waldteufel]], [[CCC]], October 04, 1998
 
* [https://www.stmintz.com/ccc/index.php?id=28772 Null move reductions] by [[Roberto Waldteufel]], [[CCC]], October 04, 1998
 
'''1999'''
 
'''1999'''
 +
* [https://www.stmintz.com/ccc/index.php?id=42137 Null move] by [[James Robertson]], [[CCC]], February 03, 1999
 +
* [https://www.stmintz.com/ccc/index.php?id=42804 Confusion on Null Move] by [[KarinsDad]], [[CCC]], February 09, 1999
 +
: [https://www.stmintz.com/ccc/index.php?id=42909 A Null Move Enhancement?] by [[Daniel Homan]], [[CCC]], February 10, 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=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=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
 
: [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
 
* [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=54279 Null move idea] by [[Heiner Marxen]], [[CCC]], June 04, 1999
 
* [https://www.stmintz.com/ccc/index.php?id=57953 Null move mate extension] by [[James Robertson]], [[CCC]], June 25, 1999
 
* [https://www.stmintz.com/ccc/index.php?id=57953 Null move mate extension] by [[James Robertson]], [[CCC]], June 25, 1999
 +
* [https://www.stmintz.com/ccc/index.php?id=76399 It is a nullmove killer (zugzwang)] by [[Rémi Coulom]], [[CCC]], November 05, 1999 » [[Zugzwang]]
 +
: [https://www.stmintz.com/ccc/index.php?id=76542 Pseudo-code for verification search] by [[Daniel Homan|Dan Homan]], [[CCC]], November 06, 1999
 
==2000 ...==  
 
==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=123156 Pseudo C code for double nullmove + PVS] by [[Vincent Diepeveen]], [[CCC]], August 06, 2000
 +
* [https://www.stmintz.com/ccc/index.php?id=123206 double nullmove??] by [[Werner Inmann]], [[CCC]], August 06, 2000 » [[#DoubleNullMove|Double Null Move]]
 
* [https://www.stmintz.com/ccc/index.php?id=129985 is this nullmove? problems in pulsar algorithm] by [[Mike Adams]], [[CCC]], September 20, 2000 » [[Pulsar]]
 
* [https://www.stmintz.com/ccc/index.php?id=129985 is this nullmove? problems in pulsar algorithm] by [[Mike Adams]], [[CCC]], September 20, 2000 » [[Pulsar]]
 +
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=18&t=32639&start=1 Re: ZChess getting much stronger...] by [[Franck Zibi]], [[Computer Chess Forums|Winboard Forum]], November 10, 2000 » [[BBchess]], [[ZChess]]
 
'''2001'''
 
'''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=148745 Can nullmoves behave like this?] by [[Severi Salminen]], [[CCC]], January 08, 2001
Line 164: Line 174:
 
* [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=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=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=239907 Null-Move: Difference between R = 2 and R = 3 in action] by [[Eli David|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=266356 Verified Null-Move Pruning, ICGA 25(3)] by [[Eli David|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
 
* [https://www.stmintz.com/ccc/index.php?id=267039 new thoughts on verified null move] by [[Scott Farrell]], [[CCC]], November 23, 2002
 
'''2003'''
 
'''2003'''
Line 174: Line 184:
 
* [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=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=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=361766 When to do a null move search - an experiment] by [[Tord Romstad]], [[CCC]], April 26, 2004
 
* [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=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=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=378541 null move question(Fruit)] by [[Jan Kaan|Jan K.]], [[CCC]], July 22, 2004
 +
* [https://www.stmintz.com/ccc/index.php?id=381931 Verified Null-moving] by [[Tor Lattimore]], [[CCC]], August 12, 2004 » [[#ZugzwangVerification|Verified Null Move Pruning]]
 
* [https://www.stmintz.com/ccc/index.php?id=389013 mate threat extension/null move] by [[Rick Bischoff]], [[CCC]], September 25, 2004
 
* [https://www.stmintz.com/ccc/index.php?id=389013 mate threat extension/null move] by [[Rick Bischoff]], [[CCC]], September 25, 2004
 
==2005 ...==  
 
==2005 ...==  
Line 199: Line 211:
 
* [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?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=33514 Null-move pruning and the hash table] by [[Robert Purves]], [[CCC]], March 28, 2010 » [[Transposition Table]]
 +
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=50971 Null moves gain] by [[Giuseppe Cannella]], [[Computer Chess Forums|Winboard Forum]], May 13, 2010
 
* [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=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?t=35543 Stockfish null move pre-condition] by [[Rein Halbersma]], [[CCC]], July 22, 2010 » [[Stockfish]]
Line 208: Line 221:
 
'''2012'''
 
'''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=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>
+
* [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>Selective Search Techniques in REBEL (introduction) from [[Rebel#ProgrammerCorner|Programmer Corner]] by [[Ed Schroder|Ed Schröder]]</ref>
 
'''2013'''
 
'''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.open-chess.org/viewtopic.php?f=5&t=2210 Null Move Fail] by [[Christian Daley|CDaley11]], [[Computer Chess Forums|OpenChess Forum]], January 10, 2013
Line 237: Line 250:
 
* [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=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=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=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=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=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]]
 
* [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]]
 +
'''2018'''
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=66410 Making null move better?] by [[Michael Sherwin]], [[CCC]], January 25, 2018
 +
'''2019'''
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69722 Null move pruning, only when score >= beta?] by [[Tom King]], [[CCC]], January 25, 2019
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70118 idea: null-move analogy] by [[Harm Geert Muller]], [[CCC]], March 06, 2019
 +
==2020 ...==
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73713 Allowing null move pruning in the endgame] by Steven Griffin, [[CCC]], April 20, 2020 » [[Endgame]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73753 Null move]  by [[Robert Pope]], [[CCC]], April 24, 2020 » [[Stockfish]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74498 Null move pruning = lottery?] by [[Oliver Brausch]], [[CCC]], July 18, 2020
  
 
=External Links=  
 
=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]]
+
* Selective Search Techniques in REBEL (null-move) from [[Rebel#ProgrammerCorner|Programmer Corner]] by [[Ed Schroder|Ed Schröder]] <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]
 
* 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]
 
* [https://en.wikipedia.org/wiki/Null-move_heuristic Null-move heuristic from Wikipedia]
 +
* [[:Category:Larry Coryell|Larry Coryell]] & [[:Category:The Eleventh House|The Eleventh House]] - [https://en.wikipedia.org/wiki/Aspects_(The_Eleventh_House_album) Ain't It Is (Aspects)], 1976, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 +
: feat. [[:Category:Terumasa Hino|Terumasa Hino]], [[:Category:Gerry Brown|Gerry Brown]], [[:Category:John Lee|John Lee]], [https://www.discogs.com/artist/138771-Mike-Mandel Mike Mandel], and guests ... [[:Category:Michael Brecker|Michael Brecker]], [[:Category:Randy Brecker|Randy Brecker]], [[:Category:James Mtume|James Mtume]] et al.
 +
: {{#evu:https://www.youtube.com/watch?v=fQRyNe2SI1c|alignment=left|valignment=top}}
  
 
=References=  
 
=References=  
 
<references />
 
<references />
 
 
'''[[Pruning|Up one level]]'''
 
'''[[Pruning|Up one level]]'''
 +
[[Category:Samuel Bak]]
 +
[[Category:The Eleventh House]]
 +
[[Category:Michael Brecker]]
 +
[[Category:Randy Brecker]][[Category:Gerry Brown]]
 +
[[Category:Larry Coryell]]
 +
[[Category:Terumasa Hino]]
 +
[[Category:John Lee]]
 +
[[Category:James Mtume]]

Revision as of 09:24, 25 September 2020

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
Pseudo-code for verification search by Dan Homan, CCC, November 06, 1999

2000 ...

2001

2002

2003

2004

2005 ...

2006

2007

2008

2009

2010 ...

2011

2012

2013

2014

2015 ...

2016

2017

2018

2019

2020 ...

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. Nullmove vs classic selective search by Ed Schröder, CCC, August 04, 2012

Up one level