|1) The Game||2) Strategy||3) Bamboo Basics|
|4) The Colon Principle||5) The Fusion Principle||6) Further Reading|
Green Hackenbush is an example of an Impartial Combinatorial Game.
The game is quite simple.
Two players take turns cutting edges on a connected rooted graph or a collection of connected rooted graphs.
For our purposes, there will only be finitely many edges on the board, we will associate all the roots with "the ground" and we will call the edges "branches".
When a player cuts an branch, the branch dissapears along with any branches that are no longer connected to the ground.
The player who cuts the last branch wins.
Now that you have the general idea, the rest of this page is dedicated to finding the values of different positions. A great place to start is with Bamboo forests.
The game to the left is a Bamboo forest with three Bamboo stalks. The value assigned to each stalk is simply the number of branches in that stalk with a "*" in front. For example, the stalk on the far left has value *3.
To find the value of the whole game we need a special way of adding the values of the
stalks. The process is as follows:
1) Convert the number of each stalk into binary
2) Add the binary values modulo 2
3) Convert the binary sum back to the number and put a "*" in front.
It takes some practice but you can use the information from the binary values of the
stalks to find the branch you want to move in. If you look at the columns of your addition
where the sum is non-0 you can usually find which stalk you need to change a 0 or a 1 in
in order to make the sum 0.
|The Colon Principle|
Bamboo forests are fine but you will only be able to beat your buddies for a short time before they catch on to the strategy. To the left is a more complicated graph which has both a tree and a bamboo stalk. How can we find the value of the tree?
We need what is called the Colon Principle. The name comes from the symbol game theorists use to denote this operation.
|The Fusion Principle|
So you think you are an expert at trees? What if you wanted to play a game that had cylces, as seen in the house to the left?
For graphs with cycles we use that is called the Fusion Principle. As the name implies, we will be fusing all the vertices of a cycle into one vertex and then playing the loops as stalks of value *1.