Zermelo's theorem (game theory)

Last updated

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. [1] The theorem is named after Ernst Zermelo, a German mathematician and logician, who proved the theorem for the example game of chess in 1913.

Contents

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. [2] [3]

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". [2] [3]

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. [4]

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). [1]

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. [5] 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. [1]

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. [5]

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. [6]

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. [4]

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. [7]

Related Research Articles

Minmax is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case scenario. When dealing with gains, it is referred to as "maximin" – to maximize the minimum gain. Originally formulated for several-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision-making in the presence of uncertainty.

<span class="mw-page-title-main">Hex (board game)</span> Abstract strategy board game

Hex is a two player abstract strategy board game in which players attempt to connect opposite sides of a rhombus-shaped board made of hexagonal cells. Hex was invented by mathematician and poet Piet Hein in 1942 and later rediscovered and popularized by John Nash.

In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equilibrium strategies of the other players, and no one has anything to gain by changing only one's own strategy. The principle of Nash equilibrium dates back to the time of Cournot, who in 1838 applied it to competing firms choosing outputs.

A solved game is a game whose outcome can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to abstract strategy games, and especially to games with full information and no element of chance; solving such a game may use combinatorial game theory and/or computer assistance.

<span class="mw-page-title-main">Ernst Zermelo</span> German logician and mathematician (1871–1953)

Ernst Friedrich Ferdinand Zermelo was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel axiomatic set theory and his proof of the well-ordering theorem. Furthermore, his 1929 work on ranking chess players is the first description of a model for pairwise comparison that continues to have a profound impact on various applied fields utilizing this method.

<span class="mw-page-title-main">Combinatorial game theory</span> Branch of game theory about two-player sequential games with perfect information

Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a position that the players take turns changing in defined ways or moves to achieve a defined winning condition. Combinatorial game theory has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.

Combinatorial game theory measures game complexity in several ways:

  1. State-space complexity,
  2. Game tree size,
  3. Decision complexity,
  4. Game-tree complexity,
  5. Computational complexity.

Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases, and where each type of case is checked to see if the proposition in question holds. This is a method of direct proof. A proof by exhaustion typically contains two stages:

  1. A proof that the set of cases is exhaustive; i.e., that each instance of the statement to be proved matches the conditions of one of the cases.
  2. A proof of each of the cases.

In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many two-player games, that the second player cannot have a guaranteed winning strategy. The strategy-stealing argument applies to any symmetric game in which an extra move can never be a disadvantage. A key property of a strategy-stealing argument is that it proves that the first player can win the game without actually constructing such a strategy. So, although it might prove the existence of a winning strategy, the proof gives no information about what that strategy is.

Sylver coinage is a mathematical game for two players, invented by John H. Conway. The two players take turns naming positive integers greater than 1 that are not the sum of nonnegative multiples of previously named integers. The player who cannot name such a number loses. For instance, if player A opens with 2, B can win by naming 3.

In mathematics, the axiom of determinacy is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game of a certain type is determined; that is, one of the two players has a winning strategy.

<span class="mw-page-title-main">Angel problem</span>

The angel problem is a question in combinatorial game theory proposed by John Horton Conway. The game is commonly referred to as the angels and devils game. The game is played by two players called the angel and the devil. It is played on an infinite chessboard. The angel has a power k, specified before the game starts. The board starts empty with the angel in one square. On each turn, the angel jumps to a different empty square which could be reached by at most k moves of a chess king, i.e. the distance from the starting square is at most k in the infinity norm. The devil, on its turn, may add a block on any single square not containing the angel. The angel may leap over blocked squares, but cannot land on them. The devil wins if the angel is unable to move. The angel wins by surviving indefinitely.

Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and similarly, "determinacy" is the property of a game whereby such a strategy exists. Determinacy was introduced by Gale and Stewart in 1950, under the name "determinateness".

In game theory, a repeated game is an extensive form game that consists of a number of repetitions of some base game. The stage game is usually one of the well-studied 2-person games. Repeated games capture the idea that a player will have to take into account the impact of their current action on the future actions of other players; this impact is sometimes called their reputation. Single stage game or single shot game are names for non-repeated games.

In game theory, a subgame perfect equilibrium is a refinement of a Nash equilibrium used in dynamic games. A strategy profile is a subgame perfect equilibrium if it represents a Nash equilibrium of every subgame of the original game. Informally, this means that at any point in the game, the players' behavior from that point onward should represent a Nash equilibrium of the continuation game, no matter what happened before. Every finite extensive game with perfect recall has a subgame perfect equilibrium. Perfect recall is a term introduced by Harold W. Kuhn in 1953 and "equivalent to the assertion that each player is allowed by the rules of the game to remember everything he knew at previous moves and all of his choices at those moves".

In descriptive set theory, the Borel determinacy theorem states that any Gale–Stewart game whose payoff set is a Borel set is determined, meaning that one of the two players will have a winning strategy for the game. A Gale–Stewart game is a possibly infinite two-player game, where both players have perfect information and no randomness is involved.

Solving chess consists of finding an optimal strategy for the game of chess; that is, one by which one of the players can always force a victory, or either can force a draw. It is also related to more generally solving chess-like games such as Capablanca chess and infinite chess. In a weaker sense, solving chess may refer to proving which one of the three possible outcomes is the result of two perfect players, without necessarily revealing the optimal strategy itself.

In graph theory, a cop-win graph is an undirected graph on which the pursuer (cop) can always win a pursuit–evasion game against a robber, with the players taking alternating turns in which they can choose to move along an edge of a graph or stay put, until the cop lands on the robber's vertex. Finite cop-win graphs are also called dismantlable graphs or constructible graphs, because they can be dismantled by repeatedly removing a dominated vertex or constructed by repeatedly adding such a vertex. The cop-win graphs can be recognized in polynomial time by a greedy algorithm that constructs a dismantling order. They include the chordal graphs, and the graphs that contain a universal vertex.

In combinatorial game theory, a subtraction game is an abstract strategy game whose state can be represented by a natural number or vector of numbers and in which the allowed moves reduce these numbers. Often, the moves of the game allow any number to be reduced by subtracting a value from a specified subtraction set, and different subtraction games vary in their subtraction sets. These games also vary in whether the last player to move wins or loses. Another winning convention that has also been used is that a player who moves to a position with all numbers zero wins, but that any other position with no moves possible is a draw.

In mathematics, S2S is the monadic second order theory with two successors. It is one of the most expressive natural decidable theories known, with many decidable theories interpretable in S2S. Its decidability was proved by Rabin in 1969.

References

  1. 1 2 3 Schwalbe, Ulrich; Walker, Paul. "Zermelo and the Early History of Game Theory" (PDF).
  2. 1 2 MacQuarrie, John (January 2005). "Mathematics and Chess, Fundamentals". Archived from the original on January 12, 2017.
  3. 1 2 Aumann, R. J. (1989). Lectures on Game Theory (PDF). Boulder, CO: Westview Press. p. 1.
  4. 1 2 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.
  5. 1 2 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.
  6. ↑ Ewerhart, Christian (May 2002). "Backward Induction and the Game-Theoretic Analysis of Chess" (PDF). Games and Economic Behavior. 39 (2): 206–214. doi:10.1006/game.2001.0900.
  7. ↑ 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.