Combinatorial Game Theory: Surreal Numbers and the Void

Chess, by Andrew Phillips (small)

[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 2nd 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 1st 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.

tweedledum and tweedledee

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 GL and GR, there exists a game G = {GL|GR}. Intuitively, the Left player moves in any game in GL, and likewise for Right in GR. 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 GL; 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 GL has value greater or equal to any member of GR. 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.

surreal chess set (bishop, queen, knight), by Johan Andersson

Fractal chess pieces, by Johan Andersson: bishop, queen, knight

∗                                   ∗                                   ∗

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×20, which we write as (1). Likewise, 2 = 1×21 + 0×20 = (10), 3 = 1×21 + 1×20 = (11), 4 = 1×22 + 0×21 + 0×20 = (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 Previous 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 Next 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{≥ 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 1st 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 (x1,…,xn) 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 (x1,…,xn) to (x1′,…,xn), their g(x)’s sum to: g(x1) ⊕ … ⊕ g(xn) = g(x1′) ⊕ … ⊕ g(xn) = b. Then subtract the other g(x)’s from both sides to get g(x1) = g(x1′). But this is a contradiction, since mex by definition excludes g(x1′) to calculate g(x1).(111)

Like with nimbers, the SG-function can get from b to any point a, where b > a ≥ 0. Let d = ab. 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 g1(x1). Then dg1(x1) < g1(x1), so that there is a move from x1 to x1′ with g1(x1′) = dg1(x1). Then we plug the latter equality into the new aggregate SG-function:

g(x1′) g(x2) ⊕ … ⊕ g(xn) = dg(x1) g(x2) ⊕ … ⊕ g(xn) = db = 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 (∅).

The Royal Game of Ur (2600 BC); see here for more on ancient games.

The Royal Game of Ur (2600 BC); see here for more on ancient games.

∗                                   ∗                                   ∗

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 GL no-one can move, in GR player 1 wins, so {GL|GR} = {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:

from Uiterwijka & Barton (2015: 5)

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 = {XL|XR} and y = {YL|YR}, we say x ≤ y iff no xL in XL is ≥ y and no yR in YR is ≤ x. Then x = y iff x ≥ y and x ≤ y. Define addition as x + y = {XL + y, x + YL | XR + y, x + YR}, e.g. ½ + ½ = {0|1} + {0|1} = {0 + ½, ½ + 0|1 + ½, 1 + ½} = {½|32} = 1. For the last equality, note: ½ ≱ 1 and 32 ≰ ½ + ½, so {½|32} ≤ 1. Next, writing 1 = {0|}, note: 0 ≱ ½ + ½ and 32 ≰ 1, so 1 ≤ {½|32}. Thus {½|32} = 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 ∅.
Advertisements

About Graham Joncas

We are a way for capital to know itself.

Posted on February 29, 2016, in Game Theory, Mathematics, Non-Philosophy, Philosophy and tagged , , , , , . Bookmark the permalink. 2 Comments.

  1. 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 Dreams for 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 (but incredibly pedantic). As for deleting, I have a bunch more essays in the works, so I don’t think it will happen anytime soon.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: