Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Thank you.

share|improve this question
add comment

2 Answers

The technique is well described in Winning Ways or (in less detail) at Sprague-Gundy theory. Each tree is a nim-heap. To get its value, look at the value of all subtrees that you can move to and the value is the minimum value not in the set. For example, consider a tree with a single stick from the root and three branches at the top. You can move to zero or a similar tree with two branches at the top. To get the value of the one with two branches, you can move to zero or two, so its value is *1. Then the one with three can move to 0 or *1, so has value *2. The value of the forest is the bitwise XOR of the binary values of all the trees. The position is losing if the value is zero. A single tree will never be zero as you can always chop it down at the root.

share|improve this answer
add comment

It is known as hackenbush. It's theory is well developed and you may google a lot...

share|improve this answer
1  
Except that hackenbush usually has the edges colored and players can only chop edges of their color. It seems OP wanted the all green version where either player can chop any edge. –  Ross Millikan Mar 5 '11 at 23:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.