Conway Game

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.

REFERENCES:

Berlekamp, E. R.; Conway, J. H.; and Guy, R. K. Winning Ways for Your Mathematical Plays. Wellesley, MA: A K Peters, 2004.

Calistrate, D.; Paulhus, M; and Wolfe, D. "On the Lattice Structure of Finite Games." In More Games of No Chance (Ed. R. J. Nowakowski). Cambridge, England: Cambridge University Press, pp. 25-30, 2002.

Conway, J. H. On Numbers and Games. Wellesley, MA: A K Peters, 2000.

Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 283-284, 1996.

Fraser, W.; Hirshberg, S.; and Wolfe, D. "The Structure of the Distributive Lattice of Games Born by Day ." http://homepages.gac.edu/~wolfe/papers/dayn/structure.pdf.

Gonshor, H. An Introduction to Surreal Numbers. Cambridge, England: Cambridge University Press, 1986.

Knuth, D. Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness. Reading, MA: Addison-Wesley, 1974. http://www-cs-faculty.stanford.edu/~knuth/sn.html.

Schleicher, D. and Stoll, M. "An Introduction to Conway's Numbers and Games." http://arxiv.org/abs/math.CO/0410026.

Siegel, A. N. "Loopy Games and Computation." Ph.D. thesis. Berkeley, CA: University of California Berkeley, 2005.

Sloane, N. J. A. Sequence A065401 in "The On-Line Encyclopedia of Integer Sequences."