# Combinatorial Game Theory: Surreal Numbers and the Void

###### [A pdf version is available here; LaTeX here]

Any number can be written as a tuple of games played by the void with itself.

Denote the void by the empty set ∅. We write: {∅|∅} = 0, with | as partition. ‘Tuple’ signifies ordering matters, so that {0|∅} = 1 and {∅|0} = −1. Then recursively construct the integers: {n|∅} = n + 1. Plug {∅|∅} into {0|∅} to get {{∅|∅}|∅} = 1, then this into {1|∅} to get {{{|}|∅}|∅} = 2…

So if games exist, numbers exist. Or rather: if games exist, numbers don’t have to.

Mixed orderings generate fractions, e.g. {0|1} = {{∅|∅}|{{∅|∅}|∅}} = ½. Games with infinity (written ω) or infinitesimals (ε = 1/ω) permit irrationals, and thus all reals. Further, it is valid to define {ω|∅} = ω + 1, etc. Once arithmetic operations are defined, more complex games can define and *use* such quantities as ∛ω and ω^{ω}.

Therefore: by defining numbers as games, we can construct the **surreal numbers**.^{(1)}

∗ ∗ ∗

As well as defining numbers as games, we can treat games like numbers.

{∅|∅} can be played as the *zero game*. Simply: player 1 cannot move, and loses. Any game where player 2 has a winning strategy is equivalent to the zero game. Take two games G and H, with G a 2^{nd} player win. The player with a winning strategy in H can treat the games separately, only moving in G to respond to the opponent. Player 2 wins G, but does not affect H’s outcome. Conversely, given G′ and H′, with G′ a 1^{st} player win, player 1 is last to move in G′, giving player 2 an extra move in H′, potentially altering its outcome. In terms of outcomes, we say G + H = 0 + H → G = 0.

For a game G, −G is G with the roles reversed, as by turning the board around in chess.

G = H if G + (−H) = 0, i.e. is a player 2 win, and so is equivalent to the zero game.

Two more properties are clear: G + (H + K) = (G + H) + K (associativity) and G + H = H + G (commutativity).

We can see that G + (−G) = 0 by a clever example called the Tweedledum & Tweedledee argument. In the game Blue-Red Hackenbush, players are given a drawing composed of separate edges. Each turn, player 1 removes a blue edge, plus any other edges no longer connected to the ground, and player 2 does likewise for red edges. Since in G + (−G) the number of pieces is the same, player 2 can just copy the moves of player 1 until all pieces are taken. Player 1 will not be able to move, and so will lose. Hence player 2 has a winning strategy.

Thus games are a proper mathematical object—namely, an Abelian group.^{(10)}

∗ ∗ ∗

A new notation links all this to surreal numbers. For any set of games G^{L} and G^{R}, there exists a game G = {G^{L}|G^{R}}. Intuitively, the Left player moves in any game in G^{L}, and likewise for Right in G^{R}. The zero game {∅|∅} = 0 is valid, and we may construct the surreals as before. Now we can write the surreals more easily with sets: {1, 2, … , n|} = n + 1.

To ‘play’ a surreal number {n|m}, a player chooses a game on their side, which the next player then plays. A player with no choice (∅) loses. If a player selects the zero game, the next player is the first to play it, and loses.

Consider a game {1|∅}. If Left moves first, they choose 1 = {0|∅} from G_{L}; Right loses. Right moving first is an instant lose. By extension, any game with positive surreal number is a win for Left. The converse holds for negative games {∅|n}. Hence we say: G > 0 if Left has a winning strategy, G < 0 if Right does. Order does not matter.

Yet, recall the class of games G = 0 where player 2 always wins: order matters, Left and Right do not. There is one more case: player 1 always wins. By elimination, such games are not positive, negative, or zero—so are not numbers. We say they are *fuzzy*: G ∥ 0. One such game is *star*, denoted ∗ = {0|0}: player 1 chooses the zero game, and thus wins.

The surreal numbers are a subset of games where no member of G^{L} has value greater or equal to any member of G^{R}. In games violating this rule, players eventually reach ∗. Thus there exist more games than numbers—infinitely more. Games such as 0, ∗, or {n|n} that are symmetric for both players are called *impartial*. We will turn to these first.

