25,161
edits
Changes
Created page with "'''Home * Search * Depth''' FILE:EschersDepth.jpg|border|right|thumb|231px|link=http://www.mcescher.com/Gallery/recogn-bmp/LW403.jpg|[[Arts#Escher|M. C. E..."
'''[[Main Page|Home]] * [[Search]] * Depth'''
[[FILE:EschersDepth.jpg|border|right|thumb|231px|link=http://www.mcescher.com/Gallery/recogn-bmp/LW403.jpg|[[Arts#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|nNMP]] 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=
Most likely inside the search routine, a ply-index is used to index [[Stack|stacks]] or [[Array|arrays]] with pre-saved search information. This index is initialized with zero at the [[Root|root]], and is then incremented after making a move each time the [[Recursion|recursive]] search is called. This index measures the ply-distance from the current [[Node|node]] to the root and would therefor be sufficient to determine the remaining depth to the horizon, also called draft:
<pre>
draft ::= depth at the root - ply index
</pre>
However, there are various reasons to decouple the depth to horizon from the ply-index or depth from root, which are often passed as independent parameters to a recursive search routine (see code below). While the ply-index is incremented by one each time, the draft may be independently altered by various [[Extensions|extension]]- or [[Reductions|reduction]]-schemes and may also consider [[Extensions#FractionalExtensions|fractional extensions]] <ref>[[David Levy]], [[David Broughton]], [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]</ref> <ref>[[David Levy]] ('''2002'''). ''[http://ticc.uvt.nl/icga/journal/contents/content25-3.htm#SOME%20COMMENTS%20ON%20REALIZATION%20PROBABILITIES SOME COMMENTS ON REALIZATION PROBABILITIES AND THE SEX ALGORITHM]''. [[ICGA Journal#25_3|ICGA Journal, Vol. 25, No. 3]]</ref> .
<span id="FractionalPlies"></span>
=Fractional Plies=
Some programs extend or reduce in fractions of one ply. Inside an [[Iterative Deepening|iterative deepening]] framework, the search depth is incremented, usually by one ply - or by a fraction of one ply, for instance 1/2 ply.
[[Amir Ban]] on [[Junior]] in [[Computer Chess Forums|rgcc]], March 1998 <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/2163f0fa2f0715f1 Funny Junior Engine in CBLight / Junior Engine ply depth] by Wolfgang Krietsch, [[Computer Chess Forums|rgcc]], February 27, 1998, post 7 and 16 by [[Amir Ban]]</ref> :
The [[Brute-Force|brute-force]] [[Ply|ply]] [[Depth|depth]] is indeed half the publicized depth. All the rest are [[Extensions|extensions]] (in conventional terminology, I don't think of them this way). If you set Junior to depth 12, e.g., then you should be able to find a 7-ply combination where it fails. If I am doing a good job, then you should have a hard time finding one.
The question of what this is equivalent to in terms of other programs, e.g. a null-mover with "standard" extensions is interesting, but I don't know the answer. In tournament conditions middlegame Junior typically gets 14-16 depths, and it looks competitive tactically.
=Depth Comparison of different programs=
Due to different implementations, the reported search depth of chess programs is not comparable in general. Programs like [[The King]] ([[Chessmaster]]), [[Junior]] and [[Rybka]] are known for interpreting depth differently for whatever reasons.
=Selective Search Depth=
Some programs also report a selective search depth beside the nominal search depth, most often much greater than the nominal search depth. Some programs determine the highest distance to the root at any node, others only at the horizon.
<pre>
int highestDepth;
int iterativeDeepening() {
...
highestDepth = 0;
for (depth = 0; depth <= maxdepth; depth += DEPTH_OF_ONE_PLY) {
score = abSearch( -oo, +oo, depth, 0 );
if (timeIsOver (...) )
break;
}
...
}
int abSearch( int alpha, int beta, int depth, int ply ) {
depth += determineExtensions(...);
depth -= determineReductions(...);
if( depth <= 0 ) return quiesce( alpha, beta );
if ( ply > highestDepth )
highestDepth = ply;
for ( all moves) {
score = -abSearch( -beta, -alpha, depth - DEPTH_OF_ONE_PLY, ply + 1 );
if( score >= beta )
return beta; // beta cutoff
if( score > alpha )
alpha = score; // alpha acts like max in MiniMax
}
return alpha;
}
</pre>
<span id="MaxPly"></span>
=Maximum Search Depth=
The Maximum Search Depth of a [[Depth-First|depth-first search]] is usually determined by a [https://en.wikipedia.org/wiki/Compile_time compile time] constant in [[Ply|ply units]] (MAX_PLAY). It is used to statically allocate [[Array|arrays]] like a [[Triangular PV-Table]], or [[Stack#SearchStack|search stacks]] inside the programs [https://en.wikipedia.org/wiki/Data_segment data-] or [https://en.wikipedia.org/wiki/.bss bss segment]. While 64 was quite common, todays programs tend to use higher values, e.g. 128. A search routine should nevertheless check the upper bound of the search stack to immediate return a [[Lazy Evaluation|lazy evaluation]] score or [[Material#Balance|material balance]] when the ply index threatens overflow.
<span id="DiminishingReturns"></span>
=Diminishing Returns=
Despite the existence of [[Search Pathology|pathology]] in searching some trees, where a deeper [[Minimax|minimax]] search results in worse play, it is quite consensus in Chess that deeper search yields in stronger play. [[Playing Strength|Strength]] improvement from depth d to depth d+1 was first systematically examined by [[Ken Thompson]] with [[Belle]] in ''Computer Chess Strength'', as introduced at the [[Advances in Computer Chess 3]] conference in 1981 <ref>[[Ken Thompson]] ('''1982'''). ''Computer Chess Strength''. [[Advances in Computer Chess 3]]</ref> . Thompson found Belle (n+1) scored about 80% versus Belle (n), which roughly translates to a 200 [https://en.wikipedia.org/wiki/Elo_rating_system Elo] improvement playing one ply deeper, while the improvement seemed constant independent from the used depths from 3 to 8, while a second experiment <ref>[[Joe Condon]], [[Ken Thompson]] ('''1983'''). ''BELLE''. [[Chess Skill in Man and Machine]]</ref> indicated a falloff beyond depth 7.
{| class="wikitable"
|-
!
! P4
! P5
! P6
! P7
! P8
! P9
! Ratings
! Improvement
|-
! P4
| style="text-align:center;" |
| style="text-align:center;" | 5
| style="text-align:center;" | ½
| style="text-align:center;" | 0
| style="text-align:center;" | 0
| style="text-align:center;" | 0
| style="text-align:right;" | 1235
| style="text-align:right;" | -
|-
! P5
| style="text-align:center;" | 15
| style="text-align:center;" |
| style="text-align:center;" | 3½
| style="text-align:center;" | 3
| style="text-align:center;" | ½
| style="text-align:center;" | 0
| style="text-align:right;" | 1570
| style="text-align:right;" | 235
|-
! P6
| style="text-align:center;" | 19½
| style="text-align:center;" | 16½
| style="text-align:center;" |
| style="text-align:center;" | 4
| style="text-align:center;" | 1½
| style="text-align:center;" | 1½
| style="text-align:right;" | 1826
| style="text-align:right;" | 256
|-
! P7
| style="text-align:center;" | 20
| style="text-align:center;" | 17
| style="text-align:center;" | 16
| style="text-align:center;" |
| style="text-align:center;" | 5
| style="text-align:center;" | 4
| style="text-align:right;" | 2031
| style="text-align:right;" | 205
|-
! P8
| style="text-align:center;" | 20
| style="text-align:center;" | 19½
| style="text-align:center;" | 18½
| style="text-align:center;" | 15
| style="text-align:center;" |
| style="text-align:center;" | 5½
| style="text-align:right;" | 2208
| style="text-align:right;" | 167
|-
! P9
| style="text-align:center;" | 20
| style="text-align:center;" | 20
| style="text-align:center;" | 18½
| style="text-align:center;" | 16
| style="text-align:center;" | 14½
| style="text-align:center;" |
| style="text-align:right;" | 2328
| style="text-align:right;" | 120
|}
Also, in other board games such as [[Othello]] and [[Checkers]], additional plies of search translated into decreasing benefits, giving rise to [https://en.wikipedia.org/wiki/Diminishing_returns Diminishing returns] for deeper searching. In their 1997 paper ''Diminishing Returns for Additional Search in Chess'' <ref>[[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]</ref> , [[Andreas Junghanns|Junghanns]], [[Jonathan Schaeffer|Schaeffer]], [[Mark Brockington|Brockington]], [[Yngvi Björnsson|Björnsson]] and [[Tony Marsland|Marsland]] conclude the existence of Diminishing returns in Chess as well, somehow hidden by the high percentage of errors made by chess programs for lower search depth.
In self-play experiments with [[Crafty]], [[Robert Hyatt]], [[Monroe Newborn]] <ref>[[Robert Hyatt]], [[Monroe Newborn]] ('''1997'''). ''CRAFTY Goes Deep''. [[ICGA Journal#20_2|ICCA Journal, Vol. 20, No. 2]]</ref> and later [[Ernst A. Heinz]] with [[DarkThought]] <ref>[[Ernst A. Heinz]] ('''1998'''). ''[http://people.csail.mit.edu/heinz/dt/node46.html DarkThought Goes Deep].'' [[ICGA Journal#21_4|ICCA Journal, Vol. 21, No. 4]]</ref> steadily discovered new best moves while searching deeper. In further experiments <ref>[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</ref> , Heinz found indications of decreasing returns from increasing search in chess. In his 2001 [[ICGA Journal]] paper ''Self-Play, Deep Search and Diminishing Returns'' <ref>[[Ernst A. Heinz]] ('''2001'''). ''Self-Play, Deep Search and Diminishing Returns.'' [[ICGA Journal#24_2|ICGA Journal, Vol. 24, No. 2]]</ref> he gave following match results (3,000 games each) <ref>[https://www.stmintz.com/ccc/index.php?id=187276 ICGA_J (June) self-play information] by [[Guy Haworth]], [[CCC]], September 05, 2001</ref> :
* 12-ply was 84 Elo points better than 11 ply
* 11-ply was 92 Elo points better than 10 ply
* 10-ply was 115 Elo points better than 9 ply
[[Tony van Roon-Werten]] made following statement on ''Diminishing Returns'' <ref>[https://www.stmintz.com/ccc/index.php?id=324592 Re: In chess we will reach diminishing returns just like in Checkers 1994] by [[Tony van Roon-Werten|Tony Werten]], [[CCC]], October 30, 2003</ref> :
If two programs play with 5 vs 6 ply search, the second engine has a 20% depth advantage. With 10 vs 11 it's only 10%. So of course the difference in wins is smaller. ...
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 Deo|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"
|-
! depth A vs B
! 7
! 8
! 9
! 10
! 11
|-
! style="text-align:right;" | 6
| style="text-align:right;" | 180
| style="text-align:right;" | 321
| style="text-align:right;" | 401
| style="text-align:right;" |
| style="text-align:right;" |
|-
! style="text-align:right;" | 7
| style="text-align:right;" | 0
| style="text-align:right;" | 147
| style="text-align:right;" | 281
| style="text-align:right;" | 389
| style="text-align:right;" |
|-
! style="text-align:right;" | 8
| style="text-align:right;" |
| style="text-align:right;" | 0
| style="text-align:right;" | 151
| style="text-align:right;" | 255
| style="text-align:right;" | 386
|-
! style="text-align:right;" | 9
| style="text-align:right;" |
| style="text-align:right;" |
| style="text-align:right;" | 0
| style="text-align:right;" | 129
| style="text-align:right;" | 255
|-
! style="text-align:right;" | 10
| style="text-align:right;" |
| style="text-align:right;" |
| style="text-align:right;" |
| style="text-align:right;" | 0
| style="text-align:right;" | 127
|}
=See also=
* [[Extensions#FractionalExtensions|Fractional Extensions]]
* [[Iterative Deepening]]
* [[Knowledge#SearchVersusEvaluation|Knowledge | Search versus Evaluation]]
* [[Match Statistics]]
* [[Odd-Even Effect]]
* [[Playing Strength]]
* [[Ply]]
* [[Search Pathology]]
* [[Selectivity]]
* [[SEX Algorithm]]
=Publications=
==1978 ...==
* [[James Gillogly]] ('''1978'''). ''Performance Analysis of the Technology Chess Program''. Ph.D. Thesis. Tech. Report CMU-CS-78-189, [[Carnegie Mellon University]]
==1980 ...==
* [[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]]
* [[Alexander Szabo]], [[Barbara Szabo]] ('''1988'''). ''The Technology Curve Revisited''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]
* [[David Levy]], [[David Broughton]], [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]
==1990 ...==
* [[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]] ('''1998'''). ''[http://people.csail.mit.edu/heinz/dt/node46.html DarkThought Goes Deep].'' [[ICGA Journal#21_4|ICCA Journal, Vol. 21, No. 4]]
==2000 ...==
* [[Ernst A. Heinz]] ('''2000'''). ''A New Self-Play Experiment in Computer Chess''. [[Massachusetts Institute of Technology]], Laboratory of Computer Science, Technical Memo No. 608, [http://supertech.lcs.mit.edu/~heinz/ps/new_exp.ps.gz zipped ps], [http://bitsavers.trailing-edge.com/pdf/mit/lcs/tm/MIT-LCS-TM-608.pdf pdf]
* [[Ernst A. Heinz]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_18 New Self-Play Results in Computer Chess]''. [[CG 2000]]
* [[Ernst A. Heinz]] ('''2001'''). ''Self-play Experiments in Computer Chess Revisited.'' [[Advances in Computer Games 9]]
* [[Ernst A. Heinz]] ('''2001'''). ''Modeling the “Go Deep” Behaviour of CRAFTY and DARK THOUGHT.'' [[Advances in Computer Games 9]]
* [[Ernst A. Heinz]] ('''2001'''). ''Self-Play, Deep Search and Diminishing Returns.'' [[ICGA Journal#24_2|ICGA Journal, Vol. 24, No. 2]]
* [[David Levy]] ('''2002'''). ''[http://ticc.uvt.nl/icga/journal/contents/content25-3.htm#SOME%20COMMENTS%20ON%20REALIZATION%20PROBABILITIES SOME COMMENTS ON REALIZATION PROBABILITIES AND THE SEX ALGORITHM]''. [[ICGA Journal#25_3|ICGA Journal, Vol. 25, No. 3]]
* [[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://www.st.ewi.tudelft.nl/%7Erenze/doc/ICGA_2005_4_DeepSearch.pdf pdf]
* [[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]]
* [[Tamal T. Biswas]], [[Kenneth Wingate Regan|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 Wingate Regan|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 Posts=
==1996 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/d6e548599141e359 Fractional depth increments] by S.Read, [[Computer Chess Forums|rgcc]], January 18, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/4b61b775ec46b7d7 Diminishing Returns in Search] by [[Jouni Uski]], [[Computer Chess Forums|rgcc]], September 6, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/cc9d40ca3989dfac 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
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/6aa8379d0b26f6a3 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]]
* [https://www.stmintz.com/ccc/index.php?id=187276 ICGA_J (June) self-play information] by [[Guy Haworth]], [[CCC]], September 05, 2001 <ref>[[Ernst A. Heinz]] ('''2001'''). ''Self-Play, Deep Search and Diminishing Returns.'' [[ICGA Journal#24_2|ICGA Journal, Vol. 24, No. 2]]</ref>
* [https://www.stmintz.com/ccc/index.php?id=198429 About diminishing returns (Uri)] by [[Jouni Uski]], [[CCC]], November 22, 2001
* [https://www.stmintz.com/ccc/index.php?id=212683 The probability to find better move is simply irrelevant for diminishing returns] by [[Uri Blass]], [[CCC]], February 09, 2002
* [https://www.stmintz.com/ccc/index.php?id=240056 The law of diminishing returns] by [[Ed Schroder|Ed Schröder]], [[CCC]], July 12, 2002
* [https://www.stmintz.com/ccc/index.php?id=310897 Regarding Qsearch with Fractional ply extensions] by [[Federico Andrés Corigliano|Federico Corigliano]], [[CCC]], August 11, 2003 » [[Quiescence Search]]
* [https://www.stmintz.com/ccc/index.php?id=324345 In chess we will reach diminishing returns just like in Checkers 1994] by Jorge Pichard, [[CCC]], October 29, 2003 <ref>[http://www.chessbase.com/newsdetail.asp?newsid=1270 Perfection in checkers], [[ChessBase|ChessBase News]], October 29, 2003</ref>
* [https://www.stmintz.com/ccc/index.php?id=345836 diminishing returns] by Duncan Roberts, [[CCC]], January 30, 2004
* [https://www.stmintz.com/ccc/index.php?id=356109 Shredder 8 secret: search depth?] by [[Jouni Uski]], [[CCC]], March 23, 2004
: [https://www.stmintz.com/ccc/index.php?id=356131 Re: Shredder 8 secret: search depth?] by [[Vasik Rajlich]], [[CCC]], March 23, 2004 » [[Shredder]], [[Junior]], [[Fritz]]
* [https://www.stmintz.com/ccc/index.php?id=362189 Diminishing returns] by [[Tony van Roon-Werten|Tony Werten]], [[CCC]], April 29, 2004
* [http://www.talkchess.com/forum/viewtopic.php?start=0&t=29011 Diminishing returns of increasing search depth] by Jarkko, [[CCC]], July 18, 2009
==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/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=43598 Elo Increase per Doubling] by [[Adam Hair]], [[CCC]], May 07, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=44889 Diminishing returns in fixed depth testing revisited] by [[Jesús Muñoz]], [[CCC]], August 25, 2012
* [http://forum.computerschach.de/cgi-bin/mwf/topic_show.pl?tid=5184 Houdini 3-Houdini 3: Nutzen der Bedenkzeitverlängerung] by Patrick Götz, [[Computer Chess Forums|CSS-Forum]], December 07, 2012 (German) » [[Houdini]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46370 Elo points gain from doubling time] by [[Kai Laskos]], [[CCC]], December 10, 2012 » [[Komodo]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48733 Scaling at 2x nodes (or doubling time control).] by [[Kai Laskos]], [[CCC]], July 23, 2013 » [[Houdini]], [[Knowledge]], [[Depth#DiminishingReturns|Diminishing Returns]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48780 Time to depth measuring tool] by [[Peter Österlund]], [[CCC]], July 28, 2013 » [[Parallel Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50220 Stockfish depth vs. others; challenge] by [[Larry Kaufman]], [[CCC]], November 24, 2013 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54296 How many plies are searched in a typical chess program?] by Stephen Dause, [[CCC]], November 09, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=56044 Fractional plies and transposition tables] by [[Alexandru Mosoi]], [[CCC]], April 18, 2015 » [[Depth#FractionalPlies|Depth - Fractional Plies]], [[Transposition Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61784 Doubling of time control] by [[Andreas Strangmüller]], [[CCC]], October 21, 2016 » [[Match Statistics#DoublingTC|Doubling TC]], [[Depth#DiminishingReturns|Diminishing Returns]], [[Playing Strength]], [[Komodo]]
* [http://www.talkchess.com/forum/viewtopic.php?t=62146 Stockfish 8 - Double time control vs. 2 threads] by [[Andreas Strangmüller]], [[CCC]], November 15, 2016 » [[Match Statistics#DoublingTC|Doubling TC]], [[Depth#DiminishingReturns|Diminishing Returns]], [[Playing Strength]], [[Stockfish]]
* [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]]
=External Links=
* [https://en.wikipedia.org/wiki/Depth Depth from Wikipedia]
* [https://en.wikipedia.org/wiki/Depth-limited_search Depth-limited search from Wikipedia]
* [https://en.wikipedia.org/wiki/Diminishing_returns Diminishing returns from Wikipedia]
* [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 Wingate 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>
=References=
<references />
'''[[Search|Up one Level]]'''
[[FILE:EschersDepth.jpg|border|right|thumb|231px|link=http://www.mcescher.com/Gallery/recogn-bmp/LW403.jpg|[[Arts#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|nNMP]] 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=
Most likely inside the search routine, a ply-index is used to index [[Stack|stacks]] or [[Array|arrays]] with pre-saved search information. This index is initialized with zero at the [[Root|root]], and is then incremented after making a move each time the [[Recursion|recursive]] search is called. This index measures the ply-distance from the current [[Node|node]] to the root and would therefor be sufficient to determine the remaining depth to the horizon, also called draft:
<pre>
draft ::= depth at the root - ply index
</pre>
However, there are various reasons to decouple the depth to horizon from the ply-index or depth from root, which are often passed as independent parameters to a recursive search routine (see code below). While the ply-index is incremented by one each time, the draft may be independently altered by various [[Extensions|extension]]- or [[Reductions|reduction]]-schemes and may also consider [[Extensions#FractionalExtensions|fractional extensions]] <ref>[[David Levy]], [[David Broughton]], [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]</ref> <ref>[[David Levy]] ('''2002'''). ''[http://ticc.uvt.nl/icga/journal/contents/content25-3.htm#SOME%20COMMENTS%20ON%20REALIZATION%20PROBABILITIES SOME COMMENTS ON REALIZATION PROBABILITIES AND THE SEX ALGORITHM]''. [[ICGA Journal#25_3|ICGA Journal, Vol. 25, No. 3]]</ref> .
<span id="FractionalPlies"></span>
=Fractional Plies=
Some programs extend or reduce in fractions of one ply. Inside an [[Iterative Deepening|iterative deepening]] framework, the search depth is incremented, usually by one ply - or by a fraction of one ply, for instance 1/2 ply.
[[Amir Ban]] on [[Junior]] in [[Computer Chess Forums|rgcc]], March 1998 <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/2163f0fa2f0715f1 Funny Junior Engine in CBLight / Junior Engine ply depth] by Wolfgang Krietsch, [[Computer Chess Forums|rgcc]], February 27, 1998, post 7 and 16 by [[Amir Ban]]</ref> :
The [[Brute-Force|brute-force]] [[Ply|ply]] [[Depth|depth]] is indeed half the publicized depth. All the rest are [[Extensions|extensions]] (in conventional terminology, I don't think of them this way). If you set Junior to depth 12, e.g., then you should be able to find a 7-ply combination where it fails. If I am doing a good job, then you should have a hard time finding one.
The question of what this is equivalent to in terms of other programs, e.g. a null-mover with "standard" extensions is interesting, but I don't know the answer. In tournament conditions middlegame Junior typically gets 14-16 depths, and it looks competitive tactically.
=Depth Comparison of different programs=
Due to different implementations, the reported search depth of chess programs is not comparable in general. Programs like [[The King]] ([[Chessmaster]]), [[Junior]] and [[Rybka]] are known for interpreting depth differently for whatever reasons.
=Selective Search Depth=
Some programs also report a selective search depth beside the nominal search depth, most often much greater than the nominal search depth. Some programs determine the highest distance to the root at any node, others only at the horizon.
<pre>
int highestDepth;
int iterativeDeepening() {
...
highestDepth = 0;
for (depth = 0; depth <= maxdepth; depth += DEPTH_OF_ONE_PLY) {
score = abSearch( -oo, +oo, depth, 0 );
if (timeIsOver (...) )
break;
}
...
}
int abSearch( int alpha, int beta, int depth, int ply ) {
depth += determineExtensions(...);
depth -= determineReductions(...);
if( depth <= 0 ) return quiesce( alpha, beta );
if ( ply > highestDepth )
highestDepth = ply;
for ( all moves) {
score = -abSearch( -beta, -alpha, depth - DEPTH_OF_ONE_PLY, ply + 1 );
if( score >= beta )
return beta; // beta cutoff
if( score > alpha )
alpha = score; // alpha acts like max in MiniMax
}
return alpha;
}
</pre>
<span id="MaxPly"></span>
=Maximum Search Depth=
The Maximum Search Depth of a [[Depth-First|depth-first search]] is usually determined by a [https://en.wikipedia.org/wiki/Compile_time compile time] constant in [[Ply|ply units]] (MAX_PLAY). It is used to statically allocate [[Array|arrays]] like a [[Triangular PV-Table]], or [[Stack#SearchStack|search stacks]] inside the programs [https://en.wikipedia.org/wiki/Data_segment data-] or [https://en.wikipedia.org/wiki/.bss bss segment]. While 64 was quite common, todays programs tend to use higher values, e.g. 128. A search routine should nevertheless check the upper bound of the search stack to immediate return a [[Lazy Evaluation|lazy evaluation]] score or [[Material#Balance|material balance]] when the ply index threatens overflow.
<span id="DiminishingReturns"></span>
=Diminishing Returns=
Despite the existence of [[Search Pathology|pathology]] in searching some trees, where a deeper [[Minimax|minimax]] search results in worse play, it is quite consensus in Chess that deeper search yields in stronger play. [[Playing Strength|Strength]] improvement from depth d to depth d+1 was first systematically examined by [[Ken Thompson]] with [[Belle]] in ''Computer Chess Strength'', as introduced at the [[Advances in Computer Chess 3]] conference in 1981 <ref>[[Ken Thompson]] ('''1982'''). ''Computer Chess Strength''. [[Advances in Computer Chess 3]]</ref> . Thompson found Belle (n+1) scored about 80% versus Belle (n), which roughly translates to a 200 [https://en.wikipedia.org/wiki/Elo_rating_system Elo] improvement playing one ply deeper, while the improvement seemed constant independent from the used depths from 3 to 8, while a second experiment <ref>[[Joe Condon]], [[Ken Thompson]] ('''1983'''). ''BELLE''. [[Chess Skill in Man and Machine]]</ref> indicated a falloff beyond depth 7.
{| class="wikitable"
|-
!
! P4
! P5
! P6
! P7
! P8
! P9
! Ratings
! Improvement
|-
! P4
| style="text-align:center;" |
| style="text-align:center;" | 5
| style="text-align:center;" | ½
| style="text-align:center;" | 0
| style="text-align:center;" | 0
| style="text-align:center;" | 0
| style="text-align:right;" | 1235
| style="text-align:right;" | -
|-
! P5
| style="text-align:center;" | 15
| style="text-align:center;" |
| style="text-align:center;" | 3½
| style="text-align:center;" | 3
| style="text-align:center;" | ½
| style="text-align:center;" | 0
| style="text-align:right;" | 1570
| style="text-align:right;" | 235
|-
! P6
| style="text-align:center;" | 19½
| style="text-align:center;" | 16½
| style="text-align:center;" |
| style="text-align:center;" | 4
| style="text-align:center;" | 1½
| style="text-align:center;" | 1½
| style="text-align:right;" | 1826
| style="text-align:right;" | 256
|-
! P7
| style="text-align:center;" | 20
| style="text-align:center;" | 17
| style="text-align:center;" | 16
| style="text-align:center;" |
| style="text-align:center;" | 5
| style="text-align:center;" | 4
| style="text-align:right;" | 2031
| style="text-align:right;" | 205
|-
! P8
| style="text-align:center;" | 20
| style="text-align:center;" | 19½
| style="text-align:center;" | 18½
| style="text-align:center;" | 15
| style="text-align:center;" |
| style="text-align:center;" | 5½
| style="text-align:right;" | 2208
| style="text-align:right;" | 167
|-
! P9
| style="text-align:center;" | 20
| style="text-align:center;" | 20
| style="text-align:center;" | 18½
| style="text-align:center;" | 16
| style="text-align:center;" | 14½
| style="text-align:center;" |
| style="text-align:right;" | 2328
| style="text-align:right;" | 120
|}
Also, in other board games such as [[Othello]] and [[Checkers]], additional plies of search translated into decreasing benefits, giving rise to [https://en.wikipedia.org/wiki/Diminishing_returns Diminishing returns] for deeper searching. In their 1997 paper ''Diminishing Returns for Additional Search in Chess'' <ref>[[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]</ref> , [[Andreas Junghanns|Junghanns]], [[Jonathan Schaeffer|Schaeffer]], [[Mark Brockington|Brockington]], [[Yngvi Björnsson|Björnsson]] and [[Tony Marsland|Marsland]] conclude the existence of Diminishing returns in Chess as well, somehow hidden by the high percentage of errors made by chess programs for lower search depth.
In self-play experiments with [[Crafty]], [[Robert Hyatt]], [[Monroe Newborn]] <ref>[[Robert Hyatt]], [[Monroe Newborn]] ('''1997'''). ''CRAFTY Goes Deep''. [[ICGA Journal#20_2|ICCA Journal, Vol. 20, No. 2]]</ref> and later [[Ernst A. Heinz]] with [[DarkThought]] <ref>[[Ernst A. Heinz]] ('''1998'''). ''[http://people.csail.mit.edu/heinz/dt/node46.html DarkThought Goes Deep].'' [[ICGA Journal#21_4|ICCA Journal, Vol. 21, No. 4]]</ref> steadily discovered new best moves while searching deeper. In further experiments <ref>[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</ref> , Heinz found indications of decreasing returns from increasing search in chess. In his 2001 [[ICGA Journal]] paper ''Self-Play, Deep Search and Diminishing Returns'' <ref>[[Ernst A. Heinz]] ('''2001'''). ''Self-Play, Deep Search and Diminishing Returns.'' [[ICGA Journal#24_2|ICGA Journal, Vol. 24, No. 2]]</ref> he gave following match results (3,000 games each) <ref>[https://www.stmintz.com/ccc/index.php?id=187276 ICGA_J (June) self-play information] by [[Guy Haworth]], [[CCC]], September 05, 2001</ref> :
* 12-ply was 84 Elo points better than 11 ply
* 11-ply was 92 Elo points better than 10 ply
* 10-ply was 115 Elo points better than 9 ply
[[Tony van Roon-Werten]] made following statement on ''Diminishing Returns'' <ref>[https://www.stmintz.com/ccc/index.php?id=324592 Re: In chess we will reach diminishing returns just like in Checkers 1994] by [[Tony van Roon-Werten|Tony Werten]], [[CCC]], October 30, 2003</ref> :
If two programs play with 5 vs 6 ply search, the second engine has a 20% depth advantage. With 10 vs 11 it's only 10%. So of course the difference in wins is smaller. ...
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 Deo|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"
|-
! depth A vs B
! 7
! 8
! 9
! 10
! 11
|-
! style="text-align:right;" | 6
| style="text-align:right;" | 180
| style="text-align:right;" | 321
| style="text-align:right;" | 401
| style="text-align:right;" |
| style="text-align:right;" |
|-
! style="text-align:right;" | 7
| style="text-align:right;" | 0
| style="text-align:right;" | 147
| style="text-align:right;" | 281
| style="text-align:right;" | 389
| style="text-align:right;" |
|-
! style="text-align:right;" | 8
| style="text-align:right;" |
| style="text-align:right;" | 0
| style="text-align:right;" | 151
| style="text-align:right;" | 255
| style="text-align:right;" | 386
|-
! style="text-align:right;" | 9
| style="text-align:right;" |
| style="text-align:right;" |
| style="text-align:right;" | 0
| style="text-align:right;" | 129
| style="text-align:right;" | 255
|-
! style="text-align:right;" | 10
| style="text-align:right;" |
| style="text-align:right;" |
| style="text-align:right;" |
| style="text-align:right;" | 0
| style="text-align:right;" | 127
|}
=See also=
* [[Extensions#FractionalExtensions|Fractional Extensions]]
* [[Iterative Deepening]]
* [[Knowledge#SearchVersusEvaluation|Knowledge | Search versus Evaluation]]
* [[Match Statistics]]
* [[Odd-Even Effect]]
* [[Playing Strength]]
* [[Ply]]
* [[Search Pathology]]
* [[Selectivity]]
* [[SEX Algorithm]]
=Publications=
==1978 ...==
* [[James Gillogly]] ('''1978'''). ''Performance Analysis of the Technology Chess Program''. Ph.D. Thesis. Tech. Report CMU-CS-78-189, [[Carnegie Mellon University]]
==1980 ...==
* [[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]]
* [[Alexander Szabo]], [[Barbara Szabo]] ('''1988'''). ''The Technology Curve Revisited''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]
* [[David Levy]], [[David Broughton]], [[Mark Taylor]] ('''1989'''). ''The SEX Algorithm in Computer Chess''. [[ICGA Journal#12_1|ICCA Journal, Vol. 12, No. 1]]
==1990 ...==
* [[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]] ('''1998'''). ''[http://people.csail.mit.edu/heinz/dt/node46.html DarkThought Goes Deep].'' [[ICGA Journal#21_4|ICCA Journal, Vol. 21, No. 4]]
==2000 ...==
* [[Ernst A. Heinz]] ('''2000'''). ''A New Self-Play Experiment in Computer Chess''. [[Massachusetts Institute of Technology]], Laboratory of Computer Science, Technical Memo No. 608, [http://supertech.lcs.mit.edu/~heinz/ps/new_exp.ps.gz zipped ps], [http://bitsavers.trailing-edge.com/pdf/mit/lcs/tm/MIT-LCS-TM-608.pdf pdf]
* [[Ernst A. Heinz]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_18 New Self-Play Results in Computer Chess]''. [[CG 2000]]
* [[Ernst A. Heinz]] ('''2001'''). ''Self-play Experiments in Computer Chess Revisited.'' [[Advances in Computer Games 9]]
* [[Ernst A. Heinz]] ('''2001'''). ''Modeling the “Go Deep” Behaviour of CRAFTY and DARK THOUGHT.'' [[Advances in Computer Games 9]]
* [[Ernst A. Heinz]] ('''2001'''). ''Self-Play, Deep Search and Diminishing Returns.'' [[ICGA Journal#24_2|ICGA Journal, Vol. 24, No. 2]]
* [[David Levy]] ('''2002'''). ''[http://ticc.uvt.nl/icga/journal/contents/content25-3.htm#SOME%20COMMENTS%20ON%20REALIZATION%20PROBABILITIES SOME COMMENTS ON REALIZATION PROBABILITIES AND THE SEX ALGORITHM]''. [[ICGA Journal#25_3|ICGA Journal, Vol. 25, No. 3]]
* [[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://www.st.ewi.tudelft.nl/%7Erenze/doc/ICGA_2005_4_DeepSearch.pdf pdf]
* [[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]]
* [[Tamal T. Biswas]], [[Kenneth Wingate Regan|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 Wingate Regan|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 Posts=
==1996 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/d6e548599141e359 Fractional depth increments] by S.Read, [[Computer Chess Forums|rgcc]], January 18, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/4b61b775ec46b7d7 Diminishing Returns in Search] by [[Jouni Uski]], [[Computer Chess Forums|rgcc]], September 6, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/cc9d40ca3989dfac 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
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/6aa8379d0b26f6a3 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]]
* [https://www.stmintz.com/ccc/index.php?id=187276 ICGA_J (June) self-play information] by [[Guy Haworth]], [[CCC]], September 05, 2001 <ref>[[Ernst A. Heinz]] ('''2001'''). ''Self-Play, Deep Search and Diminishing Returns.'' [[ICGA Journal#24_2|ICGA Journal, Vol. 24, No. 2]]</ref>
* [https://www.stmintz.com/ccc/index.php?id=198429 About diminishing returns (Uri)] by [[Jouni Uski]], [[CCC]], November 22, 2001
* [https://www.stmintz.com/ccc/index.php?id=212683 The probability to find better move is simply irrelevant for diminishing returns] by [[Uri Blass]], [[CCC]], February 09, 2002
* [https://www.stmintz.com/ccc/index.php?id=240056 The law of diminishing returns] by [[Ed Schroder|Ed Schröder]], [[CCC]], July 12, 2002
* [https://www.stmintz.com/ccc/index.php?id=310897 Regarding Qsearch with Fractional ply extensions] by [[Federico Andrés Corigliano|Federico Corigliano]], [[CCC]], August 11, 2003 » [[Quiescence Search]]
* [https://www.stmintz.com/ccc/index.php?id=324345 In chess we will reach diminishing returns just like in Checkers 1994] by Jorge Pichard, [[CCC]], October 29, 2003 <ref>[http://www.chessbase.com/newsdetail.asp?newsid=1270 Perfection in checkers], [[ChessBase|ChessBase News]], October 29, 2003</ref>
* [https://www.stmintz.com/ccc/index.php?id=345836 diminishing returns] by Duncan Roberts, [[CCC]], January 30, 2004
* [https://www.stmintz.com/ccc/index.php?id=356109 Shredder 8 secret: search depth?] by [[Jouni Uski]], [[CCC]], March 23, 2004
: [https://www.stmintz.com/ccc/index.php?id=356131 Re: Shredder 8 secret: search depth?] by [[Vasik Rajlich]], [[CCC]], March 23, 2004 » [[Shredder]], [[Junior]], [[Fritz]]
* [https://www.stmintz.com/ccc/index.php?id=362189 Diminishing returns] by [[Tony van Roon-Werten|Tony Werten]], [[CCC]], April 29, 2004
* [http://www.talkchess.com/forum/viewtopic.php?start=0&t=29011 Diminishing returns of increasing search depth] by Jarkko, [[CCC]], July 18, 2009
==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/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=43598 Elo Increase per Doubling] by [[Adam Hair]], [[CCC]], May 07, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=44889 Diminishing returns in fixed depth testing revisited] by [[Jesús Muñoz]], [[CCC]], August 25, 2012
* [http://forum.computerschach.de/cgi-bin/mwf/topic_show.pl?tid=5184 Houdini 3-Houdini 3: Nutzen der Bedenkzeitverlängerung] by Patrick Götz, [[Computer Chess Forums|CSS-Forum]], December 07, 2012 (German) » [[Houdini]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46370 Elo points gain from doubling time] by [[Kai Laskos]], [[CCC]], December 10, 2012 » [[Komodo]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48733 Scaling at 2x nodes (or doubling time control).] by [[Kai Laskos]], [[CCC]], July 23, 2013 » [[Houdini]], [[Knowledge]], [[Depth#DiminishingReturns|Diminishing Returns]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48780 Time to depth measuring tool] by [[Peter Österlund]], [[CCC]], July 28, 2013 » [[Parallel Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50220 Stockfish depth vs. others; challenge] by [[Larry Kaufman]], [[CCC]], November 24, 2013 » [[Stockfish]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54296 How many plies are searched in a typical chess program?] by Stephen Dause, [[CCC]], November 09, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=56044 Fractional plies and transposition tables] by [[Alexandru Mosoi]], [[CCC]], April 18, 2015 » [[Depth#FractionalPlies|Depth - Fractional Plies]], [[Transposition Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61784 Doubling of time control] by [[Andreas Strangmüller]], [[CCC]], October 21, 2016 » [[Match Statistics#DoublingTC|Doubling TC]], [[Depth#DiminishingReturns|Diminishing Returns]], [[Playing Strength]], [[Komodo]]
* [http://www.talkchess.com/forum/viewtopic.php?t=62146 Stockfish 8 - Double time control vs. 2 threads] by [[Andreas Strangmüller]], [[CCC]], November 15, 2016 » [[Match Statistics#DoublingTC|Doubling TC]], [[Depth#DiminishingReturns|Diminishing Returns]], [[Playing Strength]], [[Stockfish]]
* [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]]
=External Links=
* [https://en.wikipedia.org/wiki/Depth Depth from Wikipedia]
* [https://en.wikipedia.org/wiki/Depth-limited_search Depth-limited search from Wikipedia]
* [https://en.wikipedia.org/wiki/Diminishing_returns Diminishing returns from Wikipedia]
* [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 Wingate 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>
=References=
<references />
'''[[Search|Up one Level]]'''
