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.
= number of objects in heap i before move
number of heaps
number of columns required for binary conversion
= number of objects taken from heap i
= number of objects in heap i after move
= binary representations of heap sizes after
= 1 if heap i changed, 0 otherwise
= 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.
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.
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.
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.
reference this paper, please use:
Chlond M. J. and O. Akyol (2003), "A Nimatron," INFORMS Transactions on Education, Vol. 3, No 3,