∗ ∗ ∗

Combinatorial games have two players who take turns. No information is hidden, ruling out poker. As for probabilities, no dice. A player who can’t move loses, and there are no draws (unlike chess). Last, the game ends.

The most famous impartial game is Nim, after the German *nimm*: to take.^{(11)} Given zero or more piles, a player takes one or more (or all) stones from one pile at each turn. When no stones remain, the next player cannot move, and loses. One-pile Nim is trivial: player 1 takes the whole pile to win. Yet, how to win for multiple piles {x, y, z,…} is not clear.

Consider the case of two piles with *n* stones, {n, n}. Player 2 can win by a Tweedledum & Tweedledee strategy of copying the moves of player 1. Similarly, Player 1 can win {n, m} by taking from *m* so that the piles are equal: {n, n}.

For more than two piles, we need a more general tool: the *nimbers*. Nimbers uniquely express each positive integer as a sum of powers of two multiplied by zero or one, e.g. 1 = 1×2^{0}, which we write as (1). Likewise, 2 = 1×2^{1} + 0×2^{0} = (10), 3 = 1×2^{1} + 1×2^{0} = (11), 4 = 1×2^{2} + 0×2^{1} + 0×2^{0} = (100)… Each nimber counts stones in a nim-pile.

We denote a *nim-sum* by the operator ⊕, a form of addition with the rule 1 + 1 = 0. This is called modulo arithmetic (mod 2), meaning: placed top to bottom, a column with an even number of 1’s is 0, one with an odd number is 1.^{(100)}

A nim-sum usually differs from the sum of the corresponding integers, unless the nimbers do not share any 1’s in the same position, e.g. (010) ⊕ (101) = (111) = 7 = 2 + 5; such cases without modulo addition are called disjunctive sums.

A nimber added to itself is zero. For two piles, the Tweedledum & Tweedledee strategy amounts to keeping the piles’ nim-sum at zero. In fact, this generalizes for *n* piles. To see why, note that the endpoint, a nim-heap without stones, has nim-sum 0. We call this a **P**-position, since the **P**revious player (the one who just moved to it) wins. Any position that can reach a **P**-position in one move is called an **N**-position, as the **N**ext player can move to the **P**-position.

Further, *any* position with nim-sum zero is a **P**-position, or ‘safe position’, since no player can move from a **P**-position to a **P**-position, but must move to an **N**-position. For two piles: given a **P**-position {n, n}, the next player can only make the piles unequal, i.e. nonzero nim-sum. For *n* piles, **P**-positions’ safety is guaranteed by nimbers’ uniqueness. Consider: if, out of three nimbers with nim-sum 0 we know two, we can always figure out the third: there’s only one it can be. So if *n* piles nim-sum to zero and a player only takes from one pile, the new nim-sum *must* be nonzero.^{(101)}

Since the endpoint is a **P**-position, the player who can first reach a **P**-position wins by each turn moving to a new **P**-position, up to the endpoint. If the initial *n* piles have nonzero nim-sum, player 1 wins; if zero, then player 2 wins.^{(110)}

∗ ∗ ∗

The **Sprague-Grundy theorem** states that any impartial game is equivalent to a nim-pile of appropriate size. The size is determined recursively by the SG-function, which we may write in two equivalent forms:

*g*(*x*) = min{*n *≥ 0 ∶ *n* ≠ *g*(*y*), ∀*y* ϵ *F*(*x*)} ⇔ *g*(*x*) = mex{*g*(*y*) ∶ *y* ϵ *F*(*x*)}

That is, from any *x* (except an endpoint) we can move to one or more points in the set of followers *F(x)*, each with its own SG-value *g(y)*; listing those *g(y)*’s in order, the SG-value for the point *x* is the smallest number, zero or greater, not in that list. To avoid spelling this out, we define **mex** (‘minimal excludant’) as the smallest non-negative integer not in the set. If *x* is an endpoint, *F(x)* = ∅, and so the mex is just 0. If another *x* can (only) reach the endpoint, now called *y*, in one move then *y* is in *F(x)*, and since *g(y)* = 0, the new mex is 1. And so on. Clearly, the SG-value is unique.

