Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: The Limits of Positional Knowledge

Author: Ratko V Tomic

Date: 11:40:28 11/15/99

Go up one level in this thread


> This argument is in contradiction with the well-observed fact that chess
> programs become stronger and more accurate with increasing depth.

The error propagation & increasing junk percentage with increasing depth
are only some of the depth effects of chess search. There are others which
work in the opposite direction with increasing depth, the most obvious
one being the better chance of finding the nodes with early termination
(or at least a decisive material advantage).

While the net strength of program may increase, the D+1 ply program will still
lose about 20% of time to the otherwise identical D ply program. That is a clear
demonstration not only of the existence of some phenomena (or mechanisms or
causes) which act negatively on the strength of the program with increasing
depth, but also that the magnitude of their effects may be large enough to
overcome, and not infrequently so, the effects of all the positive phenomena of
the increased depth. Otherwise, if the net effect of the increased depth, when
all pluses and minuses are tallied, is exclusively positive, the D ply program
would never win against D+1 ply program.

So, there is certainly no doubt that negative phenomena (with increasing depth)
exist and in some percentage of cases can play a decisive role. There is also no
doubt that following a branching path with some nonzero chance of picking a
wrong (relative to the exact knowledge) branch at each branching point, reasults
in the increase of chance of picking the wrong branch somewhere as the number of
branching points (the depth) increases.
That doesn't mean the program will play weaker if you increase the depth, since
the increase in the chance of making the "wrong" (relative to the perfect
knowledge, i.e. to the exact vales in the full chess tree) choice since its
opponents, against which the "strength" is computed, are far from perfect
themselves. The move which would be "wrong" against a perfect opponent, but
which generates more tactical opportunities, against an imperfect opponent who
is weaker tactically (due to shallower search) will increase the "strength" of
the program. A perfect opponent would, of course, punish such cheap baits,
making the program "weaker". (There is a similar effect in human play, where
player A can beat player B in a head to head match, but player B routinely comes
ahead of A in the tournaments with large variety of players, since B knows how
to squeeze full points out of anyone in the lower half of the table, while A
lets too many of these take away half points.)

So the conventional "strength" increase with depth doesn't prove that program is
decreasing the "wrong" moves (in the absolute sense, or even against only an
imperfect, but a much stronger player). It shows only that with increased depth
it can pick, on average, better the near term decisive moves than it could at
shallower depths (the short termination nodes, since the D+1 ply program looks
at all the nodes that the D ply program looks at, plus many more). But since the
D ply program will still win around 20% of the time, despite seeing in _every_
move only a subset of the short termination (or decisive in a weaker sense than
checkmate) nodes that the D+1 program sees, that means there is a
non-negligeable percentage of cases where the increased depth "worsened" the
positional evaluation (which will generally decide the move in the absence of
finding short termination nodes) as depth increased. The topic of this thread
"The Limits of Positional Knowledge" i.e. the issues about this positional
evaluation, was what my earlier post was commenting on, not whether better
tactics can swamp, to some degree and against some type of opponents, the
effects of such limits.

To find out how do the other phenomena behave with increasing depth, using the
conventional game points is not a very efficent way, since within the given
range of depths the tactical effects may still swamp the manifestation of other
effects. To see the other effects in pure form (and thus to be able to predict
better what might happen with further increases in depth take place), one would
have to go over the game logs and remove games where the D+1, D+2,.. program won
against D ply program based solely on seeing an early termination (or strongly
decisive) nodes at its depth. The remaining score would tell us how exactly does
the positional evaluation bahave as the depth increases, does it hit a plateau,
or show clear signs of it approaching, even at the present depths? When you
superimpose such curve on top of the tactical win (short termination) curve of
larger amplitudes, these other effects can be easily buried at the present
depths.



> (the definition  of "junk" itself is not really clear).

For practical measurement of junk vs non-junk, one could rig an evaluation
function to count as "junk" any result it produces that is, say, 0.50 pawns
below the best value (for the same side) so far. The percentage of this type of
junk (whether it is 0.5 or 1.0 or 0.2 pawns) would increase, even though both
junk and non-junk would increase in their absolute numbers as the depth
increases. But the percentage of so measured non-junk would go toward 0 as depth
increases. Which is what one might label "diminishing returns".





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.