How to Be a Player: Impartial Combinatorial Games

Section 1.3 Game Trees

Look back at the example games in Figure 1.1.2. Positions 1, 3 and 4 were Alice-win and positions 2 and 5 were Bob-win. Of course, these characterizations assume that Alice and Bob use optimal play, meaning that they do not make inadvertent mistakes that cost them the game. We say that Alice has a winning strategy for positions 1, 3 and 4, and that Bob has a winning strategy for positions 2 and 5.

Mathematicians don't actually use the terms Alice-win and Bob-win. Instead, they use the Next and Previous terminology.

Our first observation is that any game position is either an \(\cN\)-position or a \(\cP\)-position. There is no ambiguity about who the winner should be, assuming optimal play. Indeed, there is no randomness in a combinatorial game, so a player cannot be defeated by bad luck. Also, there is no hidden information, so the player cannot be foiled by a lack of understanding of the current state of the game. Just like tic-tac-toe, a combinatorial game can be mastered. Ultimately, the fun of a combinatorial game is the process of discovering the optimal strategy.

Given a game position, how do we decide whether it is an \(\cN\)-position or a \(\cP\)-position? One powerful tool for resolving this question is a game tree. In this tree structure, we list all possible ways for the game to play out.

Figure 1.3.2 shows a game tree for the Nimble position \(\{1,3 \}\text{,}\) where once again we use the more compact multiset representation of a Nimble position. The root of this tree is labeled by \(\{1,3 \}\text{.}\) This root has three children, corresponding to the follower positions \(\{ 3 \}\text{,}\) \(\{ 1 \}\text{,}\) \(\{ 1, 1\}\) and \(\{1,2\}\text{.}\) The tree continues branching downward until we reach \(\emptyset\text{,}\) which signifies the end of the game.

Next, we add the symbol \(\cN\) or \(\cP\) next to each position, according to the outcome of the game (under optimal play). This is shown in Figure 1.3.3. We know that \(\{ 1, 3 \}\) is an \(\cN\)-position because Alice can set up the Tweedle position \(\{ 1,1\}\text{.}\)

Figure 1.3.3 shows that this is the only winning move for the Next player: all other moves lead to \(\cN\)-positions and Bob gets to play from this position. Having a winning strategy means that there is at least one winning move. We have observed the following general fact:

This fact simply points out that if the game is in a winning position, then there must be at least one move that puts the game into a losing position. We can devise a complementary condition for \(\cP\)-positions. In Figure 1.3.3, some \(\cP\)-positions mark terminal positions in the game, where there are no valid moves. As for the other \(\cP\)-positions, each one has a single follower that is an \(\cN\)-position. More generally, we have the following fact:

This fact simply says that if we are in a losing position, then regardless of the next move, the game must be placed into a winning position. Note that the statement above is still true when there are no valid moves: the set of followers is empty, so the statement "every follower of a \(\cP\)-position is an \(\cN\)-position" is true vacuously. Figure 1.3.7 shows the game tree for the losing Nimble position \(\{ 2, 2\}\text{.}\) This starting position has multiple moves, each of which places the game into a winning position for the opponent.

These two rules partition the set of game positions into two sets. This partitioning is so important that it leads to our first theorem. We can actually characterize the \(\cN\)-positions and \(\cP\)-positions via this partition!

This theorem encapsulates the following remarkable fact: there is only one way to a partition of the set of game positions into two sets that satisfy these conditions. If we can find such a partition, then we have in fact found the \(\cN\)-positions and the \(\cP\)-positions.

Don't be fooled by the fact that this proof is so short. This is a powerful theorem that is the backbone of all the results that follow!

This brings us to one of the most useful observations in this section. We can use the game tree to recursively determine the \(\cN\)-positions and the \(\cP\)-positions.

We start with the leaves, which correspond to games with no valid moves. Therefore, all of the leaves are \(\cP\)-positions by Rule 2. Next, we consider positions whose followers are all leaves. These are \(\cN\)-positions by Rule 1.

We continue in this manner, dealing with positions whose set of followers have already been labeled. Eventually, we are able to label all the game positions in the tree (including the root position). Figure 1.3.8 shows this process in action for the game tree of some unknown combinatorial game.

There is no denying that this method is a brute force approach, and it is time consuming. Indeed, we enumerate every possible move for every possible position (regardless of whether we think it is a good choice). Therefore, game trees can become unmanageable quite quickly. However, for small games, constructing a game tree can be very useful.

In order to develop a winning strategy, you must understand what constitutes good moves and bad moves. A game tree is a methodical way to identify game positions that are winning or losing. Once you have a sense of these categories, you can start to think about more complicated starting positions, and then formulate a broader strategy for the game at hand.