From: carabalo@phoenix.Princeton.EDU (David G. Caraballo)
Subject: Re: The Last Word on Chess Solvability
Originator: news@nimaster
Organization: Princeton University Mathematics Department
Date: Thu, 8 Oct 1992 01:39:39 GMT

Herman Rubin gives an excellent account in article
<BvpHHy.BpM@mentor.cc.purdue.edu>.  I would like to add that infinite games
cannot arise if the players will necessarily declare a draw after threefold
repetition.  Proof:  Let X be the total number of positions, taking into 
account whose turn it is to move.  Any game with > 3X moves must repeat some
position more than three times, by the pigeonhole principle, and will (by
assumption) be declared a draw.  Since all such games are finite 
(where players necessarily declare a draw after repetetion), chess is
"solvable" in this case.  (See Rubin's article for an explicit procedure.)

In what follows, suppose both players play optimally and are part of a 
2-person, 1-game match, where the one with the higher score is declared 
winner, and the match is a tie otherwise, but they both try for the best
outcome possible.  Is it reasonable that the players will necessarily declare
a draw after threefold repetition?  It depends.  Any player who loses after an 
unclaimed threefold repetition has not played optimally (a draw is better 
than a loss).  Therefore, in any game where threefold repetition occurs, 
neither player can force a win.  If win, loss, and draw are the only 
admissible outcomes, such a game must be called a draw (by process of 
elimination).  

However, it is not unreasonable to allow a fourth outcome--infinite game-- 
with a value, like draw, above "loss" and below "win".  One natural question
is "Can a player force an infinite game?"  The answer is clearly "no", since
the other player can claim repetition and get a draw.  With a draw, both
players get the same number of points (1/2, or 0, etc.), so an infinite game
must be the same way, or the player who would get fewer points than his/her
opponent would simply have claimed a draw after 3X moves. 
In fact, with optimal play, an infinite game will occur if and only if 
1)  Neither player can force a win, and
2)  An infinite game brings strictly more "points" than a draw.  (Why keep
    playing if the outcome cannot be improved at all?)  

For sake of argument, suppose infinite games are to be allowed in optimal
play.  (i.e., not every game in which neither player can force a win is
called a draw.  In the other case, chess is clearly "solvable", as discussed
above.)  Then the ordering:  loss < draw < infinite game < win
must apply.  (e.g., point values might be 0, 1/2, 2/3, and 1 respectively).
In that event, any game in which neither player can force a win will be an
infinite game (since both players will try for this)!  So chess is "solvable"
in this case, too.

NOTE:  By "chess is solvable" I mean the following:

Given a set of allowable outcomes for all games (loss, draw, win) or
(loss, draw, infinite game, win), with real number values assigned to each,
it is *theoretically* possible for a computer to determine, in finite time, 
what the outcome of each game must be, if both players play optimally.

By "theoretically", I'm allowing the amount of required time to exceed our
estimates for the duration of the universe, and I'm allowing the amount of
memory required for such a program to exceed the physical bounds of our
universe.  Is chess *practically* solvable?  Maybe, but I don't think brute
force will do the trick, at least not any time soon.

This is my first (and last, I hope) post on this subject, so please reply
via email.

David G. Caraballo
Department of Mathematics, Princeton
Newsgroups: rec.games.chess