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.

Tweedledum-Tweedledee

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.

Ameya

Comments

Popular posts from this blog

Constructions in Number Theory

Hi, I am Emon, a ninth grader, an olympiad aspirant, hailing from Kolkata. I love to do olympiad maths and do some competitive programming in my leisure hours, though I take it seriously. I had written INOI this year. Today, I would be giving you a few ideas on how to Construct in Number Theory . Well, so we shall start from the basics and shall try to dig deeper into it with the help of some important and well-known theorems and perhaps, some fancy ones as well. Okay, so without further delay, let's start off... What do we mean by "Constructions"? If noticed, you can see that you often face with some problems in olympiad saying, "... Prove that there exists infinitely many numbers satisfying the given conditions" or "... Prove that there exists a number satisfying the above conditions." These are usually the construction-problems .  For example, let's consider a trivial example : Problem. Prove that there exist infinitely many integers $a$ such th

EGMO solutions, motivations and reviews ft. Atul, Pranjal and Abhay

The  European Girls' Mathematical Olympiad a.k.a EGMO 2022 just ended. Congrats to Jessica Wan from USA, Taisiia Korotchenko, and Galiia Sharafetdinova for the perfect scores! Moreover, the Indian girls brought home 4 bronze medals! By far, this is the best result the EGMO India Team has ever achieved! To celebrate the brilliant result, here's a compilation of EGMO 2022 solutions and motivations written by my and everyone's favorite IMOTCer Atul ! And along with that, we also have reviews of each problem written by everyone's favorite senior, Pranjal !  These solutions were actually found by Atul, Pranjal,  and Abhay  during the 3-hour live solve. In the live solve, they solved all the 6 problems in 3 hours 😍!!! Okie Dokie, I think we should get started with the problems! Enjoy! Problem 1:  Let $ABC$ be an acute-angled triangle in which $BC<AB$ and $BC<CA$. Let point $P$ lie on segment $AB$ and point $Q$ lie on segment $AC$ such that $P \neq B$, $Q \neq C$ and

Q&A with experts about bashing

Heyy everyone! From the title, you can see that we are going to talk about  BASH.  Yesss, we are going to discuss whether you really need to learn bash or not?  Let me first introduce myself, I am Pranav Choudhary, a 10th grader from Haryana(India). I like to do geo and combo the most :PP. Oki so let's begin! For those of you who don't know what bashing is, lemme give you a brief introduction first. Bashing is basically a technique used to solve Geometry Problems. In general, when you try a geo problem you might think of angles, similarities, and some other techniques (e.g. Inversion, spiral similarity etc). All of which are called synthetic geometry. But sometimes people use various other techniques called "bash" to solve the same problems.  Now there are different kinds of bashing techniques, e.g. - Coordinate bash, Trig Bash, Complex bash, Barycentric Coordinates. Let me give you a brief introduction to each of them.  Coordinate Bash : You set one point as the orig