Author: José Carlos
Date: 07:28:20 04/29/04
Go up one level in this thread
On April 29, 2004 at 03:13:07, Tony Werten wrote: >Hi all, > >a while ago we had some discussions about diminishing returns in search for >chess. > >My opinion was that you can't prove that with programs searching d vs d+1 ply >depth because the advantage of the d+1 program gets smaller. ie at d=1 it has a >100% depth advantage, at d=2 it's 50% etc. > >Some people claimed that you can't compare it that way because bla bla >exponential something bla :) > >Well, I found an easier way to explain it. > >A few assumption: > >The easiest way to win is when you see a trick, your opponent doesn't see. > >The depth that needs to be searched to see a trick is equally divided. ie there >are as many tricks hidden 1 ply away as there are tricks at 2 ply ( it doesn't >really matter but it's easier to visualize ) > >w is player d+1 >b is player d > >d=1: b sees tricks 1 ply away, w sees ply 1 and 2 => w sees 2.0x as many tricks >d=2: b:1,2 w:1,2,3 => w: 1.5x >d=3: b:1,2,3 w:1,2,3,4 => w: 1.3x >... >d=10: b: 1..10 w: 1..11 => w:1.1 x > > > >Conclusion: There may or may not be diminishing returns in chess, but d vs d+1 >are not going to prove it, because those matches by itself are a clear example >of diminishing returns regardless what game is played. > >disclamer: I know chess isn't only about tricks, but it is an advantage to see >more of them then your opponent. Clearly the win percentage is depending on >other (random) stuff as well. BUT When you see less more, the advantage becomes >less. > >Tony I have the feeling that there must be some diminishing returns, but I have no mathematical reasoning to support it, nor any tests. It's obvious that there's a ceiling to playing strengh, which is seeing the whole tree. The shape of the tree (actually a graph, but that's probably irrelevant here) is growing fast until some point where terminal positions (win/draw/loss) start to show up and number of pieces become smaller. Then, the width of the tree starts decreasing (with depth) until only a few lines are unfinished. In the first plies, when the tree grows exponentially, strength seems to increase linearly with depth, or maybe exponentially also. At some point, the strength increase seems to be almost perfectly linear. We can try to imagine what happens at the bottom of the tree, where every depth step provides several terminal positions. I guess most of them will be correctly predicted by the evaluation function in advance so, together with the fact that less information is provided (less width), the strength increase with depth would be close to zero. Your argument about tricks distribution doesn't hold IMHO. Tactical secuences can be defined as long as one want, considering that 'quiet moves' are allowed in the definition of a tactical shot. You pin my queen with your bishop but I get a mate attack. The pin trick is not enough, and you'd better not have seen it and played something else. A probably better approach (from practical point of view) is to measure how often the pv move changes with depth. But that should be over a huge number of real positions, and still random noise would make it difficult to make conclusions. I belive that the fact that we, intuitively, see less and less strength increase at very high search depth is because of pruning. As the tree gets deeper, we cut more and more nodes to reduce the branching factor. So at high depths, the information is of much less quality, and thus less helpful than close to the root. José C.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.