Lay out a few piles of tokens. On your turn, take as many as you like from one pile. Whoever takes the last token wins. In 1901 Charles Bouton solved the game completely: write the pile sizes in binary, XOR them together, and that one number, the nim-sum, tells you who wins and how. Every finite impartial game turns out to be Nim in disguise.
Click a token to take it and every token to its right. The computer plays perfectly. The table under the piles shows each pile in binary and the XOR of every column. If any column has an odd number of 1s, the player to move can win. The hint, on by default, marks the move that makes every column even.
How to read this: the table writes each pile size in binary, using the place values 8, 4, 2, 1: a pile of 5 is 4 + 1, so it has 1s under 4 and 1. The xor row is red where a column has an odd count of 1s. The winning move flips the gold-outlined bits so every column turns green (even).
Find the highest column where s has a 1 (gold header). Some pile has a 1 in that column. Flip that pile's bits in every column where s has a 1. Its top flipped bit goes from 1 to 0, so the new size is smaller and the move is legal. Every odd column becomes even, so the new nim-sum is 0.
From nim-sum 0, any move changes one pile, which flips at least one of its bits, so at least one column turns odd. The player facing 0 always hands back a nonzero sum, and the empty position has sum 0. That proves Bouton's rule: a position is a P-position exactly when its nim-sum is 0.
A P-position is one where the Previous player, who just moved, wins with best play: whoever is to move loses. An N-position is one where the Next player, who is to move, wins. Recursion defines both: a position is N if some move reaches a P-position, and P if every move reaches an N-position (a position with no moves is P). Here a brute-force search labels every small position and the XOR rule is checked against it. Click a cell to see its moves.
How to read this: in the pile views, each cell is a position with a tokens in one pile and b in the other (and c in the third). Gold cells lose for whoever must move, and every move from gold lands on green. In the subtraction game, each bar is a pile of n tokens and its height is its Grundy value g(n); 0 means the mover loses.
Try this: click a few gold cells and check every faint box around them is green.
An impartial game gives both players the same moves; only whose turn it is differs. The Sprague–Grundy theorem (Sprague 1935, Grundy 1939) says every position of such a game under normal play behaves exactly like a single Nim heap of size g(x), where mex is the smallest non-negative integer missing from a set. Positions with g = 0 are the P-positions.
Playing several games side by side, choosing one to move in each turn, is the same as Nim on heaps of their Grundy values. With takes of 1, 2 or 3, a pile of n is a Nim heap of n mod 4, so piles of 5, 6 and 7 add up to 1 ⊕ 2 ⊕ 3 = 0: a P-position.
Wythoff's game (1907) has two piles. A move takes any number from one pile, or the same number from both. Picture a chess queen on a grid at (a, b) that may only move left, down, or diagonally down-left; whoever moves her into the corner (0, 0) wins. The gold cold cells are the P-positions, found by the same search as Lab 2. They sit along two lines whose slopes are the golden ratio φ and 1/φ. Click a highlighted cell to move, or click anywhere else to place the queen.
How to read this: the queen sits at (a, b) and may move left, down, or diagonally down-left. Gold cells are cold: whoever must move from one loses.
Wythoff proved that the cold cells with a ≤ b are exactly these pairs, and their mirror images. Since φ² = φ + 1, each pair's gap is n, and because 1/φ + 1/φ² = 1, the two sequences together hit every positive integer exactly once (Beatty's theorem). See 001 · The golden ratio for more on φ.