Games: Proof of the Tuft Principle

Section 4.3 Proof of the Tuft Principle

We now prove the Tuft Principle, Theorem 4.2.4. Our first step is to prove the following easy lemma. First, we define a \(k\)-tuft to be a tree whose only branching point is its root \(x\text{.}\) In other words, a \(k\)-tuft consists of \(k\) paths \(B_1, B_2, \ldots, B_k\) that all meet at vertex \(x\text{.}\) An example of a 4-tuft is shown in Figure 4.3.2.

Lemma 4.3.1.

Let \(G\) be a \(k\)-tuft rooted at vertex \(x\text{,}\) which is at ground level. Let \(B_1, B_2, \ldots, B_k\) be the paths that meet at vertex \(x\text{.}\) For \(1 \leq i \leq k\text{,}\) let \(m_i\) denote the number of edges in \(B_i\text{.}\) Then

\begin{equation*} \g(G) = \g(B_1) \oplus \g(B_2) \oplus \cdots \oplus \g(B_k) = m_1 \oplus m_2 \oplus \cdots \oplus m_k. \end{equation*}

Proof.

The idea of the proof is quite simple. We can think of the ground as one (very long) root vertex. Hacking a particular branch does not affect any of the other branches of \(G\text{.}\) So we can simply divide the tree at its root and create \(k\) independent bamboo stalks of sizes \(m_1, m_2, \ldots, m_k\) as shown in Figure 4.3.2.

Figure 4.3.2. Dividing a 4-tuft at its root \(x\) results in a forest of bamboo stalks. These two positions in Lumberjack are equivalent.

The Sprague-Grundy value of these independent bamboo stalks is just the nim sum of their individual Sprague-Grundy values by Theorem 3.5.1. Therefore

\begin{equation*} \g(G) = \g(B_1) \oplus \g(B_2) \oplus \cdots \oplus \g(B_k). \end{equation*}

The Sprague-Grundy value of a bamboo stalk is equal to its height (see Exercise 1 below), so this simplifies to

\begin{equation*} \g(G) = m_1 \oplus m_2 \oplus \cdots \oplus m_k. \end{equation*}

Lemma 4.3.1 is a special case of the Tuft Principle. It says that the Tuft Principle holds when the branching vertex is on the ground. We can now prove the Tuft Principle itself, which says that we can still take the nim sums of these branching paths when we are "up in the air." We introduce the following notation. Let \(G\) be a graph rooted at vertex \(x\text{,}\) and let \(y\) be another vertex of \(G\text{.}\) Let \(H\) be another rooted graph, with root \(z\text{.}\) We define the rooted graph

\begin{equation*} [G_y : H] \end{equation*}

to be the graph obtained by starting with the rooted graph \(G\) and then attaching the graph \(H\) to \(G\) so that the root \(z\) of \(H\) is identified with the vertex \(y\) of \(G\text{.}\) See Figure 4.3.3 for an example.

Figure 4.3.3. Joining the rooted trees \(G\) and \(H\) to obtain the graph \([G_y : H]\) We identify the vertex \(y\) in \(G\) with the root \(z\) of \(H\text{.}\)

We are now ready to prove the Tuft Principle, which we restate here for convenience:

If \(k\) paths \(B_1, B_2, \ldots, B_k\) come together at a vertex of the tree \(G\text{,}\) then we can replace this set of paths with a single path of length \(\g(B_1) \oplus \g(B_2) \oplus \cdots \oplus \g(B_k)\text{.}\)

In order to prove Theorem 4.2.4, we will rephrase it using our new notation. The Tuft Principle is equivalent to the following statement:

Let \(G\) be a tree rooted at \(x\) and let \(y\) be a leaf of \(G\text{.}\) Let \(T_1\) be a \(k\)-tuft with \(\g(T_2)=\ell\text{,}\) and let \(T_2\) be a bamboo stalk of height \(\ell\text{.}\) Then

