Nim is a two-person game of perfect information thought to be Chinese in origin. The game begins with a number of heaps of objects, usually coins or matchsticks. The players alternate moves by taking any number of objects from any single pile. The player making the last move is the winner. A Java applet to play the game is available here.

The winning strategy for Nim is attributed to Bouton (1902) and consists of expressing the heap sizes in binary notation and summing the digits of the same power of 2, modulo 2. A winning position is one where all digits of the reduced sum are zero. Each player therefore will attempt to remove objects from heaps in order to achieve such a position. Once a winning position is achieved by one player then the opposing player has no option but to adopt a losing position, that is, he is forced to move such that at least one binary column has a reduced sum of 1.

The solution identified by Bouton is easily implemented and in fact Martin Gardner (1959) mentions a number of mechanical devices constructed in the nineteen-forties and nineteen-fifties that played a perfect game of Nim. Most notable of these was the Nimatron, built in 1940 and weighing a ton. Nevertheless, the identification of an appropriate winning move may be formulated as an IP and provides a neat student exercise.

Formulation ni = number of objects in heap i before move h = number of heaps c = number of columns required for binary conversion Define variables as follows: si = number of objects taken from heap i mi = number of objects in heap i after move xi,j = binary representations of heap sizes after move di = 1 if heap i changed, 0 otherwise wi = dummy variables for winning position test

Minimize the number of heaps changed.

If the solution is zero then no winning move is available for the current position.

Convert heap numbers (after move) to binary.

Ensure safe position after move.

Ensure that heap sizes before and after the move are consistent with the move itself.

Dummy variables for each heap are set to 1 if heap is changed.

M is an upper bound on heap size.

Download Xpress-Mosel code to implement the model here.

Moore's Game

A modification of Nim proposed by E.H.Moore (1910) is where players may remove objects from up to k heaps in a single move.

As with standard Nim, heap sizes are expressed in binary notation and the digits of the same power of two are summed. The sums are reduced modulo k+1 and a winning position is where all digits of the reduced sum are zero.

Hence, the formulation to identify a winning move from a given position is identical to that for standard Nim except a winning position is ensured by:

Nim therefore is Moore's Game where k=1.

The Xpress-Mosel model above may be used to identify winning positions for Moore's game by changing the value of k.

Rosebushes

A further modification is where a single object may be removed from up to k heaps. This was proposed by Schuh (1968), embellished and investigated by de Carteblanche (1970,1974) and given further consideration by Berlekamp, Conway and Guy (1982) and Vajda (1992).

The game has not been fully investigated although solutions to a number of starting configurations are known. In particular, Vajda (1992) describes the progress of a game with 5 heaps and k=2.

Arrange the heap sizes in ascending order. Winning positions are odd-odd-odd-even-even, odd-even-even-odd-odd, even-even-odd-odd-odd and even-even-even-even-even.

An Xpress-Mosel model to identify winning positions for this configuration is here.

References

Berlekamp, E.R., Conway, R.H. and R.K. Guy (1982), Winning Ways for your mathematical plays - Volume 2: Games in particular, Academic Press.

Bouton, C. L. (1902), "Nim, A Game with A Complete Mathematical Theory," Annals of Math, Vol. 3, pp. 35-39.

de Carteblanche, F. (1970), "The Princess and the Roses," J. Recr. Math., Vol. 3, pp. 238-239.

de Carteblanche, F. (1974), "The Roses and the Princess," J. Recr. Math., Vol. 7, pp. 295-298.

Gardner, M. (1959), Mathematical Puzzles and Diversions, Penguin

Moore, E. H. (1910), "A Generalization of the Game Called Nim," Ann. of Math., Vol. 11, pp. 93-94.

Schuh, F. (1968), The Master Book of Mathematical Recreations, Dover.

Vajda, S. (1992), Mathematical Games and How to Play Them, Ellis Horwood

	To download a printable version (pdf) of this paper, click here. To download the Adobe Acrobat reader for viewing and printing pdf files, click here.
	To reference this paper, please use:  Chlond M. J. and O. Akyol (2003), "A Nimatron," INFORMS Transactions on Education, Vol. 3, No 3,  http://ite.pubs.informs.org/Vol3No3/ChlondAkyol/