Zermelo's theorem (game theory)
Zermelo's theorem (game theory)
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 not 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".
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). 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.
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.