From: hrubin@pop.stat.purdue.edu (Herman Rubin)
Subject: Re: The Last Word on Chess Solvability
Organization: Purdue University Statistics Department
Date: Tue, 6 Oct 1992 15:25:09 GMT

In article <1992Oct6.025752.12554@cbnewsl.cb.att.com> ed@cbnewsl.cb.att.com (edward.m.hummel) writes:
>(Renato Ghica) writes:
>>There are a finite number of game positions, (even when considering
>>promotions, en-passant, wether a king or a rook has moved), but...
>>game positions are not important, it's the sequence of moves leading up
>>to them that are. This is because given a chess position, one has
>>no way of precisely determining what sequence of moves will create
>>that position (indeed, there are an infinite sequence of moves
>>that will create a position if there are no such things as the 50
>>move rule). 

>In a previous posting I rejected this argument because of the
>apparent equivalence of positions that contained the same state
>information (player to move, available moves of the pieces, etc.).
>Chuck Carroll has since convinced me that my objection is flawed.
>In fact, it would seem that there are indeed an infinite number of
>possible values for the finite number of chess positions.  As such,
>the game is unsolvable.

The argument by sequence of moves is irrelevant.  There are a finite
number of positions (a position includes whose turn it is to move).
Now one can proceed as follows:

	Some positions (with black to move) are checkmates.
	These are wins for white.

	Some positions (with white to move) are checkmates.
	These are wins for black.

	Some positions are stalemates.  These are clearly draws.

We can now proceed by recursion.  If white is to move, and can 
move to a position which is a win for white, the position is a
win for white.  If white is to move, and can force a position
which is a draw, white has at least a draw.  If white is to move,
and all moves lead to positions which are wins for black, the 
position is a win for black.  If white is to move, and all moves
lead to positions which are at least draws for black, the position
is not a win for white.  We can proceed similarly for black to move.

Going through the finite number of cases, at each stage additional
positions may end up determined, or the possibilities limited. 
Eventually, a stage is reached where no further changes take place.
At that point, any position not resolved is a draw.  This is a
constructive draw in the following sense:  If it is white to move,
white can move to such a position that black does not have a win,
and if it is black to move, black can move to a position from which
white does not have a win.  If white and black use any such strategies,
the game will continue forever or end in a stalemate, and if white or
black ever deviate from this strategy, that player will lose.  So on
a sufficiently large computer with enough time, an explicit PROCEDURE
is produced such that in a given position a player wins if possible,
and otherwise only stalemates or infinite games result as long as the
players follow the recommendations.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hrubin@pop.stat.purdue.edu (Internet, bitnet)  
{purdue,pur-ee}!pop.stat!hrubin(UUCP)