Special project: Nimbers

John Conway [C] discovered that there is a collection of objects derived from combinatorial games which forms a field, called here the field of nimbers. We shall construct the set of nimbers, giving some examples along the way, but we shall not prove that it is a field. First, what do we mean precisely by a ``game''? A two person game is a sequence of moves played alternately between two players following certain rules satisfying

• there are finitely many moves at each stage,
• there is a finite sequence of moves which yields a win for exactly one of the players and after each move the number of options for each player has strictly decreased,
• there are no chance or random moves,
• there is complete information about each move,
• each move depends only on the present position, not on the existence or non-existence of a certain previous move (such as chess, where castling is made illegal if the king has been moved previously),
• the player who has no legal moves when it is their turn loses.

Sometimes we slightly abuse language and identify a game with a position $P$ of that game (it being implicitly assumed that it is known whose turn it is to move). Likewise, we may identify any move with the board position which occurs after the move is made. We shall call the two players Left (or Laura) and Right (or Robert). We identify a game position $P$ with its collection of Left options (the legal moves Left can make if it were her move), denoted $P^L$, and Right options (the legal moves Right can make if it were his move), denoted $P^R$, and we write $P=\{P^L\ \vert\ P^R\}$. If the move options for a position $P$ is a disjoint union of move options for subpositions $P_1$, $P_2$, ..., $P_k$, then we say $P$ is the sum of the games $P_1$, ..., $P_k$ as we write

$$P=P_1+P_2+...+P_k.$$

Sums of games which are not necessarily disjoint are defined later.

Example 2.9.1   The game of Domineering. In this game, two players alternate by placing certain tiles on a certain board according to certain rules. The board, which may be regarded as the initial starting position of the game, is a subset of an $m\times n$ piece of graph paper. For example,

is a possible starting position. A tile is a $1\times 2$ subgrid or a $2\times 1$ subgrid of the board position. Left may place a $1\times 2$ tile (a horizonal domino) anywhere on the board provided it does not overlap any other square which has already been played on. Right may place a $2\times 1$ tile (a vertical domino) anywhere on the board provided it does not overlap any other square which has already been played on. The only possible move Right has (from the starting position) is to remove the 2 vertical tiles, resulting in

The only possible moves Left has (from the starting position) is to remove 2 horizonal tiles tiles, resulting in

The latter move is best if Left wants to win, since Right would be left with no legal moves and therefore would loses the game. Using the above notation, we may compactly describe this set up as