Mathematics and Chess MacTutor Index

 Previous page (Puzzles) Contents Next page (Conclusion)

## Fundamentals

It is debatable though not unreasonable to claim that the deductive and finite inductive logic used in Chess problems is gratifying, as is the constructive mathematics involved in tackling Chess puzzles like the Knight's tour. These questions take snapshots of the game and ask for simple answers, or work with it in a substantially reduced form that is barely comparable to the game of Chess. It is certainly true to say that thus far we have ignored the more fundamental elements of the game. Towards righting this wrong, a piece of work by Ernst Zermelo will be discussed in which consideration is given to the absolutely fundamental (and so far unanswered) question: whether there exists a perfect strategy for either White or Black such that by playing that strategy the result will always be a win?

Firstly though, a note on the finiteness of Chess. This question has at various times been of interest to mathematicians; however, the modern FIDE rules allow little ambiguity in this regard. Under these official rules (Quoted in FIDE, 2001):

The game is drawn, upon a correct claim by the player having the move, if

1. he writes on his scoresheet, and declares to the arbiter his intention to make a move which shall result in the last 50 moves having been made by each player without the movement of any pawn and without the capture of any piece, or
2. the last 50 consecutive moves have been made by each player without the movement of any pawn and without the capture of any piece.

With this rule, it can be shown that the game is finite, assuming that given the option to call for a draw, at least one player will do so.

Each of the 16 pawns has at most 6 moves before being promoted. Assume that it is possible for every pawn to make 6 moves, then there are now 16 6 = 96 possible moves by pawns. There are also 30 pieces that can be taken during a game. So the maximum number of moves fulfilling the conditions of the rule is 126. Assuming that these moves happen as infrequently as is possible, there are at most 126 50 + 50 = 6350 moves in a game of Chess. This figure could of course be far lower, but it can be no higher.

As stated, it has been assumed that given the option to proclaim the game a draw, at least one of the players will do so. There is of course, no necessity that this assumption be true. Two players could play using only their knights, and have them dance pointlessly around each other. After even a huge number of moves, there will be no reason to assume from the position that one player has an advantage over the other, so the knights could continue to dance until one or both players die (though this in itself could be considered a condition of finiteness if in the event of a death, the game were considered finished in some way). Farcical cases aside, Chess is finite.

Whether other stopping rules necessitate finiteness in Chess is a question that has been of interest in the past. As example, an alternative stopping rule, considered in the first half of the twentieth century without success until 1938 when it was solved by Marston Morse, calls for the game to be drawn upon the third consecutive repetition of any sequence of moves. Morse, primarily known for pioneering Morse theory, found a potentially infinite sequence of two finite sub-sequences that would indeed allow a game of Chess to continue forever (Morse and Hedlund, 1944). While the proof of the existence of such a sequence is not without interest, the non-existence of such a stopping rule makes further discussion irrelevant. We now move to the main topic of this section.

Ernst Friedrich Ferdinand Zermelo was interested not only in mathematics, but also in philosophy. He was an extremely abstract mathematician, who found fame in his work on formal set theory and in particular on the axiom of choice. He also published, in 1913, what is considered to be the first formal theorem in the theory of games. This paper considerably predates the work of John von Neumann, whose 1928 paper makes him 'Without doubt "the father of game theory" ' (Kuhn, 2004).

Zermelo's paper, whose title translates as On an Application of Set Theory to the Theory of the Game of Chess (1913), considers whether Chess (as defined in the paper) has a winning strategy. It is worth noting, as Zermelo did, that there exist positions in a game of Chess from which, if each player plays correctly, the outcome is determined. Good examples of this are the Chess problems considered above, where a position is specified with a condition such as 'White to Play and Mate in Two'. Recall that the solution to these problems is found only when for every possible counter-move by the opposition, a move is found that will result in a Mate in the specified number of moves or less. It is then natural to ask whether the board is configured in such a way before play has begun. Is there, for some fixed natural number N, a solution to the problem:

White to Play and Mate in N? Zermelo considered Chess to be a potentially infinite game, but took it that if such a game occurred, it would be a draw. Thus, the N is not a restriction, since if no fixed N existed, the game could continue indefinitely (Zermelo, 1913).

'Zermelo's Theorem' has become a matter of mathematical folklore, certainly in the English-speaking world (Schwalbe and Walker, 1997). Throughout literature in the last century, variations of the theorem appeared in several forms. Some claimed that Zermelo proved something that he did not, namely that Chess, or sometimes a more general class of game, was determinate (e.g. Aumann, 1989, p.1). Others claim he used a method of proof, known as 'backwards induction' that was not employed until 1953, by von Neumann and Morgenstern. Ken Binmore (1992) writes, Zermelo used this method way back in 1912 to analyze Chess. It requires starting from the end of the game and then working backwards to its beginning. (p.32)

Zermelo did no such thing. Worst of all is the claim by M.A. Dimand and R.W. Dimand in 1996 that In a finite game, there exists a strategy whereby a first mover ... cannot lose, but it is not clear whether there is a strategy whereby the first mover can win (p.107, Dimand and Dimand, 1996).

Not only is this not what Zermelo stated, but in fact there is no reason to assume that the statement attributed to him is even true.

