Author: Ratko V Tomic
Date: 09:53:35 11/11/99
Go up one level in this thread
> 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 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.