# Computer Chess Club Archives

## Messages

### Subject: Useful tree searching post

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