How to Be a Player: Impartial Combinatorial Games

Section 4.2 Lumberjack

In the game of Bamboo Stalks, we progressively chop down a bamboo forest. Bamboo Stalks is equivalent to multi-heap nim. What if we play this game in a more interesting forest?

The game of Lumberjack is a generalization of Bamboo Stalks. Once again, we have the ground, denoted by a dashed line. We then have a collection of trees (acyclic graphs) planted on the ground. The grounded vertex is special, and we call this vertex the root of the tree. Therefore, we are playing on a rooted forest, in which every tree has a root. A move consists of picking a tree and then hacking off one edge. We remove the edge, as well as the branch of the tree that is no longer connected to the ground (or equivalently: no longer connected to the root of the tree). Once again, the last person to move wins.

Figure 4.2.1 shows a game position of Lumberjack with three rooted trees. The root vertex of each tree lies on the dashed ground. Note that the middle tree in this position is more of a bush than a tree, since it does not have a single "trunk" leading up from its root. Clearly, this position of Lumberjack is just the sum of the games played on the individual trees of the forest. By Theorem 3.5.1, the Sprague-Grundy value of this game is just the nim sum of the Sprague Grundy values of the three trees:

The rightmost tree in this forest is a bamboo stalk, so it is equivalent to the nim heap \(*4\text{.}\) What about the other two trees? As always, we could find the Sprague-Grundy value the hard way: recursively find the values of all the followers and then take the mex of those values. You can imagine how tedious this process would be: the leftmost tree has seven followers and the middle tree has nine followers. In this section, we will describe the Tuft Principle which gives a much quicker way to calculate the Sprague-Grundy value of rooted trees. The Tuft Principle is, in fact, a variation of Theorem 3.5.1 about the sum of games.

Before we get to the Tuft Principle, let's look at a family of examples. We find the Sprague-Grundy values of the rooted trees \(T_1, T_2, \ldots, T_k, \ldots \) shown in Figure 4.2.2. We recognize that \(T_1\) is equivalent to the nim heap \(*2\text{,}\) so \(\g(T_1)=2\text{.}\) To calculate \(\g(T_2)\text{,}\) we observe that there are two distinct followers of \(T_2\text{:}\) a bamboo stalk of height 2 and an empty tree. These positions are equivalent to \(*2\) and \(*0\text{,}\) and therefore \(\)\g(T_2) = \mex \{ \g(*2) , g(*0) \} = \mex \{ 2, 0 \} = 1.\(\) So \(T_2\) is equivalent to the nim heap \(*1\text{,}\) which is the same as a bamboo stalk of height 1. If this is really the case, then the game \(T_2 \oplus * 1\) must be a \(\cP\)-position. Sure enough, Right has a winning response to each of Left's moves, as shown in the partial game tree of Figure 4.2.3

Now let's consider the position \(T_3\text{.}\) We have \(\cF(T_3) = \{ *0, T_2 \}\) and therefore

Continuing on, we have

and

From here, the pattern is clear (and can be proven by induction): for \(k \geq 1\text{,}\) we have \(\g(T_{2k-1})=2\) and \(\g(T_{2k})=1\text{.}\) In other words, pairs of leaves adjacent to the same vertex cancel one another out! This is very much like the nim sum (where 1+1=0), except this cancelation is happening in the tree tops. This phenomenon is a simple example of the Tuft Principle.

We delay the proof of the Tuft Principle until the next section. For now, we explain how the Tuft Principle allows us to find the Sprague-Grundy value of any Lumberjack position.

The Tuft Principle lets us replace a given tree with a slightly simpler tree. Before we prove the Tuft Principle, let's see it in action. We return to the example in Figure 4.2.1, where we can now determine the Sprague-Grundy values of \(G_1\) and \(G_2\text{.}\) First, we handle \(G_1\text{,}\) and our calculation is shown in Figure 4.2.5.

We start at the tree top and look for a join that only involves straight branches. We find one in the upper left part of the tree and replace these two branches of length 1 with one branch of length 0 because

In other words, these two branches cancel one another. This gives tree \(G_1'\text{,}\) which has the same value as \(G_1\text{.}\) Next, we use the Tuft Principle on the highest remaining join, and calculate \(g(*1) \oplus g(*2)= 1 \oplus 2 = 3\text{.}\) Therefore we replace these two branches with a single branch of length 3. This results in \(G_1''\text{,}\) and we use the tuft principle on the last remaining join. This gives

Finally, we have \({G'''}_1\text{,}\) which is a bamboo stalk of height 5. This means that

Similarly, we can use the Tuft Principle to show that \(\g(G_2) = 3\text{.}\) The calculation is shown in Figure 4.2.6. With these calculations complete, we can find the Sprague-Grundy value of the Lumberjack position in Figure 4.2.1:

So this Lumberjack position \(G_1 \oplus G_2 \oplus G_3\) is an \(\cN\)-position. There are actually four winning moves for this position: there is one winning move in \(G_1\) and there are three winning moves in \(G_2\text{.}\) We leave finding these winning moves as an exercise.

Let's consider the tree \(G_1\) from Figure 4.2.1 one more time. We now know that \(\g(G_1)=5\text{.}\) This means that the followers \(\cF(G_1)\) must contain trees with Sprague-Grundy values of \(0,1,2,3\) and \(4\text{,}\) but not \(5\text{.}\) In Figure 4.2.7, we confirm that this is the case. (You should use the Tuft Principle to confirm the calculations of the Sprague-Grundy value for each of the seven followers of \(G_1\text{.}\))

This example gives us confidence that the Tuft Principle does give the correct Sprague-Grundy values.