Cut The Knot!

An interactive column using Java applets
by Alex Bogomolny

The Hot Game of Nim

May 2001

According to M. Gardner, Nim is one of the oldest and most engaging of all two-person mathematical games known today. The name and the complete theory of the game were invented by C. L. Bouton of Harvard University about 100 years ago. S. Schwartzman traces the possible origin of the word to the German verb nehmen "to take", with an imperative singular form nim.

Players take turns removing objects (counters, pebbles, coins, pieces of paper) from heaps (piles, rows, boxes), but only from one heap at a time. In the normal convention, the player who removes the last object wins, in the misère convention the player to move last loses.

Bouton's theory based on the binary representation and digit counting is wonderfully simple and has been explained in any number of places, see for example the Theory part at the JavaScript implementation. Express the number of objects in the heaps in binary and see to it that after your move the total number of non zero digits in any place value is even. Plainim is the most revealing variant of Nim that obviates the first step of finding binary representations. Above and beyond the theory of the game, Nim serves as an attractive playground for mathematical reasoning, the best example of which can be found in the recently republished Excursions into Mathematics by A. Beck, M. N. Bleicher and D. W. Crowe.

In Nim, there are positions that one would like to leave after one's move, and there are other positions that a player would like to face when called to move. There are differences in terminology with different intuitions to support each. Beck, Bleicher and Crowe [Excursions, p 340] call a position winning, if the player who goes first may force a win. Hardy and Wright [Hardy, p 118], on the other hand, call such a position losing, as one may wish to leave it to the opponent to struggle with. In partisan games, WW and ONAG call positions in which each player is eager to make a move hot. Positions that do not enthuse a player to move are naturally cold. Although all impartial games have temperature of zero, I think the terminology applies nicely in that case also. The usual practice in impartial games is to call a hot position N-position (advantage to the next player) and a cold one P-position (advantage to the previous player).

Let Nim be played with three heaps of objects. Let (a, b, c) describe the position of a objects in the first heap, b in the second, c in the third. Beck, Bleicher and Crowe lead the reader to the winning strategy of Nim through a series of lemmas, corollaries, and theorems. For example, (1, n, n+1) is hot iff n is odd (Lemma). Or, if (a, b, c) is cold, then so are (2a, 2b, 2c) and (2a+1, 2b+1, 2c) (Theorem), and so on. Except for the final result, the proofs only require common sense and familiarity with mathematical induction.

In 1930s, R. P. Sprague and P. M. Grundy developed a theory of impartial games in which Nim played a most important role. For this role, Nim was redressed as its bogus relative in which heaps may be enlarged, provided safeguards are set up to insure that the game terminates after a finite number of moves. The additional moves are known as reversible because their effect may be reversed on the next move. Northcott's game is one incarnation of Bogus Nim. The applet below presents another.

In this game, chips can be dragged leftward to any unoccupied position, except that moving over other chips is forbidden. Relation to Nim may not be immediately obvious, but, as a matter of fact, the lineage is surprisingly short.


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


Down the line, we find the Silver Dollar game invented by N. G. de Bruijn. The difference with the above game is twofold. First, there is now one special chip - a Silver Dollar. The purpose of the game is to gain possession of the precious coin. Second, the chips may now pile up in the leftmost position. This is where the Silver Dollar may be swept from. The game has two variants. In the first, the player who puts the Dollar in the terminal position loses, as the next player gets the right to pick up the coin on his move. In the second variant (check the Grab dollar button), a player can place the dollar in the terminal position and grab it all in one move.


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


According to the Sprague-Grundy theory every position in an impartial game can be assigned a Grundy number which makes it equivalent to a Nim heap of that size. The Grundy number of a position is variously known as its Nim-heap or nimber, for short.

Assume that from position P of an impartial game it is possible to move into positions P1, P2, ..., PN whose Grundy's numbers g(Pi) are known. Then Grundy's number g(P) of position P is determined by the Mex rule, as the smallest nimber that does not appear in the sequence g(P1), g(P2), ..., g(PN):

g(P) = Mex{g(P1), g(P2), ..., g(PN)}.

P is then equivalent to the Nim heap of size g(P), because obviously any g(Pi) smaller than g(P) is reachable from g(P), g(P) itself is not attainable, while moves into any larger g(Pi) are reversible according to the rules of Nim.

The game of Kayles provides a nice example. Kayles was introduced by Dudeney and Loyd. Two players take turns knocking down skittles - pins here in the US. Usually skittles are arranged in a row. In the applet below they make a circular pattern. With one ball a player may knock either 1 (a direct hit) or 2 adjacent skittles (hitting just in-between the two.) The players are so good at playing the game they can knock down the desired skittles at will. The last player to move wins.

Let Kn stand for a Kayles position of n adjacent pins. Then, in general, any Kayles position may be described as a disjunctive sum of Kn's. For a disjunctive sum of impartial games we have a Nim-sum rule:

