Depth is the height or nominal depth in plies between the Root and so called horizon nodes (depth 0), where a heuristic value is assigned to. Thus, depth is the number of half moves the search nominally looks ahead.
Most likely inside the search routine, a ply-index is used to index stacks or arrays with pre-saved search information. This index is initialized with zero at the root, and is then incremented after making a move each time the recursive search is called. This index measures the ply-distance from the current node to the root and would therefor be sufficient to determine the remaining depth to the horizon, also called draft:
draft ::= depth at the root - ply index
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 extension- or reduction-schemes and may also consider fractional extensions[2][3] .
Fractional Plies
Some programs extend or reduce in fractions of one ply. Inside an Iterative Deepening framework, the search depth is incremented, usually by one ply - or by a fraction of one ply, for instance 1/2 ply.
The brute-forceplydepth is indeed half the publicized depth. All the rest are 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.
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 cutoffif( score > alpha )
alpha = score;// alpha acts like max in MiniMax}return alpha;}
Maximum Search Depth
The Maximum Search Depth of a depth-first search is usually determined by a compile time constant in ply units (MAX_PLAY). It is used to statically allocate arrays like a Triangular PV-Table, or search stacks inside the programs data- or 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 score or material balance when the ply index threatens overflow.
Diminishing Returns
Despite the existence of pathology in searching some trees, where a deeper minimax search results in worse play, it is quite consensus in Chess that deeper search yields in stronger play. 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 [5] . Thompson found Belle (n+1) scored about 80% versus Belle (n), which roughly translates to a 200 Elo improvement playing one ply deeper, while the improvement seemed constant independent from the used depths from 3 to 8, while a second experiment [6] indicated a falloff beyond depth 7.
P4
P5
P6
P7
P8
P9
Ratings
RI
P4
X
5
½
0
0
0
1235
-
P5
15
X
3½
3
½
0
1570
235
P6
19½
16½
X
4
1½
1½
1826
256
P7
20
17
16
X
5
4
2031
205
P8
20
19½
18½
15
X
5½
2208
167
P9
20
20
18½
16
14½
X
2328
120
Also, in other board games such as Othello and Checkers, additional plies of search translated into decreasing benefits, giving rise to Diminishing returns for deeper searching. In their 1997 paper Diminishing Returns for Additional Search in Chess[7] , Junghanns, Schaeffer, Brockington, Björnsson and 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[8] and later Ernst A. Heinz with DarkThought[9] steadily discovered new best moves while searching deeper. In further experiments [10] , Heinz found indications of decreasing returns from increasing search in chess. In his 2001 ICGA Journal paper Self-Play, Deep Search and Diminishing Returns[11] he gave following match results (3,000 games each) [12] :
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 Schröder conducted self-play experiments with ProDeo 1.74 playing different depths. Schröder also suggests that ProDeo has a branching-factor of roughly 2, in other words an additional ply corresponds to a 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 [14] .
Despite quiescence search, where usually winning captures and even some checks are tried at or behind the search horizon, until positions become sufficiently quite, selectivity of modern chess programs, caused by extensions, pruning and reductions, notably Check Extensions, Null Move Pruning and Late Move Reductions, leads to bushy, non-uniform trees where some branches are searched deeper than nominal, but others shallower. A depth reduction R of multiple plies is often performed in forward pruning techniques like Null Move Pruning and Multi-Cut.
Table of Contents
Draft versus Ply-Index
Most likely inside the search routine, a ply-index is used to index stacks or arrays with pre-saved search information. This index is initialized with zero at the root, and is then incremented after making a move each time the recursive search is called. This index measures the ply-distance from the current node to the root and would therefor be sufficient to determine the remaining depth to the horizon, also called draft: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 extension- or reduction-schemes and may also consider fractional extensions [2] [3] .
Fractional Plies
Some programs extend or reduce in fractions of one ply. Inside an 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 rgcc, March 1998 [4] :
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.Maximum Search Depth
The Maximum Search Depth of a depth-first search is usually determined by a compile time constant in ply units (MAX_PLAY). It is used to statically allocate arrays like a Triangular PV-Table, or search stacks inside the programs data- or 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 score or material balance when the ply index threatens overflow.Diminishing Returns
Despite the existence of pathology in searching some trees, where a deeper minimax search results in worse play, it is quite consensus in Chess that deeper search yields in stronger play. 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 [5] . Thompson found Belle (n+1) scored about 80% versus Belle (n), which roughly translates to a 200 Elo improvement playing one ply deeper, while the improvement seemed constant independent from the used depths from 3 to 8, while a second experiment [6] indicated a falloff beyond depth 7.Also, in other board games such as Othello and Checkers, additional plies of search translated into decreasing benefits, giving rise to Diminishing returns for deeper searching. In their 1997 paper Diminishing Returns for Additional Search in Chess [7] , Junghanns, Schaeffer, Brockington, Björnsson and 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 [8] and later Ernst A. Heinz with DarkThought [9] steadily discovered new best moves while searching deeper. In further experiments [10] , Heinz found indications of decreasing returns from increasing search in chess. In his 2001 ICGA Journal paper Self-Play, Deep Search and Diminishing Returns [11] he gave following match results (3,000 games each) [12] :
Tony van Roon-Werten made following statement on Diminishing Returns [13] :
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 Schröder conducted self-play experiments with ProDeo 1.74 playing different depths. Schröder also suggests that ProDeo has a branching-factor of roughly 2, in other words an additional ply corresponds to a 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 [14] .
depth B
See also
Publications
1978 ...
1980 ...
1990 ...
2000 ...
2010 ...
Forum Posts
1996 ...
2000 ...
Re: Shredder 8 secret: search depth? by Vasik Rajlich, CCC, March 23, 2004 » Shredder, Junior, Fritz
2010 ...
2015 ...
External Links
References
Up one Level