From: jam+@cs.cmu.edu (Joe Mattis)
Subject: Re: Chess is not solvable
Organization: School of Computer Science, Carnegie Mellon
Date: Mon, 28 Sep 1992 01:53:08 GMT

In article <1992Sep27.210208.24486@cbnewsl.cb.att.com> ed@cbnewsl.cb.att.com (edward.m.hummel) writes:
>In article <Bv3t3K.2yF.1@cs.cmu.edu> jam+@cs.cmu.edu (Joe Mattis) writes:
>>[...]  The remaining unevaluated positions
>>represent positions where, due to repetition or lack of material, neither
>>side can force checkmate or stalemate.  Evaluate all such positions as:
>>        Neither side can force checkmate or stalemate:  0
>
>You have to make an assumption in order to assign this a value.

Not at all.  This evaluation, which seems so capricious to you, is *only*
applied to positions where (with best play) neither player can forcibly reach
+1 or -1...that's why these positions remained unassigned!  Now, a completed
chess game must end with a White win (+1), a Black win (-1), or a draw (0).
Since it's impossible to reach +1 or -1, the only possible completion (with
best play) is 0.  Therefore, IF THE GAME EVER ENDS from one of these
positions (with best play), it must end in a draw.

Note that I haven't proved that such games must end...indeed, they might not.
But I *have* proved that the only possible result from such positions (with
best play) is a draw.  If it turns out that the initial position is such a
position, that would be enough (in and of itself) to "solve" chess.  After
all, if we determined that neither White nor Black could forcibly checkmate
the other (with best play), that would certainly answer the question that
started this whole discussion, the intent of which was (paraphrasing):

	Which is correct?  (a) White can forcibly win.
			   (b) Black can forcibly win.
			   (c) Neither can forcibly win.

>When [a downstream value] turns out to depend upon the value of the node
>itself you are ARBITRARILY assigning the value zero.

Untrue!  After all, *most* positions "depend" on the value of the node
itself, since most positions can lead to back to themselves (e.g. players can
usually shuffle their kings endlessly).  Yet many such positions get +1 or -1
evaluations.  For example, the potential for king-shuffling in
K(a1)Q(a2) vs K(h1) doesn't alter the fact that the position is +1 (a win
for White).  Furthermore, there is no chance that Black could forcibly
enter a "loop" from a +1 position.  Positions are only assigned +1
if White can forcibly avoid all loops (as in the KQvsK example).

The only positions that get evaluated as 0 by the passage you quoted above
are those where no +1 or -1 positions can be forcibly reached (with best
play).  (Note that this handles all of the "drawn by fiat" positions (KvsK,
KvsKNN, etc) without resorting to special rules.)

>Consider the following trivial graph tree.  It has two nodes
>A and B.  B is a final position and has value zero.  The linkages
>are two arcs.  The first goes from A to B.  The second goes from 
>A to A.  So, what value do we give to node A?  It should have the best
>of the two possibilities (A or B).  We know B is zero, but we
>don't know A.

But we do know *something* about A...we know that neither player can forcibly
reach +1 or -1!  Therefore, we know that from this position (with best play)
IF THE GAME EVER ENDS, it must end in a draw.

>According to your argument, we must assign
>the value zero, because there can be no other outcome.  I think
>this is using an additional assumption.

Not if "0" means "Neither can forcibly win."

So, I've proved that it's theoretically possible to answer the question
above as (a) (b) or (c).  The fact that (c) implies that a game might
never end (with best play) is just as uninteresting and irrelevant from the
initial position as it is from KQvsKQ...either way, it's a drawn position
(with best play).

If you can't understand the proof or its consequences, you'll have to ask
someone else for help.

-Joe Mattis    ARPA:  jam@isl1.ri.cmu.edu
               UUCP:  ...!ucbvax!isl1.ri.cmu.edu!jam@ucbvax.berkeley.edu