Green Hackenbush

Green Hackenbush

Green Hackenbush is an impartial combinatorial game. It is played on any configuration of green line segments connected to one another by their endpoints and to a "ground" line. I will call these green line segments "edges." From any position, exactly the same moves are legal for each of the two players. Green Hackenbush was invented by mathematician John Horton Conway who was born in 1937 and is still alive today!

How to Play:

• Two players take turns cutting edges on a connected rooted graph or a collection of connected rooted graphs.
• When a player cuts an edge, it disappears along with any edges that are no longer connected to the ground
• The player who cuts the last edge wins.
• We will assume there are finitely many edges on the board

A simple kind of green Hackenbush is a picture of green snakes, which consists of a chain of green edges with just one edge touching the ground. The ground is represented as the dotted line. We can bend the topmost edge into a loop so our snakes have heads because loops are essentially just another edge. The figure below illustrates this setup. The elements made of only one segment are perhaps better called blades of grass (or baby snakes?).

                        

Berlekamp, Elwyn R., Conway, John H., and Guy, Richard K.. Winning Ways for Your Mathematical Plays. Natick, US: A K Peters/CRC Press, 2002. ProQuest ebrary. Web. 19 February 2017. (p. 41)

We can see that in this game, any move will affect just one snake and will replace that snake by a shorter one. To find the position of this game, we will assign each snake a nimber. Because each snake is a single string of edges, the nimber of a snake is the number of edges. To find the position of the game, we nim-sum the nimbers together. So in the case of this game, we have 5 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 6 ⊕ 4 = 7. Just like in Nim, because the value is not zero, we are in a N-position.

Here’s a question for the comments below: How is the game-play of Green Hackenbush consisting of snakes and grass equivalent to Nim?

Here is some strategy for Green Hackenbush with green snakes (can you see the connection to Nim?):

•  A single snake can be won by the first player every time by chopping the bottom edge of the snake.
• Two snakes of equal size have a nim-sum of zero
• A game of two unequal snakes can be won by the first player every time if the first player can equalize them by reducing the larger one
• In a three snake game, the player who first equalizes two of the snakes or eliminates a snake is the loser. In the first case, the opponent can remove the third snake. In the second, the opponeent can equalize the two non-empty snakes.

But what if someone who suffers from Ophidiophobia wants to play Green Hackenbush? Or someone who wants to start with a more complex picture? We can use the Colon Principle to find the position of a game consisting of trees.

Colon Principle: When several stalks meet at a vertex we may replace those stalks by a single stalk of the value equal to their sum.

By using the Colon Principle, we can find the position of a tree/shrub consisting of two edges emanating from point a:

1 ⊕ 1 = 0

We can see that the nim-sum of the number of edges on each branch is zero. So, we can replace the edges coming from a with no edges. As we know, a nim-sum of zero means the game is in a P-position. This may be obvious, but the previous player (player 1) will win because player 2 will erase one edge, player 1 will erase the remaining edge, and player 2 will be left with no moves and thus be the loser.

Another example:

 

3 ⊕ 2 = 1

Because the nim-sum of the branches emanating from b is 1, we can replace them with a single edge emanating from b to find the position of this game.

Using the ideas discussed above and the Colon Principle, we can find the position of a game of Green Hackenbush with a more complex tree by simplifying at points where “branches” diverge through several steps.

Berlekamp, Elwyn R., Conway, John H., and Guy, Richard K.. Winning Ways for Your Mathematical Plays. Natick, US: A K Peters/CRC Press, 2002. ProQuest ebrary. Web. 19 February 2017. (p. 191)

From using the colon principle above, we can eliminate the two branches emanating from a, and we can replace the branches emanating from b with 1 edge (see above examples). Because there is a 2 edge branch and a 1 edge branch coming from c, we can nim-sum them (2 ⊕ 1 = 3), and replace them with 3 segments. Then, we nim-sum the number of edges in each branch emanating from d: 2 ⊕ 2 ⊕ 4 = 4. So, we replace the branches emanating from d with 4 edges. Therefore, this tree has a value of 5 because we are left with 5 edges in a single line/branch. Because this value is not zero, we know we are in an N-position. This is obvious because the next player can simply chop the “trunk” of the tree (the edge touching the ground), leaving the rest of the tree detached, thus eliminating the rest of the edges and winning the game.

We’ve mastered snakes and trees, but what if we want to play a game of Green Hackenbush that has a drawing with cycles? We can analyze that using the Fusion Principle. 

The Fusion Principle states that you can fuse all the nodes in any cycle of a Green Hackenbush picture without changing its value. You fuse two nodes of a picture by bringing them together into a single one. Any edge joining them gets bent into a loop. A loop at any node has the same effect as an edge.

A small example:

In the above example, we first fused c and a. The edge joining them is bent into the purple loop. The edge between b and a still exists but since c was fused with a, the edge between b and c is now between b and a. We then fused b and a. The edges between b and a are now loops, and we are left with three loops at a. These loops can be represented as edges. By using the Colon Principle, we nim-sum the three segments together: 1 ⊕ 1 ⊕ 1 = 1. So the original picture with the cycle between a, b, and c is an N-position.

We will discuss the proof of the Fusion Principle in class.

Now we can find the position of a game of Green Hackenbush consisting of a picture of anything made of edges, including this:

Here is an example of fusing a girl:

Berlekamp, Elwyn R., Conway, John H., and Guy, Richard K.. Winning Ways for Your Mathematical Plays. Natick, US: A K Peters/CRC Press, 2002. ProQuest ebrary. Web. 19 February 2017.  (p. 192)

We fused all of the nodes in the cycles and made the loops into edges. Can you find the value of the resulting tree by using the Colon Principle? 

More things to think about: What if there is a cycle that includes the ground? We will discuss this in class but feel free to leave your ideas in the comments.

Conclusion

There is a straightforward way to find the position of any game of Green Hackenbush. However, once you find the value of the position, it may not be so easy to determine what move to make to put the game into a P-position. This game may also be made partial by assigning two colors to the edges. In addition, Green Hackenbush Theory can be applied to several other games, including "Impartial Maundy Cake." 

Sources:

Berlekamp, Elwyn R., Conway, John H., and Guy, Richard K.. Winning Ways for Your Mathematical Plays. Natick, US: A K Peters/CRC Press, 2002. ProQuest ebrary. Web. 20 February 2017.

Esselstein, Rachel. Winning Strategies for Green Hackenbush. 2017. Web. 20 February 2017. http://merganser.math.gvsu.edu/david/reed05/projects/esselstein/msri/Esselstein/

Wikipedia. Hackenbush. February 2017. Web. 19 February 2017.