Winning at the Game of Nim

Note: If you want to cut through all this confusing math and just learn how to play the Fruit Game (Nim), see our new How-To Page which gives you the lowdown on beating the computer every time.
The Fruit Game is really an old game known as Nim. We often get mail from programmers and students who are interested in writing their own Nim software on a variety of platforms.

To implement the game with a constrained range of starting positions (e.g., exactly 3 piles of no more than 7 objects each) it is probably easiest to implement the algorithm using heuristics. The original Fruit Game calculated the winning moves by simply trying to reduce the piles to a known 'winning combination' which was predefined by the author. E.g., if you can reduce the piles to 1-1, 2-2, 1-2-3, or 1-4-5, you win.

However, to solve the general situation (N piles of objects of unlimited size) you need to use more complex techniques.

A very thorough discussion of this type of game is found in Alan Tucker's excellent Applied Combinatorics (1984, John Wiley & Sons). On page 404, Mr. Tucker writes:

In this section we extend the theory of progressively finite games to takeaway games involving several piles of objects. The simplest game of this form is called Nim, a game in which two players take turns removing any amount they wish from one of the piles. The winner is the player who removes the last object from the last remaining (nonempty) pile. While the positions in [the previous sections] could be described with a single nonnegative integer representing the size or monetary value of the single pile, the position in a Nim game requires a vector of nonnegative integers (p1, p2, ... ,pm), the kth number pk representing the current size of the kth pile.
Mr. Tucker's final conclusion for winning Nim:
We now generalize the method of finding a vertex with Grundy number 0. ... Form a digital sum table for the current game position. Pick a row e with a 1 in the leftmost column having a 1 in the sum row. In row e, change the digit in every column having a 1 in the sum row, that is, in every column with an odd number of 1's. After this change of digits, every column will have an even number of 1's and the sum row will be all 0's. So this new position will be a kernel vertex. Note that since the leftmost digit that is changed in row e is a 1 (this is how row e was chosen), changing digits in row e will yield a smaller number, call it h. The first player should thus decrease the size of the eth pile to a size of h objects.
To apply this algorithm, you must understand what a digital sum is:

The digital sum c of nonnegative integers
c1 + c2 + c3 + ... + cm
is computed in the following manner: Let cik be the kth binary digit in a binary expansion of ci, that is, ci = ci(0) + ci(1)2 + ci(2)22 + ..., and similarly let c(k) be the kth digit in a binary expansion of c. Then c(k) = c1(k) + c2(k) + ... cm(k) (modulo 2). That is, the kth binary digit of c is 1 if the sum of the kth binary digits of the ci's is odd, and 0 if the sum of the kth binary digits of the ci's is even.
[p 406]

An example is in order. Suppose you have 4 piles, containing 2, 3, 4, and 6 objects respectively. The first step is to make a table where the number of objects are described as binary numbers:

  22=4 21=2 20=1
2 oranges= 0 1 0
3 peaches= 0 1 1
4 lemons= 1 0 0
6 bananas= 1 1 0
digital sum... 0 1 1

The digital sum in the last row is simply a 0 for all columns with an even number of 1's, and a 1 for all columns with an odd number of 1's.

The 21 column is the leftmost column that has a 1 in the digital sum row, so we must change a row with a 1 in the 21 column. (When we say 'change' we mean to turn all 0's into 1's and vice versa.) Suppose that we choose the first row (oranges). Then, since the 21 and 20 columns in the sum row have 1's, we change the digits in these columns in the first row. The new first row is "0 0 1"--therefore, the player should reduce the size of the first pile to 1. Note that sometimes, as in this example, there are more than one possible winning move. For practice, try to determine the correct number of peaches to remove.

Back to the Fruit Game