THE ZERMELO THEOREM — a dart

THE ZERMELO THEOREM finite perfect-information games are solved

The first theorem of game theory: in a finite two-player game of perfect information with no chance, one of three things is already true — the first player can force a win, the second can, or both can force at least a draw. The outcome is determined before a move is made; only our ignorance hides it. Zermelo proved it for chess in 1913: a perfect strategy exists, even if no one can compute it.

THE TECHNIQUE backward induction → a forced value

The demo shows a nim position whose XOR is non-zero (first player wins) and labels a game by backward induction: live demo

HISTORY & CREDIT Zermelo · 1913

“Chess is unsolved, so its outcome is unknown in principle.” — Zermelo proved a determined value exists; we simply cannot compute it. Solvability ≠ tractability. cited

terminal · label leaf positions win/lose/draw.
induct backward · a position is a win if any move reaches an opponent-loss; propagate to the root.
1913 · Ernst Zermelo, on chess — the first game-theory theorem.

The winner is fixed; only the proof is missing. theorem

RECOMMEND FOR I-13 determinacy, on the compiler

On i-13, nim [3,4,5] has XOR 2 (first player wins), and backward induction gives each position one forced label:

$ i13 run gm_zermelo-theorem.i13 RUN OK · 390 step(s) · call depth 5 nimsum = 2 first_wins = 1 win(0)=0 win(3)=0 win(4)=1 -- one forced value each determined = 1

Recommend as a NULL — a theorem (B39). The forced outcome is pinned by the game tree; backward induction is the witness every correct solver shares. NULL — finite perfect-information games are solved (existence, not tractability).