Author: Bella Freud
Date: 15:37:45 11/11/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. Hi Ratko, This reminds me very much of the Library of Babel. This contains all the books possible with a combination of abcdefghijklmnopqrstuvwxyz, "space", "comma" and "full stop". In the Library are all books, including the prophecies "Prediction of Everything That Will Happen Ever, including Details of Your Own Death". I wonder if Mr Hyatt could write a search program to find that book ! ! ! Would material be enough? Or would he need heuristics to approximate to the solution at the leaf nodes? Bella
This page took 0.01 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.