Software:Zermelo's theorem (game theory)

Short description: In board games that cannot end in a draw, one of the two players has a winning strategy

In game theory, Zermelo's theorem is a theorem about finite two-person games of perfect information in which the players move alternately and in which chance does not affect the decision making process. It says that if the game cannot end in a draw, then one of the two players must have a winning strategy (i.e. can force a win). An alternate statement is that for a game meeting all of these conditions except the condition that a draw is now possible, then either the first-player can force a win, or the second-player can force a win, or both players can at least force a draw. The theorem is named after Ernst Zermelo, a German mathematician and logician, who proved the theorem for the example game of chess in 1913.

Example

Zermelo's theorem can be applied to all finite-stage two-player games with complete information and alternating moves. The game must satisfy the following criteria: there are two players in the game; the game is of perfect information; the board game is finite; the two players can take alternate turns; and there is no chance element present. Zermelo has stated that there are many games of this type; however his theorem has been applied mostly to the game chess.

When applied to chess, Zermelo's theorem states "either White can force a win, or Black can force a win, or both sides can force at least a draw".

Zermelo's algorithm is a cornerstone algorithm in game-theory; however, it can also be applied in areas outside of finite games. Apart from chess, Zermelo's theorem is applied across all areas of computer science. In particular, it is applied in model checking and value interaction.

Conclusions of Zermelo's theorem

Zermelo's work shows that in two-person zero-sum games with perfect information, if a player is in a winning position, then that player can always force a win no matter what strategy the other player may employ. Furthermore, and as a consequence, if a player is in a winning position, it will never require more moves than there are positions in the game (with a position defined as position of pieces as well as the player next to move).

Publication history

In 1912, during the Fifth International Congress of Mathematicians in Cambridge, Ernst Zermelo gave two talks. The first one covered axiomatic and genetic methods in the foundation of mathematical disciplines, and the second speech was on the game of chess. The second speech prompted Zermelo to write a paper on game theory. Being an avid chess player, Zermelo was concerned with application of set theory to the game of chess. Zermelo's original paper describing the theorem, Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels, was published in German in 1913. It can be considered as the first known paper on game theory. Ulrich Schwalbe and Paul Walker translated Zermelo's paper into English in 1997 and published the translation in the appendix to Zermelo and the Early History of Game Theory.

Details

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. Although in the game only finitely many positions are possible, Zermelo allows infinite sequences of moves since he does not consider stopping rules. Thus, he allows for the possibility of infinite games. Then he addresses two problems:

1. What does it mean for a player to be in a 'winning' position and is it possible to define this in an objective mathematical manner?
2. If the player is in a winning position, can the number of moves needed to force the win be determined?

To answer the first question, Zermelo states that a necessary and sufficient condition is the nonemptyness of a certain set, containing all possible sequences of moves such that a player wins independently of how the other player plays. But should this set be empty, the best a player could achieve would be a draw. So Zermelo defines another set containing all possible sequences of moves such that a player can postpone his loss for an infinite number of moves, which implies a draw. This set may also be empty, i.e., the player can avoid his loss for only finitely many moves if his opponent plays correctly. But this is equivalent to the opponent being able to force a win. This is the basis for all modern versions of Zermelo's theorem.

About the second question, Zermelo claimed that it will never take more moves than there are positions in the game. His proof is a proof by contradiction: Assume that a player can win in a number of moves larger than the number of positions. By the pigeonhole principle, at least one winning position must have appeared twice. So the player could have played at the first occurrence in the same way as he does at the second and thus could have won in fewer moves than there are positions.

In 1927, a Hungarian mathematician Dénes Kőnig revised Zermelo's paper and pointed out some gaps in the original work. First of all, Kőnig argues that Zermelo did not prove that a player, for example White, who is in a winning position is always able to force a win by making moves smaller than the number of positions in the game. Zermelo argued that White can change its behaviour at the first possibility of any related winning position and win without repetition. However, Kőnig maintains that this argument is not correct as it is not enough to reduce the number of moves in a single game below the number of possible positions. Thus, Zermelo claimed, but did not show, that a winning player can always win without repetition. The second objection by Kőnig is that the strategy 'do the same at the first occurrence of a position as at the second and thus win in fewer moves' cannot be made if it is Black's turn to move in this position. However, this argument is not correct because Zermelo considered two positions different whether Black or White makes a move.

Zermelo's theorem and backward induction

It has been believed that Zermelo used backward induction as his method of proof. However, recent research on the Zermelo's theorem demonstrates that backward induction was not used to explain the strategy behind chess. Contrary to the popular belief, chess is not a finite game without at least one of the fifty move rule or threefold repetition rule. Strictly speaking, chess is an infinite game therefore backward induction does not provide the minmax theorem in this game.

Backward induction is a process of reasoning backward in time. It is used to analyse and solve extensive form games of perfect information. This method analyses the game starting at the end, and then works backwards to reach the beginning. In the process, backward induction determines the best strategy for the player that made the last move. Then the ultimate strategy is determined for the next-to last moving player of the game. The process is repeated again determining the best action for every point in the game has been found. Therefore, backward induction determines the Nash equilibrium of every subgame in the original game.

There is a number of reasons as to why backward induction is not present in the Zermelo's original paper:

Firstly, a recent study by Schwalbe and Walker (2001) demonstrated that Zermelo's paper contained basic idea of backward induction; however Zermelo did not make a formal statement on the theorem. Zermelo's original method was the idea of non-repetition. The first mention of backward induction was provided by László Kalmár in 1928. Kalmár generalised the work of Zermelo and Kőnig in his paper "On the Theory of Abstract Games". Kalmár was concerned with the question: "Given a winning position, how quickly can a win be forced?". His paper showed that winning without repetition is possible given that a player is a winning position. Kalmár's proof of non-repetition was proof by backward induction. In his paper, Kalmár introduced the concept of subgame and tactic. Kalmár's central argument was that a position can be a winning position only if a player can win in a finite number of moves. Also, a winning position for player A is always a losing position for player B.

External links

• Original Paper(in German)
• Ulrich Schwalbe, Paul Walker, Zermelo and the Early History of Game Theory, Games and Economic Behavior, Volume 34, 2001, 123-137, online