From: cec35848@uxa.cso.uiuc.edu (Chuck Carroll)
Subject: Re: (Long) Solvability Proof, Unsolvability Proof
Organization: University of Illinois at Urbana
Date: Mon, 5 Oct 1992 00:26:19 GMT

Caveat: I have not read all of the articles in the unsolvability
thread, but I have read many of them.

I started out agreeing that chess was solvable, even if a draw was
not claimed when it could be.  But someone (sorry, I forget who)
presented a convinging argument against that, and unless I see
it refuted, I must agree that chess is unsolvable.  I present it
below as an argument with the "proof."

Jerry Bryan <BRYAN@wvnvm.wvnet.edu> writes:

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

(Related question: is this so?  If a games goes to K vs. K, and one
player will not agree to a draw, do they have to play 50 moves before
the other player can claim a draw?  Isn't there some rule about it
being a draw in cases of "insufficient material?")

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

Ay, there's the rub!  Nowhere (to the best of my knowledge) in the
rules of chess does it say that "If neither White nor Black can win,
the game is a draw," or anything equivalent.  It says that stalemate
is a draw (and insufficient material?--see above), and that in the 
cases of repitition or the 50-move rule, either player may claim a draw.
It does NOT say that the game is necessarily a draw if neither black
nor white can win.

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

So far so good.

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

[proof, with which I have no problem, is deleted]

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

You have made an assumption here.  "Any position where all
following positions are '?' is a draw."  Nowhere in the minmax
procedure or in the rules of chess do I find anything to back up
this assumption.

[more deleted for brevity]
[mentions the 50-move rule limiting K vs. K to 100 half-moves]

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

Or perhaps that an infinite game is NOT a draw.

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

There you go again.  The rules of chess do not specify whether an
infinite game is better than, equal to, or worse than a draw (for
both players--it does not even specify that chess must be a zero-sum
game in the case of an infinite game.)

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

Agreed.

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

A _non sequitur_.  Once again, you have no justification for assuming
that the game is a draw just from the fact that neither side can force
a win.

-- 
Chuck Carroll					      cec35848@uxa.cso.uiuc.edu
"Counselor Troi, do you sense anything from this 'Stimpy?'"
"I sense extreme stupidity...wait, there's something else...
I feel...Happy Happy Happy, Joy Joy Joy!"
Newsgroups: rec.games.chess