Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: The Limits of Positional Knowledge

Author: Yngvi Bjornsson

Date: 12:56:05 11/17/99

Go up one level in this thread


On November 15, 1999 at 14:40:28, Ratko V Tomic wrote:

>> 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.
>

It is entirely possible for a program searching D ply deep to win against a
program that searches D+1 ply, and it has nothing to do with unexplained
phenomenon that acts negatively on the program's strength with increasing search
depth. It is simply a consequence of the fact that the programs are using
heuristic based evaluation functions to approximate the true merit of the
terminal nodes, and these evaluations are sometimes incorrect. For example, a
D+1 ply search sees a way to win a pawn and grabs it. The program searching D
ply deep didn't realize that it was losing the pawn because it didn't see deep
enough. However, the pawn happens to be poisonous and taking it loses by force,
but neither of the programs does realize this at the time. When the D+1 deep
searcher realizes this a move or two later it is already to late to do anything
about it.


>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

Again, I'm not convinced that there is such a phenomenon in chess, on the
contrary all evidence I've seen suggest it isn't. Pearl did demonstrate such
pathology in his artificial game. Like I pointed out in an earlier email, when
backing up erroneous terminal evaluations using minimax operators the
probability of an incorrect move decision at the root may indeed increase with
additional search depth. Whether it increases or decreases is simply a function
of the branching factor of the tree and the ratio of correct vs. incorrect
terminal evaluations.  In chess, I've seen no evidence that such pathology is
present.

>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.

I can understand your argument if you are talking about the game as a whole.
There each move decision is made independently of each other and there is a
nonzero change of picking a wrong move each time.  So, for example, when playing
against a perfect opponent the probability of making a critical error along the
way increases the longer (and narrower) the game-path is you have to take to
ensure the optimal result. But what I cannot see is how this applies to the
alpha-beta search.  The values that are backed up *only* depdend on the
evaluation of the terminal nodes (on the so called minimal- or critical-tree). I
cannot possible see how increasing the length of the paths will *necessarily*
introduce additional change of an error (as I think you are suggesting). Like
mentioned above, it can, but will not necessarily do so. If I'm missing
something, please explain.

 ... zip ...

-Yngvi



This page took 0.01 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.