Impartial Games and How to Solve Them

Abstract: In this post, we introduce the concept of impartial games and give a few examples. Following that discussion, we look at the process of solving an impartial game with a relatively simply example. During this example, we introduce critical concepts to impartial game theory, those being P and N Positions

In a previous post, I introduced a couple of ways of classifying games. For a quick review, the terms introduced where deterministic, perfect information, and zero-sum games. Deterministic games are games in which there is no randomness, or games that will always end up with the same outcome if following the same set of actions. Perfect information games are games in which the entire state of the game is known to all players at all times. Finally, zero-sum games are ones in which one player causes the other player to lose if they win. At this time, I would like to introduce another classification for games, Impartial and partisan.

Impartial games are games in which the available moves a player can take, is only determined by the position of the game. More informally, impartial games are games where the only difference between player A and player B, is that player A goes first. An example will be given after this definition. On the other hand a partisan game is one which doesn’t have this behavior. Almost all commonly played games are partisan games. For example, take Chess. Chess is partisan because player A and player B play with a separate set of pieces, and are only allowed to move their pieces. Tic-Tac-Toe is also another partisan game, as players play with separate markers, and can only win if they create a three of a kind with their mark.

An example of an Impartial game, would be the following:
1.) The game has two players – A and B who take turns removing chips from a pile at the the center of the table.
2.) The pile starts with 23 chips, and players must remove 1, 2, or 3 chips on their turn.
3.) Players alternate turns, with player A starting the game.
4.) The player who removes the last chip wins.

This is an example of an Impartial game, because both players have no difference in terms of moves, win conditions etc. The only difference being that one player acts first. This game is also an example of what game theorists refer to as the normal play convention, which is essentially just the “standard” way of determining the winner of a game. For impartial games, that means the winner is the last player to make a move. One could also switch the winner/loser rule so that the player who is first unable to move wins. This is referred to as Misère play. For the rest of this post, we will be assuming we are playing games under the normal play convention.

Now that we have define are terms and the rules for the first game, we can figure out how to solve the game. To do so, we will start at the end of the game, also referred to as the terminal state, and work backwards. This process can also be referred to as backwards induction. Once we have reached the terminal state, the player who just moved wins. Working backwards we can then see that if player starts their turn with 1, 2, or 3 chips in the pile they can win by taking the whole pile. However, suppose a player starts their turn with four chips. That player will have to leave either 1, 2, or 3 chips for the next player, allowing them to win. This means that four chips is a loss for the next player to act. If a player starts their turn with 5, 6, or 7 chips they can have the other player start at 4, forcing a win. With 8 chips, a player must pass either 5, 6, or 7 chips, making it a loss for the current player.

This pattern of multiples of 4 being bad for the current player continues, as the other play continue to pass back a pile with a multiple of four. With this is mind, we can now fully analyze the earlier game. Since we are starting at 23, which is not a multiple of 4, the first can player can move into 20, and use the multiples of 4 strategy discussed earlier to force a win. As such, in this game, assuming optimal play, player A will always win.

Before moving on the next major topic, it should be noted that there is some relevant terminology glossed over in this introduction. That being P-Positions and N-Positions. Simply put, P-Positions are positions in which the previous player is able to force a win, and N-Positions are positions where the next players is able to force a win. Looking at the sample game introduced earlier, we can see that 0, 4, 8, 12… are P-Positions, and 1, 2, 3, 5, 6…are N-Positions.

Generally speaking, one could (theoretically) find which positions by are P-Positions and N-Positions by using the following algorithm:

This method is just a more formulized version of what we did in the earlier chip game. We can also use this algorithm to give a formal recursive definition of P/N-Positions.

We can also think about these definitions intuitively. Since all terminal positions are the end of a game, the previous player is considered a winner. In order for a position to a P-Position, the current player needs to have no way of putting themselves in the “driver” seat, as such all moves from a P-position must lead to an N-position. Finally, in order for a position to be an N-position, the next must player must be able to put themselves in the driver seat, as such they need to be able to move into a P-position.

It should be noted that not all play from a N-position will lead to a win for the next player, only that optimal play will.

Final Thoughts and Conclusions: With the algorithm and techniques discussed earlier, one is theoretically able to solve all impartial games. However, much like the minimax algorithm discussed earlier, doing so can be quite time-consuming and difficult. Finally, there is is also the issue of games which are not finite, in terms of possible states or possible moves. Generally when discussing impartial games, we use the following bound: There must be a finite number of operations and positions for both player. For example, in our discussed game, players may only take away 1, 2, or 3 coins from the stack. Combine this with the fact that the chip stack will always be finite and decided before play, the game cannot go on forever.

Additionally, their are numerous other techniques that have been studied to help aid in the analysis of impartial games, some of which will be looked at in a future post. One of the critical ideas that will be covered is that of the Sprague–Grundy theorem, and the Sprague-Grundy function, which are critical to this area of Game Theory.