Red-Blue Hackenbush

Red-Blue Hackenbush

This is a two-person game and begins by drawing a picture of Red and bLue lines like in figure 1.  The two player’s, call them Left and Right, alternate turns erasing any of their assigned blue or red edges from the graph.  The player that has no more edges to remove is the loser.

If a player removes an edge that is connected to the “ground” (the black line at the base), then any edge connected to the one just removed must be removed as well so long as the removed edge was the only edge connecting the pieces above to the ground.

One analogy to think of is cutting down a tree.  If we cut down a single branch of a tree only the branch will fall to the ground and be removed.  If we cut the base of the tree (the red edge connected to the ground in Figure 1) then the whole tree falls with all of its branches.  You can’t have a floating tree!

 Figure 1: Sample starting game of Red-Blue Hackenbush

http://www.link.cs.cmu.edu/15859-s11/notes/Hackenbush.pdf

In the sample game in Figure 2, who will win if the players have identical “shrubs”?  If Left goes first then Right can apply a mimicking strategy and copy Left’s moves to allow Right to win.  Conversely, if Right goes first then Left can apply the mimicking strategy and copy Right’s moves to allow Left to win.

Figure 2: Sample game with equal-sized shrubs

http://www.link.cs.cmu.edu/15859-s11/notes/Hackenbush.pdf

We actually call these games where the first player to play loses, zero games.  In situations like this where we have two parts that are identical except with swapped colors, there will always be a matching move so the second person to move will win.

If when creating the picture, Left and Right keep their colors on separate sides then we can easily determine who will win by counting the number of blue edges and subtracting the number of red edges.  If the number is positive then Left will win and if the number is negative then Right will win.  If the calculation turns out to be zero, then the second player to go wins (as seen above in Figure 2).  Below is an easier notation to follow.

Outcomes

Let G be a Red-Blue Hackenbush position or any game.  Then

·        Left wins: G > 0

·        Right wins: G < 0

·        Mover loses: G = 0 (first person to move loses)

Let’s try out some examples!

Finding Basic Game Values

Example 1:

Sum: 2 à Blue is two moves ahead, G > 0

http://www-math.mit.edu/~rstan/transparencies/games.pdf

Example 2:

Sum: 0 à Mover loses, G = 0

http://www-math.mit.edu/~rstan/transparencies/games.pdf

Now, how would we calculate the hackenbush value if the colors aren’t separated?  In the example below, we know that Left will win regardless.  This is because If Right goes first, he removes his only red edge leaving Left to take his final edge to win.  Similarly, if Left goes first, then he removes his only stick which automatically eliminates Right’s “floating” edge.  Therefore, we know that the value must be greater than 0.

Example 3:

Sum = ? à clearly > 0: Left wins

http://www-math.mit.edu/~rstan/transparencies/games.pdf

Looking at the example below we can determine what the value of G is above by applying a little math.

Example 4: 

http://www-math.mit.edu/~rstan/transparencies/games.pdf

We find that x = ½ so the hackenbush value for example 3 is ½ which is greater than 0 so this makes sense.  This means that Left is ½ move ahead in G.

What would happen if in example 3, the edges were swapped making the top edge blue and the bottom edge red?  In fact, the hackenbush value would just be -½ since Right will always win!

In example 4, we see that the mover loses because G = 0.  Thus, whoever makes the first move will lose.  Care to try it out?

Example 5:

http://www-math.mit.edu/~rstan/transparencies/games.pdf

Looking at example 5 above, you wouldn’t think that the mover loses but if you try playing it out you will find that it is the result.  Since the 8 stacks on the left are all identical in order to find the value of x we must find 8x (identical stacks) + 13 (blue edges) à x = -13/8.  Thus, we find that the mover loses since G = 0.

Simplicity Rule

Even though it is a bit tedious, it might be helpful to trace the results of every possible combination of moves to find the game’s value.  Consider the example below.

Figure 3: Sample game

http://www-math.mit.edu/~rstan/transparencies/games.pdf

We know that a value for this game would be 3 – 2 = +1 (Left wins).  Now, let’s analyze all possible combinations of this game.

If Left has to move from this position then the resulting positions have values of 0, -1 and -2.  Remember we are strictly looking at removing blue values only right now and determining what the game value would be after removing each blue edge.

If Right has to move from this position then the resulting positions have values of 2 and 3.  Again, we are only looking at removing red values right now and determining what the game value would be after removing each red edge.

This might not make sense so please feel free to ask questions in the comments!  I will go over this in class.

