<![CDATA[Introduction to Combinatorial Game Theory, Part 2]]>

<![CDATA[Introduction to Combinatorial Game Theory, Part 2]]>Follow-up of the first part.

So, we know a couple of things about Hackenbush. We know a few outcomes: “Left wins”, “Right wins”, and “second player wins”. We’re missing one more: “first player wins”… What would “first player wins” be?

Consider $\{0|0\}$ . Here, whoever to move is forced to move to the zero game, which is a loss for the player to move. Thus here, the first player wins, as the second player loses. But what is its value?

This is not positive, as a positive value indicates that Left wins. Not negative either, as it means Right wins. Not zero too, since the first player instead of the second player is the one that wins! So this is not a number like our previous games are. Mathematicians call this $* = \{0|0\}$ , the star game.

But can a star game appear in Hackenbush?

As it turns out, no, it cannot! Hackenbush doesn’t allow star games. Thus to look at star games, we need to change games.

One possible approach is to make a variant of Hackenbush. The original Hackenbush is called Blue-Red Hackenbush, since it uses the colors blue and red. Let’s modify this into Blue-Red-Green Hackenbush, which adds edges of a third color, green, which can be removed by either player.

Thus, what is a Blue-Red-Green Hackenbush with a single green segment?

Exactly, it’s the star game. Whichever player to move must leave the zero game to the other player, thus this is $\{0|0\}$ .

We can analyze a few more positions here, but let’s turn our attention to another possible game that introduces stars… Nim.

In Nim, we have several piles, each containing some stones. In the position above, we have stones with 1, 3, and 6 stones; for convenience, we will call this position $(1,3,6)$ , so I don’t have to keep making images. The rules are simple: each player takes any number of stones from a single pile. Thus for example, a player might take four stones from the pile of 6, turning to the position $(1,3,2)$ , or they can remove the entire first pile, leaving $(0,3,6)$ . The winner, of course, is the player that makes the last move. Note that the only way to have no move left is if all stones are removed.

Here we see what’s called an impartial game, where the same moves are available to both players, compared to partisan game like Blue-Red Hackenbush where not the same moves are available to the players. (Note that in Blue-Red-Green Hackenbush, if the position contains only green edges (and thus the same moves are available to both players), it is also an impartial game.) Note that in an impartial game, there is no concept of “Left wins” or “Right wins”; only “first player wins” or “second player wins”.

First, as moves are available to both players, we can shorten our notation of a position: instead of repeating the same thing twice like $\{0|0\}$ , we’ll just do it once like $\{0\}$ . This makes it closer in notation to a set; but then again a position is simply a set of available moves!

Also, for convenience, let’s call $p_n$ to be a pile of $n$ stones. Thus the position above is $p_1 + p_3 + p_6$ . Note how two different piles never affect each other from the rules, hence why we can just assume they are separate games that are added together. You still remember game additions, no?

The simplest pile is $p_0$ , having no stone at all! This is clearly a zero game, so $p_0 = \{\} = 0$ .

The next simplest pile is $p_1$ . A pile of one stone is just like a position of a single green segment in Blue-Red-Green Hackenbush, with the only available move reducing to $p_0$ , or the zero game. So $p_1 = \{p_0\} = \{0\} = *$ .

What about $p_2$ ? What position is this? Listing out the moves, we get $p_2 = \{p_0, p_1\} = \{0, *\}$ … Uh oh, what is this? This is nothing we have encountered before.

Well, mathematicians also decide to just ditch it, making yet another notation. $*n$ is the value, called the nimber $n$ , which represents the value of $p_n$ , the pile with $n$ piles. So $0 = *0, * = *1, \{0,*\} = *2$ , and many more… We also see that the value for the position depicted in the image is $*1 + *3 + *6$ . Can we simplify this?

Let’s start analyzing a few things. What is $*0 + *n$ ?

Remember how zero games never affect additions? Yes, since $*0$ is just the zero game, the result is simply $*n$ . Thus $*0 + *n = *n$ . Also, of course, $*n + *0 = *n$ .

What about $*1 + *1$ ? Let’s list the moves. We can either move in the first game, reducing it to $*0 + *1 = *1$ , or in the second game, reducing it to… $*1 + *0 = *1$ . Well, either way, we’re left with $*1$ , so $*1 + *1 = \{*1\}$ . What is its value?

Well, since $*1$ is a win for the player to move, and the first player must move to that, we have the second player wins; in other words, $\{*1\} = 0$ . Or we can think in Nim piles: a Nim position with two piles, each of size 1. The first player must take one of the stones; note that they cannot take both. The second player must also take the remaining stone, but that means the second player wins.

