Changes

Jump to: navigation, search

Null Move Pruning

3,618 bytes added, 09:24, 25 September 2020
no edit summary
'''[[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#: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], [https://en.wikipedia.org/wiki/University_of_Minnesota [University of Minnesota]]</ref> ]]
'''Null Move Pruning''',<br/>
<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 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>
==Double Null Move==
==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]
* [[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]]''. [[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>* [[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]]
* [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» [[#ThreatDetection|Threat Detection]]
* [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=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=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=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=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 ...==
* [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]]
* [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'''
* [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=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 [[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 [[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
'''2003'''
* [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=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=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=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
==2005 ...==
* [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.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=35543 Stockfish null move pre-condition] by [[Rein Halbersma]], [[CCC]], July 22, 2010 » [[Stockfish]]
'''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 [Rebel#ProgrammerCorner|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=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]]
'''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=
* [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 [Rebel#ProgrammerCorner|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]
* [[: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 />
 
'''[[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]]

Navigation menu