What is a combinatorial game?
2. What is a combinatorial game?
Like the games you are most familiar with, combinatorial games have players, moves, rules, and winners or losers. In fact, here already we are departing from some games you know like chess, which do not always have a winner. The games we are interested in can not end in a draw. (Chess is clearly an interesting game, so combinatorial game theorists also extend what they think about to include games where draws are allowed.) Since sometimes it may not be easy to see that the game can not end in a draw, this immediately sets a mathematical challenge: to prove that there is a winner in a given game. Although combinatorial style games can have more than two players or only one (solitaires), we will restrict our attention to games with only two players. Furthermore, we will be interested in games which do not go on forever. Since the games that interest us can not end in a draw or last forever, one player wins and one player loses. It will turn out that there is a staggering variety of combinatorial games and because this is a rapidly evolving area of mathematics, the terminology used in the discussions of combinatorial games is not yet etched in stone. However, one notion being pushed by John Conway simplifies talking about the rules of combinatorial games, and so deserves to become standard terminology: In a given combinatorial game, IF YOU CAN NOT MOVE, YOU LOSE! Another way to put this is that a player who makes the last allowed move wins. We will adopt this convention here and refer to this as the standard form (standard play) of a game. Not surprisingly, one could also adopt the convention: If you can not move, you win. For a given game, the new game which results from adopting the "if you can not move, you win" convention is historically called the misère form of the original. Typically, but not always, it is much more complicated to analyze the misère form of a game rather than the standard form.
A few more remarks are in order concerning the taxonomy of games. One of the major services that mathematics typically performs for any area it investigates is to provide a taxonomy of the domain being studied. Games can be classified according to the number of players, according to whether or not a draw can occur, etc. Many games you are familiar with (e.g. chess, checkers) have pieces that can only be played by one of the players. For example, we can call the players red and blue, and one player plays only the red pieces, and the other player plays only the blue pieces. The games we will study here do not have pieces that are played by a particular player. At each play of the game either player can, so to speak, move any of the pieces. Games of this kind are sometimes called impartial games, while games where a player has his/her particular set of pieces are calledpartizan games. Another important aspect of games that you are most familiar with (e.g. bridge, poker) involves chance. No matter how much skill you have as a bridge player, if you get a poor hand, you will not win that particular round of the game. The games we are discussing do not involve chance. Rather, at each stage of play, each player knows exactly what he/she can do and exactly how his/her opponent can respond to his/her actions. Such games are often referred to as games of perfect information.
Here are some examples of impartial combinatorial games you might enjoy playing with a friend:
Start with a collection of piles of stones. A player's move is to pick a pile of stones and select one or more stones to remove from the pile.
(Remember that you lose Nim when you can not move.)
Movie aficionados will recall that Nim is played in Alain Resnais's movie Hiroshima Mon Amour. If you would like to play Nim online, here is one place to do so. The game has many variants. Nim will be discussed in detail shortly.
Slither is played on a rectangular array of dots. A move consists of taking a pair of dots and joining them in such a way that the resulting subgraph is a path. If a player can not move, he/she loses.
The diagram above shows a Slither position on a 3x5 board. The next player has three legal moves: from the left hand endpoint of the path add a down segment in the vertical position, or from the right hand endpoint of the path add a segment in the vertical position up or down. Playing Slither on a rectangular array of dots is an appealing game, but one can generalize the game to play on any graph, where each player tries to continue to create a path using edges that are in the graph. (Thought of this way, Slither as described above is played on the m x n grid graph.) Slither was introduced by David Silverman and like many combinatorial games was treated by Martin Gardner in one of the columns which he used to write for Scientific American and which serve as the basis for many of his books. At the time that Gardner wrote about the game it was not solved, but - partly due to his column - eventually William Anderson, going beyond work of Ronald Read, developed a solution to a generalized version of Slither based on the concept of a matching in a graph.
John Conway invented this game which involves positive integers. The reason for the peculiar spelling of silver is to honor James Joseph Sylvester (1814-1897). Players alternate picking different numbers but one can not pick any number which is the sum of numbers that have been picked previously. For example, if 5 and 7 have been picked, one can not pick 5, 7, 10, 12, 14, 15, or 17 (among other numbers) on a future move. Adopting standard play here would lead to an uninteresting game since the first player would always win by picking the number 1. Thus, Sylver Coinage is a misère game: the winner is the person who does not pick 1.
Consider a few examples of the play of Sylver Coinage. Suppose the first player picks 100, the second player 99, the first player 98, etc. until 1 is reached. So in this example, the sequence of moves defines a win for the first player. The game went on for 100 moves. We could have started our sequence with 100000, 99999, etc. and the game would have gone on for 100,000 moves. It is tempting to believe that the game might go on forever, that is, that for any sequence of choices of moves there would always be a number different from 1 that could be picked which was not a sum of numbers already chosen. However, Sylvester proved a nifty theorem whose generalization can be used to show that though this game might go on for a very many moves, it can not go on forever.
Given two positive integers, a and b, a positive linear combination of a and b is a number Z = xa + yb where x and y are positive integers. For example, some positive linear combinations of 5 and 9 are 14, 19, 23, and 24. The greatest common divisor of a and b is the largest integer which divides both a and b. The greatest common divisor of a and b is denoted gcd(a, b). Gcd (5, 9) = 1. Sylvester looked at the question of finding the largest multiple of d = gcd(a, b) which is not a positive linear combination of a and b. For example, for 5 and 9, the gcd of the numbers is 1 and the largest multiple of 1 not expressible as a positive linear combination of 5 and 9 is 31. (Check for yourself that 32 is 3(9) + 5 and all integers larger than 32 can be expressed in the form 5x + 9y.) Similarly, given 10 and 14, 116 is the largest multiple of 2 (the gcd of 10 and 14) which can not be expressed in the form 10x + 14y.
The general result of Sylvester is:
If d = gcd (a, b) then ab - a - b is the largest multiple of d which can not be expressed in the form ax + by where x and y are positive integers.
Now we know that Sylver Coinage is a combinatorial game in the sense we have been discussing, namely, that it terminates. However, Sylver Coinage, like many misère games, is still not fully understood. Many unresolved questions about the game remain.
Many interesting combinatorial games have been known for a long time and interesting new games surface regularly. Perhaps you can invent a new game that will be appealing!
What is a combinatorial game?
Finding the winner of a game
Towards a theory for combinatorial games
Towards the surreal