Keep in mind that whenever Left erases one of his edges, the situation is always worse for him because he now has fewer options so the game value decreases when he removes a blue edge (better for Right).  Likewise, whenever Right erases one of his edges, the situation is worse for him and the game value increases when he removes a red edge (better for Left).

Therefore, the overall value of the game must be larger than all the game values after Left moves but smaller than all the game values after Right moves.

Let B₁, B₂, …, B_n be the game values after a Left move (n being the possible moves for Left) and let R₁, R₂, …, R_n be the game values after a Right move (m being the possible moves for Right).

The overall game value V must be larger than all the B_i and smaller than all the R_i.  The notation is as follows:

V = { B₁, B₂, …, B_n | R₁, R₂, …, R_n}

This does not tell us the value of V but is how we will write that value in terms of the B_i and R_i.

How might we find all possible moves for Left and Right using this notation?  Excellent question my friend!  We already found all the possible moves so we can write the value of the game as:

{-2, -1, 0 | 2, 3}.

Note: b = {-2,-1,0} and r = {2,3}. 

The game value will be a number that is greater than all the Left-moved-created values (b) and less than all the Right-moved-created values (r).  So the value of the game is the “simplest” number that lies between the largest number on the left and the smallest number on the right.

{-2, -1, 0 | 2, 3} = {0|2}.

What is the simplest number in this case?  Why, +1 of course!

Definitions

1.   If there is an integer n satisfying b < n < r, then v(G) is the closest such integer to 0.

2. Otherwise v(G) is the unique rational number x satisfying b < x < r whose denominator is the smallest possible power of 2.

Figure 4: example 3

http://www-math.mit.edu/~rstan/transparencies/games.pdf

The example we just went over in Figure 3 we found that the game value was +1 which satisfies Definition 1.

We have already seen this example above but let’s try using the “simplest rule” instead.

There is only one move available to each player.  If Left moves then everything is erased which gives us a position with a value of 0.  Right’s only move leaves a single blue edge which gives us a position with a value of 1.  So the value of the game, {0|1}, will be the simplest number between 0 and 1.  So ½ will do the trick!  This choice is a unique number and satisfies Definition 2.

http://www-math.mit.edu/~rstan/transparencies/games.pdf

What would the Hackenbush value be in this example above?

http://www-math.mit.edu/~rstan/transparencies/games.pdf

We start by evaluating the tree first.  If Left goes first, they can remove the branch on the right, then we have a position with a value of +1/2 (third picture from left).  But if Right goes first, they can remove the branch on the right which will leave us with a position with a value of +2 (fourth picture from left).  So our values are b = ½, r = 2 so what does x equal?  We get { ½ | 2} = 1.

http://www-math.mit.edu/~rstan/transparencies/games.pdf

Thus, the tree has a value of 1 and the single red edge is -1 which gives us a total of 0, so the mover loses.

Another Way to Find Game Values

·        Count the number of blue (or red) edges that are connected in one continuous path.  If there are n of them, start with the number n.

·        For each new edge going up, assign that value of that edge to be half of the one below it.  If it is a blue edge make it positive.  If it is a red edge make it negative.

·        When you reach the top count all of your values that you have and this will be the overall value of the stalk.

This method can be used with the simplicity rule and can help us calculate the game value much faster!

Example: Say we have the stalk whose edges are, starting from the ground: BBBRRBR.

We begin with 3 because there are three blue edges connected.  The first R gets a value of -½ and the next red gets -¼ and the next blue gets 1/8 and the final red gets -1/16.  If we add these values we get an overall game value of 37/16.  

How are we doing?  I will provide you with some examples in class but if you have any questions, let me know and I will try to clarify them!

Conclusion

So much can be said about Red-Blue Hackenbush.  In fact, there are several other versions of including Hackenbush games that are infinite and mixed games that have blue, red, and black edges.

I haven’t even scratched the surface about how in depth Hackenbush can go!  This would be a great topic to do for a final project!!

Please post any questions or comments you might have!

Citations

Davis, Tom. “Hackenbush.” December 15, 2011. Accessed February 20, 2017. http://www.geometer.org/mathcircles/hackenbush.pdf.

Bartlett, Padraic. “A Short Guide to Hackenbush.” August 12, 2006. Accessed February 20, 2017. http://www.link.cs.cmu.edu/15859-s11/notes/Hackenbush.pdf.

Accessed February 20, 2017. http://www-math.mit.edu/~rstan/transparencies/games.pdf.