Combinatorial games offer an excellent example of the divide between theory and practice. On the one hand, we have Zermelo's Theorem (Theorem 4.17) asserting that one player can guarantee victory in any such game by following a particular series of moves. On the other hand, this theorem offers no practical help in executing the move-by-move play of a long and complicated game. While the theory of combinatorial games might be said to begin with Zermelo's Theorem, it certainly does not end with this result.

Recall that we have defined a combinatorial game to be a sequential-move finite win-lose game of perfect information. We begin this chapter by extending our proof of Zermelo's Theorem for takeaway games (Theorem 10.9) to the general case of combinatorial games. We then introduce an example of a Nim-like game called Northcott's Game and apply Bouton's Theorem (Theorem 17.11) to determine the winner and winning strategy. Each takeaway game gives rise to a new combinatorial game called the Misère version. We analyze the Misère version of Two-Pile Nim using both the Binary and Ordinal Labeling Rules. Finally, we introduce the idea of strategy stealing for takeaway games and apply this argument to give weak solutions for the games Chomp and Hex.

Zermelo's Theorem

Mathematically, a combinatorial game is modeled by a game tree. We recall a game tree is a rooted tree with end nodes labeled with the winning player (Definition 2.3). For takeaway games, the end-node labels are unnecessary: the player who moves to an end node on his or her turn is the winner. In Chapter 10, we used the Binary Labeling Rule (Definition 4.16) and the Principle of Induction for Trees (10.2) to prove Theorem 10.9. The idea was simply to label the game tree and then read off the winner and the winning strategy from the labels.

Here we extend this argument to prove Zermelo's Theorem for combinatorial games (Theorem 4.17).