Nim is a game that involves strategy and math. Two players take turns removing objects from separate groups, called heaps or piles. On each turn, a player must take at least one object, and can take any number as long as they are all from the same heap or pile. The goal of the game depends on the version being played: either to avoid taking the last object or to take the last object.

Nim is important to the Sprague–Grundy theorem, which states that every impartial game (a game where both players have the same rules and options) is the same as a Nim game with one pile when considered as part of a larger impartial game.

History

Variants of nim have been played for many years. The game is believed to have started in China, where it is similar to a traditional game called jiǎn-shízǐ, or "picking stones." However, its exact origin is not certain. The earliest European mentions of nim date back to the start of the 16th century. The game’s current name was invented by Charles L. Bouton of Harvard University in 1901. He also created the full theory of the game, but the reason for choosing the name was never fully explained. The Oxford English Dictionary says the name comes from the German word "nimm," which means "take."

At the 1939 New York World's Fair, Westinghouse showed a machine called the Nimatron that played nim. Between May 11 and October 27, 1940, only a few people managed to beat the machine during that six-month time. Those who succeeded received a coin labeled "Nim Champ." The Nimatron was one of the first electronic games that used a computer. In 1951, Ferranti built a computer that played nim and displayed it at the Festival of Britain. In 1952, engineers Herbert Koppel, Eugene Grant, and Howard Baller from the W. L. Maxson Corporation created a machine weighing 23 kilograms (50 pounds) that played nim against a human and often won. A machine that played nim was also made using tinkertoys.

The game of nim was discussed in Martin Gardner’s February 1958 "Mathematical Games" column in Scientific American. A version of nim is played and holds symbolic importance in the French New Wave film Last Year at Marienbad (1961).

Game play and illustration

Nim is usually played as a misère game, where the player who takes the last object loses. It can also be played as a "normal play" game, where the player who takes the last object wins. In both types of play, if there is exactly one heap with two or more objects, the next player can win easily. If the player removes all or all but one object from that heap, no heaps will have more than one object. Players must then take turns removing one object at a time until the game ends. If the player leaves an even number of heaps with objects (as in normal play), they will take the last object. If they leave an odd number of heaps (as in misère play), the other player will take the last object.

In normal play, two players take turns removing any number of objects from one heap. The goal is to be the last player to take an object. In misère play, the goal is to force the opponent to take the last remaining object.

An example of a normal game involves fictional players Bob and Alice, who start with heaps containing three, four, and five objects.

Winning positions

To win the game of nim, a player should aim to place the other player in one of the specific positions described. After that, the player should continue to make moves that lead to smaller positions each turn. The final move is the only one that differs between misère and normal play.

In general, the values of n and m can be any numbers greater than 0. These numbers can be the same or different.

Mathematical theory

Normal-play nim (or nimbers) is a key concept in the Sprague-Grundy theory, which states that in normal play, every fair game (where both players have the same moves) is equivalent to a nim heap. This means the game behaves the same way as a pile of objects when played alongside other fair games (called disjunctive sums).

In normal play, all fair games can be assigned a nim value, but this is not true under the misère convention (a rule where the last player to take an object loses). Only certain types of games, called tame games, can use the same strategy as misère nim.

Nim is a specific type of poset game, where the structure consists of separate lines (called chains) that represent the heaps of objects.

The structure of nim with three heaps is similar to three branches of the evolution graph of the Ulam–Warburton automaton, a mathematical pattern.

Nim has been solved mathematically for any number of heaps and objects. There is a clear method to determine which player will win and what moves are available.

The key idea in solving nim is the binary digital sum of the heap sizes. This means adding the sizes of the heaps in binary (without carrying over digits), a process also called "bitwise xor" or "vector addition over GF(2)." In combinatorial game theory, this is called the nim-sum, written as x ⊕ y. For example, with heaps of size 3, 4, and 5, the nim-sum is calculated as 3 ⊕ 4 ⊕ 5 = 2.

An alternative method is to write each heap size as a sum of distinct powers of 2, cancel matching powers, and add the remaining values.

In normal play, the winning strategy is to make moves that leave the nim-sum of all heap sizes equal to zero. This is always possible unless the nim-sum is already zero. If the nim-sum is zero, the next player will lose if the opponent plays correctly. To find the correct move, calculate the nim-sum (X) of all heaps. Identify a heap where the nim-sum of X and the heap’s size is smaller than the heap’s size. Reduce that heap to the nim-sum of its original size and X. For example, with heaps of 3, 4, and 5, the nim-sum is 2. The only heap that meets the condition is the heap of size 3, so it should be reduced to 1 (by removing 2 objects).

If only two heaps remain, the winning strategy is to make the heaps equal in size. After this, the player can mirror the opponent’s moves on the other heap, ensuring they take the last object.

In misère play, the strategy differs only when the normal play move would leave heaps of size 1. In this case, the correct move is to leave an odd number of heaps with one object (in normal play, the correct move would leave an even number).

These strategies for normal and misère play are the same until only one heap with two or more objects remains. At that point, the next player removes all or all but one object from that heap, leaving only heaps of size 1. Players then take turns removing one object until the game ends. In normal play, the player who leaves an even number of heaps wins. In misère play, the player who leaves an odd number of heaps wins.

In a misère game with heaps of sizes 3, 4, and 5, the strategy would follow these steps.

Proof of the winning formula

The effectiveness of the best strategy for a normal Nim game was shown by C. Bouton.

Theorem: In a normal Nim game, the first player can always win if the nim-sum of the heap sizes is not zero. If the nim-sum is zero, the second player can win instead.

