In this blog post, we will talk about Combinatorial games, how to quantify positions, and analyse games. Most of this is based on the beginning chapters of the comprehensive book Winning Ways for your Mathematical Plays by Berlekamp, Conway and Guy.
What is a Game?
You might be familiar with multiple 'games', all with greatly varied meanings. For example, a game could refer to a wild animal hunted for sport (This post isn't about those!). We will talk about games that are defined by the following (restrictive) rules:
- There are just 2 players, often named Left and Right.
- There are several well-defined positions and a starting position.
- There are clearly defined rules specifying the moves each player can make from a position, and the resulting positions are called options.
- Left and Right move alternately in gameplay.
- In the normal play convention, the player unable to move loses. In misere play, the last player to move loses.
- The rules ensure that the game ends and one player wins after a finite number of moves.
- Both players have complete information about the present state of the game.
- There are no moves based on chance like rolling a die.
You might find these rules a bit extensive, especially since games like chess and tic-tac-toe are excluded (possibility of a draw). However, the techniques developed to analyse games under these rules are applicable to the analysis of games such as Chess and Go.
Blue-Red Hackenbush
So which games will we even talk about? We will begin with the description and discussion of Hackenbush, typically played on a graph of Red and Blue edges such as that in figure 1, such that all edges are connected via some sequence of edges to 'ground', which is the grey line at the bottom of figure 1. One player (Left) plays as Blue, and the Right plays as Red. In a move, a player removes an edge of his colour and also removes any edges which are now disconnected from the ground. We analyse Hackenbush in the normal play convention. In figure 1, if Left starts and takes the left foot, no other edges are removed since they are all still connected to the right foot. Right can win in his move by taking the right foot, which will erase the entire figure.
 |
| Figure 1: A Hackenbush Starting Position |
It is highly recommended that you play some games of Hackenbush on various figures to get a feel for the games. You can find an interactive player here.
Tweedledum-Tweedledee
Consider the Hackenbush starting position in figure 2.
 |
| Figure 2: Tweedledum and Tweedledee |
 |
| Figure 3: A game of value +3 |
Why did we choose to assign the number zero to such a game? Consider a game of the form in figure 3, where the Blue and Red edges lie on separate trees. With optimal play, each player chops down his tree from the top-down, and the player with more edges wins, with the difference to spare. That is, in figure 3, Left has the advantage of exactly 3 moves, and we assign this game a value of 3.
When would you assign the value -3 to a game? (Try flipping colours and players)
Why would figure 2 be a 'zero' game?
If the value of only the left component of figure 2 is $x$, what is the value of the right component?
If the value of two Hackenbush games are $x$ and $y$, what is the value of the game consisting of these as independent components?
Half a Move?
Consider the Hackenbush game in figure 4.
First, let us only consider the leftmost component, a blue edge atop a red edge. Irrespective of who plays first Right takes the red edge in his move and wins. Thus, the left component has a negative value, an advantage over the Right. What is its value? |
| Figure 4: Half moves? |
Consider the Hackenbush game formed by the 2nd and 3rd components of figure 4, where we have added an extra move for Left to compensate for his disadvantage in the last game. If Left starts, he takes the edge above the red edge and wins in his next turn. If the Right starts, the Left wins in his turn. Thus, this game is of positive value, an advantage to Left! The right had an advantage in the previous game, but not as much as a full one move.
Now let us consider the entire game in figure 4. If Left starts, he should not take the 3rd component, since then Right will take a stem and turn the game in his favour. If Left takes a leaf, Right will take the other stem, again yielding a game in his favour. However, if Right starts, he is forced to take a stem, after which Left takes a leaf and wins in his next move. Thus, we have arrived at a zero game. Two copies of the left component, exactly cancel the single move advantage for the Left. So, the left component gives an advantage of half a move to Right and is of value $-\frac{1}{2}$.
Here is an exercise for you: what are the values of the Hackenbush games in figure 5?
 |
| Figure 5 |
Many questions would be bugging you right now: Is it correct to weigh a game by its value? Are all Hackenbush positions quantifiable like this? If so, how do you determine the value of a Hackenbush game? What about games other than Hackenbush? Is it correct to add and subtract games like we are doing? Is it correct to compare games, talk about positives and negatives?
Conway's Notation
Consider once again the Hackenbush position worth half a move, a red edge on top of a blue edge. If Left plays from this position, he has exactly one option, and that brings us to no edges, a game of value 0. If Right plays from this position, his only option brings us to a single blue edge, a game of value 1. We already saw that this game has a value of $\frac{1}{2}$. We represent this using Conway's Notation as
$$ \{0 | 1 \} = \frac{1}{2}$$
The left side of the notation consists of the values of Left's options and considers the most positive value, the greatest advantage for Left. Similarly, the right side consists of the least value among the Right's options.
 |
| Figure 6: A game of value $\{5 | 6 \} = 5\frac{1}{2} = 5 + \frac{1}{2}$ |
In general, considering a game of the form figure 6, we have
$$\{ n| n+1 \} = n + \frac{1}{2}$$
If you solved the exercise in figure 5, you will see easily that
$$\left \{ 0 | \frac{1}{2}\right \} = \frac{1}{4}$$
$$\left \{ \frac{1}{2} | 1 \right \} = \frac{3}{4}$$
Further, as an exercise, you may generalise figure 5 by adding continuous red edges atop a single blue edge and obtain that
$$\left \{ 0 | \frac{1}{2^k} \right \} = \frac{1}{2^{k+1}}$$
(Hint: Induction, based on the method from figure 4)
Can we have a game whose value is $\frac{5}{8}$? We can simply add $\frac{1}{2}$ and $\frac{1}{8}$, to obtain the position:
 |
| Figure 7: $\frac{5}{8}$ game |
From figure 7, it is clear that $$\left \{ \frac{1}{2} \,|\, \frac{3}{4} \right \} = \frac{5}{8}$$
In exactly the same way, we can show that $$\left \{\frac{p}{2^{n}} \, | \, \frac{p+1}{2^n}\right \} = \frac{2p+1}{2^{n+1}}$$
With all these examples, you might have an idea for how to compute $\{a|b\}$, simply take their average! This is incorrect, as will be shown in the next section. How indeed to compute a general such value is rather involved, and we shall discuss it later.
What do we do if the Left or Right has no moves from a position? We simply write the empty set in their corresponding place, and it is a common notation to simply leave it blank. Thus we have the results
What do we do if the Left or Right has no moves from a position? We simply write the empty set in their corresponding place, and it is a common notation to simply leave it blank. Thus we have the results
$$\{n|\,\} = n+1$$
$$\{\,|-n\}= -n -1$$
Surreal Numbers and the Simplicity Rule
Conway's notation can be considered in a context-independent of games, and indeed this leads to a construction of the real numbers more exciting than standard real analysis, with very interesting properties. This is the construction called the Surreal Numbers, and in addition to the real numbers, it contains infinite ordinals and infinitesimals. It provides the concept of simplicity, which is essential to the present discussion, however, it is a topic for another blog post.
What is the value of the game $X = \{\frac{1}{4}| 1\}$? You might expect it to be the average, $\frac{5}{8}$. We can test this by considering the game $x - \frac{5}{8}$, and attempting to show that it is a zero game. We have
$$X + -\frac{5}{8} = \left\{\frac{1}{4}| 1\right\} + \left\{-\frac{3}{4}| -\frac{1}{2}\right\}$$
Left has no good move from this position, since if he moves in the $X$ component, the option is of value $\frac{1}{4} - \frac{5}{8} < 0$ and if he brings the $-\frac{5}{8}$ component to $-\frac{3}{4}$, Right can play on the $-\frac{3}{4}$, bringing it to $-\frac{1}{2}$ after which Left is forced to play on $-\frac{1}{2}$ bringing it to $-1$ and giving a losing position. Indeed, the Right option of $-\frac{1}{2}$ guarantees a win for Right, and hence $X - \frac{5}{8}$ is a negative game.
In fact, you can see that the value of the game $X$ must be $\frac{1}{2}$ for exactly this reason, that it is the simplest number in between $\frac{1}{4}$ and $1$. Here, $\frac{1}{2}$ is simple because it's immediate options are $0$ and $1$, none of which lie in between $\frac{1}{4}$ and $1$. We can summarise this in the neat Simplicity Rule: The expression $\{a|b\}$ evaluates to the simplest number between $a$ and $b$.
 |
| Figure 8: The Binary Tree of Numbers, and Hackenbush Strings |
Attached in figure 8 is the Binary tree of numbers, numbers closer to the root are simpler than those further from the root. Also below you can see the Hackenbush stalks corresponding to the values. If you are familiar with the Surreal Number Construction, this is simply the Surreal Number Creation tree (figure 9).
 |
| Figure 9: The Surreal number creation tree, with Ordinals |
Game Arithmetic and Outcome Classes
Here we generalise our notation in the abstract. For a game $G$, we denote it in Conway's notation as $\{G^L|G^R\}$ where $G^L$ and $G^R$ are sets of Left and Right options respectively.Further, we define the sum of two games $G$ and $H$ as follows:
$$G + H = \{(G^L + H) \cup (G + H^L)\,\,|\,\, (G^R + H) \cup (G+ H^R) \}$$
In words, this means the following definition of the sum of two games: In each move, the player picks either component of the sum game and plays a legal move in that game. There is no restriction on which component he chooses to play.
It is possible to demonstrate via the Surreal Number construction why this corresponds to adding the values of the games.
The set of Combinatorial games can be divided into four outcome classes:
- Positive Games ($G>0$): Left always wins, regardless of the first player.
- Negative Games ($G < 0$): Right always wins, regardless of the first player.
- Zero Games ($G = 0$): The second player always wins.
- Fuzzy Games ($G || 0$): The first player always wins.
You might ask: why assign 'zero' only to the 3rd type, and call the 4th type 'fuzzy'? We will talk about fuzzy games and their arithmetic in a future post. It so happens that Fuzzy positions never arise in Hackenbush. Indeed this is why we can always assume Hackenbush positions to have numerical values (surreal numbers) and compare them like ordinary numbers. All these heuristics will be made rigorous in a future post about the Surreal Numbers.
Why is the third type of game called a 'zero game' ? Consider the sum of a game $G$ with a zero game $H$. The winning player in $G$ never needs to play in $H$, except to respond to a move of his opponent in $H$. Being the second player in $H$ and the winning player in $G$, he, therefore, wins the sum game $G+H$. The outcome of a game is not affected when a zero game is added to it. In particular, the sum of two zero games is a zero game. (This is not true for a fuzzy game, and we will see this when we talk about them in a future post).
The negative of a game $G = \{G^L|G^R\}$ is defined as $-G = \{-G^R|-G^L\}$. Can you reason why this definition makes sense? (Hint: What is the sum of a game and its negative?)
The proof of why Hackenbush is never fuzzy is left as an exercise for the reader, and an elegant proof will be provided after the discussion of Surreal numbers (and pseudo numbers in particular). What we want to prove is that there is no game where the first player wins regardless of colour. In other words, if a player (say Left playing BLue) can force a win playing first, they can necessarily force a win playing second, there is no advantage associated with playing first (such games are called cold games).
Conclusion and Further Reading
This post is an introduction to the rich theory of Combinatorial games and in particular the class of partizan games (games which are asymmetric wrt the 2 players, i.e they have different moves). Multiple amazing features arise from their study, including fascinating insights into advanced set and number theory. Multiple books have been written on these subjects, and the interested reader may check them out. Note that these books are fairly advanced in nature.
- Winning Ways for your Mathematical Plays Vol1&2 - Berlekamp, Conway and Guy
A comprehensive research-oriented textbook containing modern results about game analysis. - On Numbers and Games - John H Conway
A well-written concise book, with a bidirectional discussion on games and numbers. A bit hard to follow. - Surreal Numbers - Donald Knuth
A great 100-page introduction to the surreal numbers. - Mathematical Go: Chilling gets the last point - Berlekamp and Wolfe
A book on the modern analysis of the game Go.
In a future blogpost, we will talk about the Surreal Number construction, the pseudo numbers, impartial games and NIM.
Ameya
Nice
ReplyDelete