Hackenbush
Hackenbush
We discuss here a simple game called Hackenbush. In it are two colours: A is black (male) and B is red (female). Given a figure like the one below (Figure 1), A may erase any black coloured stroke and B any red one. If after a move other parts of the figure have become disconnected from the ground, they too will disappear. Hackenbush is partesan, as the two colours are distinct. A and B will alternate moves, the winner being who plays last.
Figure-1
Look at Figure 1 and we shall analyse the possible moves. Suppose A begins.If A eliminates the line 1 (black), B will answer eliminating line 1' (red), and that will cause the eradication of all lines (for disconnection from the ground) and therefore victory for B.
If A eliminates first the line 2 (and he must do something), B will respond eliminating her line 2' (red), leaving a situation with just one move for A and certain victory of B.
If B were to begin the game, she also has two alternatives. If she begins erasing line 1' (red), A will respond erasing his line 1 and winning. But if B begins with line 2', line 2 (black) will also disappear. A will follow with just one alternative (line 1) and B will answer and win erasing 1'.
We see that independent of who begins, B can always guartantee victory. Translating in the terms we used above, Figure 1 has a negative value.
To understand better the question of practical decisions to be made in playing a game, let's see in more detail how to calculate the value of a configuration in Hackenbush. A configuration which values zero describes a situation in which whoever begins will lose. As examples, think of i) an empty figure or ii) a figure with k lines of each colour, disconnected from each other. We shall say the a figure has positive value x if A has x more moves than B, and negative value x for the contrary: B has x more moves than A. So if A has n moves and B has m moves, the value of the configuration is n – m.
In the Figure 2a we have a configuration whose value we declare to be equal to ½. We justify this somewhat unusual fact by calling its value x and considering in Figure 2b a configuration which consists of “ 2x – 1” , that is two figures called x and another which we've already seen as – 1. We now show that 2x – 1 = 0, which implies that x is ½.
Figure-2a Figure-2b
Looking at Figure 2b, suppose that the player A (black) begins. He has only one real alternative. B responds eliminating the upper part of the remaining two stick figure, leaving one free black trace and one red. B (red) will obviously win the game.
If B begins, she eliminates one of the red upper parts and A responds eliminating the other double stick entirely. Once again there remains two independent traces, one black and one red, and A will win. If B had begun eliminating the independent red trace (on the right), A will respond in the same way and once again will win.
Thus, whoever begins the game at the right in Figure 2b, will lose. By definition that implies that its value is zero and therefore that x = ½.
There is an exact, general method of determining the value of a configuration. We comment that that does not imply that it is always easy to calculate! The method is general in that it may be applied to many different games. We illustrate the method for the game Hackenbush.
With advantage for A being called positive and for B negative, we see that on playing, A desires that the value of the configuration after his move is the greatest possible value, whereas B plays with the intention to make the value the smallest possible (and negative, if possible). So we examine the configuration and see which are A's best move and B's best move. We write the values between brackets with a bar between them. The value of the configuration is the “most simple” value contained between these two values – a concept to be explained in more detail later on. For example, in the case of Figure 2a each player has just one possible move. For A it means eliminating everything (value zero). For B, one black trace is left, of value one. Thus the value is calculated as { 0 | 1 } = ½, that is, ½ is the simplest value between zero and one.
Consider Figure 3. Once again, A and B have only one distinct move each. A will eliminate the whole figure (value zero) and B will leave as remaining exactly the figure that we proved of value ½ above. Thus the value of the configuration is { 0 | ½ } which has value ¼. The reader who desires to prove that more rigorously may design four repetitions of the figure and add one red trace alone beside them, and by calling
Figura 3
The figure in question of value x she will be examining the value of 4x – 1, which in a similar way to what we saw before may be shown to have value zero.
Repeating this calculation a number of times permits us to calculate the valuew of a more complex configuration.
Partesan games rarely have fuzzy configurations and in Hackenbush they do not exist. In impartial games they are very common, as in fact all impartial configurations always have value either zero or fuzzy.