Author: Amir Ban
Date: 15:50:05 11/12/99
Go up one level in this thread
On November 11, 1999 at 12:53:35, Ratko V Tomic wrote: >> I believe that the deeper you go, the more accurate your 'scores' have >> to be (by scores I mean weights for each positional thing you recognize). > >The reason for this is the error propagation effect, which as you propagate the >uncertain scores up the tree, increases the uncertainty of the backed up score >(unless the leaf uncertainty was 0, such as if checkmate was found, in which >case the error remains 0). Altough there are artificial "pathological" games >where the error grows exponentially with depth (Judea Pearl's book "Heuristics" >has a chapter on this error propagation and gives such examples), in chess, or >other "normal" strategy games, the error band behaves as it propagates like a >random walk, spreading as the sqrt(Depth). > >Namely, when you have several uncertain values v1, v2,... from the child nodes >and pick one as the "best," due to the overlap of error intervals among the >similar quality moves, depending on amount of the overlap there is a >non-vanishing chance you will pick the wrong move, the true value of which is >actually worse than the one you ignored. In the worst case, if this happens >several times up the tree, you can systematically (linearly with depth) drift >away from the true best move (and the true best value). On average, though, you >are performing a random walk within these overlapping error intervals as you >cross the depth levels, which sometimes will make worsening choice, sometimes >improving choice (the right move for the wrong reason). The general outcome of >such random walk is a slowly expanding error, growing like sqrt(#Steps), and the >"steps" here are the depth levels of the tree. > >This error propagation is the underlying reason why the searchers with imperfect >evaluation as they increase the depth eventually hit the region of diminishing >returns. (Of course, if you had a perfect evaluation, you wouldn't need to >search a tree; hence all searchers do have an imperfect evaluation.) >Another way to see these diminishing returns, as suggested in our earlier >discussion, is to realize that the proportion of non-junk nodes evaluated drops >to 0 exponentially with depth (since even the otherwise good moves which follow >junk moves create a junk variations and evaluations in the entire subtree below >the junk move, while to get a non-junk variation all moves from the root to the >leaf have to be non-junk moves.) Hence, as depth increases, even the smallest >leaf node evaluation uncertainty will be more likely to cause a miss of the >sparser and sparser sparks of non-junk in the exponentially growing dark sea of >junk. This argument is in contradiction with the well-observed fact that chess programs become stronger and more accurate with increasing depth. The "diminishing returns" has been prophesied many times in the past. The argument here is that this is because the junk swamps the non-junk. But, it seems to me that with increasing depth, the absolute outcome of the position will be found, regardless of the increase of proportion of junk over non-junk (the definition of "junk" itself is not really clear). The quality of the node scores won't matter in such a case. The error propagation model that is proposed here doesn't seem right. It suggests that somehow the objectively correct score is somewhere in the leaves, but gets corrupted as it moves up the tree to the root. In fact the opposite of this is true: the score of the nodes is a fiction of the program, but this fiction is transmitted faithfully and exactly by the alpha-beta algorithm. Whether the node scores have any resemblance to reality depends on the programmer. The result of the evaluation is as good as the evaluation function, but a deep tree gives it stability and increases its accuracy (much more than a shallow tree, as we all know). The "uncertainty intervals" mentioned, are just a more elaborate fiction used by some programs. The only objective scores are WIN, LOSE or DRAW. Amir
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.