Games: Lumberjack

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. A Lumberjack position for a rooted forest with 3 rooted trees.

🔗

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:

g (G_{1} \oplus G_{2} \oplus G_{3}) = g (G_{1}) \oplus g (G_{2}) \oplus g (G_{3}) .

🔗

The rightmost tree in this forest is a bamboo stalk, so it is equivalent to the nim heap

* 4 .

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.

🔗

🔗
Figure 4.2.2. A family of rooted trees.

🔗

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}, \dots, T_{k}, \dots

shown in Figure 4.2.2. We recognize that

T_{1}

is equivalent to the nim heap

* 2,

g (T_{1}) = 2 .

To calculate

g (T_{2}),

we observe that there are two distinct followers of

T_{2} :

a bamboo stalk of height 2 and an empty tree. These positions are equivalent to

* 2

and

* 0,

and therefore

\g(T_2) = \mex \{ \g(*2) , g(*0) \} = \mex \{ 2, 0 \} = 1.

T_{2}

is equivalent to the nim heap

* 1,

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

P

-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

🔗

🔗
Figure 4.2.3. A partial game tree for the position $T_{2} \oplus * 1$ which shows that $T_{2} \oplus * 1$ is a $P$ -position.

🔗

Now let's consider the position

T_{3} .

We have

F (T_{3}) = {* 0, T_{2}}

and therefore

g (T_{3}) = mex {g (* 0), g (T_{2})} = mex {0, 1} = 2.

🔗

Continuing on, we have

g (T_{4}) = mex {g (* 0), g (T_{3})} = mex {0, 2} = 1

🔗

and

g (T_{5}) = mex {g (* 0), g (T_{4})} = mex {0, 1} = 2.

🔗

From here, the pattern is clear (and can be proven by induction): for

k \geq 1,

we have

g (T_{2 k - 1}) = 2

and

g (T_{2 k}) = 1 .

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.

🔗

Theorem 4.2.4. The Tuft Principle.

Consider a rooted tree in the game of Lumberjack. When $k$ paths $B_{1}, B_{2}, \dots, B_{k}$ come together at a single vertex, you can replace them with a single path of length $g (B_{1}) \oplus g (B_{2}) \oplus \dots g (B_{k}) .$

🔗

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} .

First, we handle

G_{1},

and our calculation is shown in Figure 4.2.5.

🔗

🔗
Figure 4.2.5. Using the Tuft Principle on $G_{1} .$

🔗

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

g (* 1) \oplus g (* 1) = 1 \oplus 1 = 0.

🔗

In other words, these two branches cancel one another. This gives tree

G_{1}^{'},

which has the same value as

G_{1} .

Next, we use the Tuft Principle on the highest remaining join, and calculate

g (* 1) \oplus g (* 2) = 1 \oplus 2 = 3 .

Therefore we replace these two branches with a single branch of length 3. This results in

G_{1}^{″},

and we use the tuft principle on the last remaining join. This gives

g (* 2) \oplus g (* 4) \oplus g (* 2) = 2 \oplus 4 \oplus 2 = 4.

🔗

Finally, we have

{G^{‴}}_{1},

which is a bamboo stalk of height 5. This means that

g (G_{1}) = g ({G_{1}}^{'}) = g ({G_{1}}^{″}) = g ({G_{1}}^{‴}) = 5.

🔗

🔗
Figure 4.2.6. Using the Tuft Principle on $G_{2} .$

🔗

Similarly, we can use the Tuft Principle to show that

g (G_{2}) = 3 .

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:

\begin{matrix} (4.2.1) & g (G_{1} \oplus G_{2} \oplus G_{3}) = g (G_{1}) \oplus g (G_{2}) \oplus g (G_{3}) = 5 \oplus 3 \oplus 4 = 2. \end{matrix}

🔗

So this Lumberjack position

G_{1} \oplus G_{2} \oplus G_{3}

is an

N

-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} .

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 .

This means that the followers

F (G_{1})

must contain trees with Sprague-Grundy values of

0, 1, 2, 3

and

4,

but not

5 .

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} .

)

🔗

🔗
Figure 4.2.7. The followers $F (G_{1})$ of the tree $G_{1}$ from Figure 4.2.1.

🔗

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