Mark D. Niemiec's Page on Numbers and Games

Introduction | Rules | Nomenclature | Numbers | Games | Nimbers | Small Games | Halves | Loopy Games | Calculator | Bibliography | Links



Introduction

This page is about John Horton Conway's Numbers and Games. These define a kind of objects called Games, that represents positions in a two-person zero-sum game of complete information. A specific subset of games, that Conway initially just called Numbers, but which Donald Knuth called Surreal Numbers, form a complete field that behave just like real numbers, but is much larger, including transfinite numbers and their inverses (infinitesimals). Furthermore, this is the largest field it is possible to create using Cantor's set theory.


Rules

Numbers and Games are defined by the following basic rules:

Or, symbolically:

All of these rules are defined recursively, with each number or game being defined in terms of sets of simpler, previously-defined numbers or games. If one thinks of numbers and games being created on successive days from sets of numbers or games created on previous days, one can assign a day number to each number or game that specifies the earliest day on which that number or game appears. This number is always a non-negative ordinal number. Where convenient, it will be shown here in [square brackets]. The very first number, created on day 0, must have empty sets on both sides, since there have been no other numbers created before it. It is 0 ⇔ { | } [0].


Nomenclature

Since the surreal numbers contain many more values than reals, and games even more, the notation used to describe them is more complicated than that used to describe real numbers. The following conventions are used:


Numbers

