Game Theory and the Game of Chess

Key Result by von Neumann

• One of the first results in game theory by von Neumann
• Concerning the game of chess, one and only one of the following statements is true:
  1. White has a winning strategy
  2. Black has a winning strategy
  3. Each player has a strategy guaranteeing at least a draw
• The fourth option (none of the above) is not possible

Proving the Result Formally

• Notation and Definitions
  • Game tree vertices = game situations
  • Γ(x): Subtree rooted at vertex x, including x
  • n(x): Number of vertices in Γ(x)
  • Terminal node: nx = 1, game ends in one of three outcomes (win, lose, draw)

Induction Proof Method

• Base Case (nx = 1):
  • If nx = 1, x is a terminal node, thus exactly one of the three outcomes is true
• Induction Hypothesis:
  • Assume for all y in Γ(y) with n(y) < n(x), exactly one of the three statements holds
• Inductive Step: nx > 1
  • Must apply induction hypothesis to all subtrees of x

Consider White's Move (Without loss of generality)

• C(x): All nodes reachable from x in one action by the current player (White)
• Three Cases:
  1. Existence of a Node y₀ in C(x) where White has a winning strategy
     • White can move to y₀ to guarantee a win at x
  2. For all Nodes y in C(x), Black has a winning strategy
     • Black can ensure a win no matter White's action
  3. Neither of the Above (Case 1 and Case 2 do not hold)
     • If 1 doesn't hold: White has no winning strategy in any node of C(x). By hypothesis for each y in C(x), either Black has a winning strategy or both have a draw strategy
     • If 2 doesn't hold: There exists y' in C(x) where Black does not have a winning strategy. White can move to y' to ensure a draw strategy for both players

Conclusion

• The proof confirms that one and only one of the three statements about the game of chess (White wins, Black wins, or both draw) is always true.