To see why the theorem works, consider a sum of games. Recall that any games where player 2 has a winning strategy are equivalent to the zero game, and can be removed. So each remaining game is a 1^{st} player win, like a single nim-pile. Next we must show that the aggregate SG-function behaves like the nimbers.

Let *b* be the sum of the SG-values, and (x_{1},…,x_{n}) the positions in each game. We’ll show that no follower of a position with aggregate SG-value *b* has the same value *b*. Imagine that both values **are** equal to *b*. For a move from position (x_{1},…,x_{n}) to (x_{1}′,…,x_{n}), their *g(x)*’s sum to: *g(x _{1})* ⊕ … ⊕

*g(x*=

_{n})*g(x*⊕ … ⊕

_{1}′)*g(x*=

_{n})*b*. Then subtract the other

*g(x)*’s from both sides to get g(x

_{1}) = g(x

_{1}′). But this is a contradiction, since mex by definition excludes g(x

_{1}′) to calculate g(x

_{1}).

^{(111)}

Like with nimbers, the SG-function can get from *b* to any point *a*, where *b* > *a* ≥ 0. Let *d* = *a* ⊕ *b*. Take powers of two and write *a*, *b*, *d* as nimbers. Consider the leftmost 1 in *d*. We know *b* has a 1 in that position and *a* has a 0. Since *b* is a sum of *g(x)*’s, at least one *g(x)* has a 1 in that position; let’s say it’s *g _{1}(x_{1})*. Then

*d*⊕

*g*<

_{1}(x_{1})*g*, so that there is a move from x

_{1}(x_{1})_{1}to x

_{1}′ with

*g*=

_{1}(x_{1}′)*d*⊕

*g*. Then we plug the latter equality into the new aggregate SG-function:

_{1}(x_{1})*g(x _{1}′) *⊕

*g(x*⊕ … ⊕

_{2})*g(x*=

_{n})*d*⊕

*g(x*⊕

_{1})*g(x*⊕ … ⊕

_{2})*g(x*=

_{n})*d*⊕

*b*=

*a*.

Sprague-Grundy theorem: impartial games are equivalent to nimbers. Next, any nimber can be written in surreal form.

Let’s first use surreal form to show ∗ + ∗ = 0. In the game ∗ + ∗ = {0|0} + {0|0}, player 1 chooses a 0 in ∗, so the full game is now 0 + {0|0} = {∅|∅} + {0|0}. But now player 2 can choose a 0 in ∗, so player 1 *must *choose ∅, losing.

Player 1 wins one-stone Nim, so its value is ∗. For two stones, player 1’s moves are {0, ∗|0, ∗} = ∗2. For three stones: {0, ∗, ∗2|0, ∗, ∗2} = ∗3. As *k*∗+*k*∗ = 0, so 2∗+3∗ = ∗. Typical nim-sums (⊕) apply, and any Nim game has value 0 or ∗.

Anatol Rapoport notes (1962: 110): “When a strategic game is completely analyzed by game-theory methods, nothing is left of the game.” We have borne this out by showing that all impartial games reduce to tuples of the void (∅).

∗ ∗ ∗

Historically, the surreal numbers were discovered after John Conway thought very hard about the game Go. He saw that certain endgame positions act like separate subgames, and can be given a value. Go is a partizan game: one player is white, one black. Partizan games have no analogue to the SG-function, but beget various bizarre pseudo-numbers.

In Toads & Frogs, toads only move right and frogs left. Each can move one space, or hop over the opposite species. Game T_TFF has outcomes {_TTFF|TFT_F}; in G^{L} no-one can move, in G^{R} player 1 wins, so {G^{L}|G^{R}} = {0|∗} ≡ ↑. Contrariwise, {∗|0} ≡ ↓, so that ↓ = −↑ → ↓ + ↑ = 0. Now let G = TT_FF = {T_TFF|TTF_F} = {↑|↓}. Take G + ∗, where ∗ = {0|0}. If Left first chooses 0 in ∗, Right moves frog in ↓ to win. If Left moves toad in ↑, Right chooses ∗ to win; symmetrically if Right goes first. Since player 2 wins, G + ∗ = 0, and since −∗ = ∗, therefore G = {↑|↓} = ∗ = {0|0}.^{(1000)}

