Nim is a game where two players take turns removing objects from different heaps or piles. On each turn, a player must remove at least one object, and may remove any number of objects as long as they all come from the same heap or pile. The goal of the game depends on the version being played; sometimes the aim is to avoid taking the last object, and other times it is to take the last object.

Nim is important in a rule called the Sprague-Grundy theorem. This rule states that every impartial game is equivalent to a Nim game with a single pile when it is part of a bigger game.

History

People have played different versions of nim for a very long time. The game is believed to have started in China, where it closely matches the Chinese game of jiǎn-shízǐ, or "picking stones." However, the exact origin is not certain. The earliest European records about nim date back to the beginning of the 16th century. The game's current name was created by Charles L. Bouton of Harvard University, who also developed the full theory of nim in 1901. The origin of the name was never fully explained. The Oxford English Dictionary suggests the name comes from the German verb "nimm," which means "take."

At the 1939 New York World's Fair, Westinghouse showed a machine called the Nimatron that played nim. From May 11 to October 27, 1940, only a few people managed to beat the machine during that six-month period. Those who succeeded received a coin labeled "Nim Champ." The Nimatron was also 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 plays nim was 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 meaning 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 games, if there is exactly one heap with two or more objects, the player who takes the next turn can win easily. If this player removes all or all but one object from that heap, no heaps will have more than one object. Then, players must take turns removing one object at a time until the game ends. If the player leaves an even number of heaps with objects (as they would in normal play), they will take the last object. If the player leaves an odd number of heaps with objects (as they would 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 of three heaps. 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 is played between two fictional players, Bob and Alice, who start with heaps containing three, four, and five objects.

Winning positions

The good way to win at the game of Nim is for a player to put the other player into one of these positions. Each turn after that, the player should make smaller positions. Only the last move changes between misère and normal play.

For the general rules, n and m can be any numbers greater than 0. They can be the same number.

Mathematical theory

Normal-play Nim is very important to the Sprague–Grundy theorem. This theorem states that in normal play, every impartial game (a game where both players have the same moves) is equivalent to a Nim heap. This equivalence helps predict the outcome when multiple games are played together (called a disjunctive sum).

In normal play, all impartial games can be given a Nim value. However, this is not true in misère play (a version where the last player to take an object loses). Only games called "tame games" can use the same strategy as misère Nim.

Nim is a specific type of poset game (a game involving a partially ordered set) where the game pieces are arranged in separate chains (the heaps of objects).

The evolution graph of Nim with three heaps is the same as three separate parts of the evolution graph of the Ulam–Warburton automaton (a mathematical structure).

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

The key to solving Nim is the binary digital sum of the heap sizes. This means adding the sizes of the heaps in binary (base-2), ignoring any carries between digits. This process is also called "bitwise xor" or "vector addition over GF(2)" (addition modulo 2). In combinatorial game theory, this is called the "nim-sum." The nim-sum of two numbers, x and y, is written as x ⊕ y to distinguish it from regular addition (x + y). For example, with heaps of size 3, 4, and 5:

An easier way to calculate the nim-sum is to write each heap size as a sum of distinct powers of 2, cancel pairs of equal powers, and add the remaining values.

In normal play, the winning strategy is to make moves that leave a nim-sum of 0 after each turn. This is always possible if the nim-sum is not already 0. If the nim-sum is 0, the next player will lose if the opponent plays correctly. To find the right move, calculate the nim-sum of all heap sizes (X). Then, find a heap where the nim-sum of X and the heap size is smaller than the heap size. Reduce that heap to the nim-sum of its original size and X. For example, if the heaps are 3, 4, and 5, the nim-sum is X = 3 ⊕ 4 ⊕ 5 = 2. The nim-sums of each heap with X are:

Only heap A (size 3) can be reduced. The winning move is to reduce heap A to 1 (by removing 2 objects).

If there are only two heaps left, the strategy is to make the heaps equal. After that, 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 1 object (in normal play, an even number is correct).

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

In a misère game with heaps of sizes 3, 4, and 5, the strategy would be applied as described above.

Proof of the winning formula

The correctness of the best strategy for a normal nim game was shown by C. Bouton.

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

Proof: The nim-sum (⊕) follows the same rules as regular addition (commutative and associative laws) and has a special rule: any number combined with itself using nim-sum equals zero.

Let the sizes of the heaps before a move be $ x_1, x_2, …, x_n $, and after the move be $ y_1, y_2, …, y_n $. Let $ s $ be the nim-sum of the original heap sizes, and $ t $ be the nim-sum after the move. If the move is made in heap $ k $, then all heaps except heap $ k $ remain unchanged, and the size of heap $ k $ decreases from $ x_k $ to $ y_k $. Using the properties of nim-sum, the new total $ t $ can be calculated as $ t = s oplus x_k oplus y_k $.

This means that to update the total nim-sum after a move, the old value of heap $ k $ is removed from the total, and the new value is added.

The theorem is proven using logical steps and previous results.

Lemma 1: If the total nim-sum $ s $ is zero, any move will result in a new total $ t $ that is not zero.
Proof: If no moves are possible, the first player loses by definition. If a move is made in heap $ k $, the new total becomes $ t = x_k oplus y_k $. Since $ x_k $ and $ y_k $ are different, $ t $ is not zero.

Lemma 2: If the total nim-sum $ s $ is not zero, there is a move that makes the new total $ t $ equal to zero.
Proof: Find the leftmost nonzero bit in the binary representation of $ s $, and choose a heap $ k $ where this bit is also nonzero. Let $ y_k = s oplus x_k $. This ensures $ y_k < x_k $, so the first player can remove $ x_k – y_k $ objects from heap $ k $, making the new total $ t = 0 $.

For misère play, the strategy changes when the game reaches a state with only one heap of size 2 or more. In this case, the player following the winning strategy must adjust their move. Instead of reducing the heap to size 0 or 1 (as in normal play), they leave an even number of heaps with size 1. After this point, 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 can remove 1, 2, or up to k objects at a time. This version of the game is typically played with one pile of objects.

Bouton’s method for analyzing this game can be applied to versions with multiple piles. The first step involves adjusting the number of objects in each pile by dividing it by k + 1 and using the remainder. 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 single pile with 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 conclusion comes from analyzing the pattern of numbers in the subtraction game and using the Sprague–Grundy theorem, which helps determine winning strategies in such games.

The game "21" is a misère game 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 forced to say "21" loses. This game 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 number that is 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 two players start at 0 and take turns adding numbers from 1 to 10. The player who reaches 100 wins. The strategy is to aim for numbers with consecutive digits (like 01, 12, 23, etc.) and control the game by reaching these numbers. If 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 there are 10 objects and a player removes 3 in the first move, the next player cannot remove 3 in one move.

In Grundy’s game, players divide 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 either normal or misère play.

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

Let the largest pile have m stones and the second largest have n stones. Let p_m be the number of piles with m stones and p_n be the number of piles with n stones. 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 stones from one pile makes p_m even.
– If p_m is odd and equal to 1, adjusting the largest pile to match the second largest or removing it entirely can also make p_m even.
Conversely, if p_m is even, any move will make it odd. The final position (p_m = 0) is even, so all even p_m positions 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 heaps. The number of objects removed from each heap can be limited, similar to the subtraction game. The winning strategy involves calculating the sum of heap sizes in binary, adjusted for the number of heaps (k + 1), and making moves to ensure this sum is zero for all digits.

In "building nim," players first create a game of nim by placing stones into empty piles. Once all stones are placed, the game begins with the next player. This is denoted as 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 a hyper-row on a board with dimensions k₁ × … × kₙ. The game can start with a full board or other configurations.

In another variation, the starting board is a disconnected graph, and players take turns removing adjacent vertices.

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