From: Joe.Mattis@mailbox.bison.mb.ca (Joe Mattis)
Newsgroups: rec.games.chess
Subject: Re: Chess is not solvable
Date: 24 Sep 92 22:28:22 CST

Organization: School of Computer Science, Carnegie Mellon

In article <cek8TIW2ATvuR1gkRq@pitt.edu> tasst2+@pitt.edu (Teri A Meyers) writes
:
>Here are my thoughts on this matter, which come more from philosophy than
>from game theory.

Don't be put off by the term "game theory"...that's just an intimidating
phrase for some ideas that follow from common-sense reasoning.

>I operate on the assumption that from the initial position
>neither side can force a win.

Well, that assumption might be wrong (that's why you called it an
"assumption"), which makes the rest of your analysis invalid.  But you still
raise some interesting points, so I'll address those.

>This assumption may be mathematically unprovable
>but neither can it be disproved,

Not quite true.  The assumption is *practically* unprovable/undisprovable...
i.e. we cannot prove/disprove it in actual practice.  However, the assumption
IS theoretically (mathematically) provable/disprovable...you just don't know
how such proofs work (yet!).

>Anyways, if the starting position represents a balance (a "draw" [...]),
>than it strikes me that the game
>can only be won if someone disturbs the balance (ie, makes mistakes).

Your statement captures the essence of the "minimax" algorithm for games.
Assign the following numeric evaluations to all possible final game positions:
        Black to move (in check); no legal moves (checkmate):     +1
        Black to move (not in check); no legal moves (stalemate):  0
        White to move (not in check); no legal moves (stalemate):  0
        White to move (in check); no legal moves (checkmate):     -1
Unless a player makes a mistake, White will always move in such a manner
so as to reach a position with the "maximum" possible evaluation, and Black
will move so as to reach a position with the "minimum" possible evaluation.

>[...] who can say there is any theoretical upper
>limit to the number of possibilities (actual moves plus the vast horizon
>of possible variants).

But there *is* one, since "vast" does not mean "infinite"!  First, there's the
"50 move rule"...if no pawn was advanced or piece captured in the last 50
moves, either player may claim a draw.  With 16 pawns (which can advance
6 ranks) and 30 pieces (which can be captured), games can last at most:
                 (16 * 6 + 30) * 50 = 6300 moves
before the "50 move rule" can be invoked for a draw.

But even if we ignore the "50 move rule", there are only a finite number
of possible positions.  With 64 squares, which can be in one of (at most)
13 states (empty or occupied by W/B * KQRBNP), there are (at most) 13 ^ 64
board configurations.  For each configuration, either W/B moves next (2),
each king can/cannot castle K/Q-side ((2*2)^2), and there are (at most)
9 "en passant" states (none or file abcdefgh).  So there are (at most):
        (13 ^ 64) * 2 * (4 ^ 2) * 9 ~= 5.6 * 10^73 positions

Each of these positions will either be a final position (with an evaluation
of +1, 0, or -1), or it will lead into a few of the 5.6 * 10^73 other
positions, based on the range of possible legal moves.  Thus, all of chess
can be represented by a huge cyclic directed graph, where the nodes represent
positions, and the links represent legal moves.  The task of "solving
chess" consists of determining evaluations for all of the unevaluated
(non-final) positions:
        White to move, and can force checkmate: +1
        White to move, and can force stalemate:  0
        Black to move, and can force stalemate:  0
        Black to move, and can force checkmate: -1

This is actually very simple!  Cycle through the unevaluated positions,
performing the following computation:
        IF White to move THEN
                IF some move leads to a +1 position THEN
                        evaluate this position as +1
                ELSE IF all moves lead to evaluated positions THEN
                        evaluate this position as the MAXIMUM of the
                        evaluations of all possible moves
                ELSE this position remains unevaluated this cycle.
        ELSE /* Black to move */
                IF some move leads to a -1 position THEN
                        evaluate this position as -1
                ELSE IF all moves lead to evaluated positions THEN
                        evaluate this position as the MINIMUM of the
                        evaluations of all possible moves
                ELSE this position remains unevaluated this cycle.

Keep doing these cycles until an entire cycle is performed during which
no new evaluations were determined.  The remaining unevaluated positions
represent positions where, due to repetition or lack of material, neither
side can force checkmate or stalemate.  Evaluate all such positions as:
        Neither side can force checkmate or stalemate:  0

Now, every possible chess position, including the initial position, has
an evaluation:
        Black is checkmated, or White can force checkmate:     +1
        Neither side can force checkmate, thus both sides
                can force a draw:                               0
        White is checkmated, or Black can force checkmate:     -1

Theoretically, this evaluated graph can be constructed, so theoretically,
chess is solvable!  But, practically, I'm confident that it will never
actually be solved.

>[...] However, when can the machine stop its analysis and declare the
>position conclusively a draw? [...] how does it know it will not find the
>win by searching one ply further? [...]

This is rather insightful for somebody who (apparently) doesn't know anything
about game theory and searching.  What you've described is a serious concern
for computerized theorem provers...such programs never can be sure when to
give up and declare a theorem "unprovable", since applying "reduction" just
one more time might yield a completed proof.

But since chess positions are finite in number (unlike proofs), this concern
does not apply to chess.

-Joe Mattis    ARPA:  jam@isl1.ri.cmu.edu
               UUCP:  ...!ucbvax!isl1.ri.cmu.edu!jam@ucbvax.berkeley.edu

 * Origin: The Electronic Mailbox (1:348/7.0)