Proof: The nim-sum (⊕) follows the same rules as regular addition (commutative and associative laws) and has an extra rule: when a number is added to itself using nim-sum, the result is zero.

Let the sizes of the heaps before a move be $ x_1, x_2, …, x_n $, and the sizes after the move be $ y_1, y_2, …, y_n $. Let $ s = x_1 ⊕ x_2 ⊕ … ⊕ x_n $ (the nim-sum before the move) and $ t = y_1 ⊕ y_2 ⊕ … ⊕ y_n $ (the nim-sum after the move). If the move is made in heap $ k $, then $ x_i = y_i $ for all heaps except heap $ k $, and $ x_k > y_k $. Using the rules of nim-sum, we find:

$ t = s ⊕ x_k ⊕ y_k $.

This means that to update the nim-sum after a move, we remove the original value of heap $ k $ ($ x_k $) and add the new value ($ y_k $).

The theorem is proven using mathematical induction based on the following two rules:

Lemma 1: If the nim-sum $ s = 0 $, then any move will result in a new nim-sum $ t ≠ 0 $.
Proof: If no moves are possible, the rule is automatically true (the first player loses). Otherwise, any move in heap $ k $ results in $ t = x_k ⊕ y_k $. Since $ x_k ≠ y_k $, $ t $ must be nonzero.

Lemma 2: If the nim-sum $ s ≠ 0 $, a move can be made to make the new nim-sum $ t = 0 $.
Proof: Let $ d $ be the position of the leftmost nonzero bit in the binary form of $ s $. Choose a heap $ k $ where the $ d $-th bit is also nonzero. Let $ y_k = s ⊕ x_k $. This ensures $ y_k < x_k $, as the $ d $-th bit decreases from 1 to 0. The first player can remove $ x_k – y_k $ objects from heap $ k $, resulting in a new nim-sum of zero.

For misère play, the strategy changes only when there is one heap with two or more objects. In such cases, the normal play strategy (reducing the heap to size 0 or 1) is adjusted to the opposite action. After this, all moves are forced.

Variations

In a game often called "nim" but more accurately known as the "subtraction game," players can only remove a limited number of objects from a pile during each turn. Instead of taking any number of objects, a player may remove 1, 2, or up to k objects at a time. This game is usually played with a single pile of objects.

Bouton's analysis applies to the general version of this game with multiple piles. The first step is to adjust the sizes of all piles by using a mathematical process called "modulo k + 1." If all piles have zero objects after this step (in misère play), the winning move is to remove k objects from one pile. In a game with one pile of n objects, the second player can win if:
– n divided by (k + 1) leaves no remainder (in normal play), or
– n divided by (k + 1) leaves a remainder of 1 (in misère play).

This result comes from analyzing the "nim-sequence" of numbers (1, 2, …, k) and using the Sprague–Grundy theorem.

The game "21" is a misère version where players take turns saying numbers. The first player says "1," and each player adds 1, 2, or 3 to the previous number, without exceeding 21. The player who says "21" loses. This can be modeled as a subtraction game with a pile of 21 − n objects. The winning strategy for two players is to always say a multiple of 4. If the first player starts with "1," they are in a losing position.

The "21" game can also use different numbers, such as adding up to 5 and losing on 34.

An example of the "21" game with the winning strategy:

A similar game is the "100 game," where players start at 0 and take turns adding 1 to 10 to the total. The first player to reach 100 wins. The strategy is to reach numbers like 01, 12, 23, 34, etc., and control the game by moving through these numbers. Once a player reaches 89, the opponent can only choose numbers from 90 to 99, and the next player can always reach 100.

Another variation of nim allows players to remove the same number of objects from multiple piles.

In "circular nim," objects are arranged in a circle, and players take turns removing 1, 2, or 3 adjacent objects. For example, if a circle has 10 objects and a player removes 3, the next player cannot remove 3 in one move.

In Grundy's game, players split a pile into two unequal nonempty piles. For example, a pile of 6 can be split into 5+1 or 4+2, but not 3+3. This game can be played as normal or misère play.

Greedy nim is a variation where players can only take objects from the largest pile. In misère greedy nim, the last player to make a move loses.

If the largest pile has m objects and the second-largest has n objects, and there are p_m piles with m objects and p_n piles with n objects, a theorem states that positions where p_m is even are "P positions" (winning positions for the second player). This is because:
– If p_m is odd and greater than 1, removing all objects from one pile makes p_m even.
– If p_m is 1 (a unique largest pile), reducing it to n (if p_n is odd) or removing it entirely (if p_n is even) also results in p_m being even.
Conversely, if p_m is even, any move will make it odd. Since the final position (p_m = 0) is even, all positions with even p_m are P positions.

A generalization of multi-heap nim, called "index-k nim," was studied by E. H. Moore in 1910. In this version, players can remove objects from 1 to k different piles. The number of objects removed from each pile may be limited, similar to the subtraction game. The winning strategy involves calculating the sum of each binary digit of the pile sizes modulo (k + 1) and making moves to ensure this sum is zero for all digits.

In "building nim," players first place stones into empty piles, then play a standard nim game. This variant is denoted BN(n,s), where n is the number of stones and s is the number of piles.

In "n-d nim," players remove continuous pieces from hyper-rows on a k₁ × … × kₙ board. The game can start with a full board or other configurations.

In a variation involving graphs, players remove adjacent vertices from a disconnected graph.

"Candy nim" is a version of normal-play nim where players aim to take the last object and also collect the most candies by the end of the game.