Author: Yngvi Bjornsson
Date: 12:56:05 11/17/99
Go up one level in this thread
On November 15, 1999 at 14:40:28, Ratko V Tomic wrote: >> 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. > It is entirely possible for a program searching D ply deep to win against a program that searches D+1 ply, and it has nothing to do with unexplained phenomenon that acts negatively on the program's strength with increasing search depth. It is simply a consequence of the fact that the programs are using heuristic based evaluation functions to approximate the true merit of the terminal nodes, and these evaluations are sometimes incorrect. For example, a D+1 ply search sees a way to win a pawn and grabs it. The program searching D ply deep didn't realize that it was losing the pawn because it didn't see deep enough. However, the pawn happens to be poisonous and taking it loses by force, but neither of the programs does realize this at the time. When the D+1 deep searcher realizes this a move or two later it is already to late to do anything about it. >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 Again, I'm not convinced that there is such a phenomenon in chess, on the contrary all evidence I've seen suggest it isn't. Pearl did demonstrate such pathology in his artificial game. Like I pointed out in an earlier email, when backing up erroneous terminal evaluations using minimax operators the probability of an incorrect move decision at the root may indeed increase with additional search depth. Whether it increases or decreases is simply a function of the branching factor of the tree and the ratio of correct vs. incorrect terminal evaluations. In chess, I've seen no evidence that such pathology is present. >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. I can understand your argument if you are talking about the game as a whole. There each move decision is made independently of each other and there is a nonzero change of picking a wrong move each time. So, for example, when playing against a perfect opponent the probability of making a critical error along the way increases the longer (and narrower) the game-path is you have to take to ensure the optimal result. But what I cannot see is how this applies to the alpha-beta search. The values that are backed up *only* depdend on the evaluation of the terminal nodes (on the so called minimal- or critical-tree). I cannot possible see how increasing the length of the paths will *necessarily* introduce additional change of an error (as I think you are suggesting). Like mentioned above, it can, but will not necessarily do so. If I'm missing something, please explain. ... zip ... -Yngvi
This page took 0.02 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.