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 for 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 entice 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 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 the 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. The relation to Nim may
not be immediately obvious, but, as a matter of fact, the lineage is
surprisingly short.
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.
Assume that from position P of an impartial game it is possible to move
into positions P1, P2, ..., PN whose
Grundy numbers g(Pi) are known. Then the Grundy 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:
