25,161
edits
Changes
no edit summary
'''[[Main Page|Home]] * [[Search]] * Depth'''
[[FILE:EschersDepth.jpg|border|right|thumb|231px|link=http://www.mcescher.com/Gallery/recogn-bmp/LW403.jpg|[[Arts#:Category:M. C. Escher|M. C. Escher]], Depth, 1955 <ref>[http://www.mcescher.com/Gallery/gallery-recogn.htm Picture gallery "Recognition and Success 1955 - 1972"] from [http://www.mcescher.com/ The Official M.C. Escher Website]</ref>
]]
'''Depth''' is the height or ''nominal'' depth in [[Ply|plies]] between the [[Root|root]] and so called [[Horizon Node|horizon nodes]] (depth 0), where a heuristic value is assigned to. Thus, depth is the number of half moves the search ''nominally'' looks ahead.
Despite [[Quiescence Search|quiescence search]], where usually winning captures and even some checks are tried at or behind the search horizon, until positions become sufficiently quite, [[Selectivity|selectivity]] of modern chess programs, caused by [[Extensions|extensions]], [[Pruning|pruning]] and [[Reductions|reductions]], notably [[Check Extensions|check extensions]], [[Null Move Pruning|nNMPNMP]] and [[Late Move Reductions|LMR]], leads to bushy, non-uniform [[Search Tree|trees]] where some branches are searched deeper than nominal, but others shallower. A [[Depth Reduction R|depth reduction R]] of multiple plies is often performed in forward pruning techniques like [[Null Move Pruning|null move pruning]] and [[Multi-Cut|multi-cut]].
=Draft versus Ply-Index=
=See also=
* [[Alpha-Beta Conspiracy Search]]
* [[Extensions#FractionalExtensions|Fractional Extensions]]
* [[Iterative Deepening]]
* [[Selectivity]]
* [[SEX Algorithm]]
* [[Alexander Szabo#TechnologyCurve|The Technology Curve]]
=Publications=
* [[David Levy]], [[David Broughton]], [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]
==1990 ...==
* [[David McAllester]], [[Deniz Yuret]] ('''1993'''). ''Alpha-Beta Conspiracy Search''. [http://ttic.uchicago.edu/~dmcallester/abc.ps ps (draft)] » [[Alpha-Beta Conspiracy Search]]
* [[Robert Hyatt]], [[Monroe Newborn]] ('''1997'''). ''CRAFTY Goes Deep''. [[ICGA Journal#20_2|ICCA Journal, Vol. 20, No. 2]]
* [[Andreas Junghanns]], [[Jonathan Schaeffer]], [[Mark Brockington]], [[Yngvi Björnsson]], [[Tony Marsland]] ('''1997'''). ''Diminishing Returns for Additional Search in Chess''. [[Advances in Computer Chess 8]], [http://www.ru.is/faculty/yngvi/pdf/JunghannsSBBM97.pdf pdf]
* [[Ernst A. Heinz]] ('''2003'''). ''Follow-Up on Self-Play, Deep Search, and Diminishing Returns.'' [[ICGA Journal#26_2|ICGA Journal, Vol. 26, No. 2]]
* [[Jonathan Schaeffer]] ('''2004'''). ''8. Search Depth''. in AI- and Search, Online Course, [http://webdocs.cs.ualberta.ca/%7Ejonathan/Courses/657/Notes/8.SearchDepth.pdf slides as pdf]
* [[Jan Renze Steenhuisen]] ('''2005'''). ''New Results in Deep-Search Behaviour''. [[ICGA Journal#28_4|ICGA Journal, Vol. 28, No. 4]], [http://wwwciteseerx.stist.ewipsu.tudelft.nledu/%7Erenzeviewdoc/doc/ICGA_2005_4_DeepSearchsummary?doi=10.1.1.104.pdf pdf9527 CiteSeerX]
* [[Matej Guid]], [[Ivan Bratko]] ('''2007'''). ''Factors affecting diminishing returns for searching deeper''. [[CGW 2007]] » [[Crafty]], [[Rybka]], [[Shredder]], [[Depth#DiminishingReturns|Diminishing Returns]]
* [[Matej Guid]], [[Ivan Bratko]] ('''2007'''). ''Factors affecting diminishing returns for searching deeper''. [[ICGA Journal#30_2|ICGA Journal, Vol. 30, No. 2]], [http://www.ailab.si/matej/doc/Factors_Affecting_Diminishing_Returns.pdf pdf]
==2010 ...==
* [[Diogo R. Ferreira]] ('''2013'''). ''The Impact of the Search Depth on Chess Playing Strength''. [[ICGA Journal#36_2|ICGA Journal, Vol. 36, No. 2]]» [[#DiminishingReturns|Diminishing Returns]], [[Match Statistics]], [[Playing Strength]], [[Houdini]] <ref>[https://www.hiarcs.net/forums/viewtopic.php?t=10004 Ply versus ELO] by Greg, [[Computer Chess Forums|HIARCS Forum]], May 30, 2020 » [[Diogo R. Ferreira#Impact|Diogo R. Ferreira - Impact of the Search Depth ...]]</ref>
* [[Tamal T. Biswas]], [[Kenneth W. Regan]] ('''2015'''). ''Quantifying Depth and Complexity of Thinking and Knowledge''. [http://www.icaart.org/EuropeanProjectSpace.aspx?y=2015 ICAART 2015], [http://www.cse.buffalo.edu/~regan/papers/pdf/BiReICAART15CR.pdf pdf]
* [[Tamal T. Biswas]], [[Kenneth W. Regan]] ('''2015'''). ''Measuring Level-K Reasoning, Satisficing, and Human Error in Game-Play Data''. [[IEEE]] [http://www.icmla-conference.org/icmla15/ ICMLA 2015], [http://www.cse.buffalo.edu/~regan/papers/pdf/BiRe15_ICMLA2015.pdf pdf preprint]
* [[Matej Guid]], [[Ivan Bratko]] ('''2017'''). ''Influence of Search Depth on Position Evaluation''. [[Advances in Computer Games 15]]
=Forum PostsPostings= ==1983 ...==* [http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.07_alice.349_net.chess.txt chess strength] by [[Ken Thompson]], [http://quux.org:70/Archives/usenet-a-news/NET.chess net.chess], January 7, 1982
==1996 ...==
* [https://groups.google.com/d/msg/rec.games.chess.computer/1uVIWZFB41k/VUcAUkzyFd0J Fractional depth increments] by S. Read, [[Computer Chess Forums|rgcc]], January 18, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/aqg3nQsm9qM/8UIE5idQoJUJ Suggested chess experiment] by Henri H. Arsenault, [[Computer Chess Forums|rgcc]], February 17, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=92700 diminishing returns w/ increased search depth?] by [[Peter Kappler]], [[CCC]], January 27, 2000
* [https://www.stmintz.com/ccc/index.php?id=112359 A New Self-Play Experiment - Diminishing Returns Shown with 95% Conf.] by [[Ernst A. Heinz]], [[CCC]], May 24, 2000 » [[Depth#DiminishingReturns|Diminishing Returns]]
* [https://www.stmintz.com/ccc/index.php?id=129504 Faster, deeper and more of such...] by [[Ed Schroder|Ed Schröder]], [[CCC]], September 14, 2000 » [[Search Statistics]]
==2010 ...==
* [http://www.open-chess.org/viewtopic.php?f=5&t=1403 Node counts at a given depth/iteration in search] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], May 23, 2011
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=42677 Counting depth as a function of number of legal moves] by [[Pio Korinth]], [[CCC]], February 28, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=43134 Elo versus speed] by [[Peter Österlund]], [[CCC]], April 02, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=43596 From 5 ply to 6....] by [[Fernando Villegas]], [[CCC]], May 06, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=63326 Ridiculous QSearch Depth] by [[Jonathan Rosenthal]], [[CCC]], March 03, 2017 » [[Quiescence Search]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70217 Depth reduced but ELO increased] by [[Tom King]], [[CCC]], March 16, 2019 » [[Countermove Heuristic]], [[Playing Strength]]
==2020 ...==
* [https://www.hiarcs.net/forums/viewtopic.php?t=10004 Ply versus ELO] by Greg, [[Computer Chess Forums|HIARCS Forum]], May 30, 2020 » [[Diogo R. Ferreira#Impact|Diogo R. Ferreira - Impact of the Search Depth ...]]
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77202 On reaching maximum ply] by [[Martin Bryant]], [[CCC]], April 29, 2021 » [[#MaxPly|Maximum Search Depth]], [[Ply]], [[Search]]
=External Links=
=References=
<references />
'''[[Search|Up one Level]]'''
[[Category:M. C. Escher]]
[[Category:Roy Hargrove]]
[[Category:Ban Quotes]]
