Computer Chess Club Archives




Subject: Re: The Limits of Positional Knowledge

Author: Ratko V Tomic

Date: 20:14:01 11/11/99

Go up one level in this thread

>You say, "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)."
>How does an evaluation between the root and a leaf affect the final value
>assigned to a root move?  Isn't this value always the value propagated
>back from the leaf and perhaps combined with a root evaluation value (if
>the leaf evaluation is intentionally brief)?

The average difference between the value assigned to the root node (via backing
up the approximate value from one of the leaves) and the true value of the root
grows as the square root of the number of depth levels being traversed from the
leaf (where the approximate values were computed) to the root node.

Namely, at each such level traversal, while backing up, we are performing a key
part of the full "evaluation procedure" (the so-called "evaluation function" is
just one of the components of the full root node evaluation procedure) -- it is
a decision process (based on effectively comparing the approximate values of
child-nodes), resulting in a pick of the "best" move (in the minimax sense).

Since we are comparing among themselves only the approximate minimax values,
which often will have an overlapping error intervals, our decision as to which
branch to pick as the "best" one will have some odds of being wrong (wrong with
respect to the _true best decision_, and not, of course, with respect to the
approximate values, even though the usual alpha-beta procedure may operate on
them, and the programmers will talk and think about them, as if they were the
true values).

The worst case I was mentioning above occurs when, level after level, you do
pick a wrong branch. Odds for that worst case are small, of course, especially
as depth increases. The average behavior, though, is that of a random walk,
where you drift not linearly in number of steps but proportionately to the
square root of the number of steps. The quality of the evaluation function
affects the proportionality factor C in the C*sqrt(D) error margin, the better
the function the smaller this C factor is, thus masking the sqrt(D) type error
spread, up to some depths, but eventually the error spread can exceed any
predefined margin, making a final pick into an almost random choice.

>P.s., I read your brief autobiography here a while ago, and it somewhat
>parallels mine.  Except I quit chess before I went to study physics!

Well, I quit, too, when I began as the physics major at the university (earlier,
I played near the end of high-school; had a late start in chess), and stayed off
it until the end of the undergradute school, but then when I went to the
graduate school, the 'bug bit' again, and I played for a year or so, then I had
to quit again. Since then, whenever the bug happens to decide to bite, I play
against the programs. It has been really enjoyable in the last couple years,
with the latest crop of the top programs, to have such strong opponents which
can put a real fight, any time of day or night.

> Another
> question: you seemed to feel that you had to write the autobiography
> in response to an etiquette issue -- does CCC require an autobiography?

Knowing a bit more about someone with whom you only communicate facelessly,
voicelessly, gesturelessly, scentlessly, rightbrainlessly,... in these online
forums, helps, I think, in seeing better where the persons views come from,
saving the time and the trouble of trivial misunderstandings and the emotionally
charged flame wars that may follow. There were also several emails I got around
that time from the CCC members, asking along those lines and I probably used the
next post to indirectly answer those questions as well.

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.