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. force a win). An alternate statement is that for a game meeting all of these conditions except the condition that a draw is not possible, then either the first-player can force a win, or the second-player can force a win, or both players can force a draw. The theorem is named after Ernst Zermelo, a German mathematician and logician.
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 they 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).
In 1912, during 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 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. 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. Zermelo's "On an Application of Set Theory to the Theory of the Game of Chess" became a novelty for the mathematician community and can be considered as the first known paper on game theory.
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:
- 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?
- 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 he defines another set containing all possible sequences of moves such that a player can postpone her loss for an infinite number of moves, which implies a draw. This set may also be empty, i. e., the player can avoid her loss for only finitely many moves if her 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. Of course, 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 Denes Konig revised Zermelo's paper and pointed out some gaps in the original work. First of all, Konig 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, Koning 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 objective by Konig 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 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.
Zarmelo's algorithm is a cornerstone algorithm in game-theory however it can be applied in areas outside of finite games. Apart from chess, the Zermelo's theorem has been applied in computer science. Zermelo's algorithm is applied across all areas of computer science. In particularly, it is applied in model checking and value interation.
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. 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. Kalmar generalised the work of Zermelo and Konig in his paper "On the Theory of Abstract Games". Kalmar 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. Kalmar's proof of non-repetition was proof by backward induction. In his paper, Kalmar introduced the concept of subgame and tactic. Kalmar's his 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.
Lastly, in view of the official game laws, chess is an infinite game. Strictly speaking, the game does not have a rule or a set of rules that ends it after a finite number if moves has been made. The game does not stop when the number of moves exceeds a given limit. Instead a player may claim to end the game in a draw when he makes a move that leads to a position where the last 50 two player moves have been made without any pawn and without capturing the other player's piece. Secondly, the game may end effectively without the player making a claim where a checkmate cannot occur by any possible series of moves. Following these rules it is possible to construct an infinite path in the game. It is the possibility of infinite paths in chess that makes the game infinite.
- Schwalbe, Ulrich; Walker, Paul. "Zermelo and the Early History of Game Theory" (PDF). Cite journal requires
- Ebbinghaus, Heinz-Dieter (14 October 2010). Ernst Zermelo: An Approach to His Life and Work (2 ed.). Berlin: Springer. p. 150. ISBN 9783642080500. Retrieved 26 April 2021.
- MacQuarrie, John (January 2005). "Mathematics and Chess, Fundamentals". Archived from the original on January 12, 2017.
- Aumann, R. J. (1989). Lectures on Game Theory (PDF). Boulder, CO: Westview Press. p. 1.
- Wooldridge, Michael (17 March 2015). "Thinking Backward with Professor Zermelo". IEEE Intelligent Systems. 30 (2): 62–67. doi:10.1109/MIS.2015.36. S2CID 12397521. Retrieved 24 April 2021.
- Ewerhart, Christian (May 2002). "Backward Induction and the Game-Theoretic Analysis of Chess". Games and Economic Behavior. 39 (2): 206–214. doi:10.1006/game.2001.0900.
- Schwalbe, Ulrich; Paul, Walker (January 2001). "Zermelo and the Early History Game Theory". Games and Economic Behavior. 34 (1): 123–137. doi:10.1006/game.2000.0794. Retrieved 26 April 2021.