Combinatorial Games (Part II): Different Moves for Left and Right

6. Surreal numbers and games

In his important book, On Numbers and Games, John Conway developed an approach to combinatorial games which pointed out their connection to numbers. This work shows that there is a natural way to associate numbers with "values" of games and that the collection of numbers one gets in this way is unexpectedly rich. Thus, there are numbers that behave as if they are "infinitely small" and "infinitely large." The situation is perhaps even more amazing in that games come in such amazingly varied forms that there are values of games that do not "correspond" to numbers. We have seen how one can do some of this in the specific context of the game of Hackenbush.

Here I will try to give some hint as to this wonderful connection between games and these very rich number systems. This will be done by using a more formal approach than the geometric approach involving Hackenbush. Conway introduces a notation which indicates the moves available to the two players Left and Right in a manner very similar to the notation we used above that makes the transition between the ordinal numbers and the surreal numbers. Games will be defined in terms of the opportunities that the players Left and Right have in making moves in other games. The notation G₁ ={ X, Y, Z, ... | U, V, W, .... } denotes a game in which Left must make a move by selecting one of the games X, Y, or Z to play, while Right must make a move by selecting one of the games U, V, or W. If, for example, Left moves to Y, then we have a new game G₂ = { X₁, X₂, X₃, ... | U₁, U₂, U₃, ... }, where now Right must make a move into one of the games to the right of the vertical bar. In this spirit consider the simplest of all games: { | }. Since there are no moves to either the left or right of the bar, whoever must make the first move will have no move to make and thus will lose in standard play. In terms of being able to assign a value to this game, neither player has any "free move(s)." By contrast, in the game { 0 | }, Left has a move if he/she goes first, while Right has no move. Thus, Left has one "free move" and it seems reasonable to assign this game the value +1. In the game { | 0 }, Right has one "free move" and we assign this game the value -1. In this framework, the symmetrical game { | } is a second player win and has value 0. (Note, 0 has many representations. Think of different Hackenbush positions with value 0.) Now the game { 0 | 0 } is symmetrical but neither Left nor Right has a built-in advantage. Whoever goes first in this game wins. Conway developed a natural way to develop a "calculus" of games using this notation.

It turns out that we can think of all partizan games as falling into one of four types:

Positive games, which are those where the player named Left always wins.

Negative games, which are those where the player named Right always wins.

Zero games, which are those where the player who plays second always wins.

Fuzzy games, which are those where the player who plays first can always win.

Examples of the first three types can be illustrated using blue and red edge Hackenbush but the last type, fuzzy games, requires that one have edges that are green, blue, and red. Left cuts blue edges, Right cuts red edges and either player can cut the green edges (but not the grass).

To see the issue with fuzzy games consider the following position of green, red, and blue Hackenbush:
 

Figure 1
 

Again green edges (other than the grass) can be cut by either player. This means that for the game above the first player who moves can win. One might be tempted to think this would mean that neither Left nor Right has an advantage in this game, but the issue is more subtle. Notice that this game has more blue edges than red edges. Does this not suggest that Left has "some advantage" over Right? To see that this is indeed true, consider the game shown below:

 

 

If Right cuts a green edge, then Left wins by cutting the other green edge. However, if Right cuts red edges, because there are more blue edges, Left can stall using a green edge until Right has used up all the red edges available. Thus, with optimal play, Left wins! The critical point is that regardless of who starts this game, Left will win with optimal play. If the game in Figure 1 were "worth" 0, then two copies of it should also be worth 0, but as we have just seen, this is not true (two copies of the game in Figure 1 have positive value). This is why the game in Figure 1 is called fuzzy. It's a game where a "number value" that behaves the way a respectable number should is not  possible! Fuzzy games can not be said to be positive, negative, or zero. Our earlier example, { 0 | 0 }, is the simplest example of a fuzzy game. This game is commonly denoted *, and it does not correspond to a number. Conway uses the term "nimber" for discussing * and related games. In particular, nimbers come into play in the analysis of impartial games (even when there are finitely many piles of stones, each with a finite number of stones), where we saw that some piles of stones were forced wins for the first player and some were forced wins for the second player. As "numerous" as the surreal numbers are, games are so "varied" that one can not use surreal numbers to capture all the issues involved.

It is tempting to try to focus money, research, and energy in directions where it will do the "most good." Unfortunately, "directed" efforts often follow known paths and, hence, do not find the unexpected. Some would view the theory of games as a "recreational topic." Yet the exciting ideas that it has led to broaden the tools mathematicians can bring to bear on all the problems they address. Tomorrow's mathematics for applications is often today's mathematics for the fun of it.

1. Introduction
2. Hex
3. Hackenbush
4. Counting and sets
5. Surreal numbers
6. Surreal numbers and games
7. References