Feature Column from the AMS

Finding the winner of a game

3. Finding the winner of a game

People who play games like to win. Is there a way of telling who will win a combinatorial game? Since the games we are looking at are games of perfect information, we know exactly what moves the first player can make and what responses the second player can make to each of these first moves, and so on. One of the earliest contributions to the study of combinatorial games is due to Ernst Zermelo (1871-1953), whose name is familiar to many in the mathematics community for his work on what has become the standard axiomatization of set theory, Zermelo-Fraenkel set theory.

One interesting idea that emerges from looking at combinatorial games is that such games might have the property that the first player could win no matter how well the second player plays, while other games might have the property that the second player could win regardless of how well the first player plays. Zermelo showed that for terminating two-player games of perfect information, either the first player has a winning strategy or the second player has a winning strategy. (Actually, the way Zermelo formulated his approach to games allowed for infinite games and draws, so his theorem was that either a game was a win for the first player, a win for the second player, or each player could play so as to force a draw.)

Let us use some geometrical thinking to understand better the idea of how one might design a way to play a combinatorial game which proceeds not from the perspective of "what move should I make now," but instead "how should I play that guarantees that if I can win, I will." Rather than be very abstract, consider the following game, which belongs to a family of similar games:

Subtract:

Rules:

Suppose that one is given a positive integer m which is at least 1, which you can think of as representing a pile of stones. Given this number, one can move by reducing the given number by either 1 or 3 as long as the result is greater than or equal to 0. The two players alternate. As usual if you can not move, you lose.

Suppose m =11. The first graph (diagram) we will draw has a dot to represent the start of play, and a vertex to represent every move that one can get to from the start. Now for each outcome of a possible move by the first player, we can draw all the possibilities for what can happen when the second player moves, and so on, until we reach a position where the game is either won or lost. The diagram we obtain in this way is a tree - it is connected and has no circuits. (Strictly speaking, perhaps one should use directed edges rather than edges because one can only move down on the diagram below.)

Game tree for subtracting 1 or 3 from a pile of 11 stones

The diagram, only partially completed, shows which moves each player can make at each stage of the game. The first row of dots (below the initial position dot) corresponds to actions of the first player and the second row of dots corresponds to possible responses that the second player can make. Positions from which no further move is possible in a completed diagram have the property that only one edge appears at the vertex of the tree in question. Furthermore, such vertices which are terminal positions in the game are indicated in blue here. If you are at one of the blue dots, and it is your move, you lose. This diagram has two problems. Some equivalent positions appear in two different places. For example, one can get to the number 7 by the first player subtracting 3 and the second player subtracting 1 or by the first player subtracting 1 and the second player subtracting 3. Furthermore, there are lots of vertices in the tree even for this very simple game. Drawing this diagram for many realistic games would not be practical. Nevertheless, the diagram is helpful in thinking about what is going on. However, for a simple situation such as the one here, one can determine who will win the game and the moves that are involved in achieving a win.

A different geometric diagram can also be looked at. In this type of diagram, each dot indicates a position which can arise at some stage of play by legal moves by the players. A directed line segment drawn between two dots means that it is possible for one of the players to move from the first position to the second. This diagram can be thought of as a positions digraph (short for directed graph) for the game. Terminal positions are labeled with a W, because the person who moves to these positions wins since the person who must move next has no move, and therefore loses. Now we work backwards from the terminal positions. We label with an L any vertex which has at least one edge coming into a W position. We label with a W any vertex which has the property that all edges from it lead to vertices labeled L. These rules capture the strategic implications from a non-terminal position as we move back through unlabeled moves. For the subtraction game starting with 11, and removing 1 or 3 stones, we get the digraph below:

Position digraph for subtracting 1 or 3 from a pile of 11 stones

The person who makes the first move must win. In fact, the first player wins no matter how badly the second player moves, though this is rarely true of games. Remember, the L and W denote that a person who has to move to a position with this label has arrived at a position which is losing (L) or winning (W), assuming his/her opponent plays optimally.

Note again that in many situations it is not practical to compute this digraph, though it typically has many fewer vertices than the game tree we drew first. Curiously, a successful mathematical analysis of a combinatorial game - that is, being able to tell before the start of play which player has a forced win and what moves the player should make to achieve this win - can rob the players of all the fun in playing! A complete analysis can also tell a player who knows that he/she can not win if the opponent plays optimally, how to exploit an opponent's mistake. Shortly, we will disclose the ingenious secret about how to completely analyze Nim, so try playing a few rounds of the game to either rediscover the solution for yourself or to gain perspective on the cleverness of the solution.