\begin{equation*} \g([G_y:T_1]) = \g([G_y:T_2]) \end{equation*}

.

Let's interpret what this statement is saying (since there is a lot of notation). Returning to Figure 4.3.3, we see that

\begin{equation*} \g(H) = *1 \oplus *2 \oplus *3 = 0. \end{equation*}

Therefore, \(\g(H)\) is equivalent to \(*0\) (or equivalently, a bamboo stalk \(P_1\) of height 0). The Lemma tells us that

\begin{equation*} \g([G_y: H]) = \g([G_y: P_1]). \end{equation*}

Of course, the graph \([G_y:P_1]\) is the same as the graph \(G\text{,}\) so we conclude that \(\g([G_y: H]) = \g(G)\text{.}\) What does this mean? The addition of \(H\) to \(G\) does not change the outcome of the game: it merely adds some reversible moves. Indeed, if your opponent chooses to hack an edge in the \(H\)-part of the graph \([G_y:H]\) then you can always find a counter-hack in the remaining \(H\)-part to return the value of the game back to its value prior to your opponent's move.

We are now ready to prove the Tuft Principle!

Proof of Theorem 4.2.4.

A crucial ingredient to this proof is that we know how to calculate the Sprague-Grundy values for \(T_1\) (by Lemma 4.3.1) and \(T_2\) (because it is a bamboo stalk). The methodology of our proof is quite elegant: we make clever use of the Tweedledum-Tweedledee Principle! We will prove that the sum of games

\begin{equation*} [G_y : T_1] \oplus [G_y : T_2] \end{equation*}

is a \(\cP\)-position. This means that

\begin{equation*} 0 = \g \big( [G_y : T_1] \oplus [G_y : T_2] \big) = \g \big( [G_y : T_1] \big) \oplus \g \big( [G_y : T_2] \big). \end{equation*}

Of course, this last equation is equivalent to \(\g([G_y:T_1] )= \g([G_y:T_2]).\) So let's get started.

Figure 4.3.4. The Lumberjack position \([G_y:T_1] \oplus [G_y:T_2]\text{.}\) When \(\g(T_1) = \g(T_2)\text{,}\) this is a \(\cP\)-position.

Consider the Lumberjack position \([G_y:T_1] \oplus [G_y:T_2]\) with Left to move, as shown in Figure Figure 4.3.4. We show that this is a \(\cP\)-position by strong induction on \(m\text{,}\) t he maximum number of edges in the graphs \([G_y:T_1]\) and \([G_y:T_1]\text{.}\) We will show that for every possible Left move, Right has a countermove that puts the game into a \(\cP\)-position.

Our base case is \(m=0\text{,}\) where neither graph has any edges. Of course, this is a terminal position (hence a \(\cP\)-position). Futhermore, in this case, \([G_y:T_1] = [G_y:T_2]\text{,}\) so this is not very satisfying. So let's look and the next values of \(m\text{.}\) If \(m=1\text{,}\) then once again, the graphs are identical: they must each be bamboo stalks of height 1. This is obviously a \(\cP\)-position by Tweedledum-Tweedledee. At \(m=2\text{,}\) we finally have a non-trivial example: there are three possibilities for the position \([G_y:T_1] \oplus [G_y:T_2]\text{,}\) shown in Figure 4.3.5. Each of these positions is a \(\cP\)-position. Only the third example has \(T_1 \neq T_2\text{.}\)

Figure 4.3.5. The two possible structures for \([G_y:T_1] \oplus [G_y:T_2]\) when the larger of the two graphs has 2 edges. All three positions are \(\cP\)-positions.

Next, assume by induction that the lemma holds when there are fewer than \(m\) edges in each of \([G_y:T_1]\) and \([G_y:T_2]\text{.}\)

