Problem: Find the Sprague-Grundy values of the graphs, and find a winning move, if any.
Solution: The SG value of the three-leaf clover is 2. The SG value of the girl is 3. The SG value of the dog is 2. And the SG value of the tree is 5. So there exists a winning move on the tree that reduces the SG value to 3. The unique winning move is to hack the left branch of the rightmost branch completely away.
I can play this game using the colon principle and fusion principle to reduce the graphs to the correct Nim piles of sizes 2, 3, 2, and 5, and solve the Nim game by reducing the rightmost pile to size 3, but I cannot produce the last sentence in the solution. I can infer from the Nim game that the winning move in the Green Hackenbush game must be a cut on the tree, but I would have no idea which branch to cut. I could guess-and-check every possible move using the colon principle, but this would be prohibitively tedious for a human player in more complex graphs. Two ideas I had are…
-
Is there an inverse colon principle, such that I could use the reduced Nim pile to construct a (possibly non-unique) subgraph of the original Green Hackenbush tree which should remain after an optimal move?
-
Is there a method to simultaneously apply the colon principle not to an individual graph, but to a family or function of graphs (i.e., all followers of the given graph)?
If not, then is there some other human-viable way to reason through this last step of Green Hackenbush?
Best Answer
Here is how you find the winning move on any Green tree. My strategy is much better than brute-force trying every edge.
I do not know how to handle the case where the graph has loops. To solve this, you would need to carefully examine the proof of the Fusion Principle.
First, compute the value of tree. As you are doing this, mark each vertex of the tree with the Grundy value of the tree from that point upward. Furthermore, at each point where the tree branches, you should write down the calculation which produces the value. Here is what I mean in the case of your tree:
We are going to proceed upwards on this tree, until we find the correct move. Specifically, at any point in the calculation, we will be located at some particular vertex of the tree. Initially, we are at the root.
Suppose there is a single edge above the current vertex.
If the target value is $0$, then the desired move is to chop that edge.
Otherwise, you should move upwards along that edge, while decreasing the target value by $1$.
If there are multiple edges extending upward from the current vertex, then consider the nim position where there is one heap for each of the subtrees above, with the sizes of the heap equaling the values of the subtrees. Figure out which heap you need to move on to make that nim position into the target value. Say you need to move on heap $h$, reducing it to $m$. There are two cases:
If $m=0$, then simply chop the edge corresponding to that subtree.
If $m>0$, then move upwards along the corresponding edge, and replace the target value with $m-1$.
Here is how the algorithm plays out in your case.
Start at the root, the $5$ vertex. The target is $3$.
There is a single edge above, and the target is nonzero. Therefore, move up to the $4$ vertex, and reduce the target to $2$.
To choose which branch point to ascend on, consider the nim position with heaps of sizes $2, 2, $ and $4$. We want to make a move on this which changes it to a value of $2$. Some thought shows you can move on heap $4$, reducing it to $2$. Therefore, we move upwards along the rightmost edge, and set our new target value to $2-1=1$.
We are at the vertex labeled "$3=2+1$", with a target of $1$. We imagine a nim position with heaps of size $2$ and $1$, and find a move which turns the value into $1$. Clearly, the required move is to reduce the $2$ heap to a $0$ heap. Therefore, we have found our desired move: chop the leftmost branch of the "$3=2+1$" vertex.