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.