We may generalize ↑ and ↓. Define *Tiny* as **☩**_{x} = {0|{0|−x}} with x ≥ 0; **☩**_{x} is positive. Its (negative) opposite is *Miny*, **⎶**_{x} = {{x|0}|0} for x ≥ 0. Setting x = 0 gives **☩**_{0} = {0|{0|**0**}} = {0|∗} = ↑ and **⎶**_{0} = {{**0**|0}|0} = {∗|0} = ↓. In *Domineering*, Left (Vera) puts dominos vertically on a grid, Right (Horace) does so horizontally. Games Vera wins have values >0, Horace’s are < 0. In a 2×4 game, Vera moving first makes a game where player 2 wins, i.e. 0. In Horace’s game, Vera going first makes a zero game, *or* Horace wins and leaves games valued −1 + −1 = −2. Thus:

Partizan games have a *temperature*. In a *hot game* players improve their position by moving. *Cold games* worsen players’ position each move. A player in a cold position who would prefer not to move at all (but must) is ‘in *zugzwang*’. Domineering is hot, numbers are cold. Cold games are expressible as surreal numbers, hot games as pseudo-numbers. In Go jargon, moves that increase a game’s temperature have *sente* (先手), moves decreasing it have *gote* (後手). Games can be cooled by *taxing* moves (e.g. G − *t*), and *thermographs* show how each move’s temperature alters as *t* increases.^{(1001)}

Now we may say: the theory of games is *combinatorial* in that it observes the void’s play with every combination of itself.

∗ ∗ ∗

The philosopher Alain Badiou claims that the surreals let us speak of ‘Number’ as a unified concept, and open the way to “thinking number as a unified figure of multiple-being” (2008: 107), but he disregards their roots in combinatorial game theory. Badiou’s main idea is that “mathematics is ontology” (ibid, 122). Games help show its implicit Platonism: it is considered bad form to include a term in its own definition, but this is just what occurs with the little word ‘is’.

Rather, combinatorial games support the idea that numbers do not strictly ‘exist’—mathematical fictionalism. They show also that games are primordial to numbers. However, games of the void with itself take the form of (and so presuppose) the concept of set supplemented with that of ordering, so as to form a tuple. The notion of difference is thus required as catalyst, perhaps with {∅|∅} as ‘difference-in-itself’. Difference is play, and games are its syntax.

As combinatorial games show, games need not *exist* to be played. More strictly, players never play a *game*, but play the play of the void. Games’ affinity to numbers explains why game theory is so often useful in science. Some ask what makes such models *games*. Answer: there is only one game, and mathematical models are instances of it.

Therefore: if mathematics is ontology, game theory is the science of the void.

Current research on combinatorial games aims to expand their standard definition, which still excludes many ordinary games, such as those with over two players. Moreover, while no bridge from combinatorial games to economic games has yet been made, research on cooperative and incomplete information combinatorial games shows promise.

The standard definition also leads to the *hypergame paradox* (Zwicker, 1987). In hypergame, player 1 chooses any game at all for player 2 to play. The problem is that players can keep choosing hypergame so that the game never terminates. So no formal system of games can include hypergame, which is counterintuitive. In practice, theorists define a class of non-terminating *loopy games* whose graphical representations have loops. These, in turn, open up to *transfinite games*.

∗ ∗ ∗

Applications of combinatorial games are few, but do exist. *Lexicodes* are a type of error-correcting code where “code words correspond to winning positions in certain impartial games,” so that if the underlying game is known, it can be solved to reveal the message (Milvang-Jensen, 2000: 91). Several well-known codes (e.g. Hamming codes) are cases of lexicodes. Games have also been used in computer science to describe types of data structures (Burke, 2015).^{(1010)}

By far the most interesting (potential) application is *surreal analysis*. Like real analysis, the aim is to provide foundations for calculus on surreal numbers. Many functions used in physics diverge to infinity, giving nonsensical answers to well-posed questions; hence mathematicians hope surreal analysis will let them rigorously work *with* these infinites. The main obstacle is that no one has yet been able to satisfactorily define integration (Matthews, 1995).

Perhaps someday all of these research programmes may converge to a new foundation for science—a glass bead game.