g(Kn1 + Kn2 + ... + KnN) = g(Kn1) ^ g(Kn2) ^ ... ^ g(KnN),

where ^ is the bitwise XOR operation that applies to individual bits of binary representations of g(Kni)'s. As an example, g(K0) = 0. g(K1) = 1.

g(K2) = Mex{g(K0), g(K1)} = 2.

g(K3) = Mex{g(K1), g(K2), g(K1) ^ g(K1)} = Mex{1, 2, 0} = 3.

g(K4) = Mex{g(K2), g(K3), g(K1) ^ g(K1), g(K1) ^ g(K2)} = Mex{2, 3, 0, 3} = 1.

g(K5) = Mex{g(K3), g(K4), g(K1) ^ g(K3), g(K2) ^ g(K2), g(K1) ^ g(K2)} = Mex{3, 1, 2, 0, 3} = 4.

Continuing in this manner we obtain the following table that is useful for playing the game with a small number of pins:

K0  K1  K2  K3  K4  K5  K6  K7  K8  K9  K10  K11 
0  1  2  3  1  4  3  2  1  4  2  6 
K12  K13  K14  K15  K16  K17  K18  K19  K20  K21  K22  K23 
4  1  2  7  1  4  3  2  1  4  6  7 
K24  K25  K26  K27  K28  K29  K30  K31  K32  K33  K34  K35 
4  1  2  8  5  4  7  2  1  8  6  7 

The sequence acquires a period of 12 after n = 72 (R. Guy).


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


Kayles belongs to the Take-and-Break variety of impartial games. Scoring is an example of Subtraction games in which only a prescribed number of objects may be removed on a single move. In the applet below you are given a number of minuends and a number of subtrahends. Players take turns subtracting subtrahends from minuends - one subtraction at a time. Only non negative results are legal. The player unable to move loses. A horizontal line separates minuends (placed above the line in a rectangular array) from subtrahends (always located in a row below the line).

To perform a move, select a minuend and then click on a subtrahends.

The game has three parameters. #Nums is the number (from 1 through 12) of minuends to subtract from. #Subs is the number (from 1 through 8) of possible subtrahends to be subtracted from minuends. Max is the absolute maximum of minuends. Subtrahends may change between 1 and 9 (inclusive). They may be modified when the Define button is checked.

The numbers that could be modified (#Nums, #Subs, Max and subtrahends) are modified by clicking a little off their vertical central line. Clicking on the right from the line increases the number, clicking on the left decreases it.


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


As we can see, the general theory of impartial games is helpful in mastering particular instances. However many individual games and their classes preserve their unique treats. For example, (Grundy numbers of) subtraction games are always periodic. Whether or not this is true for Break-and-Take games is an open question.

The examples above and the one in the previous column do not even scratch the surface of the vast theory and its gameful applications developed in WW and ONAG. WW may not be encyclopedia, but it's full of surprises. Can you imagine how Kayles crops up in another children's game of Dots-and-Boxes? This will be covered in the forthcoming 3rd volume of WW. Something to look forward to.

Since the appearance of WW and ONAG, the theory of combinatorial games expanded into a branch of mathematical sciences. For an accessible introduction into combinatorial games, see R. Guy's articles in the R. Nowakowski's volume Games of No Chance, and his small brochure fair game for a short introduction into the theory of impartial games. Games of No Chance is a fine collection of articles presented at an MSRI workshop (1994) on Combinatorial Game Theory. A spirited review by Ed Sandifer of the book itself can be found in the MAA's online collection Read This!. The book also contains a bibliography by Aviezri Fraenkel of 666 works in the subject. The updated version of the bibliography of 1064 items is available online in various formats: Postscript, dvi, and as a LaTeX2e file.

References

  1. A. Beck, M. N. Bleicher, D. W. Crowe, Excursions into Mathematics, Millennium Edition, A K Peters, 2000
  2. E. R. Berlekamp, The Dots and Boxes Game, A K Peters, 2000
  3. E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, A K Peters, 2001
  4. J. H. Conway, On Numbers And Games, A K Peters, 2001
  5. A. Fraenkel, Combinatorial Games: Selected Bibliography With A Succinct Gourmet Introduction, ever growing.
  6. M. Gardner, Hexaflexagons and Other Mathematical Diversions, The University of Chicago Press, 1988
  7. R. Guy, fair game, Comap's Explorations in Mathematics, 1989
  8. G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, Fifth Edition, 1996
  9. R. Nowakowski (Ed), Games of No Chance, Mathematical Sciences Research Institute Publications, No 29, Cambridge University Press, 1996
  10. S. Schwartzman, The Words of Mathematics, MAA, 1994

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2017 Alexander Bogomolny

 62645420

Search by google: