Combinatorial Games (Part II): Different Moves for Left and Right
3. Hackenbush
We will follow the usual convention that names the two players Left (who cuts blue edges) and Right (who cuts red edges). Furthermore, we adopt the rule of standard (normal) play: if a player can not move, that player loses. For the game in (a), if Left moves first she can cut the blue edge, leaving Right no move. Right loses. If Right goes first, there being no red edge, he loses. This game is a win for Left. For the game in (b) if Left moves first, she loses since there is no move for her, there being no blue edges. If Right goes first he cuts the one red edge, leaving Left with no move. Left loses. Now consider the game in (c). If Left moves first, she loses because she has no move. If Right moves first, he has the choice of cutting the top edge or the bottom edge, in which case the top edges tumble to the ground. But in either case, Right wins because Left has no move. What if the game consisted of the positions in (a) and (c) combined? In this case if Left goes first, she has a move but Right can still win because whichever edge Right cuts will still leave Left with no move. If Right goes first and cuts the bottom edge, Left has a move and Right would have no response. However, if Right cuts the top red edge, Left has a move but Right has a response and wins.
Next consider play from the position consisting of (a) and (b). In this case if Left goes first, Right responds and Left loses, having no move. However, if Right goes first, left responds and Right loses because there is no move left. In other words, this game is won by Left if Left goes first and by Right if Right goes first. This symmetry suggests that it would be natural to assign a value of "0" to this game. In light of this it would also be reasonable to have the position (a) given the value +1 and (b) the value 1. (It is merely by convention that games where Left wins regardless of who moves first have positive value and those where Right wins regardless of who moves first have negative value.) It also seems natural to have the size of the value indicate how much "advantage" Left or Right has. If these values are really to behave like numbers, they should obey the properties of numbers. One can work out a framework in which all of this can be accomplished. To give some of the flavor of this, you can verify that the values of the positions from left to right above are +1, 1, 2, +3, while the value of the game below is 0.
As with impartial games each player would like to know at a given position whether or not he/she can win the game from the current position. If a win is possible, the player would like to know how to find a move that achieves a win. The player who knows by looking at a position that he/she can not win from this position would like to know how to play so as to take advantage of any future mistake in play that might occur. For the position in (a), if Left goes first she has a move but Right can respond and win. If Right goes first, Right moves but Left can not respond, so Left loses. Thus, the value of this game is negative but this position does not seem as strong for Right as a single red edge. The position (b) by symmetry has a positive value the same size as the value for the (a) position. Can you determine if positions (c) and (d) have positive or negative value?
Suppose we have a game consisting of two copies of (a) and a single blue edge. What would be the result of play?
If Left moves first and selects the single blue edge, Right moves and destroys a blue edge in the process. Thus, Left can respond but can not prevent a Right win. On the other hand, if Left moves by taking one of the top blue edges, Right can respond by cutting the red edge with a blue one on top of it. Left now must take the single blue edge, meaning that Right can still win by taking the remaining red edge! Thus, Right wins if Left goes first. It is easy to check that if Right goes first, then Left wins. Thus, this game should have zero value. Since a single blue edge is worth +1, this means, that each of the other games must have value 1/2. Hackenbush positions can have rational values.
A very elegant and simple way to find the value of this Hackenbush position was found by Elwyn Berlekamp. The unexpected dividend, but a typical one that arises when one studies "pure" mathematics, is the possibility of putting ideas of this kind to work in the area of data compression.
The method can also be used in reverse to find a string whose value is a given number. Thus, to represent 19/8 we can write this as 2 + 3/8. Writing the fraction in binary we get .011. To draw the Hackenbush string remember that the terminal 1 must be deleted. Since the value is positive and has integer part 2, we begin with 2 blue segments, and then the binary point is represented by an additional blue and red segment. After the terminal 1 of 011 is deleted we have 01, which means we get the diagram below: In the games we have looked at previously we have insisted that features such as the number of edges or the number of stones in a pile be a finite number. However, when we permit an infinite number of stones or edges, we can encounter some fairly "exotic" numbers. Not all numbers associated with an infinite number of features will be exotic. In fact, some of these infinite colored "graphs" turn out to have very unexotic values. For example, the chain consisting of alternating blue and red edges in a path has the value 2/3. (Check that a bluered path has value 1/2, blueredbluered has value 5/8, blueredblueredbluered has value 21/32, and continuing in this fashion one gets the sequence of fraction values, 85/128, 341/512, etc.). So what about the exotic values? We can think of an infinite path of blue edges as having the value ω (see next section). Think of this as an infinite blue "beanstalk." Furthermore, it is possible to imagine a beanstalk with some additional edges at the top to climb. If there is one additional edge, this would have value ω + 1, and if two edges at the top, ω + 2. Using ideas in this spirit one creates all kinds of strange "beanstalks." Hackenbush has many variants including ones where the edges above the ground are green and where green edges (not part of the base line) can be cut by either player. It turns out that allowing moves which involve blue, red, or green edges is essential for being able to understand the full ramifications of Conway's approach to numbers built around games. 
Welcome to the These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics. Search Feature Column Feature Column at a glance 
Comments: Email Webmaster 
© Copyright
, American Mathematical Society


