From: BRYAN@wvnvm.wvnet.edu (Jerry Bryan)
Newsgroups: rec.games.chess
Subject: (Long) Solvability Proof, Unsolvability Proof
Date: 1 Oct 92 18:15:00 GMT
Article-I.D.: wvnvm.92275.141500BRYAN

I do not normally subscribe to this discussion, but I recently subscribed
to follow the Fischer-Spassky match.  Much to my surprise, there was
a discussion going on in which there was serious disagreement as to
whether chess was solvable.  I have gone through the details of such
proofs before, but even without the details of the proof, I would think it
the solvability would be intuitively obvious based on the finiteness of
the number of positions.  I therefore agree that in large measure this
discussion is pointless.  But at the risk of wasting my time and everybody
else's time, let me try a couple of new arguments to try to convince the
naysayers that chess is solvable.

To keep things simple, I will work with the most reduced of all possible
positions, where both White and Black have a lone king.  I am going to
give two proofs.  First, I am going to prove the (obvious) conclusion
that the position is solvable (namely it is a draw).  Then, I am going
to prove (falsely) that the position is not solvable.  My false proof
will deliberately include the same sort of discussion that others have
included in their arguments that chess as a whole is not solvable.
It is my hope that a false proof in such a reduced case will help those
who believe chess is not solvable to understand the errors in their
arguments.

As a preliminary I want to admit that I do not have a copy of the laws
of chess in front of me.  It is my understanding that the fact of
K vs. K being a draw is not explicitly stated in the laws.  Rather, it
is trivially derived from the laws.  If K vs. K is explicitly stated
in the laws as being a draw, then my false proof below will not work.
In this event, I ask the reader to suspend disbelief and pretend
that K vs. K is not explicitly stated.  My false proof will work just
as well with any slightly more complicated situation, such as K plus N
vs. K, but I would rather work with the simplest case.

To prove that K vs. K is solvable, we observe that neither White nor
Black can win.  That is, neither can legally deliver a check, and a
a check is prerequisite to checkmate.  Since neither White nor Black
can win, the game is a draw.

The false proof that K vs. K is not solvable is a bit more complicated.
First, observe that under a static evaluation (not looking ahead at all)
exactly one of the following is true for each chess position.

   1. A win for White (which I will denote by W).
   2. A win for Black (which I will denote by B).
   3. A draw (which I will denote by D).
   4. The status of the position is not yet known, and requires further
      searching (which I will denote by ?).

Observe that something so trivial as a problem where White is
to play and mate in one is a ?, not a W, even if you clearly see the mate.
I want to keep emphasizing that I am only talking about static evaluations.

The conditions for W are as follows:

    1. It is Black's move
    2. Black is in check
    3. Black can make no legal move that gets out of check

The conditions for B are as follows:

   1. It is White's move
   2. White is in check
   3. White can make no legal move that gets out of check

The conditions for D are as follows:

   1. It may be White or Black's move.
   2. The player to move is not in check.
   3. The player to move has no legal moves (in other words, a stalemate).

In all other cases, the static evaluation is ?