Let’s try generalizing it. If we have $*n + *n$ , what is its value? Think in terms of Nim piles first; you have two equal-sized piles, who wins?

We can see that the second player wins. To see this, the second player simply mirror the first player’s move on the other pile, leaving both piles equal. If we start with $(5,5)$ , and the first player reduces the first pile to 3, then the second player mirrors it, reducing the second pile to 3 too, giving $(3,3)$ . If the first player then reduces the second pile down to zero, the second player also cleans up the first pile, leaving $(0,0)$ which is the zero game, as there is no move left. So first player loses. So $*n + *n = 0 = *0$ . This can also be proven by induction; if we have the result $*n + *n = *0$ for all $n < k$ , then we can conclude the same when $n=k$ too, proving the claim for all $n$ . Well, this addition is surely a weird thing…

Note how we had $\{*1\}$ from our discussion of $*1 + *1$ ? That is, a position having $*1$ but not $*0$ ? This is not our usual Nim pile, but turns out we can still simplify it. Let's generalize it. Suppose we have a position whose values are nimbers, but not necessarily in the form $\{*0, *1, *2, \ldots, *k\}$ for some $k$ . For example, $\{*1\}$ doesn’t have $*0$ . What is its value?

Suppose that our position $P$ includes $*0, *1, *2, \ldots, *(n-1)$ , but is missing $*n$ . Let's consider the game $P + *n$ . If the first player moves in $P$ , reducing it to $*k$ where $k < n$ , then the second player can move in $*n$ to $*k$ ; remember how a pile of $n$ stones can be reduced to $k$ stones if $k n$ ? Then the second player simply moves in the same game, reducing it to $*n$ , since $k > n$ and thus $*n$ is a move from $*k$ . And now $*n + *n = *0$ .

Thus we see the second player wins, and thus $P + *n$ must have been the zero game after all! This strongly suggests that $P = *n$ , since we know that $*n + *n = *0$ . As it turns out, we can prove that $P = *n$ indeed. Thus we know a rule: the value of any position whose available moves are nimbers is itself a nimber, equal to the smallest missing value of the available moves. Applying to $\{*1\}$ , as the smallest missing value is $*0$ , we have $\{*1\} = *0$ . Similarly, even though $\{*1, *2, *3, \ldots, *2015\}$ might seem to be such a wide array of moves, it is missing $*0$ , so it is still the zero game anyway. Additionally, this fits with what we know: $\{*0, *1, \ldots, *(n-1)\} = *n$ follows the rule too!

So, armed with this, let’s return back to addition. What is the value of $*1 + *2$ ? Listing its moves, we have $\{*0+*2, *1+*0, *1+*1\} = \{*2, *1, *0\}$ . So $*1 + *2 = *3$ . And then, we also have $*1 + *3 = \{*0+*3, *1+*0, *1+*1, *1+*2\} = \{*3, *1, *0, *3\} = *2$ . Well, this will be hard.

A relatively nice method for a human to compute the sum is to make a table of addition. For convenience, let’s assume the rows are ordered in ascending order from top to bottom, and so as the columns from left to right.

The above has been partially filled with what we have known.

Now pick a cell we want to compute, look on all cells above or to the left of our cell (but not both!), and find the smallest missing value.

Yes, keep doing this.

If you know the XOR operation, the table is precisely that. We can prove that it is indeed the case, but for now we’re satisfied enough with having a table.

Thus, to compute $*1 + *3 + *6$ , we can just use the table:
$*1 + *3 + *6$
$= *2 + *6$
$= *4$

What if we want to find a winning strategy for Nim? For example, who wins the above? Since $*4$ is a win for the first player to move (the first player moves to $*0$ ), the first player wins. But what move?

We know that $(*1 + *3 + *6) + *4 = *0$ . Now we try adding each of the piles with $*4$ and see which one reduces the count. For example, $*1 + *4 = *5$ , so we cannot move on the first pile, as we would need to add four stones to it instead of removing stones. $*3 + *4 = *7$ , so it doesn’t work either, but $*6 + *4 = *2$ , so we can move in the third pile, reducing it to 2 stones. We can show that there always exists one such pile as long as the original value is not $*0$ , so there’s always a winning strategy for the player not having $*0$ .

Well, that was math heavy, wasn’t it? But you still need to be prepared. The third part, and the final part of the series for now, will walk you through the game induced by my Monorail move (put 1-3 tiles that are contiguous in a straight line and stuff).

]]>