Towards a theory for combinatorial games

5. Towards a theory for combinatorial games

There is a paradox to the study of games. From the players' point of view, if mathematics makes it possible to determine the winner of the game, and tell that winner what moves to make, the game is rather dull! On the other hand, from a mathematical point of view, it's an exciting challenge to analyze a game and possibly formulate a winning strategy. As a dividend of the mathematical analysis of combinatorial games, a rich collection of phenomena of interest in nearly all parts of mathematics has emerged, ranging from ideas in number theory, to graph theory, to combinatorics, to algebra.

Perhaps one of the most intriguing aspects of the study of games is that one can have descriptions of two games which sound very different but which amount to the same game when stripped of the story about the game; the two games are isomorphic (i.e. have the same structure). Here is an example:

The game in the diagram below is played by moving a single small black dot (checker) any number of squares to the left until it reaches a red wall.

Since this is a game with perfect information, there is a forced win for one of the players. Which player is that?

One could solve this game from first principles but it is easy to see that this game is really Nim in disguise. The first checker can be moved one, two, or three positions to the left, which corresponds to a stack of three stones, and one can make a move consisting of removing one, two, or three stones, while the other checker's moves correspond to having a stack of two stones. Nim and this game are isomorphic, that is, they have the same structure.

One of the most remarkable theorems concerning combinatorial games involves the issue of isomorphism. This theorem informally states the following:

All two-person (standard play) impartial combinatorial games of perfect information are Nim in disguise!

This statement grows out of what is often called the Sprague-Grundy Theory of impartial games. Roland Percival Sprague (in 1936) and Patrick Michael Grundy (in 1939) were mathematicians who independently developed a theory of solving impartial games. Unfortunately, because of what was going on in world politics at the time, their work did not get the attention it deserved until much later. In simple terms what they did was to show that one could take any impartial game and analyze it in terms of nim heaps which could grow or decrease in size. If one refers to a pile of stones (often called a heap) that either grows or diminishes in size (but where a player can reverse this move ) as a bogus nim heap then one has the following approach to (terminating) impartial games.

The Sprague-Grundy Theory of Impartial Games (though Sprague and Grundy did not formulate it in these terms):

Each position of an impartial game (standard play) is equivalent to a Nim position with bogus nim heaps. Once one has converted a game position to an equivalent collection of piles of stones (which can be moved using the rules of Nim), one can then find a nim-sum of these separate games. Using this sum, which gives the same answer as computing the nim-addition on the numbers of stones in each pile, one can find out whether or not one is at an N-position or a P-position.

The problem with Sprague-Grundy Theory is that it does not provide a fast algorithm for specific games to find the equivalent bogus nim heaps for each position. There may be many moves (exponentially many) on the way from the initial position to the terminal position. Since the theory requires that one may have to work backwards through all these positions to get to a particular position whose value (win or loss) one wants to know, the Sprague-Grundy Theory is not always practical. In practice, the theory boils down to looking at the structure of the individual game to enable one quickly to find the value of a particular position without going through all the positions that follow. This is what Bouton did for Nim!

To facilitate the analysis of a collection of nim piles it is convenient to formalize the idea of nim-addition, which gives a decimal number equivalent to the indicator of a nim position. If a nim pile of stones has n stones we will denote this by n. Furthermore, if we have two piles of stones of size n and m, we will denote by n m the decimal value of the indicator position for piles of this size. The special addition symbol used means that we convert n and m to binary, add them without carries (or one can interpret the calculation as being done in the algebraic structure known as a field which has two elements, e.g. GF(2)). Now change the result back to decimal notation. This process is called nim-addition, though there are other ways to carry out the process which are perhaps faster than the way I have described. Nim addition has some very nice algebraic properties. It obeys both the commutative law, a b = b a, and the associative law, a (b c) = (a b) c.

Here is a portion of the nim addition table. Remember that a b tells one the decimal value of the indicator value for a position of piles of stones with a and b elements.

This table has a variety of very interesting patterns. First note that a a = 0, and that the table breaks up into blocks of size 4 (when one includes a row and column for 0) which are symmetric with respect to the diagonal of the 4x4 subtables. To see this, however, one will have to extend the table. Remember that 0 n = n.

