Author: Ratko V Tomic
Date: 11:40:28 11/15/99
Go up one level in this thread
> This argument is in contradiction with the well-observed fact that chess > programs become stronger and more accurate with increasing depth. The error propagation & increasing junk percentage with increasing depth are only some of the depth effects of chess search. There are others which work in the opposite direction with increasing depth, the most obvious one being the better chance of finding the nodes with early termination (or at least a decisive material advantage). While the net strength of program may increase, the D+1 ply program will still lose about 20% of time to the otherwise identical D ply program. That is a clear demonstration not only of the existence of some phenomena (or mechanisms or causes) which act negatively on the strength of the program with increasing depth, but also that the magnitude of their effects may be large enough to overcome, and not infrequently so, the effects of all the positive phenomena of the increased depth. Otherwise, if the net effect of the increased depth, when all pluses and minuses are tallied, is exclusively positive, the D ply program would never win against D+1 ply program. So, there is certainly no doubt that negative phenomena (with increasing depth) exist and in some percentage of cases can play a decisive role. There is also no doubt that following a branching path with some nonzero chance of picking a wrong (relative to the exact knowledge) branch at each branching point, reasults in the increase of chance of picking the wrong branch somewhere as the number of branching points (the depth) increases. That doesn't mean the program will play weaker if you increase the depth, since the increase in the chance of making the "wrong" (relative to the perfect knowledge, i.e. to the exact vales in the full chess tree) choice since its opponents, against which the "strength" is computed, are far from perfect themselves. The move which would be "wrong" against a perfect opponent, but which generates more tactical opportunities, against an imperfect opponent who is weaker tactically (due to shallower search) will increase the "strength" of the program. A perfect opponent would, of course, punish such cheap baits, making the program "weaker". (There is a similar effect in human play, where player A can beat player B in a head to head match, but player B routinely comes ahead of A in the tournaments with large variety of players, since B knows how to squeeze full points out of anyone in the lower half of the table, while A lets too many of these take away half points.) So the conventional "strength" increase with depth doesn't prove that program is decreasing the "wrong" moves (in the absolute sense, or even against only an imperfect, but a much stronger player). It shows only that with increased depth it can pick, on average, better the near term decisive moves than it could at shallower depths (the short termination nodes, since the D+1 ply program looks at all the nodes that the D ply program looks at, plus many more). But since the D ply program will still win around 20% of the time, despite seeing in _every_ move only a subset of the short termination (or decisive in a weaker sense than checkmate) nodes that the D+1 program sees, that means there is a non-negligeable percentage of cases where the increased depth "worsened" the positional evaluation (which will generally decide the move in the absence of finding short termination nodes) as depth increased. The topic of this thread "The Limits of Positional Knowledge" i.e. the issues about this positional evaluation, was what my earlier post was commenting on, not whether better tactics can swamp, to some degree and against some type of opponents, the effects of such limits. To find out how do the other phenomena behave with increasing depth, using the conventional game points is not a very efficent way, since within the given range of depths the tactical effects may still swamp the manifestation of other effects. To see the other effects in pure form (and thus to be able to predict better what might happen with further increases in depth take place), one would have to go over the game logs and remove games where the D+1, D+2,.. program won against D ply program based solely on seeing an early termination (or strongly decisive) nodes at its depth. The remaining score would tell us how exactly does the positional evaluation bahave as the depth increases, does it hit a plateau, or show clear signs of it approaching, even at the present depths? When you superimpose such curve on top of the tactical win (short termination) curve of larger amplitudes, these other effects can be easily buried at the present depths. > (the definition of "junk" itself is not really clear). For practical measurement of junk vs non-junk, one could rig an evaluation function to count as "junk" any result it produces that is, say, 0.50 pawns below the best value (for the same side) so far. The percentage of this type of junk (whether it is 0.5 or 1.0 or 0.2 pawns) would increase, even though both junk and non-junk would increase in their absolute numbers as the depth increases. But the percentage of so measured non-junk would go toward 0 as depth increases. Which is what one might label "diminishing returns".
This page took 0.03 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.