How to Be a Player: Impartial Combinatorial Games

Section 4.4 Green Hackenbush

In this section, we take the game of Lumberjack to its full generalization: Green Hackenbush.¹ In this game, we allow any type of rooted multi-graph, not just trees. In other words, our picture now consists of rooted graph components that are allowed to have loops and multiple edges.

A move still consists of hacking away an edge in one of the rooted graphs. When the removal of an edge disconnects part of the graph from the ground, that part of the graph is removed from play. Figure 4.4.1 shows an example game position of Green Hackenbush with three components.

Just as in Lumberjack, we will find the Sprague-Grundy value of a complicated position (like that in Figure 4.4.1) by replacing it with a series of simpler Green Hackenbush positions. In fact, we can find a forest whose Sprague-Grundy value is identical to the original game. So we can solve Green Hackenbush by turning it into Lumberjack!

First, we deal with loops. Recall that a loop is an edge that connects a vertex to itself, a leaf is a vertex of degree 1, and a twig is an edge that is incident with a leaf. We can use the elementary Loop Principle to simplify our graph.

Next, we deal with cycles. Recall that a cycle is a sequence of successive edges such that (1) no edges repeat and (2) the only repeating vertices are the first and last vertices. In particular, a loop is actually a cycle of length 1. If there are two edges between vertices \(x\) and \(y\text{,}\) then they form a cycle of length 2. We can deal with cycles using the marvelous Fusion Principle. You fuse two vertices \(x,y\) together by joining them together into a single vertex. Each edge joining \(x\) and \(y\) is bent into a loop. (And a loop is equivalent to a twig by [cross-reference to target(s) "lemma:loop" missing or not unique].)

We delay the proof of the the Fusion Principle until the next section. For now, let's use it to determine the Sprague-Grundy value of the position in Figure 4.4.1. We deal with this position one component at a time. First, we prune the evergreen component into a bamboo shoot in Figure 4.4.4. This evergreen has a single cycle of length 4. We fuse all of these vertices together, creating a flower with 4 loops for petals. We then replace these loops with twigs by the Loop Principle. Finally, we use the Tuft Principle to find that \(\g(G_1)=2\text{.}\)

Next, we melt the snowman in Figure 4.4.5. This graph has multiple edges, and one loop. We apply the Fusion Principle twice and the Loop Principle five times to get a tuft with 5 twigs. Taking the nim sum of these branches, we find that \(\g(G_3)=1\text{.}\)

This brings us to the reindeer, which is obviously more complicated. The only new move of note is that we should immediately merge the two grounded hoofs since the ground (dashed line) is really one large vertex. Beyond that, we alternately apply the Tuft, Fusion, and Loop Principles. In Figure 4.4.6, we immediately replace loops with twigs when we apply the Fusion Principle. Our transformation of the reindeer requires patience, as we alternately fuse vertices and use the Tuft principle to simplify tree-like branches. Ultimately, we find that \(\g(G_2)=5\text{.}\)

Note that we perform this reindeer transformation very slowly: we show eight intermediate transformations. Likewise, you should be methodical so that you do not make any mistakes. Make incremental changes, and do not skip steps. It is okay to work on independent parts of the graph simultaneously. For example, we actually make 4 different changes to get from the reindeer to the next graph: we join the root vertices into one and also apply the Tuft Principle three times.

Finally, we can determine the Sprague-Grundy value of the game position \(G\) in Figure 4.4.1. We use the Sprague-Grundy Theorem to find that the position satisfies

Between the Fusion Principle, the Loop Principle and the Tuft Principle, we can determine the Sprague-Grundy value of any Green Hackenbush position. This often requires care and perseverance. As noted above, you should only apply one principle at a time (to a given part of the graph). Skipping steps is the easiest way to make mistakes. Take your time, and enjoy the metamorphosis from rooted graph to bamboo shoot.

There is a more important reason to take your time during this process: finding the winning move! Our wintery scene in Figure 4.4.1 has Sprague-Grundy value of 6. There must be at least one move to a position with Sprague-Grundy value 0. How do we find it? It turns out that the only winning move must occur in the reindeer component \(G_2\) (see the exercises for why).

We must change the Sprague-Grundy value of that component from 5 to 3 so that the nim sum of the components becomes \(2 \oplus 3 \oplus 1 = 0\text{.}\) Figure 4.4.6 shows nine equivalent positions. It is clear which edge we should hack in the ninth picture: removing the edge at height 4 gives the bamboo stalk \(*3\text{.}\) We can now rewind our process and figure out which edge in the original reindeer corresponds to the edge of height 4. Once again, we must be meticulous in this process. We do this in Figure 4.4.7, which tracks our desired edge through the reversed process. We find that there are actually five different edges that we can hack to achieve a Sprague-Grundy value of 3 for our reindeer.