We have seen that gambling games and zero-sum games are described by a real number, the expected value E. For a gambling game, E is the average payoff for a round of the game. For a zero-sum game, E is the expected value at the mixed-strategy equilibrium (Definition 15.4).

In this chapter, we consider a class of strategic games described by an ordinal number, by which we mean a nonnegative integer n = 0,1,2, …. Recall that a takeaway game is a finite two-player sequential-move strategic game with perfect information for which the last player to move wins. In Chapter 10, we proved Zermelo's Theorem for this class of games (Theorem 10.9), establishing that one player has a strategy that guarantees victory. Our proof of Theorem 10.9 depended on the Binary Labeling Rule (Defintion 4.16) and the Principle of Induction for Trees. In this chapter, we introduce a refinement of the Binary Labeling Rule we call the Ordinal Labeling Rule. This new rule assigns an ordinal number called the Sprague–Grundy number to a takeaway game. Like the Binary Labeling Rule, the Ordinal Labeling Rule determines the winner and winning strategy for a takeaway game.

We then revisit the prototypical takeaway game: Nim. With many piles and many chips, the game Nim is too large to solve directly by labeling rules. Charles Bouton produced an elegant solution to the general game in 1901 involving binary numbers. We introduce binary numbers here and use them to prove Bouton's Theorem. We apply Bouton's Theorem, in turn, to address Question 1.4 from Chapter 1.

Sprague–Grundy Numbers

We introduce a new labeling system for game trees of takeaway games. Given a finite set of ordinal numbers S, the number Mex (S) is defined to be the smallest ordinal not in S. The term Mex(S)stands for the minimum excluded number of S.