Winning Strategies for
Green Hackenbush

By Rachel Esselstein

Dartmouth College

1) The Game 2) Strategy 3) Bamboo Basics
4) The Colon Principle 5) The Fusion Principle 6) Further Reading













The Game

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.







top























Strategy

Soon we will be assigning values to the positions in the game. The only strategy you need to win is the following:

When e're it is your turn to play,

Bring the value down to *0 if there is a way.

If the game has non-*0 value, such a move you will find.

Stick with this strategy, and win everytime!












top





















Bamboo Basics


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.


An example of this with pictures!!!









top























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.

Colon Principle-- When several stalks meet at a vertex we may replace those stalks by a single stalk of the value equal to their sum.




Another example with pictures!!!










top















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.

Fusion Principle-- We may replace any cycle with the equivalent graph where all the vertices of that cycle are fused into one.




Yet another example with pictures!!!










top















Further Reading

In case you would like to learn more....

Berlekamp, Elwyn R., Conway, John H. and Guy, Richard. "Winning Ways for Your Mathematical Plays". Vol. 1. A K Peters Ltd., (2001).

Conway, John H. "On Numbers and Games" 2nd ed. A K Peters Ltd., (2001).

Ferguson, Thomas S. "Game Theory" http://www.math.ucla.edu/~tom/Game_Theory/Contents.html.












top