Nevertheless, the proposition “All the world’s a game” is not well-formed. We know that all combinatorial games can be reduced to tuples of the void, and like surreal numbers, they do not *exist*. If all the world is a game, then there is no ‘world’ to be a game. So even if everything is fully describable in game theoretic terms, the ‘is’ remains undefined.

Thus: Existence is itself played by an *arché-game* prior to difference and ontology. We call this the One-in-One.

*.*

**Notes:**

^{(1)}: Practically, we write the surreals as {L|R}, with L and R as sets of numbers. Surreal numbers obey the rule: no member of L is ≥ any member of R, i.e. ℓ ≱ r (∀ℓ ∈ L)(∀r ∈ R). For *x *= {X^{L}|X^{R}} and *y* = {Y^{L}|Y^{R}}, we say x ≤ y iff no *x ^{L}* in X

^{L}is ≥

*y*and no

*y*in Y

^{R}^{R}is ≤

*x*. Then x = y iff x ≥ y and x ≤ y. Define addition as x + y = {X

^{L}+ y, x + Y

^{L}| X

^{R}+ y, x + Y

^{R}}, e.g. ½ + ½ = {0|1} + {0|1} = {0 + ½, ½ + 0|1 + ½, 1 + ½} = {½|

^{3}⁄

_{2}} = 1. For the last equality, note: ½ ≱ 1 and

^{3}⁄

_{2}≰ ½ + ½, so {½|

^{3}⁄

_{2}} ≤ 1. Next, writing 1 = {0|}, note: 0 ≱ ½ + ½ and

^{3}⁄

_{2}≰ 1, so 1 ≤ {½|

^{3}⁄

_{2}}. Thus {½|

^{3}⁄

_{2}} = 1. For a step-by-step derivation from first principles, see Knuth’s quasi-novel

*Surreal Numbers*(1974) which coined their name.

^{(10)}: This is from Nowakowski (2009: 7-8). A *group* has a set and an operation combining two elements to get a third. For games, the operation is addition. Games count as a group since they have an identity element (G + 0 = G, so G is identical), have an inverse (−G), are closed (any G + H is a game), and are associative. Since games are commutative, they are Abelian.

^{(11)}: Nim was formalized by Bouton in 1902. The origin of its name is confirmed by Walsh (1953).

^{(100)}: As well as nim-sums, one can also do nim-multiplication; thus, in the terminology of group theory, the nimbers are a *field* (cf. Ferguson, 2014).

^{(101)}: Another way to think about uniqueness is that nimbers make a closed system: if a ⊕ b ⊕ c = 0 → a ⊕ b = c. This can be rearranged for any missing nimber in the system. Systems of *n* nimbers may be solved similarly.

^{(110)}: We’ve only covered normal play, where a player who can’t move loses. An alternate convention is *misère play*: a player who can’t move *wins*. In some simple misère games, such as Nim, misère and normal play are largely similar; yet, in the majority of cases misère games are far harder to solve. Notably, the SG-function does not always apply. Thanks goes to Thane Plambeck for confirming that any misère game is writable in surreal form, in keeping with the main argument of this paper.

^{(111)}: The two proofs are from Ferguson (2014), followed by Albert, Nowakowski & Wolfe’s (2007) notation for nimbers.

^{(1000)}: This example is from Demaine (2009). The next paragraph on **☩**_{x} and **⎶**_{x} is from Uiterwijk & Barton (2015: 5).

^{(1001)}: Another partizan game is Hex, invented by John Nash. It has a rhombus-shaped board with hexagonal spaces. Each player places a stone on some hexagon, and the goal is to form a diagonal line reaching from one end to the other: player 1 uses white stones to form an off-diagonal line (bottom-left to top-right), player 2 wants a black diagonal line. Curiously, draws are impossible in Hex: this is guaranteed by Brouwer’s fixed point theorem, the idea behind Nash equilibrium. Further, Nash showed player 1 has a winning strategy by a ‘strategy-stealing’ argument: if player 2 has an optimal strategy, player 1 can start with an arbitrary move, then copy all of player 2’s moves. So player 1 can ‘steal’ player 2’s optimal strategy, plus have the advantage of an extra stone on the board, and thus can win. Yet, this proof is non-constructive: we know an optimal strategy *exists*, but can’t find it. The proof for Nash equilibrium is similarly non-algorithmic.