That Zermelo's paper was originally published only in German may have been a significant factor leading to the confusion regarding what was discussed therein. Regardless, the falsities in modern literature these days are a warning about taking for granted what is written before.

Since Ulrich Schwalbe and Paul Walker faithfully translated Zermelo's paper in 1997 and published the translation in the appendix to Zermelo and the History of Game Theory, it has become easier to determine the truth of what is discussed. Zermelo considers the class of two-person games without chance, where players have strictly opposing interests and where only a finite number of positions are possible. Chess is an obvious example of such a game

Zermelo attempts to answer the following question:

Can the value of an arbitrary position, which could possibly occur during the play of a game, as well as the best possible move for one of the playing parties be determined or at least defined in a mathematically objective manner ... ? (Zermelo, 1913, p.133)

Let P = {p0 , p1 , ... , pt}, be the set of possible positions, where a position is considered to be different depending on whether White or Black is to play, castling is allowed, etc. This is a huge but finite set.

Now, if q is such a position, then there exist endgames q = {q , q1 , q2 , ...} where qi+1 follows by a legal Chess move from qi. Such endgames can end in Checkmate, Stalemate, or can be potentially infinite in which case, as stated, the result is considered a draw.
Let Q be the set of all possible q starting from q. Q is a well-defined subset of the set Pa comprising all possible countable or finite sequences formed from elements of P.

Now, within the set Q, some q may lead to a Checkmate for White in r or fewer moves (defined by Zermelo to be a single change in position, rather than the more common definition of a move where both White and Black affect one change.) Obviously though, the play will be dictated by the movement of Black, and so the existence of such a q does not guarantee a win for White in r or fewer moves. Zermelo claims that a necessary and sufficient condition such that White can force a win in at most r moves regardless of the play of Black is the existence of a (non-vanishing) subset Ur(q) of Q that has the following properties:

1. All elements q of Ur(q) end in at most r moves with a win for White, such that no sequence contains more than r + 1 elements and Ur(q) is definitely finite.
2. If q is an element of Ur(q), and qb is the result of a move by Black in q where there exists an alternative move leading to qb' , then there exists an element of Ur(q) such that the sequence is the same as q until qb-1 and has qb' instead of qb.

Note that while the first condition has simply been reproduced from the translation of Zermelo's paper, the second has been paraphrased somewhat for simplicity of reading. There may exist more than one possible set Ur(q), so the condition, where Ur(q) is the union of all possible Ur(q), is better stated thus: Ur(q)  .

Zermelo claimed that in order that White be in a 'Winning position' at all, the necessary and sufficient condition was the existence of a non-empty set U(q) = Ut(q), recalling that there are t positions possible on a Chessboard. This is equivalent to saying that if White can win, then it must be possible to win in less moves than there are positions on a Chessboard. He reasoned that if there existed a winning sequence q, where |q| > t, then there must be at least one position that occurs twice. If this is the case, then when the position appears the first time, White should play as he would have when the position occurred the second time, thus removing the need for the moves in between the first and second appearance of the position and reducing the length of q.

This will be true as long as q has length greater than t, and so if White can win at all, then it must be possible to win in less than t moves.

Unfortunately, thirteen years later, Dénes König (more famous for writing Theorie Der Endlichen Und Undenlichen Graphen in 1936, the first comprehensive treatise on graph theory) published a paper whose title translates as On a Method of Conclusion from the Finite to the Infinite in which he claimed that Zermelo's argument was flawed. König claimed that Zermelo did not consider the possibility that Black will also change his strategy between the first and the second occurrence of a repeated position, and that this oversight invalidated the argument. Zermelo responded with a correct proof of his statement, using methods similar to those employed by König.

Returning now to Zermelo's original argument, we must consider what it means for the set U(q) to be empty. In this case, White is not in a winning position. A new subset V(q) of Q must now be defined. The details of its construction are similar to those of the construction of U(q) and will be omitted. In essence though, the subset contains all possible q where White postpones defeat indefinitely. It is the intersection over s of all subsets Vs(q), where White postpones defeat for at least s moves. Note that the possibility that V(q) is empty contradicts the claim by Dimand and Dimand (1996) that White, playing correctly, cannot lose.

We thus have the following conditions:

U(q) non-empty White is in a winning position
U(q) empty, V(q) empty Black is in a winning position
U(q) empty, V(q) non-empty Result will be a draw if both play perfectly

Certainly these sets can be determined for certain values of q: those q employed in Chess problems for example. The question of whether Chess is 'solvable' is reduced to determining the size of these sets when q = p0 , the starting position of the game. As Zermelo himself states

Should it be answered exactly, Chess would of course lose the character of a game at all. (Zermelo, 1913, p. 136)

Note that, while Zermelo did not prove the truth of this, 'Zermelo's Theorem' as it is often stated, is still true. Namely,

In chess either white can force a win, or black can force a win, or both sides can force at least a draw (Aumann, 1989, p.1)

It is thus the sheer complexity of the game of Chess alone that allows it to retain its mystery. It is no less determinable (in theory though not in practice) than Noughts and Crosses.

 Previous page (Puzzles) Contents Next page (Conclusion)

John MacQuarrie January 2005