Zermelo's theorem is a fundamental result in game theory that states that in a two-player game where
- each player has perfect information about the state of the game
- players take turns placing their move
- no chance is involved
- games end after a finite number of moves
- games do not end in a draw
one of the two players will have a winning strategy. I first encounter this theorem in Hugo Steinhaus'
Mathematical Snapshots (a book that I cherish as I received it as a prize from participating in the first
LVAIC Mathematics Competition). This result basically states that one of the two players can always win if he or she plays appropriately. On the surface this is easy to understand. If player A does not have a winning strategy, then this means that whatever moves player A makes, player B has a move that prevent A from winning. Since the games do not end in a draw, this means that player B will win eventually, i.e. B has a winning strategy. This is an very interesting result since it implies that these games are inherently not fair; one player always has the advantage. The problem is that in complicated games we don't know which player has this advantage. When applied to chess this implies that either black or white can always force a win or a draw; we just don't know which color that is. Since the game is finite, given enough computational power and time, it is possible to find out which player has the winning strategy by exploring all possible scenarios. Or we may find out that by playing appropriately, all chess games will end in a draw. Once such exhaustive search is done, computers playing chess would lose its excitement and allure, since we know apriori which color will win (or draw) and the winning strategy can be implemented via table lookup. Fortunately, the number of moves in a chess game and the range of moves result in a search space so large that its complete exploration is out of reach for many years to come.
