Towards the surreal

6. Towards the surreal

John Conway's remarkable insight was that games have natural values and that many of these values behave like ordinary numbers except that there are lots more of these numbers than are captured by the real number system! In fact, games have so many values that some games could not be assigned a number value even in the extended number system that Conway was creating. To help visualize and understand this new world Conway developed a collection of graph games called Hackenbush. Most of these games are not impartial games, but as a warm up for dealing with the more complex theory of partizan games let us look at a game Conway studied which I will refer to as Neutral Hackenbush.

Neutral Hackenbush

Rules:

Along a horizontal L a graph is drawn which has vertices which lie along the line L. While traditionally the word graph is used to mean a structure with finitely many vertices and edges, here we bend the definition to allow infinitely many vertices and edges. A Neutral Hackenbush board is shown below. For emphasis the horizontal line is shown in green, and the graph edges are shown in black. The way Neutral Hackenbush works is that if one cuts any edge in the graph, this edge is removed from the graph together with any portions of the graph which would become disconnected (come tumbling down!) by the edge being cut. For example, in the Neutral Hackenbush board shown below, the result of making the move of cutting edge ea would be that edges ef and eg would also fall to the ground. However, if the edge hk is hacked, then since the number of components of the graph is not increased, no other edges fall to the ground.

If you are wondering why this game is called Neutral Hackenbush, Hackenbush is a game where the edges attached to the horizontal line are in two colors, azure and black. When player A makes a move, only azure edges can be hacked while when player B makes a move only black edges can be hacked. This is a partizan game rather than an impartial game.

It is interesting to note that the theory of Neutral Hackenbush includes Nim within its structure. This is achieved by the following: for each pile of stones, with m stones, one attaches a path with m edges to the horizontal line. Cutting an edge in Neutral Hackenbush corresponds to removing a certain number of edges from a pile of stones. Remember that Neutral Hackenbush allows graphs attached to the green line which are infinite. Hence, we get something like Nim with infinite piles of stones. If you want to understand what to do about circuits in evaluating the value of Neutral Hackenbush positions as well as gain a wealth of additional fundamental insights into combinatorial games, information can be found in the idea-loaded book Winning Ways by Elwyn Berlekamp, John Conway, and Richard Guy.

For the Neutral Hackenbush game above it is not hard to show that each of these individual trees can be replaced by a path, so that any Neutral Hackenbush games which consist of sets of (finite) trees can be reduced to playing a game of Nim.

Here is a very brief discussion of how to see this. If one were restricted to make moves above vertex a, the three edges at a are as if there were three heaps to make moves from, each of which had one stone. So taking the nim sum of *1, *1, and *1 we would get *1. We can replace the three edges at a by a single edge and have an equivalent game. At c and f there are two edges and since *1 has nim-sum with *1 of *0, we can merely delete the two upward pointing edges at both c and f. At h, after deleting the two upward pointing edges at g, we have paths going up of lengths 1, 4, 3, and 1. The nim sum of these would be 7. Using an analysis of this kind, we can replace each tree by a single path. Thus, the trees shown are equivalent to having paths of different lengths instead. To find the value of the hackenbush position we have to compute the nim-sum of these different heap sizes.

In the continuation of this column I will treat partizan games and show how they are connected to the surreal numbers of John Conway.

1. Introduction
2. What is a combinatorial game?
3. Finding the winner of a game
4. Solving Nim
5. Towards a theory for combinatorial games
6. Towards the surreal
7. References