The simplest kind of numbers are called Ordinal numbers. Non-negative ordinals have empty right sets (and correspond to Georg Cantor's ordinal numbers), while their negatives have empty left sets. Of course, the first possible number 0 ⇔ { | } is both. Ordinal numbers contain integers, but they also contain transfinite numbers like ω, ω+1, 2ω, ω², ωω, etc.

Integers are constructed recursively, e.g. 1 ⇔ { 0 | }, 2 ⇔ { 1 | }, etc. Their negatives are similar, e.g. ¯1 ⇔ { | 0 }, ¯2 ⇔ { | ¯1 }, etc. The names assigned to such arbitrary numbers are the same as the corresponding reals, and can be verified algebraically; e.g. for all numbers x, 0+x=x, 0·x=0, 1·x=x, ¯1·x=-x, 2·x=x+x, etc.

Binary rationals, i.e. all fractions whose denominators are powers of 2, can similarly be constructed recursively, e.g. (2x+1)/2y ⇔ { (2x)/2y | (2x+2)/2y } ⇔ { x/2y-1 | (x+1)/2y-1 }, where y>0.

For example, ½ ⇔ { 0 | 1 }, ¼ ⇔ { 0 | ½ }, ¾ ⇔ { ½ | 1 }, etc.

NOTE: While it is always true that a number's value lies somewhere between the values in its left and right sets, it is not necessarily the average. Rather, it is the simplest (i.e. earliest constructed) number that fits. While this may not seem intuitive, it can be verified by using algebraic methods. For example, to verify that x = { 2¼ | 3 } has a value of 2½ it suffices to show x+x-5 = 0.

Another thing that is easily verifiable is that only the innermost values in the two sets are important (i.e. the largest value in the left set, and the smallest value in the right set). Symbolically, { a, b | c, d } = { b | c }, when ab and cd. In this case, left option a is dominated by b, so it is irrelevant. Similarly, d is dominated by c. (This principle is best illustrated by looking at games; for example, if someone offers you a choice of a $100 dollar bill, a $10 dollar bill, or a $1 dollar bill, the $100 bill dominates the others; since there is no situation in which one would prefer them, their inclusion in the list of choices is totally superfluous.)

Things begin to get much more interesting if one uses infinite sets, that have no specific greatest or least members. For example:

The transfinite ordinal ω is an ordinal larger than than any real number. It may be thought of as the simplest number that cannot be reached by counting. Ordinals like ω+1, 2ω ω², ωω etc. are even larger. These are all ordinary numbers, and can be used in any context that other numbers can be. This is unlike the infinity ∞ used in real analysis, that is not, in fact, a number, and has many ugly properties, e.g. ∞+1=∞, ∞/2=∞, ∞-∞=indeterminate, etc. This also yields many related transfinite non-ordinals, like ω-1, ω/2, √ω, etc.

The number ε = 1/ω deserves special mention. It is an infinitesimal that is greater than zero, but smaller than any positive real.

(NOTE: For ease of notation, all fractional expansions in the following sections will be in base two, rather than the more customary base ten.)

All remaining rationals, and indeed, all remaining reals, can be represented by Dedekind cuts, by expressing the number as an infinite binary fraction, and including successive approximations (rounded down) in the left set, and successive approximations (rounded up) in the right set. These are all created on day ω. For example:

Exponentiation to any numeric power can be defined in similar ways. For example:

Just as real numbers have their limiting value ∞ that is not actually a real number, surreal numbers also have a similar limiting value, on ⇔ { on | }, that is not actually a number (nor even a normal game), because its definition is recursive. (It is actually a loopy game.) It is mostly used as a limit; e.g. all numbers are less than on, all positive infinitesimals are greater than 1/on, all positive reals are less than ω1/on, and all positive transfinite numbers are greater than ω1/on.


Games

Games are a superset of Numbers, formed by removing the constraint that no left option may be greater or equal to any right option. This means that we can no longer rely on the fact that a game's value lies between its options. Also unfortunately, games do not form a field, so many of the operations like multiplication, division, and square root no longer apply in general.

A Game is analogous to a position in a two-player zero-sum game of complete information, without infinite play, and in which the first player unable to move loses. This includes games like Nim. It does not directly include games that permit infinite play (like Checkers), or that permit draws (like Chess), or that keep score (like Go), although such games can used if their rules are altered slightly (for example, in Chess by forbidding moves that would draw by repetition or by long sequence of moves, and by considering stalemate a loss, and similarly forbidding infinite play in Checkers).

The Left player's list of options (i.e. left options) is the set of games, each of which is a position Left can reach by making a legal move, and the Right player's list of options is defined similarly. Such a game x can have one of four kinds of values:

The numeric values of games are interesting, because many complicated games have moves that split the gaming area into smaller disjoint pieces where either player may make a move in any one piece. This is equivalent to the sum of multiple games, and it often becomes possible to analyze complicated games by analyzing the sums of their parts.

A move in a game reduces it to a simpler game. Each player thus has an incentive to play in a particular game that is the difference between the value of that game after the move, and before it. Symbolically, for game x, Left's incentives are xL-x and Right's incentives are x-xR. Note that for Numbers, these incentives are always negative; i.e. no player will willingly move in a game equivalent to number unless absolutely necessary, and if it is necessary, will prefer to move in numbers with the smallest possible incentives (e.g. infinitesimals before fractions before integers before transfinites) to minimize the disincentives. Such games are also called cold games.

Fuzzy games are also called hot games, because their incentives are non-negative, and players will wish to claim as many incentives as possible. As a result, players will always want to play in hot games if possible, with the hottest game (i.e. one with the largest incentive) first.

The simplest fuzzy game is Star, * ⇔ { 0 | 0 } [1]. This is less than any positive number, greater than any negative number, but not equal to zero.


Nimbers

A special sub-category of games, called impartial games occurs when both players have the same options, that are themselves impartial games. Nim is the simplest classic example of such a game: one starts with several piles of items (coins, matchsticks, etc.) and each move consists of removing one or more items from a non-empty pile. Because of this, the game positions in Nim are called nimbers. They have a one-to-one correspondence with non-negative ordinal numbers. (Because the options are the same on both sides, and are always nimbers, a simplified notation will be used here, showing only one set of options, with the * symbol omitted from the option sets). Nimbers are formed as follows:

Because both option sets are the same, the arithmetic rules for nimbers are a simplified version of those used for numbers:

From the equality rule (=), it follows that the value of the result is the same as the minimum excluded option (mex). For this reason, nimbers must include all options to force the next higher one, unlike ordinal numbers that only need to include the highest option (e.g. 3 = {2 | }, but *3 = {0 1 2} ).

The addition rules for nimbers *x + *y are somewhat unusual. Each nimber must be separated into distinct powers of two (e.g. *6 ⇔ *2 + *4). These are then added according to the following rules:

This is equivalent to base-2 addition without carry, or the xor operation implemented on most computers. This also means that every nimber is its own negative.

The multiplication rules for nimbers *x · *y are even more unusual. Each nimber must be separated into distinct powers of two, which must in turn be separated into products of distinct Fermat powers of two (i.e. 21, 22, 24, etc.), so, for example, *9 ⇔ *8 + *1 ⇔ *4·*2 + *1). These are then multiplied according to the following rules, applying usual algebraic rules for distributing multiplication over addition:

Nimbers form a field, so from the above rules, it is also possible to derive rules for division, powers, roots, etc. These rules are consistent, but have highly unusual properties. For example:


Small Games

The game Up, ⇔ { 0 | * }, is strictly positive, yet smaller than the smallest infinitesimal number. It if fuzzy with respect to *, but strictly less than any other game that is greater than *. Even the most infinitely large multiple of ↑ is smaller than the smallest infinitesimal numbers. This is why all multiples of ↑ are called small games. Small positive integer multiples of ↑ are usually signified by multiple arrows, e.g. ⇑, ⤊, ⟰, etc. while negative multiples (i.e. multiples of Down) use down-arrows, e.g. ↓, ⇓, ⤋, ⟱, etc.

Up is actually just the largest of a group of games called Tinies, ⧾x ⇔ { 0 | { 0 | -x } }, defined for all non-negative numbers x. If x > y, even the largest multiples of ⧾x is smaller than the most infinitesimal positive multiple of ⧾y. The smallest possible positive game is ⧾on. Negatives of tinies are called Minies, ⧿x ⇔ -⧾x.


Halves of Games

Calculating half of a number is quite easy. Some examples are given in previous sections. However, calculating half of a game, especially a hot game, is not as simple. In particular, half of nimber x is not a nimber at all, because if it were, adding it to itself would yield 0, and not x.

One of the exercises in On Numbers and Games is to find the game Semi-star, i.e. */2. The solution to this problem leads to many interesting sub-problems.

It should be noted that in any hot game c ⇔ { a | b }, where ab, c+ca+b because if Left moves to a in one of the copies of c, Right will counter-move to b in the other copy, and/or vice versa. Thus, it's trivially easy to create games that are halves of other games by sufficiently inflating their options. For example, if c ⇔ { a | -a* }, then c+c ⇔ *. In particular, c ⇔ { 1 | ¯1* } works. c+c ⇔ *. However, this is not the simplest game with this property.

(In fact, if any game c has this property, so does -c, since -c+-c ⇔ -* which is just *. Thus, the partial game */2 has a similar ambivalent relationship to impartial games (nimbers) and addition that imaginary number i has to real numbers and multiplication.)

The simplest game with this property is { *,↑ | 0,↓* }. This fulfills the requirement that every member of the left set ⧐ some member of the right set, and every member of the right set ⧏ some member of the left set. Note that game */2 is distinct from nimber */*2, which is equal to *3.

It is possible to construct similar half-values for any non-zero nimber: (*n)/2 ⇔ { *n, {0 | *n} | 0, ↓* }.


Loopy Games

Games that violate the non-recursion requirement (i.e. their sets contain games that were not created earlier, and can lead to infinitely-repeating sequences of moves), are called loopy games, and require special treatment. For example, even the basic rules for comparison and addition must be altered to handle them - usually by considering two sets of non-loopy games, in which infinite play is considered a win for Left, or for Right.

The three simplest loopy games are on ⇔ { on | }, the limit of Ordinal Numbers and the largest game, off ⇔ -on ⇔ { | off }, the smallest game, and dud ⇔ { dud | dud }, the Dynamic Universal Draw, that is fuzzy with respect to all games. These may be viewed as super-magnified versions of 1, ¯1, and *. All loopy days are created on day on.

The theory for loopy games can get very complicated, and is too involved to explain here. A good explanation of them is found in Winning Ways.



Calculator

I have written a simple desk calculator program that allows one to explore a little bit about Numbers and Games. Details are on a separate page.


Bibliography


Links to other Numbers and Games-related Web pages



Home page

Copyright © 1997, 1998, 1999, 2013, 2014 by Mark. D. Niemiec. All rights reserved.
This page was last updated on 2015-02-19.