Conway games were introduced by J. H. Conway in 1976 to provide a formal structure for analyzing games satisfying certain requirements:
1. There are two players, Left and Right ( and
),
who move alternately.
2. The first player unable to move loses.
3. Both players have complete information about the state of the game.
4. There is no element of chance.
For example, nim is a Conway game, but chess is not (due to the possibility of draws and stalemate). Note that Conway's "game of life" is (somewhat confusingly) not a Conway game.
A Conway game is either:
1. The zero game, denoted as 0 or , or
2. An object (an ordered pair) of the form , where
and
are sets of Conway games.
The elements of
and
are called the Left and Right options
respectively, and are the moves available to Left and Right. For example, in the
game
, if it is
's move, he may move to
or
,
whereas if it is
's
move, he has no options and loses immediately.
A game in which both players have the same moves in every position is called an impartial game. A game in which players have different options is a partisan game. A game with only finitely many positions is called a short game. A game in which it is possible to return to the starting position is called loopy.
Some simple games which occur frequently in the theory have abbreviated names:
1.
2.
3. for any positive integer
4.
5.
6.
A recursive construction procedure can be used to generate all short games. Steps in the procedure are called days, and the set of games first appearing (born) on
day is denoted
. The zeroth day is
. Subsequent days are
where
and
range over all elements of
.
Day 1 has four elements,
,
and the number of elements in
for
, 1, ... are 1, 4, 22, 1474, ... (OEIS A065401).
D. Hickerson and R. Li found
in 1974, but no other terms are known.
The following pairifaction table shows in terms of their left and right options:
0 | 1 | ||||
1 | |||||
0 | |||||
0 | 0 | ||||
0 | 0 | ||||
The set of all Conway games forms an Abelian group with the operations:
Here, expressions of the form mean the set of all expressions of the form
with
in
.
The set of all Conway games forms a partial order with respect to the comparison operations:
1. . If the second player to move in the
game
can win (
and
are equal).
2. . If the first player to move in the
game
can win (
and
are fuzzy).
3. . If Left can win the game
whether he plays first or not (
is greater than
).
4. . If Right can win the game
whether he plays first or not (
is less than
).
We have denoted
by
.
will mean either
or
, and similarly for
. For example, we have
,
, and
.
Each is a partial
order with respect to the relation
.
A basic theorem shows that all games may be put in a canonical form, which allows an easy test for equality. The canonical form depends on two types of simplification:
1. Removal of a dominated option: if and
, then
; and if
and
, then
.
2. Replacement of reversible moves: if , and
, then
.
is said to be in canonical form if it
has no dominated options or reversible moves. If
and
are both in canonical form, they both have the same sets of
left and right options and so are equal.