Section 1.2 Combinatorial Games
Having seen one example of a combinatorial game, we are now ready to give a precise definition. We restrict our attention to impartial combinatorial games, where both players have the same possible moves from each position. Whenever we say "combinatorial game," or more simply "game," we mean an "impartial combinatorial game."
A (impartial) combinatorial game \(\cG\) satisfies the following conditions. There are two players. There is a set, usually finite, of possible positions of the game. The rules of the game specify which moves to other positions are legal moves. These are called the followers of the current position. The legal moves are determined only by the current position of the game (and do not depend on the player whose turn it is). If \(X\) is a game position, then we denote the set of its followers by The players alternate moving. The game ends when a position is reached from which no moves are possible. In other words, the position \(X\) has no followers, \(\cF(X) = \emptyset\text{.}\) Such a position \(X\) is called a terminal position. The last player to move wins. Or more precisely, the first player who cannot move loses! The game ends in a finite number of moves no matter how it is played.
Definition 1.2.1.
There are two parts of this definition that are worth emphasizing.
Fact 1.2.2.
The game is impartial because the legal moves only depend upon the current position, not on the current player.
In other words, the coins in Nimble are "gray" instead of being "black" or "white." This restriction excludes games like tic-tac-toe, checkers and chess. 1 Second, the victory condition is always the same:
Fact 1.2.3.
The last player to move wins.
This excludes games like Mancala and Go, where you accumulate points until the end of the game. Finally, it is crucial to note what else is omitted in this definition.
No random moves such as the rolling of dice or the dealing of cards are allowed. This rules out games like Backgammon, Poker and Monopoly.
A combinatorial game is a game of perfect information: hidden information and simultaneous moves are not allowed. This rules out Battleship, Poker and Rock-Paper-Scissors.
No draws are possible.
When analyzing a combinatorial game, it is useful to give names to the players. You might be tempted to call them "the first player" and "the second player." Or perhaps you might choose "Player 1" and "Player 2." However, during gameplay this becomes confusing. As we alternate moves, these numbers no longer correspond to which player is active for the current move. (That is, after Player 1's first move, Player 2 becomes the first player for the new position.)
| First move of the game | Second move of the game |
| Alice | Bob |
| Left | Right |
| Blue | Red |
We actually need two sets of names to distinguish the players. First, we want to give them absolute names that never change throughout the game. The names we will use appear in Table \ref{table:names}. Recently, Alice and Bob have become the conventional names for players, with Alice being the first to act in the game (because \(A\) precedes \(B\)). More traditionally, the players have been called Left and Right, with Left being the first to act (because we read from left to right). Blue and Red are also common names, sometimes written as bLue and Red to emphasize the connection to Left and Right.
Our second set of names is associated to the current position (rather than the actual player). The Next player is the person whose turn it is. The other player is the Previous player. We abbreviate these names as \(\cN\) and \(\cP\text{,}\) respectively. Since we use such fancy type, these symbols must be important!
Now that we have these two different ways to refer to players, let us look at the example play of Nimble shown in Figure 1.2.5. In this figure, we also describe the position as a multiset (a set where elements can repeat) where we list the locations of the coins in brackets. This more compact notation will be quite useful.
The game starts with three coins on square 3, represented by the multiset \(\{3,3,3\}\text{.}\)
Alice goes first in this game, so she starts as player \(\cN\) and Bob starts as player \(\cP\text{.}\) Alice moves one coin to square 1. The game position is now \(\{1,3,3\}\text{.}\) Bob becomes player \(\cN\) (because now it is his turn) and Alice becomes player \(\cP\text{.}\)
Bob sees that he can set up a Tweedledum-Tweedledee position by moving the coin at square 1 off of the board. The game position is now \(\{3,3\}\text{.}\)
Now Alice is player \(\cN\) again. She realizes that she will lose the game no matter what. She removes one coin from the board. The game position is now \(\{3\}\text{.}\)
Bob becomes player \(\cN\text{.}\) He copies her move. This brings us to the final (empty) board \(\emptyset\text{.}\)
Alice is player \(\cN\) and there are no valid moves. Therefore, Bob is the winner.