Finding the winner of a game
3. Finding the winner of a game
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.)
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.
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.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance