Birthday

Birthday is a concept in Combinatorial Game Theory. Informally it is the number of levels required to construct a game beginning from the zero game; or, equivalently, the length of the longest sequence of moves possible (without requiring alternating play).

Table of contents Formal definition Example: the birthday of ↑ Games classified by their birthday Games with birthday 0 Games with birthday 1 Games with birthday 2 Games with infinite birthdays

Formal definition

More formally, for a game ``G={L_1, L_2, ... | R_1, R_2, ...}``, the birthday ``b(G)`` is defined inductively as ``b(G)={ b(L_1), b(L_2), ... b(R_1) b(R_2), ... | }`` This definition looks circular, but the apparent circularity ends when the game is reduced down to the zero game as in the worked example below. This is possible because the formal definition of an abstract game requires there to be no infinite sequence of options (though an infinite number of options is allowed).

A birthday is a “number” as defined at surreal numbers, and for finite games (as in go) the birthday will always be a non-negative integer; for more general numbers (¿and games?) the birthday is an ordinal.

Example: the birthday of ↑

As an example, we calculate the birthday of the game ↑ (also known as “UP”).

Recall that “↑” is shorthand for ``{0|ast}``, where “*” is shorthand for ``{0|0}`` and “``0``” is shorthand for ``{|}``, the canonical form of the zero game.

Therefore we have ``b("↑")={b(0), b("*") | }`` and we need to calculate ``b(0)`` and ``b("*")``.

Since ``0={|}``, we have ``b(0)={|}=0``.

Since ``ast={0|0}``, we have ``b("*")={b(0), b(0), | 0} = {0, 0|}``

Therefore ``b("↑")={ 0, {0, 0 |} | }``.

We can simplify this by deleting dominated options to reduce it to canonical form: ``{0, 0|}`` is equal to ``{0|}``, which is called ``1``, and then ``{0, 1|}`` is equal to ``{1|}``, which is called “``2``”.

Therefore we conclude that ``b("↑")=2``.

Games classified by their birthday

Working from the other direction, we can build up a list of games according to birthdays.

Games with birthday 0

Since we have no games to work with on day ``0``, the only game with birthday 0 has no options, i.e. ``0={|}`` is the only game with birthday ``0``.

Games with birthday 1

We make games with birthday ``1`` by using ``0``, and can use it as a left option, a right option or both.

This yields three games, namely

• ``{0|}``, called ``1``
• ``{|0}``, called ``-1``
• ``{0|0}``, called ``ast`` or STAR.

Games with birthday 2

We make games with birthday ``2`` by using games with birthday ``1`` or ``0``.

There are many games with birthday ``2``. We can start with:

``{|1}, {|-1}, {|ast}, {0|1}, {0|-1}, {0|ast}, {1|}, {1|0}, {1|1}, {1|-1}, {1|ast}, {-1|}, {-1|0}, {-1|1}, {-1|-1}, {-1|ast}, {ast|}, {ast|0}, {ast|1}, {ast|-1}," and "{ast|ast}``.

(Are these 21 games all different? or are any two of them equal? -- xela)

Then there are things like ``{1, 0 | 0}``, which is equal to ``{1|0}`` (we can delete a dominated option); and ``{0, ast | 1}``, which is equal to ``{0|1}`` because ``ast`` is a reversible option (is this correct? -- xela), and so on.

xela: I'm not sure if this last part is either correct or useful. I'm really just thinking out loud; feel free to correct or delete sections as appropriate.

Games with infinite birthdays

Games can have infinite birthdays, starting with ω, but in go we are normally only concerned with games with finite birthdays.

See On Numbers and Games for a full treatment, and in particular the tree of numbers on page 11 and the definition (for numbers) on page 30.