Combinatorial games and Nim

Based on the most recent posts it seems that my blog in transforming into a learning diary on game theory. Because I started this blog as a tool for self-reflection, this change is by no means bad. It might even prove that I have found an area I am passionate about and wish to pursue even further.

In the beginning of July I finished the Open Yale course on game theory and was looking for new material on game theory to study further. I considered buying the course book by Mr. Dutta, but found Mr. Thomas S. Ferguson’s book on game theory as a free Internet version and decided to continue from there.

Mr. Ferguson’s books starts with an introduction on combinatorial games , and on impartial games in specific, something that was not included in deep detail in the Yale Course, so this book seems to have a different approach to the subject. I have started studying combinatorial games in the book and the first exercises have been quite nice, requiring some elementary skills in proving mathematical formulae. Below I introduce one example from the exercises and my work on it, a couple of weeks old now. But first I give a brief introduction on Nim

Nim

Nim is a combinatorial game where two players take turns in removing objects from a given set. In the easiest variation of the game, there is one pile of sticks and each player must remove at least one stick, while the amount of removed sticks may not exceed a predefined maximum. The possible amounts that may be removed from the pile form the subtraction set S. E.g. if one, two or three sticks are permissible moves, then S = (1, 2, 3). Under the normal play rule, the person to remove the last stick wins.

In a game of Nim the winner is decided by the initial amount of sticks and the order, in which the players start the game, presuming that the players play optimally. In Nim there are so called P- and N-positions in the game. These correspond to the number of sticks remaining in the pile after the last move. A P-position is such, that the player who moved previous to the current position, is winning. An N-position is such that the player to move next is winning.

Before going into the general case, a brief example should illustrate the P- and N- positions. As shown in figure 1, we have a game of Nim starting from a pile with 9 sticks and S = (1, 2, 3). Since the player to take the last stick wins, the terminal position (zero sticks left in the pile) is a P-position, since the player who will have moved previously will win. Due to S = (1, 2, 3), positions where there are 1, 2 or 3 sticks left in the pile are N-positions, since the player to move from those positions, or the next player to move, can reach zero and win. Likewise, 4 is a P-position, since from this position a player can only move to positions 1, 2 or 3, thus not being able to win, but leaving the next player in a position to win, should he play optimally. Working backwards to the start position of this example, we see that who ever starts can always win by removing one stick and moving to 8, which is a P-position.

Formally, P- and N-positions are defined recursively as follows:

1. The terminal position is a P-position.
2. A N-position is such that there is at least one possible move into a P-position.
3. A P-position is such that from it is possible to move only into an N-position.

The definition of P- and N-positions contains a noteworthy subtlety. From an N-position a move into at least one P-position is guaranteed, but there are also potential moves into further N-positions. Thus being in an N-position does not guarantee winning the game with any play, but a win is guaranteed, if the player in the N-position plays optimally, that is, moves to the available P-position.

A slightly generalized version of Nim

I will prove the general formula for finding the P-positions in a simple one-pile Nim under the normal play rule.

Let the initial number of sticks in the pile be N and let S = (1, 2, …, n), where S has no gaps in it, i.e. for all members of S s(i) it is true that s(1) = 1 and s(i+1) = s(i) + 1 for i = 2, 3, …, n-1.

Since the terminal position is the final and winning position, it is a P-position. Into this position we can move from any position ≤ n. I claim that the P-positions in this variant of Nim are given by the formula p(k) = (max(S) + 1)*k, where k = 0, 1, 2, … The proof follows by induction.

For k = 0 we get p(0) = 0, which is the terminal position, so the formula holds for k = 0. Now I will show that if the formula holds for some k = m, then it also holds for k = (m + 1).

Let us assume that the formula holds for k=n. Then we have a P-position p(m) = (max(S) + 1)*m = (n + 1)*m.

For (m + 1) we get a potential P-position p(m + 1) = (max(S) + 1)*(m + 1) = (n + 1)*(m + 1) = (n + 1) + (n + 1)*m.

Position p(m) can only be reached by removal of sticks from positions that are below p(m + 1) since p(m) + max(S) = n + (n + 1)*m < p(m + 1) = (n + 1) + (n + 1)*m. On the other hand, the mentioned positions can all be reached by removal of sticks from position p(m + 1), since p(m + 1) – max(S) = 1 + (n + 1)*m, and this is the last position before p(m), which is a P-position. Thus by the definition of P- and N-positions, when p(m) is a P-position, so is also p(m + 1), and the positions between these two are N-positions.

Since the proposed formula holds for case k=0 and it also holds for p(m + 1) when it holds for p(m), the formula holds for the general case p(k) q.e.d.

In conclusion, for single-pile game of Nim under the normal play rule, starting with N sticks and with S = (1, 2, …, n), the P-positions are

p(k) = (max(S) + 1)*k, where k = 0, 1, 2, …

Obviously we also required that p(k) =< N for all k.

The first player to move will win the game with optimal play if and only if   N ≠ p(k) for all k. Otherwise the second player to move will win, if he plays optimally. This can be proven quite easily. First we define optimal play as such, that a player will move from an N-position into a P-position, whenever possible. By definition then, optimal play is such that the player will win, if he gets to move first in a game starting from an N-position. Thus, the first player will win with optimal play, if he gets to start from a N-position. Conversely, if the first player wins after starting from N-position he must have played optimally, presuming that player two also plays optimally. Otherwise, at some point in the game, player one would have moved from an N-position into another N-position, leaving player two the possibility to move into a P-position and consequently win the game. Therefore, as stated before, when both players play optimally, the player who starts will win if and only if N ≠ p(k) for all k.