TOPICS
Search

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 (L and R), 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 {G^L|G^R}, where G^L and G^R are sets of Conway games.

The elements of G^L and G^R are called the Left and Right options respectively, and are the moves available to Left and Right. For example, in the game {{a,b}|{}}, if it is L's move, he may move to a or b, whereas if it is R'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. *={0|0}

2. 1={0|}

3. n={n-1|} for any positive integer n

4. 1/2={0|1}

5. ^={0|*}

6. v={*|0}

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 n is denoted G(n). The zeroth day is G(0)={0}. Subsequent days are G(n)= union {{L|R}} where L and R range over all elements of G(n-1). Day 1 has four elements, G(1)={0,*,1,-1}, and the number of elements in G(n) for n=0, 1, ... are 1, 4, 22, 1474, ... (OEIS A065401). D. Hickerson and R. Li found G(3) in 1974, but no other terms are known.

The following pairifaction table shows G(2) in terms of their left and right options:

*{*,0}-101
1{1|*}{1|{0,*}}{1|-1}{1|0}1*
0^v*{0|-1}*1/2
*0v{*|-1}v0
-10-1/2-1*-1/20
{*,0}^*2{{0,*}|-1}^*1/2

The set of all Conway games forms an Abelian group with the operations:

G+H={(G^L+H) union (G+H^L)|(G^R+H) union (G+H^R)}

-G={-G^R|-G^L}

Here, expressions of the form G^L+H mean the set of all expressions of the form g+H with g in G^L.

The set of all Conway games forms a partial order with respect to the comparison operations:

1. G=H. If the second player to move in the game G-H can win (G and H are equal).

2. G||H. If the first player to move in the game G-H can win (G and H are fuzzy).

3. G>H. If Left can win the game G-H whether he plays first or not (G is greater than H).

4. G<H. If Right can win the game G-H whether he plays first or not (G is less than H).

We have denoted G+(-H) by G-H. G>=H will mean either G=H or G>H, and similarly for <=. For example, we have 1>0, *=*, and *||0.

Each G(n) 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 G={{L_1,L_2,...}|G^R} and L_2>=L_1, then G={{L_2,...}|G^R}; and if G={G^L|{R_1,R_2,...}} and R_1>=R_2, then G={G^L|{R_2,...}}.

2. Replacement of reversible moves: if G={{{A^L|{A^(R_1),A^(R_2),...}},G^(L_2),...}|G^R}, and A^(R_1)<=G, then G={{{A^(R_1^L)},G^(L_2),...}|G^R}.

G is said to be in canonical form if it has no dominated options or reversible moves. If G and H are both in canonical form, they both have the same sets of left and right options and so are equal.


See also

Domineering, Game Theory, Hackenbush, Nim, Surreal Number

This entry contributed by Keith Briggs

Explore with Wolfram|Alpha

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 n." 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."

Referenced on Wolfram|Alpha

Conway Game

Cite this as:

Briggs, Keith. "Conway Game." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/ConwayGame.html

Subject classifications