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=
Diminishing returns are only proven (IMO) if 6 vs 5 wins more games than 12 vs 10 because only then are you comparing something linear and you give a linear advantage.
[[Ed Schroder|Ed Schröder]] conducted self-play experiments with [[Pro DeoProDeo|ProDeo 1.74]] playing different depths. Schröder also suggests that ProDeo has a [[Branching Factor|branching-factor]] of roughly 2, in other words an additional ply corresponds to a [[Match Statistics#DoublingTC|doubling of time]]. In the following table the values indicate the Elo advantage of ProDeo playing with depth A against itself with depth B. The exact tournament conditions can be studied on his webpage <ref>[http://www.top-5000.nl/ply.htm Experiments in computer chess: The value of depth and diminishing return effects] by [[Ed Schroder|Ed Schröder]], June 2012</ref> .
{| class="wikitable"
|-
=See also=
* [[Alpha-Beta Conspiracy Search]]
* [[Extensions#FractionalExtensions|Fractional Extensions]]
* [[Iterative Deepening]]
* [[Selectivity]]
* [[SEX Algorithm]]
* [[Alexander Szabo#TechnologyCurve|The Technology Curve]]
=Publications=
* [[Ken Thompson]] ('''1982'''). ''Computer Chess Strength''. [[Advances in Computer Chess 3]]
* [[Joe Condon]], [[Ken Thompson]] ('''1983'''). ''BELLE''. [[Chess Skill in Man and Machine]]
* [[Dana Nau|Dana S. Nau]] ('''1983'''). ''Decision quality as a function of search depth on game trees.'' [[ACM#Journal|Journal of the ACM]], Vol. 30, No. 4
* [[Hermann Kaindl]] ('''1983'''). ''Searching to Variable Depth in Computer Chess.'' Proceedings of [http://www.informatik.uni-trier.de/~ley/db/conf/ijcai/ijcai83.html IJCAI 83], pp. 760-762. Karlsruhe. [http://ijcai.org/Past%20Proceedings/IJCAI-83-VOL-2/PDF/039.pdf pdf]
* [[Monroe Newborn]] ('''1985'''). ''A Hypothesis Concerning the Strength of Chess Programs''. [[ICGA Journal#8_4|ICCA Journal, Vol. 8, No. 4]]
* [[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 ...==
* [httphttps://groups.google.com/groupd/msg/rec.games.chess.computer/browse_frm1uVIWZFB41k/thread/d6e548599141e359 VUcAUkzyFd0J Fractional depth increments] by S.Read, [[Computer Chess Forums|rgcc]], January 18, 1996* [httphttps://groups.google.com/groupd/msg/rec.games.chess.computer/browse_frm/threadS2G3dexGt9c/4b61b775ec46b7d7 UbX9UBq_xggJ Diminishing Returns in Search] by [[Jouni Uski]], [[Computer Chess Forums|rgcc]], September 6, 1996* [httphttps://groups.google.com/groupd/msg/rec.games.chess.computer/browse_frm/threadzJ1AyjmJ36w/cc9d40ca3989dfac bw5pRTcamXMJ HIARCS 5 Maximum Search Depth] by Kevin Miller, [[Computer Chess Forums|rgcc]], January 7, 1997
* [https://groups.google.com/d/msg/rec.games.chess.computer/eaOE_hvSZwc/fBwfX6LzD0kJ Ply depth (was: Deep Blue)] by [[Moritz Berger]], [[Computer Chess Forums|rgcc]], February 18, 1997
* [httphttps://groups.google.com/groupd/msg/rec.games.chess.computer/browse_frm/threadaqg3nQsm9qM/6aa8379d0b26f6a3 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=62622 Diminishing returns and hyperthreading] by [[Kai Laskos]], [[CCC]], December 27, 2016 » [[Depth#DiminishingReturns|Diminishing Returns]], [[Match Statistics]], [[Playing Strength]], [[Thread]]
* [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 ...]]
=External Links=
* [https://en.wikipedia.org/wiki/Draft Draft (disambiguation) from Wikipedia]
* [https://rjlipton.wordpress.com/2015/10/06/depth-of-satisficing/ Depth of Satisficing] by [[Kenneth W. Regan|Ken Regan]], [https://rjlipton.wordpress.com/ Gödel's Lost Letter and P=NP], October 06, 2015 » [[Depth]], [[Match Statistics]], [[Pawn Advantage, Win Percentage, and Elo]], [[Stockfish]], [[Komodo]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=57890 Regan's latest: Depth of Satisficing] by Carl Lumma, [[CCC]], October 09, 2015</ref>
* [[:Category:Roy Hargrove|Roy Hargrove Quintet]] - Depth, [https://en.wikipedia.org/wiki/Newport_Jazz_Festival Newport Jazz Festival], [https://www.setlist.fm/festival/2001/newport-jazz-festival-2001-73d69e8d.html August 11, 2001], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=8Edz7DZPtto|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one Level]]'''
[[Category:M. C. Escher]]
[[Category:Roy Hargrove]]
[[Category:Ban Quotes]]
