Red-Blue Hackenbush

Red-Blue Hackenbush

If you enjoy taking the chainsaw to the shrubbery, then Hack-en-bush is the game for you. Hackenbush is a combinatorial game. The game-board is preset, containing red and blue lines connected at vertices. All of these lines are somehow connected to the ground/bottom of the paper. There are numerous different playing-boards to choose from, an example of one playing-board is the Hackenbush girl depicted below in Figure 1. Players alternate removing lines. The Right player is allowed to remove only red lines, the Left player is allowed to remove on blue lines (Right=Red, Left=bLue). Once a line is removed, all of the lines above the removed line, not connect to the ground will be erased. For example, in Figure 1, if the blue arm line was removed, the blue hand on that arm and the red ball would also be erased. The player who removes the last line wins. I would highly recommend trying the game out for yourself: Play Red-Blue Hackenbush! I found after playing a few rounds it made a lot more sense. 

Figure 1: Hackenbush Girl

As we have seen, Red-Blue Hackenbush clearly fulfills the requirements for a combinatorial game:
1. There are exactly two players (Left and Right).
2. No chance is involved.
3. Both players have perfect information.
4. Game is finite.
5. Someone must win, and the winner is determined by who makes the last move. 

Who wins?

Under optimal play, we should be able to determine which player will win the game before they even begin. Let's start out with an easy example. Take a look at Figure 2 below. Who will win?

Figure 2: Girl and Boy

As we can see, Left player has $14$ edges and Right player has $11$ edges. Left will win because they have $3$ more moves, $(14-11=3)$. So no matter who starts the game, Left will always win. Now this is an extremely simple game seeing as Lefts moves will not effect Rights moves and vice versa. Let's look at a bit trickier of an example in Figure 3.

Figure 3: Tweedledee and Tweedledum

After close examination , we notice red edges have been exactly interchanged with blue edges. Both Left and Right have 19 edges. The second player will always win this game as long as they copy the first players strategy. (If Left takes its blue center stomach line, then Right should take its red stomach line). This strategy, of copying the moves of the first player is known as the Tweedledee and Tweedledum strategy. No matter who starts, the second player will always win, this is known as zero position.

Zero Position: A position in which whoever starts the game will lose the game.

Fractional Moves

How do you determine the value of a move? In Figure 2: Girl and Boy, every move was worth an integer value. But some moves have fractional values. Let's take a look at Figure 4.

Figure 4: Half Moves

What is the value of the position in Figure 4(a)? As you can see, no matter who goes first, Left will always win the game in 4a. But what happens when you add a red move of value $-1$. (Note: The value of moves are represented in terms of the value of the move to Left, so blue moves will be possitive, where red moves will be negative). As you can see in Figure 4(b), when a single red edge is added, Right will always win, no matter who goes first. So we know the value of the position in Figure 4(a), lets denote as $a$, must be $0<a<1$. In Figure 4(c), we finally have a zero game. After playing around, you will see that whoever goes first will lose. Now we know the value of the single red edge is $-1$ and we know the value of the game is $0$, so we know the value of $a$ can be determined by the equation $a+a-1=0$. Hence the value of the position $a$ is $\frac{1}{2}$.

What is the value of the position in Figure 4(d)? (Hint: whoever goes first will lose). That's right, you got it, Figure 4(d) is a zero position.

The value of particular moves can be difficult to determine and takes a lot of playing around with different scenarios. Figure 5 displays a table of already known values of certain positions.

Figure 5: Given Values of Hackenbush Positions

Once you know the values of certain positions it becomes easier to determine the values of other positions. It is even easier if you know the game is a zero game. Let's take a look at Figure 6.

Figure 5: A Zero Game

We know this game is a zero game. We know the value of the middle position is worth $-\frac{1}{2}$ to Left. We also know the value of the position on the far right is wort $-1$ to Left. We also know all the positions, when added together must equal $0$ since we know the game is a zero game. Let us call the position on the far left side (with two blues and a red) position $z$, we know $z-\frac{1}{2} -1 = 0$, thus we know $z=1\frac{1}{2}$. So the value of the far left position is $1\frac{1}{2}$.

Determining the Value of a Hackenbush Games

Figure 6: Tree and Stump

Examining the Hackenbush game in Figure 6. The tree has value $9$ and the stump has value $\frac{1}{2}$, so the entire position has value $9\frac{1}{2}$. Lets examine the possible moves. Right only has one move, and that is to a position of value $10$. The best move for Left would be to remove the blue edge of the stump, which would result in a position of value $9$.

The best move by Left is to move to a position of value $9$, the best move by Right is to move to position of value $10$. We can express this by the equation ${9|10}=9\frac{1}{2}$.

In general we have:
${n|n+1}=n+\frac{1}{2}$
${n| }=n+1$
${ | }=n+1$
${ |-n}=-(n+1)$

Simplicity Rule

Let v(G) represent the value of any Hackenbush position.
Let b be the largest value of any position blue can move to.
Let r be the smallest value of any position red can move to.

Then
a.) There exist an integer $x$, such that $b<x<r$. So $v(G)$ will be the closes integer to zero.
If no such integer exist, then
b.) There exist a rational number, $x$, such that $b<x<r$ whose denominator is the smallest possible power of two.

Figure _ depicts possible b and r values. Try and determine the corresponding x value (without looking first).

Figure 7: Practice with Simplicity Rule

Outcomes

Let $G$ represent the value of Hackenbush game.
If $G>0$ Left wins.
If $G<0$ Right wins.
If $G=0$ the second player wins.

What's your Next Best Move?

When games get complicated it is not always easy to tell your best next move. Luckily we can use the binary number tree for that. Once you find the value of the position of your current game, you can find the value of the position you should move to in order to win. (This will make more sense when I explain in class).

Figure 8: Binary Number Tree

Further Explorations

For this post I focused on Red-Blue Hackenbush. But there are numerous Hackenbush variations. Green Hackenbush is where all segments are green, and both players are allowed to choose any green segment. Red-Blue-Green Hackenbush is where there are red, green, and blue segments. Left player can choose any blue or green segments, while right player can choose any red or green segments. Although these seem like simple changes in the playing board, the effect on determining the best playing option is drastically different. 

References

https://en.wikipedia.org/wiki/Hackenbush
http://www-math.mit.edu/~rstan/transparencies/games.pdf
http://www.link.cs.cmu.edu/15859-s11/notes/Hackenbush.pdf
http://geometer.org/hackenbush/index.html
Game Theory, Thomas S. Ferguson
Winning Ways For Your Mathematical Plays, Volume 1, E.R. Berlekamp, J. H. Conway, R.K. Guy