How Do You Always Win at Nim?

Before the computer’s secret, here is one you can find yourself.

Two piles: copy the other player

Start with the simplest Nim there is: two piles of the same size, say 4 and 4, and your friend goes first.

Whatever your friend takes from one pile, you take the same number from the other pile. If they take 3, leaving 1 and 4, you take 3, leaving 1 and 1. After each of your moves the piles are equal again, so your friend can never take the last stone: you always can.

Equal piles are a losing position for the player whose turn it is. With three piles, the losing positions are harder to see. Binary shows them.

The secret, in binary

In the board below, press Show the binary. Beside each pile, its size is written in binary, as fours, twos and ones: 5 is 4 + 1, so it is written 101. Underneath, the board counts how many 1s there are in each column. An odd count is ringed in red.

• a.After every move Perfect makes, what do you notice about the column counts?
• b.Start from 1-2-3 and go first. Look at the columns before you move. Can you win?
• c.Try a game between two Random players, and watch the columns: is there anything they keep doing?

Write the pile sizes in binary, one under another, like a sum, and count the 1s in each column. Here are 3, 5 and 7:

The ones column has three 1s, an odd number. Call a position where every column is even an even position. The rule for winning Nim is one sentence:

After your move, leave every column even.

From 3, 5, 7, taking one stone from any pile turns its last 1 into 0 and makes the ones column even: 2, 5, 7 or 3, 4, 7 or 3, 5, 6. Those are the 3 winning first moves.

Two facts make the rule work.

Fact 1: from an even position, every move makes a column odd

A move changes one pile to a smaller number. A different number has at least one different binary digit, so at least one column changes by exactly one 1: from even to odd. Whatever your friend does, they hand you an odd column.

Fact 2: from a position with an odd column, there is always a move back to even

Here is how to find it. Say the piles are 2, 5 and 4:

• a.Find the leftmost odd column: here, the twos.
• b.Choose a pile that has a 1 in that column: pile 0.
• c.In that pile, flip the digit in every odd column (1 becomes 0, 0 becomes 1). Pile 0 is 010; flipping its twos and ones digits makes 001, which is 1.
• d.So take 2 − 1 = 1 stone from pile 0. The piles become 1, 5, 4: 001, 101 and 100, with 2, 0 and 2 in the columns. All even.

Flipping the leftmost odd column turns a 1 into a 0 there, so the new number is always smaller, whatever happens to the digits on its right: a binary digit is worth more than all the digits to its right put together (4 is more than 2 + 1). So it is a move you are allowed to make.

Why the even player wins

You leave an even position; your friend must make a column odd (Fact 1); you make them all even again (Fact 2). The last position, no stones at all, is all even, so it is you who leaves it: you take the last stone. If the game starts even (1-2-3, 2-4-6), the second player can do this.

Adding without carrying

Keeping only “odd” or “even” for each column is adding the binary numbers without carrying: 1 + 1 makes 0, and nothing is carried. Write 1 under each odd column and 0 under each even one, and you get the nim sum: 001 for 3, 5 and 7. A position is even exactly when its nim sum is 0.

It has a name. Among the logic gates you could try in Grade 7 was XOR, “one or the other, but not both”. 1 XOR 1 is 0, 1 XOR 0 is 1, 0 XOR 0 is 0. Every processor has XOR built in, and Python writes it ^.

With blocks: is it an even position?

This program asks for three piles of up to 7 stones. A pile’s ones digit is the remainder when it is divided by 2. Taking that digit off and halving moves the twos digit into the ones place (5 is 101; take off the 1 and halve: 2, which is 10). Three times round the loop covers ones, twos and fours, and odd counts the odd columns.

In Python (from Grade 8): the nim sum

Python has XOR built in: a ^ b is the nim sum of a and b. bin() shows a number in binary, after the letters 0b.

print(bin(3), bin(5), bin(7))print(3 ^ 5)print(3 ^ 5 ^ 7)print(1 ^ 2 ^ 3)

0b11 0b101 0b111610

3 ^ 5 is 6: 011 and 101 make 110 without carrying. 3, 5, 7 has an odd column; 1, 2, 3 is even.

A player in eight lines

Now a function the board can play. choose_move(piles) gets the piles as a list, such as [3, 5, 7], and gives back a move as a list of two numbers: which pile (counting from 0, as Python does), and how many stones to take.

How does it find the pile to change and the new size? XOR does Fact 2’s flipping for you. If s is the nim sum, then piles[i] ^ s is pile i with its digits flipped in every odd column. When that is smaller than the pile, it is the size to leave.

def nim_sum(piles):    total = 0    for p in piles:        total = total ^ p    return total def choose_move(piles):    s = nim_sum(piles)    if s != 0:        for i in range(len(piles)):            target = piles[i] ^ s            if target < piles[i]:                return [i, piles[i] - target]    # Every column is even: no move wins. Take one stone and hope.    for i in range(len(piles)):        if piles[i] > 0:            return [i, 1] print(nim_sum([3, 5, 7]), choose_move([3, 5, 7]))print(nim_sum([2, 5, 4]), choose_move([2, 5, 4]))print(nim_sum([1, 2, 3]), choose_move([1, 2, 3]))

