Nim

Nim is a mathematical game of strategy in which two players alternately remove objects from several heaps, with the only rule being that a player must take at least one object per turn and may take any number so long as they all come from a single heap.¹⁸ It is the most well-known example of an impartial game — a game in which both players have the same available moves at every position, so that the only distinction between them is who moves first — and it has been completely solved, meaning an exact optimal strategy is known for any starting configuration.¹ The heaps are also called piles and the objects stones.¹⁸

In the standard, or normal, form of the game, the player who removes the last stone wins, and the player unable to move loses.¹⁵ A variant called misère Nim reverses this: the player forced to take the last stone loses instead.¹ In combinatorial game theory, the normal convention — the win going to the last player to move — is the default, and misère play requires only a small modification to the winning strategy near the end of the game.¹

The game requires no board and no special equipment: it can be played with pebbles, coins, matchsticks, or any collection of small tokens, or, lacking them, with marks made on paper and crossed off in turn.⁵ Because the state of play is fully captured by the number of stones remaining in each pile, both players always know everything about the current position, making Nim a game of perfect information.⁸

Strategy

The complete solution rests on the nim-sum, the bitwise operation that computer scientists call XOR.¹ To compute the nim-sum of two non-negative integers, each is written as a sum of distinct powers of two; powers appearing in both are canceled, and the remaining powers are added.¹ For example, 3 (as 2¹ + 2⁰) combined with 5 (as 2² + 2⁰) cancels the shared 2⁰, leaving 2¹ + 2² = 6.¹ The operation is associative, commutative, has 0 as identity, and is self-inverse in that any value combined with itself yields zero.¹ These properties make the nim-sum of several piles well-defined regardless of the order in which they are combined.¹

The governing theorem, proved by C. Bouton, states that the player to move wins in normal Nim if and only if the nim-sum of all the pile sizes is not zero.¹ When the nim-sum is nonzero, a winning move exists that reduces some single pile so that the nim-sum of the resulting position becomes zero; from a position whose nim-sum is already zero, every move leaves a nonzero nim-sum, so the player to move loses against perfect play.¹ Bouton’s proof proceeds from the base case in which all piles are empty — a position whose nim-sum is zero and in which the player to move has already lost — and builds outward using the arithmetic properties of the operation.¹

In the classic starting position of piles of 3, 4, and 5, the nim-sum is 2 — nonzero — so the first player wins, the winning first move being to reduce the pile of 3 to a single stone, after which the three piles nim-sum to zero.¹⁸ A worked example of such a game runs nine moves, with the first player, having secured the zero-sum position, able to answer every reply until taking the final stone.¹

Simpler special cases make the same logic visible without the arithmetic. With two piles of equal size, the second player wins by always mirroring the opponent’s move in the other pile; with two unequal piles, the first player wins by first equalizing them and then mirroring.⁸ This pairing strategy extends to any even number of equal-sized piles, where the second player pairs the heaps and mirrors within each pair.⁸ With five stones there are seven distinct starting configurations, and the first player has a winning strategy in all of them.⁸

In misère Nim the optimal play is nearly identical to normal play, diverging only once the position is about to consist of piles of size one: the correct aim is to leave an odd number of single-stone piles, the reverse of the even count that normal play seeks.¹ This adjustment is applied only when the player’s move would otherwise leave no pile of size two or larger; up to that point, the normal strategy is followed unchanged.¹

Play and context

A frequently taught restricted version of the game allows each player to remove only one or two objects from a single pile per turn, with the taker of the last object winning; it is often demonstrated by starting from a single row of a chosen number of counters, such as thirteen.⁵ Because pencil and paper suffice, Nim has become a common demonstration game in mathematics education, used to introduce students to the idea that a simple game can conceal a rigorous, complete strategy.⁵ As a two-player game of perfect information, it guarantees that one of the two players always possesses a winning strategy once the starting position is fixed, though which player that is depends on the configuration and identifying the correct sequence of responses is not always straightforward.⁸

The theory of Nim extends beyond the game itself through the Sprague–Grundy theorem, which assigns to every position in any impartial game a value — a “nimber” — equivalent to a single Nim heap, so that Nim serves as the canonical model to which a wide class of impartial games can be reduced.¹

Adaptations in computing

Nim’s simplicity and complete solvability made it an early subject for automated play. Its rules require only counting and the XOR operation, which map directly onto digital hardware, and the game has long been used as a compact illustration of game-solving algorithms.¹ The word “nim” has since accumulated many unrelated uses, including as the name of a statically typed, compiled systems programming language whose designers took its name as shorthand for Nimrod.²¹¹

History as an early computer game

The game’s foundations were established in 1901 by Charles L. Bouton? of Harvard University, who published “Nim, A Game with a Complete Mathematical Theory” in the Annals of Mathematics and gave the game its modern name.¹²¹⁷ Bouton coined the term “nim,” most likely from the imperative of the German verb nehmen (“to take”), the imperative being nimm; the choice has been linked to the years he spent in Leipzig, where he received his doctorate.¹³ The paper both introduced the winning theory based on binary addition modulo two and helped give rise to the field of combinatorial game theory?.¹²¹⁷ Although Bouton fixed the name and the mathematics, variants of the game had been played for centuries, with examples recorded in Europe as early as the 16th century and origins sometimes traced to ancient China, where a comparable pebble game was known as jianshiji, or “pick up pebbles”.¹⁵¹⁶

Because its rules reduce to counting and the bitwise XOR operation, Nim proved well suited to mechanization, and it became one of the earliest games to be implemented on computing machinery.¹² In 1940 the American physicist Edward Uhler Condon? and an associate built the Nimatron?, an automatic machine that played a perfect game of Nim; it was exhibited at the New York World’s Fair? in 1940.¹⁴ In 1951 the game inspired the Nimrod? computer, one of the first machines built specifically to play a game.¹²¹⁸ The Nimrod is frequently cited alongside OXO and Tennis for Two among the earliest computer games, none of which were sold to the public because they were too large or too costly to leave the laboratory.¹⁸