Nim
Nim is a two-player impartial combinatorial game in which players alternate turns removing one or more objects from a single heap among several distinct heaps, with the objective of taking the last object to win under the normal play convention.[1] The game is typically played with heaps of stones, matches, or similar items, and a player may remove any positive number of objects from exactly one heap per turn, but cannot touch multiple heaps simultaneously.[2] A position is losing for the player about to move if all heaps are empty, as no legal move is possible.[2] Variants of Nim have existed since ancient times and are believed to have originated in China, where a similar game called jiǎnshízǐ (translated as "pick up pebbles") was played.[3] This early form involved collecting stones or pebbles, and analogous games spread to Europe by at least the 16th century, often under names like "the game of Kayles" or other subtraction-based variants.[4] The modern version of Nim, as a multi-heap game with complete mathematical analysis, was formalized and named by American mathematician Charles L. Bouton in his 1901 paper published in The Annals of Mathematics, where he provided a rigorous theory based on binary representations of heap sizes.[5] Bouton's analysis revealed that the game's outcome is determined by the bitwise exclusive or (XOR) of the heap sizes, known as the Nim-sum; if the Nim-sum is zero at the start, the second player has a winning strategy by always responding to maintain a zero Nim-sum, while a non-zero Nim-sum favors the first player.[1] This binary digital method, or "Nimbers," forms the foundation of combinatorial game theory (CGT), enabling the evaluation of complex impartial games as sums of simpler Nim heaps.[2] The Sprague-Grundy theorem, independently developed in the 1930s by Roland Sprague and Patrick Grundy, generalized Bouton's insights, proving that every impartial game under normal play is equivalent to a Nim heap of a certain size (its Grundy number), thus establishing Nim as the canonical example in CGT.[1] Beyond the standard rules, Nim has numerous variants, including misère Nim (where taking the last object loses), subtraction Nim (limiting removable objects), and multi-player extensions, which have influenced fields from computer science algorithms to recreational mathematics.[6] Its simplicity yet strategic depth has made Nim a staple in mathematical education and a precursor to broader applications in game-solving software and theoretical computer science.[7]Gameplay Fundamentals
Basic Rules
Nim is an impartial combinatorial game for two players, meaning both players have access to the same set of possible moves from any given position.[8] It is played under the normal play convention, in which the player who makes the last move wins.[5] The setup consists of multiple distinct heaps, each containing a positive number of objects such as stones, matches, or coins; the number of heaps and their initial sizes can vary, for example, three heaps with 3, 5, and 7 objects respectively.[5] Players alternate turns, beginning with the first player. On each turn, a player must select exactly one heap and remove any positive number of objects from it—at least one, but up to the entire contents of that heap.[8] Removing objects from more than one heap in a single turn is not permitted.[5] The game's objective is to force the opponent into a position with no legal moves available, which occurs when all heaps are empty.[8] The player unable to move on their turn loses. In combinatorial game theory, each heap functions as an independent subgame, and the overall position is the disjunctive sum of these subgames.[8] A variant known as misère Nim reverses the winning condition so that the player making the last move loses, though standard Nim adheres to normal play.[5] A complete winning strategy for normal play exists, determined by the nim-sum of the heap sizes, though its details involve binary digital sums.[5]Illustrative Example
Consider a simple instance of Nim featuring three distinct heaps containing 1, 3, and 5 stones, respectively.[9] Player A begins the game, and players alternate turns, with each required to select exactly one heap and remove at least one stone from it (but not from multiple heaps in a single turn).[9] A common beginner mistake is attempting to remove stones from more than one heap at once, which is illegal and would result in an invalid move.[10] The initial position can be represented as:- Heap 1: 1 stone
- Heap 2: 3 stones
- Heap 3: 5 stones
- Heap 1: 0 stones
- Heap 2: 3 stones
- Heap 3: 3 stones
- Heap 1: 0 stones
- Heap 2: 0 stones
- Heap 3: 3 stones
Historical Context
Ancient Origins
Variants of the game Nim have roots in ancient China, where a similar pastime known as jiǎn shízi (picking up stones) was played using pebbles or small objects arranged in heaps. This early form, involving alternate removals from the heaps, is believed to date back to ancient times, though the precise origins remain obscure. The game was typically recreational, played informally without structured rules or strategic analysis, often as a social activity among children or adults using readily available materials like stones or sticks.[3][6][11] Possible antecedents to Nim-like games appear in other ancient cultures, where subtraction-based or object-taking pastimes may have existed, though direct historical evidence is limited and debated among scholars.[12] By the early 16th century, Nim variants had reached Europe, manifesting as folk "taking games" that spread through oral traditions across rural and urban communities.[4] In the 18th and 19th centuries, these evolved into popular pastimes using matchsticks, coins, or beans, particularly in British pubs where they fostered social bonding and light wagering. The simplicity of these folk iterations—requiring no specialized equipment—ensured their endurance as casual diversions until formal study in the early 20th century.[13]Modern Mathematical Analysis
The modern mathematical analysis of Nim began in the early 20th century with Charles L. Bouton's seminal work, which provided the first complete winning strategy for the game and laid the groundwork for impartial game theory. Bouton, an associate professor at Harvard University, analyzed Nim in his 1901–1902 paper, demonstrating that the game's outcome depends on the binary digital representation of pile sizes and their exclusive or (XOR) combination, known as the nim-sum. This approach not only solved standard Nim but also introduced a systematic method for determining winning and losing positions in impartial games, marking a pivotal shift from recreational puzzle to rigorous mathematical object. Bouton's insights directly influenced subsequent developments in the 1920s and 1930s, particularly the Sprague-Grundy theorem, which generalized his Nim strategy to arbitrary sums of impartial games. Independently formulated by Roland Sprague in 1936 and Patrick M. Grundy in 1939, the theorem assigns a nimber (Grundy number) to each game position as the minimum excludant (mex) of the nimbers of its options, proving that any impartial game is equivalent to a Nim heap of that size. Sprague's work, published in German as "Über mathematische Kampfspiele," extended Bouton's XOR method to composite games, while Grundy's "Mathematics and Games" in the Cambridge University magazine Eureka formalized the recursive assignment of values, enabling analysis of complex game combinations beyond Nim heaps.[14] These contributions established Nim as the canonical example in combinatorial game theory, bridging isolated game solutions to a unified framework. Post-World War II, Nim's mathematical significance expanded through popularization and computational applications, solidifying its role in both theoretical and practical contexts. The 1982 book Winning Ways for Your Mathematical Plays by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy synthesized decades of progress, using Nim as a foundational tool to explore advanced impartial games, misère variants, and surreal numbers, thereby influencing generations of mathematicians and computer scientists. Computationally, Nim featured prominently in early AI and programming education; the 1951 Ferranti Nimrod, a specialized digital computer exhibited at the Festival of Britain, implemented Bouton's strategy in hardware to play against humans, demonstrating real-time XOR calculations and marking one of the first purpose-built computing devices for game-playing.[15]Strategy for Standard Nim
Winning and Losing Positions
In standard Nim under normal play convention—where the player unable to move loses—a game position is classified as either a winning position or a losing position based on optimal play by both participants. A losing position, often denoted as a P-position (indicating the previous player wins), is one in which every possible legal move leaves the opponent in a winning position, thereby guaranteeing the current player's defeat if the opponent plays perfectly. Conversely, a winning position, or N-position (next player wins), is one from which the current player can make at least one move that forces the opponent into a losing position, securing victory with flawless subsequent play. This binary classification underpins the strategic analysis of Nim and stems from foundational work in combinatorial game theory.[16][5] The simplest examples illustrate these concepts clearly. The terminal position, consisting of all heaps empty (zero objects in every heap), is a losing position, as the player to move has no options and thus loses immediately. For a single-heap game, a heap of size zero is losing, while any heap of size greater than zero is winning, since the player can remove all objects in one move, leaving the empty position for the opponent. In multi-heap configurations, the all-zero state remains losing, but other setups vary: for instance, two heaps of equal non-zero size (e.g., one heap of 3 and another of 3) constitute a losing position, as any reduction in one heap permits the opponent to mirror the move in the other, preserving equality and eventually forcing the first player into the terminal loss.[17][16] This classification exhibits a recursive structure, evaluated backward from the known terminal losing position. Starting with the endgame, each prior position is assessed by examining all reachable subsequent states: if any leads to a losing position, the current one is winning; if all lead to winning positions, it is losing. This inductive process, applied to increasingly larger heap configurations, reveals patterns and builds strategic intuition without requiring exhaustive computation for every case. For small instances, such as two heaps of unequal sizes (e.g., 2 and 4), the first player can win by reducing the larger heap to match the smaller, shifting to a losing position for the second player. Such examples highlight how balanced or symmetric setups often prove disadvantageous, guiding players toward disruptive moves that unbalance the game in their favor. The precise identification of these positions in general relies on tools like the nim-sum, as detailed in the following section.[17][16]The Nim-Sum and XOR Calculation
In standard Nim, the nim-sum provides a computational method to evaluate the game's position by combining the heap sizes using their binary representations. Specifically, the nim-sum is obtained by performing a bitwise exclusive or (XOR) operation on the binary forms of all heap sizes, where XOR compares corresponding bits and results in 1 if the bits differ and 0 if they are the same.[18] This operation, equivalent to summing the binary digits in each column modulo 2 (i.e., counting the number of 1s in each bit position and taking the parity), was introduced by Charles L. Bouton in his analysis of Nim.[18] A position in Nim is a winning position (N-position) for the player about to move if the nim-sum is nonzero, meaning the first player can force a win with optimal play; conversely, it is a losing position (P-position) if the nim-sum is zero, as any move will leave a nonzero nim-sum for the opponent.[18] For heaps of sizes a_1, a_2, \dots, a_n, the nim-sum is denoted as a_1 \oplus a_2 \oplus \dots \oplus a_n.[18] To illustrate, consider heaps of sizes 3, 5, and 7. In binary, these are 011, 101, and 111, respectively (padded to three bits for alignment). First, XOR 011 and 101: bit by bit, 0⊕1=1, 1⊕0=1, 1⊕1=0, yielding 110 (decimal 6). Then XOR 110 with 111: 1⊕1=0, 1⊕1=0, 0⊕1=1, resulting in 001 (decimal 1), which is nonzero. Thus, this is an N-position.[19] To find a winning move from an N-position, the player selects one heap and reduces its size to a value that makes the overall nim-sum zero. If the current nim-sum is s \neq 0, for a chosen heap a_i, the target size is a_i \oplus s, provided this is less than a_i (ensuring a valid reduction). Continuing the example with heaps 3, 5, 7 and s = 1 (001 in binary), targeting the heap of 7 (111): 111 ⊕ 001 = 110 (decimal 6), so reducing the 7-heap to 6 yields new heaps 3, 5, 6. Their nim-sum is 011 ⊕ 101 ⊕ 110 = 011 ⊕ 101 = 110, then 110 ⊕ 110 = 000, a P-position.[19] The following table shows nim-sums (XOR results) for small heap combinations, using binary representations up to 3 bits (values 0–7), to demonstrate the operation's pattern:| Heap A (binary) | Heap B (binary) | Nim-sum (binary, decimal) |
|---|---|---|
| 000 (0) | 000 (0) | 000 (0) |
| 001 (1) | 001 (1) | 000 (0) |
| 001 (1) | 010 (2) | 011 (3) |
| 011 (3) | 101 (5) | 110 (6) |
| 110 (6) | 111 (7) | 001 (1) |