Skip to main content

Whose Game?

 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.


Consider the Hackenbush starting position in figure 2.
Figure 2: Tweedledum and Tweedledee

For every move of the first player, the second player can simply mirror the move in the other component, and indeed this move for the second player is always available(why?). This is called the Tweedledum-Tweedledee argument. Thus, regardless of whether Left or Right starts, the second player is the winner. Such a game, in which the first player always loses, is called a zero game.

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. 
Figure 4: Half moves?

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?

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
$$\{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.



Post a Comment

Popular posts from this blog

The importance of "intuition" in geometry

Hii everyone! Today I will be discussing a few geometry problems in which once you "guess" or "claim" the important things, then the problem can easily be finished using not-so-fancy techniques (e.g. angle chasing, power-of-point etc. Sometimes you would want to use inversion or projective geometry but once you have figured out that some particular synthetic property should hold, the finish shouldn't be that non trivial) This post stresses more about intuition rather than being rigorous. When I did these problems myself, I used freehand diagrams (not geogebra or ruler/compass) because I feel that gives a lot more freedom to you. By freedom, I mean, the power to guess. To elaborate on this - Suppose you drew a perfect  diagram on paper using ruler and compass, then you would be too rigid on what is true in the diagram which you drew. But sometimes that might just be a coincidence. e.g. Let's say a question says $D$ is a random point on segment $BC$, so maybe

LMAO Revenge

Continuing the tradition of past years, our seniors at the Indian IMO camp(an unofficial one happened this year) once again conducted LMAO, essentially ELMO but Indian. Sadly, only those who were in the unofficial IMOTC conducted by Pranav, Atul, Sunaina, Gunjan and others could participate in that. We all were super excited for the problems but I ended up not really trying the problems because of school things and stuff yet I solved problem 1 or so did I think. Problem 1:  There is a   grid of real numbers. In a move, you can pick any real number  ,  and any row or column and replace every entry   in it with  .  Is it possible to reach any grid from any other by a finite sequence of such moves? It turned out that I fakesolved and oh my god I was so disgusted, no way this proof could be false and then when I was asked Atul, it turns out that even my answer was wrong and he didn't even read the proof, this made me even more angry and guess what? I was not alone, Krutarth too fakesol

Edge querying in graph theory

In this post, I will present three graph theory problems in increasing difficulty, each with a common theme that one would determine a property of an edge in a complete graph through repeated iterations, and seek to achieve a greater objective. ESPR Summer Program Application: Alice and Bob play the following game on a $K_n$ ($n\ge 3$): initially all edges are uncolored, and each turn, Alice chooses an uncolored edge then Bob chooses to color it red or blue. The game ends when any vertex is adjacent to $n-1$ red edges, or when every edge is colored; Bob wins if and only if both condition holds at that time. Devise a winning strategy for Bob. This is more of a warm-up to the post, since it has a different flavor from the other two problems, and isn't as demanding in terms of experience with combinatorics. However, do note that when this problem was first presented, applicants did not know the winner ahead of time; it would be difficult to believe that Bob can hold such a strong