Game on the tree, cutting branch

12
votes

We have a forest of rooted trees. Two players makes alternating moves according to the following rule: one move is to cut vertex and all its children. Player which makes last move (no vertices remain) wins.

How can we compute Grundy function for the positions in the game?

Suppose we have a trees and we need to say whether current position is winning or losing?

1
algorithmtreegame-theory
Sounds very difficult homework! - Paul Hadfield
I suggest you get a copy of "Winning Ways" en.wikipedia.org/wiki/Winning_Ways_for_your_Mathematical_Plays from your local library and work it out for yourself. - Doc Brown
I admit that this problem is computer-sciency, however it falls more in the mathematical-category than in the programming-category. So you might find more help here: > math.stackexchange.com - Bernd Elkemann
I hope this isn't for codechef.com/MARCH11/problems/SQUAGAME - because thats a currently running contest. - kyun
Isn't this just a variation of Nim? Each tree can be replaced by a heap with as many stones as the longest path in that tree. - Nick Johnson

1 Answers

5
votes

This is the Hackenbush game. I highly recommend this article, which covers Grundy numbers with great clarity and thoroughly discusses hackenbush toward the end.