Combinatorial Games

The focus of my academic research paper is going to be game theory, and in particular the theory of combinatorial games. Game theory is a branch of applied mathematics used extensively in the social sciences, most notably in economics. Formally, “Game theory studies the behavior of rational players in interaction with other rational players. Players act in an environment where other player’s decisions influence their payoffs.”(Eichberger) In this case, “rational” refers to the standard economic assumption that individuals act to maximize their utility, usually in the form of maximizing their payoff. Games are often used to model markets with a few participants, as the decision of one participant often depends on the decisions made by others. In a game, each player has an available set of strategies. In Game Theory for Economists, Eichburger writes, “A strategy is a complete plan for how to play the game. ‘Complete’ means in this context that for any contingency the plan must specify what the player would do.” Thus a strategy specifies a reaction for any possible situation that could arise in a game. Games are solved by finding an equilibrium strategy for each player, that is a strategy that maximizes the payoff of each player, taking into account the decisions made by others.

It is common to make a distinction between pure and applied mathematics, and the traditional game theory that I have described falls squarely into the applied category. However the combinatorial games that this paper will focus on have very little in common with traditional economic games. Rather than modeling real life situations, combinatorial game theory uses mathematics to search for solutions of games in the common sense of the word, such as Chess or Go. Players in combinatorial games are, in a sense, trying to maximize their payoffs. In this case, however, the payoff consists of either winning or losing. Combinatorial games are sequential games with perfect information. This means that players take turns making moves, and at any given time all players are aware of the moves available to the other players. Outcomes depend strictly on the rules of the game and the decisions made by players. There is no randomness or element of chance. The nature of these conditions allows for elegant solutions, often with results of great interest to pure mathematicians. One such result is construction of the surreal numbers, the largest possible ordered field. (Conway) This was motivated by studies of Go.

For the sake of simplicity, it is assumed that the games consist of a finite number of turns. Combinatorial games can be further classified into partisan and impartial games. In an impartial game, all players have the same set of moves available to them for a given position. This restriction is lifted for partisan games. (Demaine) Chess, for example, is a partisan game as each player has his own pieces that he can control. The emphasis of this paper is going to be on impartial games. In a impartial game, the winner is determined by the last player to make a move. In normal play, the last player to move is the winner. If the last player to move loses, it is known as miserè play. While games are often played miserè, normal play is more commonly used in theory, as it allows for much more conclusive results. One such result is deeply related to the game of strategy known as Nim.

Nim is a simple two player impartial game. At the beginning of the game, the players are presented with any number of objects. These objects are divided between one or more piles, known as heaps. The players take turns removing objects from the heaps. They may remove any number of their choice, with the requirement that they remove at least one object per turn and all objects removed must come from the same heap. (It is understood that in the case of a single heap game, the first player may not remove all of the objects in the first turn.) Under normal play, the last player to remove an object wins. This begs the question, do either of the players have a strategy that will guarantee victory every time? The answer is “yes!”, as was discovered by Charles Bouton back in 1901. In his paper, “Nim, the Game with a Complete Mathematical Theory”, Bouton demonstrates that one player has the ability to turn the game completely in his favor, provided he makes the right move each turn. (Bouton) Essential to this solution is the concept of a safe combination. For each of the heaps on the board, the number of objects in each heap can be represented as a binary number. Bouton defines a sort of addition on these numbers, often referred to as the nimsum. To calculate the nimsum, each bit of the number is added to the corresponding bit of the other number(s) being added, mod2. For example if we use “+” to mean the bitsum, 1001 + 1111 = 0110. If we imagine these binary numbers in a column, each column with an even number of ones is assigned the value “0” and each column with an odd number of ones is assigned the value “1”. If the nimsum of all of the heaps is equal to 0, it is known as a safe combination.

Bouton proves that if a Player A is able to leave player B with a safe combination, then Player A will win the game, provided he does not make any mistakes. A safe combination can be formed by removing the correct number of objects from the largest heap, until the nimsum of all of the heaps is equal to 0. In the case of two heaps, this is equivalent to making the heaps equal in size. Bouton shows that a game with a safe combination present cannot be made into a safe combination, however any other combination can be made safe. Thus if Player A is able to establish a safe combination, he will be able to do so after each of Player B’s turns, until Player A removes the last object and wins. Thus if the initial setup of the game is not a safe combination, Player A can make it safe in the first move and guarantee himself a victory. If the initial setup is safe, this option is then reserved for Player B. To visualize this, imagine a game of Nim with two heaps. One heap contains three objects, the other two. The first player can create a safe combination by removing one of the objects from the heap containing three, leaving two objects in each heap. The second player can either remove one or both objects from one of the heaps. If both objects are removed, the first player can remove the whole other heap and win. If one is removed, the first player can remove an object from the other heap, creating another safe combination. As two, single-object heaps are remaining, the second player may only remove one of these. It is clear at this point that the first player wins.

The importance of Nim comes into play with a result known as the Sprague-Grundy theorem. The Sprague-Grundy theorem states that any impartial game under normal play is equivalent to some single heap game of Nim. (Demaine) What do I mean by equivalent? For any two games, G and H, we can define their sum, G+H, as a new game where the players may choose to move in either G or H each turn. Thus two games, G and G` are said to be equivalent if and only if for any game H, G+H = G`+H. The particular game of Nim that some game may be equivalent to is known as a nimber. For example, the nimber *7 refers to a game of Nim with a single heap containing 7 objects. An interesting consequence of this theorem is that the concept of safe combinations can be generalized to other impartial games. If the player whose turn it is can leave a safe combination, that player is said to be in a winning position. This is also known as an N-game, with the ‘N’ referring to the next player being in the winning position. (Notice that in this case, “game” refers to the current position rather than the game as a whole. This is OK, as each position within a larger game is equivalent to some smaller game with the second player now going first.) The opposite situation is referred to as a P-Game, with the previous player being in the winning position.

The Sprague-Grundy theorem allows us to consider any impartial game as equivalent to some variation of Nim. There are several such games that can be considered. One example can be found in the article “Take Away Games” by Allen J. Schwenk, who explores games where the number of objects one is allowed to remove is dependent on the amount removed in the previous turn. Even in this specific subclass of games, there are plenty of variations. Over the coming weeks, I hope to explore as many variations as I possibly can, looking for unanswered questions and possible avenues for original research. I very much look forward to sharing my results as this project progresses.