Feature Column from the AMS

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

3. Hackenbush

Another interesting example of a partizan game is called Hackenbush. The diagram below shows a game of Hackenbush. The way that the game works is that the two players are restricted to make a move that removes (hacks or cuts) an edge whose color is reserved for that player.

In our Hackenbush diagrams we have a green line (often called grass) out of which are growing various red and blue branches. When an edge is cut, that edge together with any edges of either color that are no longer connected to the grass will tumble down. In the diagram above, all the separate graphs growing in the grass are trees. However, this is not a requirement, as shown by the Hackenbush game below, where there are circuits in the graph structure:

We will follow the usual convention that names the two players Left (who cuts blue edges) and Right (who cuts red edges). Furthermore, we adopt the rule of standard (normal) play: if a player can not move, that player loses.

Consider the Hackenbush positions below:

For the game in (a), if Left moves first she can cut the blue edge, leaving Right no move. Right loses. If Right goes first, there being no red edge, he loses. This game is a win for Left. For the game in (b) if Left moves first, she loses since there is no move for her, there being no blue edges. If Right goes first he cuts the one red edge, leaving Left with no move. Left loses.

Now consider the game in (c). If Left moves first, she loses because she has no move. If Right moves first, he has the choice of cutting the top edge or the bottom edge, in which case the top edges tumble to the ground. But in either case, Right wins because Left has no move.

What if the game consisted of the positions in (a) and (c) combined? In this case if Left goes first, she has a move but Right can still win because whichever edge Right cuts will still leave Left with no move. If Right goes first and cuts the bottom edge, Left has a move and Right would have no response. However, if Right cuts the top red edge, Left has a move but Right has a response and wins.

Next consider play from the position consisting of (a) and (b). In this case if Left goes first, Right responds and Left loses, having no move. However, if Right goes first, left responds and Right loses because there is no move left. In other words, this game is won by Left if Left goes first and by Right if Right goes first. This symmetry suggests that it would be natural to assign a value of "0" to this game. In light of this it would also be reasonable to have the position (a) given the value +1 and (b) the value -1. (It is merely by convention that games where Left wins regardless of who moves first have positive value and those where Right wins regardless of who moves first have negative value.) It also seems natural to have the size of the value indicate how much "advantage" Left or Right has. If these values are really to behave like numbers, they should obey the properties of numbers. One can work out a framework in which all of this can be accomplished. To give some of the flavor of this, you can verify that the values of the positions from left to right above are +1, -1, -2, +3, while the value of the game below is 0.

As with impartial games each player would like to know at a given position whether or not he/she can win the game from the current position. If a win is possible, the player would like to know how to find a move that achieves a win. The player who knows by looking at a position that he/she can not win from this position would like to know how to play so as to take advantage of any future mistake in play that might occur.

The prior discussion gives a framework for showing positions of Hackenbush games associated with any integer. Are there Hackenbush positions that have a value which would be a rational number? To help us with trying to answer this question consider the collection of positions below:

For the position in (a), if Left goes first she has a move but Right can respond and win. If Right goes first, Right moves but Left can not respond, so Left loses. Thus, the value of this game is negative but this position does not seem as strong for Right as a single red edge. The position (b) by symmetry has a positive value the same size as the value for the (a) position. Can you determine if positions (c) and (d) have positive or negative value?

Suppose we have a game consisting of two copies of (a) and a single blue edge. What would be the result of play?

A Hackenbush position with a portion having value 1/2

If Left moves first and selects the single blue edge, Right moves and destroys a blue edge in the process. Thus, Left can respond but can not prevent a Right win. On the other hand, if Left moves by taking one of the top blue edges, Right can respond by cutting the red edge with a blue one on top of it. Left now must take the single blue edge, meaning that Right can still win by taking the remaining red edge! Thus, Right wins if Left goes first. It is easy to check that if Right goes first, then Left wins. Thus, this game should have zero value. Since a single blue edge is worth +1, this means, that each of the other games must have value -1/2. Hackenbush positions can have rational values.

Thus, the notion of the sum of games of a simpler kind can lead to a "calculus" for complex Hackenbush positions. Doing this in a sense generalizes what is done for impartial games where the two players do not have separate sets of pieces to play. However, we need to specifically address the value of a string of colored edges such as the one below:

A Hackenbush position to illustrate Berlekamp's rule

A very elegant and simple way to find the value of this Hackenbush position was found by Elwyn Berlekamp. The unexpected dividend, but a typical one that arises when one studies "pure" mathematics, is the possibility of putting ideas of this kind to work in the area of data compression.

Berlekamp's method associates a value to the path in the diagram above as follows. The sign of the answer depends on whether the edge attached to the green line is red or blue. If the attaching edge is blue, the value is positive and if the attaching edge is red, the value is negative. The value is an integer if the whole string is one color. Otherwise there is a place where the color changes from red to blue or blue to red. This pair of consecutive edges is interpreted as a "binary point" and the additional value of the edges beyond this pair is coded in binary, blue edges being assigned a 1 and red edges a 0. At the very end, one terminates this sequence by adding a 1. In the diagram above initially we have three red edges (value -3) leading to the "binary point." The remaining three edges blue, red, blue are replaced by .101 and a 1 is tacked on, giving .1011. This string interpreted in binary has value 1(1/2) + 0(1/4) + 1(1/8) + 1(1/16) = 11/16, so the value of this Hackenbush position would be -3 + 11/16 = -(2 + 5/16).

The method can also be used in reverse to find a string whose value is a given number. Thus, to represent 19/8 we can write this as 2 + 3/8. Writing the fraction in binary we get .011. To draw the Hackenbush string remember that the terminal 1 must be deleted. Since the value is positive and has integer part 2, we begin with 2 blue segments, and then the binary point is represented by an additional blue and red segment. After the terminal 1 of 011 is deleted we have 01, which means we get the diagram below:

A Hackenbush position to illustrate Berekamp's rule

In the games we have looked at previously we have insisted that features such as the number of edges or the number of stones in a pile be a finite number. However, when we permit an infinite number of stones or edges, we can encounter some fairly "exotic" numbers. Not all numbers associated with an infinite number of features will be exotic. In fact, some of these infinite colored "graphs" turn out to have very unexotic values. For example, the chain consisting of alternating blue and red edges in a path has the value 2/3. (Check that a blue-red path has value 1/2, blue-red-blue-red has value 5/8, blue-red-blue-red-blue-red has value 21/32, and continuing in this fashion one gets the sequence of fraction values, 85/128, 341/512, etc.).

So what about the exotic values? We can think of an infinite path of blue edges as having the value ω (see next section). Think of this as an infinite blue "beanstalk." Furthermore, it is possible to imagine a beanstalk with some additional edges at the top to climb. If there is one additional edge, this would have value ω + 1, and if two edges at the top, ω + 2. Using ideas in this spirit one creates all kinds of strange "beanstalks."

Hackenbush has many variants including ones where the edges above the ground are green and where green edges (not part of the base line) can be cut by either player. It turns out that allowing moves which involve blue, red, or green edges is essential for being able to understand the full ramifications of Conway's approach to numbers built around games.