From: dseal@armltd.co.uk (David Seal)
Newsgroups: sci.math
Subject: Re: "Solvability" in Chess
Date: 29 Sep 92 12:34:13 GMT
Distribution: sci
Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK

In article <1992Sep28.155640.152096@Cookie.secapl.com>
frank@Cookie.secapl.com (Frank Adams) writes:

>In article <1992Sep25.014035.1269@cbnewsl.cb.att.com> ed@cbnewsl.cb.att.com (edward.m.hummel) writes:
>>I think this argument rest on the assumption that chess is a zero sum game.
>>How do you prove that?  Suppose the value of an infinite game is less than
>>a draw for each player (but more than a loss), then neither player
>>would choose a draw *with best play*.
>
>As noted, this was intended to read "more than a draw for each player (but
>less than a win)".  However, it is actually closer to correct as written:
>the value of an infinite game *is* less than a draw; not as specified by the
>rules, but in fact: no one wants to spend the rest of their life playing a
>single game of chess.  This isn't *in* the rules for chess; it is *assumed*
>by them.

In normal circumstances, I would agree with you. But it isn't provable, and
isn't even true in abnormal circumstances. Imagine a game of chess with the
following playing conditions:

(a) Play will be adjourned to the next day after each 40 moves;

(b) When the game ends, both players will be executed.

Under such circumstances, I would not merely prefer an infinite game to a
draw: I would also prefer it to a win! And yes, I would want to spend the
rest of my life playing that game of chess (and in fact, I would do so
whether I wanted to or not...).

Of course, it wouldn't be a very interesting game of chess. Since the
players probably want to rattle through their 40 moves as quickly as
possible, I would guess the first day's play goes something like:

  1. Nf3 Nc6
  2. Ng1 Nb8
  3. Nf3 Nc6
  4. Ng1 Nb8
  :
  :
  39. Nf3 Nc6
  40. Ng1 Nb8

without either player claiming the draw. The play on future days would be
just as optimal - and just as boring :-)

I'm not seriously suggesting that this situation is likely to occur! But if
you're willing to look a bit beyond simple min/max, you don't *need* to make
any assumption about the values the players place on the possible outcomes
of the game (i.e. win, loss, draw or infinite game). You can show that chess
is solvable whatever these values are, by showing the following:

  For any preference ordering of the 4 possible outcomes by white and any
  preference ordering of the 4 possible outcomes by black, chess is
  solvable.

  The proof is essentially to apply the min/max algorithm as far as it goes,
  then deal with any loops that the players provably don't want to break out
  of by assigning them the infinite game value, and repeat this sequence of
  two steps until the whole game tree is labelled. (Unlike the straight
  min/max algorithm, this does inescapably have large memory requirements as
  well as large time requirements - but it's still solvable in principle.)

In other words, changing the players' preference orders of the outcomes
makes no difference to whether the game is solvable - merely to what the
solution is. (It can also make a difference to whether the game is solvable
in practice in some silly cases - e.g. if white's most preferred outcome is
a loss, the game is solvable in practice: white resigns :-)

David Seal
dseal@armltd.co.uk

All opinions are mine only...
Newsgroups: sci.math