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 managed to play this game before viewing the solution using the colon and fusion principles 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 couldn't make sense of 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 what to cut. Obviously I could guess-and-check arbitrary possible cuts using the colon principle, but this would be extremely tedious for a human player, especially for more complex graphs. Two ideas I had are...
1) Is there a procedure to invert the colon and fusion principles, such that I could use the reduced Nim pile to reconstruct a (possibly non-unique) subgraph of the original Green Hackenbush tree, indicating what it should look like after an optimal move?
2) Is there a procedure to apply the colon and fusion principles not to an individual graph, but to a family or function of graphs (i.e., all possible followers of the given graph) all at once?
If not, then is there some other human-efficient way to reason through this last step of playing Green Hackenbush?
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 managed to play this game before viewing the solution using the colon and fusion principles 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 couldn't make sense of 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 what to cut. Obviously I could guess-and-check arbitrary possible cuts using the colon principle, but this would be extremely tedious for a human player, especially for more complex graphs. Two ideas I had are...
1) Is there a procedure to invert the colon and fusion principles, such that I could use the reduced Nim pile to reconstruct a (possibly non-unique) subgraph of the original Green Hackenbush tree, indicating what it should look like after an optimal move?
2) Is there a procedure to apply the colon and fusion principles not to an individual graph, but to a family or function of graphs (i.e., all possible followers of the given graph) all at once?
If not, then is there some other human-efficient way to reason through this last step of playing Green Hackenbush?