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.