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 B1, B2, …, Bn be the
game values after a Left move (n being the
possible moves for Left) and let R1,
R2, …, Rn 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 Bi
and smaller than all the Ri.
The notation is as follows:
V = { B1,
B2, …, Bn | R1, R2, …, Rn}
This does not tell us the value of V but is how we will write
that value in terms of the Bi and Ri.
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.
