From: ghica@fig.citib.com (Renato Ghica)
Subject: Re: The Last Word on Chess Solvability
Originator: ghica@duck
Organization: Citibank IBISM
Date: Tue, 29 Sep 1992 16:56:30 GMT



NOT!

In article <Sep.26.07.44.22.1992.24110@remus.rutgers.edu>, clong@remus.rutgers.edu (Chris Long) writes:
|> No three-position draw rule or 50-move draw rule is needed to
|> show that it is solvable.  The only possible outcomes are Black

I disagree, the rules are needed to solve it.

|> wins, infinite game, Black stalemates White, White stalemates
|> black, White wins; denote these by B, b, I, w, W and assume some
|> total ordering (for example W>w>i>b>B).  Starting with the initial
|> setup, generate the game tree recursively.  If one of the four
|> situations B, b, w, W is reached, mark that branch with the appropriate
|> value.  If all branches of a given position have been marked, take
|> the maximum of the value of the branches, assign that value to the
|> position, and prune.  If a position is repeated, mark with an i and
                         ^^^^^^^^^^^^^^^^^^^^^^^^
This is the crux of the issue:

You can't determine that a position gets "repeated unless" you have a rule
such as

"a position is repeated if it occurs three times"
or
"a position is repeated if it occurs 50 times and there are no captures
 or pawn moves".

that can be described in whatever algorithm you are using. You can't
describe it otherwise. Just repeating twice, for example won't do
(because it's legal).  It depends on the RULES OF THE GAME.

|> proceed as above.  Since there are only a finite number of game
|> positions, this procedure must terminate in a finite number of steps

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



ie:
A chess player remembers "positions" and associates winning or losing
with them,but he is lost if he has no idea how they come about.
No sense in thinking about the BxH7, N-G5+, Q-H5 "position" if it can
never happen. And you don't know if it can happen if you don't know
how to get there. The material aspect of this is important only to 
soeme extent, since "BxH7+" is equivalent to "B-H7+" if it is forced.

For example, there is an infinite number of ways to create the starting
position, just by moving the knights back and forth.


|> (in fact, the number of steps is bounded by the number of different
|> positions).  The *only* assumptions are that the game must be
|> deterministic, there are a finite number of game positions, and there

Something is "deterministic" if it is defined that make it so. 
An NP type problem is not deterministic because ther are no rules
binding it. The traveling salesman problem with constrictions on it such
as "best route in 10 trips or less" becomes deterministic. "Best route"
by itself is not.


|> is some total ordering among the possible outcomes.  For example, it
|> follows that shogi and go can be solved, also.
|> 

Try again.

|> Of course, this is only a theoretical result, and it is unclear
|> if it is actually physically possible to solve chess.
|> -- 
|> Chris Long, 265 Old York Rd., Bridgewater, NJ  08807-2618

Add some more rules to it, such as
		"must give check if possible"
		"must capture if possible"
		"must do both if possible"
and it becomes very easy.

Take away the 50 move rule, and the game (and its algorythmic
representation) becomes unsolvable - or a different game.


-rg
-- 

"I am a brain, Watson."
"These views are my own. / Mail me or Flame me"