Consider a pair of trees \([G_y:T_1]\) and \([G_y:T_2]\) where at least one of these trees has \(m\) edges. We handle the case where Left hacks an edge in \([G_y:T_1]\text{.}\) There are two kinds of moves available to Left.

First, Left can hack off an edge in the \(G\)-part of \([G_y:T_1]\text{.}\) Right responds by hacking that same edge in the \(G\)-part of \([G_y:T_2]\text{.}\) If these moves disconnect vertex \(y\text{,}\) then the branches \(T_1\) and \(T_2\) fall off; we are left with two identical subtrees of \(G\text{.}\) This is a \(\cP\)-position by Tweedledum-Tweedledee. If these moves do not disconnect \(y\text{,}\) then we are left with graphs \([G'_y:T_1]\) and \([G'_y:T_2]\) and each graph has fewer than \(m\) edges. By induction, this is a \(\cP\)-position with Left's turn to play.

Second, Left can hack off an edge in the tuft \(T_1\) of \([G_y:T_1]\) to result in the graph \([G_y:T_1']\) where \(T_1'\) is a follower of \(T_1\text{.}\) There are two cases to consider, depending on whether \(\g(T_1') > \g(T_1)\) or \(\g(T_1') < \g(T_1)\text{.}\) (Why do we know that \(\g(T_1') \neq \g(T_1)\text{?}\))

If \(\g(T_1') > \g(T_1)\text{,}\) then Right will respond by also playing in the same component. Since \(\g(T_1') > \g(T_1)\text{,}\) we know that \(T_1'\) has a follower \(T_1"\) such that \(\g(T_1") = \g(T_1)\text{.}\) Right hacks the appropriate \(T_1"\) edge to get to \([G_y : T_1"]\text{.}\) This puts us in the game position \([G_y : T_1"] \oplus [G_y : T_2]\text{.}\) We have \(\g(T_1") = \g(T_1) = \g(T_2)\) and the total number of edges in this position is smaller than \(m\text{.}\) By induction, this is a \(\cP\)-position with Left's turn to play.
If \(\g(T_1') < \g(T_1)\) the Right will respond by hacking an edge in \(T_2\text{.}\) Indeed, \(T_2\) has a follower \(T_2'\) with \(\g(T_2') = \g(T_1')\text{,}\) so Right hacks the appropriate edge to create the position \([G_y : T_1'] \oplus [G_y : T_2']\text{.}\) This position satisfies the conditions of the Lemma, and has fewer than \(m\) edges. By induction this is a \(\cP\)-position with Left's turn to play.

We have now shown that Right can respond to any move of Left, putting the game into a \(\cP\)-position. Therefore the original position \([G_y:T_1] \oplus [G_y:T_2]\) is a \(\cP\)-position. This completes the proof of the Tuft Principle.

Finally we summarize why the Tuft Principle enables us to find the Sprague-Grundy value of any tree. Starting from the leaves of the tree, we work our way towards the root. Every time we encounter a vertex of degree 3 or larger, we have found a tuft. We apply the Tuft Principle to replace that tuft with a path of the appropriate length. This operation preserves the Sprague-Grundy value of the tree.

We continue this process until we are left with a rooted path (otherwise known as a bamboo stalk). The Sprague Grundy value of a bamboo stalk is equal to its height. Therefore, the height of the resulting path is the Sprague-Grundy value of the original tree.

Figure 4.3.6. Each tree is obtained from the previous one via the Tuft Principle. Each of the trees has Sprague-Grundy value of 4.

Figure 4.3.6 shows a complicated example. The original tree has 4 vertices of degree 3 or more, so it takes 4 applications of the Tuft Principle to find the Sprague-Grundy value.

So we've solved the game of Lumberjack, just as we solved the game of Nim. After calculating the Sprague-Grundy value, we know if we are in a winning \(\cN\)-position, or a losing \(\cP\)-position. When the Sprague-Grundy value is positive, then a winning move is to create a position with a Sprague-Grundy value of zero.