Very often it is unclear from the description of a combinatorial game whether or not the game really terminates. For Sylver Coinage, we had to use Sylvester's theorem to see this. For Nim, it is clear that the game terminates since each move reduces the total number of stones that can be removed in the future and, thus, eventually, the number of stones left must become zero. Therefore, the fact that heaps might grow in the analysis might seem to be a problem. Here is a variant of Nim that sets the stage for the insight of the bogus nim heap. Suppose that as one plays Nim one gets to keep the stones that one takes off the board, and at a given move one can can make a usual nim move or put some of these captured stones back into some specific pile of stones. One might also have an initial supply of such stones for each player that can be used for this purpose. This game is called Poker Nim. It may seem that the game requires a totally new analysis from the game of Nim. However, note that if you are looking at the nim heaps and know that you have a winning position, then if your opponent adds some stones to a heap, all you have to do to maintain your winning position is to reverse your opponent's action by removing the stones from the pile he/she added to and restore the pile to the size that existed before this delaying move. Thus, the analysis of Poker Nim can be easily reduced to that of standard Nim. This game shows the usefulness of allowing heaps to grow in the analysis of the game provided the consequence of this growth is reversible.

Finally, to fully appreciate the Sprague-Grundy Theory, consider the following perspective on playing Nim. Suppose that one has a collection of nim heaps. Think of each of these heaps as a separate game. Is there a way of thinking of making a Nim move in any one of these separate games as being equivalent to playing Nim on a single (bogus) heap? We are asking for a way to compute the sum of games which are nim heaps in terms of the size of these heaps. Suppose we use *a and *b to represent the game value of a nim heap with a stones and b stones, respectively. We will use the symbol + to represent the sum of these two games, which we will refer to as the nim-sum. Thus, *a + *b is the game value of the size of a nim heap equivalent to playing separate games of nim on piles with a and b stones. It turns out that the nim-sum of *a and *b is the same as the nim-addition a b. Thus, we can in essence use the addition table above to do our calculations. The size of the single heap, which is equivalent to a collection of heaps is called the nim-value of the given heaps. Suppose that two players are playing a game G where when it is a player's move, the player can move to one of the nim heaps *u or *v or *w, ..., or *z. It turns out that in this situation G can be regarded as the nim heap *n, computed using the mex rule on *u, *v, *w, ..., *z, where mex refers to maximum excluded value. Thus, *n will be the smallest non-negative integer not in the set {u, v, w, ..., z} (where we allow elements to be repeated). For example, mex {0, 2, 3, 4, 3, 8} = 1 while mex {1, 2, 3, 3, 3, 4} = 0 and mex {1, 0, 3, 4, 5, 6, 5} = 2. Note that playing the game consisting of the single heap *u in this framework, is the situation where each player has the moves *0, *1, ..., *(u-1). In games where one must make a transition to what seems like a complicated set of nim heap choices, the mex rule enables us to find a single heap (nim-value) equivalent to these choices.

To illustrate, consider the game called Kayles. A move in Kayles consists of knocking down a single pin or two adjacent pins in a row of bowling pins, with a single throw. Verify that for 0, 1, and 2 pin games the situation is equivalent to having heaps of size 0, 1, or 2 respectively. (For 2 pins we can knock down both pins or only 1 so it's like a heap of size 2.) For three pins, abc, with one throw we can leave ab, bc, a, c, or a c standing. Since mex does not change if a set has duplicate values, we need only find the equivalent nim heap sizes for ab, a, and a c. We know that ab is equivalent to *2 and a is equivalent to *1. What about a c? Using our knowledge of nim addition we can compute the value of the position a c to be 1 1, whose value is 0, which can be viewed as the heap *0. So what is the size of a single nim heap equivalent to Kayles played on a row of three pins? We need to compute the mex of {2, 1, 0} which is 3. Thus, this game is equivalent to playing Nim on the single heap with 3 stones, which has the value *3. For each length n of a row of pins one can use this approach to finding the size of a single nim heap (i.e. nim value) for the game. Unfortunately, for Kayles, the pattern at the beginning is erratic before one starts to see a periodic pattern to the nim values. This situation is not uncommon for impartial games. For some games, if there is a periodic pattern eventually, the pattern is not evident!

Although the game sum idea is a more general framework than nim-addition, nim-addition gives the same answers as nim-sum, and, in many situations, for impartial games (standard play), we need only concern ourselves with whether a position is a P-position (nim value 0) or an N-position (nim value positive).

1. Introduction
2. What is a combinatorial game?
3. Finding the winner of a game
4. Solving Nim
5. Towards a theory for combinatorial games
6. Towards the surreal
7. References