1 [0, 1]3 [0, 1]0 [0, 1]

The second line is the example worked out above. The third is an even position: no move wins, so the function takes one stone and waits for a mistake.

Now play against it. The board below calls choose_move from the program just above, as you have it (press Edit to change it), every time Your code has to move.

A hundred games

One game proves little. This board plays many games between two computer players, from Random starts (three piles of 1 to 7 stones each game).

Is the binary rule really right for every position? A computer can check, without knowing anything about binary, from the game’s rules alone. No stones left is a loss for the player to move (the other took the last stone). Any other position is a win if some move leaves the other player a losing position, and a loss if none does. The program works through every position of three piles of 0 to 7, smaller piles first, so each move’s result is already known, and keeps a list of the losing ones.

def moves(piles):    result = []    for i in range(len(piles)):        for take in range(1, piles[i] + 1):            new = list(piles)            new[i] = new[i] - take            result.append(new)    return result losing = []for a in range(8):    for b in range(8):        for c in range(8):            piles = [a, b, c]            can_win = False            for m in moves(piles):                if m in losing:                    can_win = True            if not can_win:                losing.append(piles) print(len(losing), 'of the 512 positions lose for the player to move')print('With three different piles, none empty:')for p in losing:    if 0 < p[0] < p[1] < p[2]:        print(p) agree = 0for a in range(8):    for b in range(8):        for c in range(8):            if (a ^ b ^ c == 0) == ([a, b, c] in losing):                agree = agree + 1print('The binary rule agrees on', agree, 'of 512 positions')

64 of the 512 positions lose for the player to moveWith three different piles, none empty:[1, 2, 3][1, 4, 5][1, 6, 7][2, 4, 6][2, 5, 7][3, 4, 7][3, 5, 6]The binary rule agrees on 512 of 512 positions

(list(piles) makes a copy of the list, so changing the copy leaves piles as it was.)

• The search never mentions binary, yet the positions it finds are exactly those with a nim sum of 0: all 512 agree.
• In each of the seven, the biggest pile is the other two added without carrying: 1 ^ 2 = 3, 3 ^ 5 = 6 (though 3 + 5 is 8).
• Only 64 of the 512 positions lose, 1 in 8: from a random start, the first player can usually win.

The search had to look at all 512 positions; the rule answers any position at once, even piles of a million stones. The search shows what is true; the rule explains why. Charles Bouton proved the rule in 1901, with no computer at all.

Bouton had no computer to list his 35. Yours can check his count in a moment:

count = 0for a in range(1, 16):    for b in range(a + 1, 16):        for c in range(b + 1, 16):            if a ^ b ^ c == 0:                count = count + 1print(count, 'safe combinations')

35 safe combinations

The last stone loses. Bouton wrote that this version seemed to be the better known one in 1901, and that its rule is nearly the same: play as before until your move would leave only piles of one stone; then leave an odd number of them, so your friend must take the last. That is Challenge ★★★.

Games in disguise. In the 1930s Roland Sprague and Patrick Grundy, working separately, showed that every game of this kind (both players have the same moves, the game always ends, and whoever can’t move loses) behaves like one pile of Nim. So the nim sum solves games that don’t look like Nim at all.

An open question: Sprouts. Draw a few dots on paper. On your turn, draw a line from a dot to another dot (or back to itself) without crossing any line, and put a new dot on it. No dot may have more than three lines; whoever can’t move loses. John Conway and Michael Paterson made it up in the early 1960s. Nobody has found a rule like Bouton’s for it. Computers search, as your program did, and their answers follow a pattern: the first player wins exactly when the number of dots, divided by 6, leaves 3, 4 or 5. Does the pattern go on for ever? Nobody knows.

★ The two-pile game (blocks)

Two piles. Finish the program so that it says how many stones to take from the bigger pile to make the piles equal (0 if they already are). Then press Test.

★★ Every winning move (Python, from Grade 8)

Write winning_moves(piles): a list of every move [pile, count] that leaves an even position, in any order ([] if there are none). Piles may be bigger than 7, and there may be any number of them.

def winning_moves(piles):    # give back a list of [pile, count] moves that leave every column even    return [] print(winning_moves([3, 5, 7]))

★★★ When the last stone loses (Python, from Grade 8)

Now whoever takes the last stone loses (mathematicians call this version “misère”). Write misere_move(piles) that gives back a winning move. Every test has one; if there are several, any is right.

def misere_move(piles):    # give back [pile, count]: a winning move when taking the last stone loses    return [0, 1] print(misere_move([1, 1, 5]))

• Grade 6, Zeros and Ones: counting in binary, where the secret is written.
• Grade 7, True or False: Logic: logic gates, including XOR, the nim sum’s gate.
• Grade 8, Functions: writing functions like choose_move that answer a question.
• Can eight rules play tic-tac-toe without ever losing? A list of rules that never loses at another game.
• How can a computer never lose at tic-tac-toe? (Grades 9–12): when there is no simple rule, search every future, as your search program did here.