Before proving K vs. K not to be solvable, I will demonstrate how to show
that "White to play and mate in one" is solvable.  First, assume that
it is not a win for Black and it is not a stalemate.  (It cannot be a win
for White since it is White's move).  Then, the static evaluation is ?.
I will start a little game tree.

    Level 0, White to move                   ?

Now, assume that there is one move that results in a mate for White,
one that results in stalemate, and several that let Black make a move.
Continuing with static evaluations, the game tree would now appear as
follows.

    Level 0, White to move                   ?
                                             |
                                             |
                              -----------------------------------
                              |       |          |       |      |
                              |       |          |       |      |
    Level 1, Black to move    W       D          ?       ?      ?


The W is the mate for white, the D is the stalemate, and the ?'s are
the cases where Black can make a legal move.

At this point, we have enough information to cease and  desist with
static evaluations.  Instead, we can perform a dynamic evaluation and
use minimax (max in this case) to "backup" the W at Level 1 to a W
at Level 0.  This is a long way of saying that White can force a win,
and the dynamically evaluated, or minimaxed tree would look as follows:


    Level 0, White to move                   W
                                             |
                                             |
                              -----------------------------------
                              |       |          |       |      |
                              |       |          |       |      |
    Level 1, Black to move    W       D          ?       ?      ?


This does not explain everything about minimax search, but it gives its
flavor.

If the same procedure is applied to K vs. K, the original
position at level 0 is ?.  At level 1, every position is ?  At level 2,
every position is ?  This process continues forever, no backing up can
ever occur, the ? at level 0 is never resolved, and the original
position is therefore unsolvable.

I trust it is totally obvious that the argument that K vs. K is
unsolvable is false.  What may or
may not be obvious is that many the arguments that have been made for the
unsolvability of chess in general are exactly analogous to this false
proof of the unsolvability of K vs. K.  (I ignore the silliness about
the Uncertainty Principle).

Let me take several issues in turn.  First, let me take the 50-move rule.
If you applied the 50-move rule to my false proof, at level 100 of the tree
all the static evaluations would become D rather than ?.  (It is level 100
of the tree rather than level 50 because it takes two levels for every
move  -- one level for White and one move for Black).  The D's at level
100 would be backed up to level 99, the D's at level 99 would be backed up
to level 98, and so on until level 0 would be D rather than ?.  The
position would therefore be solvable.

There are at least two objections to this line of reasoning.  The first
is that a draw under the 50-move rule must be claimed  ---  it is not
automatic.  It might be that neither player claims the 50-move rule.  The
game would therefore be infinite and would remain undecided.  Now
why would a player not claim the draw?  The only reason that has been
put forth has been the hope or knowledge of a win if the game continues  --
perhaps the opponent might make a mistake.

However, remember that in
the case of a program written to solve chess, there is no opponent.
The program is playing both sides of the board, and it is making no mistakes
because it is searching every possible position even if it takes longer than
until the end of time.  Since it is making no mistakes, the program would
have to search past the
50-move limit to know whether to claim the draw or not.  If in so doing it
discovers a win for white, it would then know that black should (and would)
claim the draw.  If in so doing it discovers a win for black, it would
then know that white should (and would) claim the draw.  If it discovers
a draw, it might as well declare a draw at 50 moves as at any subsequent
time.  So whether the game is a win for white, a win for black, or a draw
if you went beyond 50 moves, it will be a draw at 50 moves in all three
cases.  Since this is true, the proof program can legitimately declare
draw at 50 moves whether you think of either side claiming the draw or not.
And since it can do so in all three cases, it does not really need to do
any searching beyond the 50 move limit.

The second objective to the 50 move rule is the 2N rule, where if it is
known that one side has a mate in N, then the game can proceed for 2N more
moves.  In all truth, the 2N rule makes the 50 move rule irrelevant to
a program to solve chess.  For example, if it were discovered that chess
were a mate for white in 941 moves, then White would have 1882 moves to
execute its mate, and the 50 move rule would never come into play.
Therefore, whatever the error is in my false proof that K vs. K is not
solvable, the error must be rectified without appeal to the 50 move rule.

That brings us to the 3 repetition rule.  In the case of K vs. K, the
third  time through any particular position, the ? would become a D.
Since there is only a finite number of positions, each leaf node of the
tree would become a D.  At that point in the search,  all the D's would
be backed up recursively to higher levels in the tree, and ultimately
the initial position would be a D, and the position would be solvable.

Again, the objection is that a player might not claim the draw.  We
now come to the crux of the matter.  There are certainly a finite number
of chess positions.  If there is an absolute termination criteria for
the search,  then there are a finite number of games, and the game is
solvable.  If there is not an absolute termination criteria (for example,
neither player claims the draw), then there are an infinite number of games
(even though the number of positions is finite), and the game might not
be solvable.

I now assert that a program to solve chess does not need for a player
to claim the draw.  Indeed, only 2 repetitions are needed to terminate
the search, and the repetition rule does not even need to be explicitly
stated in the laws of chess to terminate the search.  Thus, the search
can be properly terminated making the search tree finite, irrespective of
either the 50 move rule or the 3 repetition rule.  And that is the
mistake in my false proof that K vs. K is unsolvable.

The argument is as follows.  Suppose the search tree for K vs. K is being
constructed breadth first.  That is start at level 0, construct all of
level 1, construct all of level 2, etc.  To be precise, we should start
at one particular position of the kings, although it doesn't matter which
which initial position we choose.  Eventually, a repetition (actually, many
repetitions) will occur.  A "repetition" is the second occurrence of a
particular position with the same color to move, and with the second
occurrence being a direct descendent of the first occurrence in the tree.

Irrespective of whether a real player in a real game would claim a draw,
a  program to solve chess can treat any repetition as a draw.  If the
first occurrence of the repetition is eventually determined to be a win
for White, then so too will the second and subsequent occurrences, but
at a lower level in the tree.  You might as well keep the win at the
higher level of the tree and ignore the wins at the lower level.  If
the first occurrence of the repetition is eventually determined to be a
win for Black, then so too will the second and subsequent occurrences, but
at a lower level in the tree.  You might as well keep the win at the
higher level of the tree and ignore the wins at the lower level.  If the
first occurrence of the repetition is eventually determined to be a
draw in the explicit sense of a stalemate, then so too will the second and
subsequent occurrences, but at a lower level in the tree.  You might as
well keep the draw at the higher level of the tree and ignore the draws
at the lower level.  Finally, if none of the above are true, the
first occurrence of the repetition cannot be explicitly categorized
by the rules we have promulgated so far.  This in particular means that
White cannot force a win and Black cannot force a win.  Therefore, the
position is a draw.  You might as well keep the draw at the higher level
of the tree (at the first occurrence of the repetition) and ignore the
draws at the lower level.  Therefore, potentially infinite searches are
terminated, the total search tree is finite, and chess is therefore
solvable.