On Numbers and Games, Conway
A book on combinatorial game theory.
The first (“zeroth”) part of the book introduces the objects that Conway calls Numbers but which are now known as the surreals, which are what you get when you smash together the ideas of Dedekind cuts and von Neumann ordinals. All the familiar real numbers are in there, like $0$, $3/2$, $-\pi$, and so on, but also infinitely more numbers than you could ever imagine, tightly squeezed below, above and in-between: like $\infty$, $\infty + 1$, $1/\infty$, $\frac{1}{\infty^\infty - \infty}$, and so on.
The second (“first”) part of the book then relaxes one of the constraints in the original construction of Numbers to obtain the class of all Games, written $\mathbf{Pg}$. Every number is a game, but not the other way around. While they don’t enjoy all the properties of numbers (e.g. you can’t compare them nicely, and $x = y$ doesn’t imply $xz = yz$), they’re an unbelievably rich mathematical structure. So-called because each element corresponds to a two-player perfect-information game, lurking within them are the nimbers, ups, downs, bynumbers, hot games, cold games, double-ups, double-downs, superstars, and so on, ad infinitum.
- For a list of all games considered in the book (and more!), see [[Games]]^{N}.
- Related books:
- Related blog posts:
- [[Winning colourful Nim with the eeny-meeny rule]]^{B}, on a generalisation of Nim.
Notes
Part 0: “…On Numbers”
Chapter 0: “All Numbers Great and Small”
Chapter 1: “The Class $\mathbf{No}$ is a field”
Chapter 2: “The Real and Ordinal Number”
Chapter 3: “The Structure of the General Surreal Number”
Chapter 4: “Algebra and Analysis of Numbers”
Chapter 5: “Number Theory in the Land of $\mathbf{Oz}$”
Chapter 6: “The Curious Field $\mathbf{On} _ 2$”
Part 1: “…and Games”
Chapter 7: “Playing Several Games at Once”
Chapter 8: “Some Games are Already Numbers”
Chapter 9: “On Games and Numbers”
Chapter 10: “Simplifying Games”
Chapter 11, “Impartial Games and the Game of Nim”
This chapter covers impartial games, which are games where each player has access to exactly the same set of moves for any position. Games like this include Nim, Sprouts and Kayles, but not Tic-Tac-Toe (you place $X$s, your opponent places $O$s), Chess or Go (you play white, they play black).
The main result of this chapter is effectively the Sprague-Grundy theorem, which states that every impartial game under the normal play convention is equivalent to a one-heap game of Nim. This was not a new result when the book was published, it had been known since at least the 1940s. But the approach to get to it is very different, and leads to a subset of Games called the nimbers. Applying the same definition of addition to nimbers as there is for every other sum of two games leads implicitly to Bouton’s theorem, which says you can win a multi-heap game of Nim if you can make the bitwise XOR (“nim-sum”) of the two pile sizes equal to zero – hence if you have a dictionary of the Nim-values for any impartial game, you can play optimally.
@Define what it means for a game $G$ to be impartial.
For every position $P = \{L \mid R\}$ of $G$, $L = R$ as sets.
How can you shorten the notation for
\[G = \\{A, B, C, \ldots \mid A, B, C, \ldots \\}\]
i.e. where $G$ is an impartial game?
Just write $G = \{A, B, C, \ldots\}$ and use $G’$ for both $G^L$ and $G^R$.
@Define the nimbers inductively, including infinite nimbers
so in particular:
- $\star 0 = \{ \vert \}$
- $\star 1 = \{0 \mid 0\} = \star$
- $\star 2 = \{0, \star \mid 0, \star\}$ (and not just $\{\star \mid \star\})$.
In general, nimbers are defined for all ordinals where
\[\star \alpha = \\{\star \beta\\}_{\beta < \alpha'}\](Theorem 70) @State a theorem about when a game played with a finite collection of numbers is equivalent to a position in Nim, and quickly justify why it is true.
Suppose:
- $G$ is any game played with a finite collection of numbers
- Each move affects just one number and strictly changes that number
- Any decrease of a number is always obtainable by a legal move, but some increases may also be possible
- The rules of the game ensure that it always terminates
Then:
- The outcome of any position in $G$ is the same as that of the corresponding position in Nim.
The player who is winning at Nim doesn’t need to use the moves which increase any number. If their opponent increases a number, then (3) implies that the player who is winning can immediately decrease that number again (their opponents moves are reversible).
(Theorem 71) @State a theorem which connects a certain class of games $G$ to Nim?
Suppose:
- $G$ is a short impartial game
- (short: there are only finitely many positions in the game)
- (impartial: each opponent has access to the same set of moves)
Then:
- $G$ is equivalent in play to some Nim heap.
(in fact, you drop the condition that it is a short by allowing infinite Nim-heaps).
(Theorem 71) @Prove that if
- $G$ is a short impartial game
- (short: there are only finitely many positions in the game)
- (impartial: each opponent has access to the same set of moves)
then:
- $G$ is equivalent in play to some Nim heap.
Since $G$ is a short impartial game, $G = \{A _ 1, \ldots, A _ m\}$ for some $m$. By induction, these positions are equivalent to Nim-heaps of sizes $a _ 1, \ldots, a _ m$.
Let $n = \text{mex}(a _ 1, \ldots, a _ m)$.
Then $G$ is essentially a Nim-heap of size $n$. Why?
Any decrease of $n$ is obtainable by a legal move $a _ i$ by the definition of $\text{mex}$, like in Nim. An increase of $n$ corresponds to some $a _ j$ where $a _ j > n$, but if an opponent increases to $a _ j$, then the other player can still make their original decrease since all decreases are possible.
But it is not possible to move onto $n$ itself.
Then by Theorem 70, $G$ is essentially a Nim-heap of size $n$.
If $G$ is an impartial game and its options correspond to nimbers $\star a$, $\star b$, and so on, what nimber is $G$ equivalent to?
@Define the octal game corresponding to $0.A _ 1 A _ 2 A _ 3 \cdots$.
If digit $A _ k$ has binary expansion $2^{k _ 1} + 2^{k _ 2} + \cdots + 2^{k _ n}$, this means it is legal to remove $k$ objects from any heap and then partition the remainder of that heap into $k _ 1, k _ 2, \ldots, k _ n$ new heaps. A move is legal iff it is allowed by some $A _ k$.
Octal games are where $A _ k < 8$, since these correspond to games with interpretations in terms of lines of objects.
Can you define the octal “numbers” corresponding to Nim and Kayles?
- Nim: $0.333\cdots$
- You can remove any of stones from a heap (hence expansion infinite).
- You can leave either 0 heaps or 1 heaps (the former corresponding to taking a whole pile, and the latter corresponding to only taking a portion of the pile).
- Kayles: $0.77$
- You can either remove a single stone from a line or two stones from a line.
- In each case, you can leave either $0$, $1$ or $2$ lines:
- $0$: Completely obliterate a line.
- $1$: Remove stones from the beginning or the end of a line.
- $2$: You hit the middle of a line, splitting it into two.