^{(1010)}: A variant of Nim can even be used to derive Chebyshev’s inequality (Stolarsky, 1991). As well, algorithmic tools can be used to prove that certain combinatorial games are PSPACE-complete, EXPTIME-complete, or EXPSPACE-complete.

.

**References**

- Albert, M., Nowakowski, R., Wolfe, D. (2007).
*Lessons in Play: An Introduction to Combinatorial Game Theory*. Wellesley, MA: A.K. Peters - Badiou, A. (2008).
*Number & Numbers*. Malden, MA: Polity. - Bouton, C. (1902). “Nim, a game with a complete mathematical theory.”
*Annals of Mathematics*3(1/4), pp. 35-9 - Burke, K. (2015). “An abstract game for each data structure.”
*Journal of Computing Sciences in Colleges*30(6), pp. 60-1 - Demaine, E. (2009). “Surreal Numbers & Games.” Course notes for SP.268 (The Mathematics of Toys & Games) at MIT.
- Ferguson, T. (2014).
*Game Theory*, 2nd Ed. Unpublished textbook, ch. 1: Impartial Combinatorial Games - Knuth, D. (1974).
*Surreal Numbers*. Boston, MA: Addison-Wesley - Matthews, R. (1995). The man who played God with infinity.
*The New Scientist*147, p. 36-40 - Milvang-Jensen, B. (2000).
*Combinatorial Games, Theory & Applications*. Unpublished thesis, IT University of Copenhagen - Nowakowski, R. (2009). “The History of Combinatorial Game Theory.”
*Proceedings of the Board Game Studies Colloquium*XI. - Rapoport, A. (1962). “The Use & Misuse of Game Theory.”
*Scientific American*207(6), pp. 108-18 - Stolarsky, K. (1991). “From Wythoff’s Nim to Chebyshev’s Inequality.”
*American Mathematical Monthly*98(100), pp. 889-900 - Uiterwijk, J. & Barton, M. (2015). “New results for Domineering from combinatorial game theory endgame databases.” ArXiv preprint.
- Walsh, J. (1953). “The Name of the Game of Nim.”
*The Mathematical Gazette*37(322), p. 290 - Zwicker, W. (1987). “Playing Games with Games: The Hypergame Paradox.”
*American Mathematical Monthly*94(6), pp. 507-14

.

**TL;DR**

- Any number can be written as a tuple of games played by the void (∅) with itself.
- We can also treat games like numbers. In fact, numbers are a subclass of games.
- In Nim, players take stones from piles. To find a winning strategy, we invent
*nimbers*. - Sprague-Grundy theorem: any impartial (symmetric) game is equivalent to a nimber.
- Solutions for partizan (asymmetric) games use various other pseudo-numbers.
- Mathematicians want to use surreal numbers for new foundations of mathematics.
- Surreal numbers, nimbers, and pseudo-numbers can all be written as tuples of ∅.
- Therefore combinatorial games support the thesis that numbers do not truly ‘exist’.
- It is invalid to say “All the world’s a game,” since games are solely composed of ∅.

Posted on February 29, 2016, in Game Theory, Mathematics, Non-Philosophy, Philosophy and tagged Badiou, combinatorial game theory, combinatorial games, nim, nimbers, surreal numbers. Bookmark the permalink. 2 Comments.

Hi,

Just wanted to ask if you are familiar with Philip Mirowski’s work? He is an interesting historian and philosopher of economic thought.

You can easily find many of his papers on academia.edu and the book I would recommend as first would be

Machine Dreams: Economics Becomes a Cyborg Science.Great work with the blog, BTW, had only the chance to glimpse at it. Hope you are not planning to delete it by any chance :)

Regards,

Michał

Thanks Michal. I’ve been meaning to read

Machine Dreamsfor a while, but keep putting it off. I really liked Mirowski’s paper “Markets Come to Bits,” but overall he comes across to me as kind of a man-child — he ruins so many great ideas by framing them through a shallow heterodox lens. If you like his stuff, you should check out Velupillai’s papers, which are very profound (butincrediblypedantic). As for deleting, I have a bunch more essays in the works, so I don’t think it will happen anytime soon.