Unit 18: Winning Games

A pile of sticks and one rule

Twelve sticks. Take 1, 2 or 3 on your turn. Whoever takes the last one wins.

Both players are perfect, so this is not about tactics: every position is already decided, and the question is only which.

The definition, and it is the whole subject

A position is winning if some move leads to a losing one. It is losing if every move leads to a winning one.

Zero sticks is losing — the player about to move has already lost. Everything else follows from there, smallest first.

Python

n = 12
moves = [1, 2, 3]
win = [False] * (n + 1)

for i in range(1, n + 1):
    for m in moves:
        if i - m >= 0 and not win[i - m]:
            win[i] = True

print(win)

It prints

[False, True, True, True, False, True, True, True, False, True, True, True, False]

The pattern falls out

Losing at 0, 4, 8, 12 — the multiples of four. And the reason is plain once you see it: whatever your opponent takes from a multiple of four, you take the rest of the four.

So the answer for a million sticks is n % 4 == 0, with no table at all. Building the small table to find the pattern is the standard contest move.

Python

n = 20
moves = [1, 2, 3]
win = [False] * (n + 1)
for i in range(1, n + 1):
    for m in moves:
        if i - m >= 0 and not win[i - m]:
            win[i] = True

print([i for i in range(n + 1) if not win[i]])
print([i for i in range(n + 1) if i % 4 == 0])

It prints

[0, 4, 8, 12, 16, 20]
[0, 4, 8, 12, 16, 20]

Change the rule and the pattern changes

Allow 1, 3 or 4 instead and the losing positions become 0, 2, 7, 9, 14, 16 — a pattern of period 7, and nobody would have guessed it.

That is why you always build the table first. Guessing the pattern before seeing it is how a wrong answer gets submitted with confidence.

Python

n = 20
moves = [1, 3, 4]
win = [False] * (n + 1)
for i in range(1, n + 1):
    for m in moves:
        if i - m >= 0 and not win[i - m]:
            win[i] = True

print([i for i in range(n + 1) if not win[i]])

It prints

[0, 2, 7, 9, 14, 16]

Several heaps at once

Heaps of 3, 4 and 5 sticks. On your turn take any number from one heap. Last stick wins.

The table from lesson 1 will not do: the positions are now triples of numbers, and there are far too many of them.

Xor the heap sizes

Here is the whole answer, and it is astonishing: the player to move loses exactly when the xor of all the heap sizes is 0.

3 xor 4 xor 5 is 2, so the first player wins. Nothing about this is obvious, which is why the next card checks it.

Python

piles = [3, 4, 5]

x = 0
for p in piles:
    x ^= p

print(x, x != 0)
print(1 ^ 4 ^ 5)

It prints

2 True
0

Checking it against a real search

Label every position of three small heaps the slow way — a position is winning if any move reaches a losing one — and compare with the xor rule. They agree everywhere.

This is exactly how you should treat a rule you cannot prove: search the small cases and see whether the rule survives.

Python

LIMIT = 5
memo = {}

def winning(a, b, c):
    if (a, b, c) in memo:
        return memo[(a, b, c)]
    piles = [a, b, c]
    result = False
    for i in range(3):
        for take in range(1, piles[i] + 1):
            nxt = piles[:]
            nxt[i] -= take
            if not winning(nxt[0], nxt[1], nxt[2]):
                result = True
    memo[(a, b, c)] = result
    return result

same = True
for a in range(LIMIT):
    for b in range(LIMIT):
        for c in range(LIMIT):
            if winning(a, b, c) != ((a ^ b ^ c) != 0):
                same = False

print(same)

It prints

True

And it tells you the move to play

If the xor is not 0, find a heap where pile ^ x is smaller than the pile, and cut it down to that. The new xor is 0, so your opponent is now the one in trouble.

From 3, 4, 5 with an xor of 2: 3 becomes 1, and 1 xor 4 xor 5 is 0.

Python

piles = [3, 4, 5]
x = 3 ^ 4 ^ 5

for i in range(len(piles)):
    if (piles[i] ^ x) < piles[i]:
        print(i, piles[i], piles[i] ^ x)

It prints

0 3 1

Winning and losing is not enough information

To combine several games you need more than "this one is lost". You need to know which Nim heap it behaves like.

That number is the position's Grundy value, and a Grundy value of 0 is exactly a losing position.

The smallest number not among the moves

Look at the Grundy values of every position you can move to. The value here is the smallest whole number missing from that list — usually called the mex.

For take-1-2-or-3 it comes out as n % 4, which is a nicer version of lesson 1's table: it says 0 at exactly the losing positions and tells you the heap size everywhere else.

Python

def grundy(n, moves):
    g = [0] * (n + 1)
    for i in range(1, n + 1):
        seen = set()
        for m in moves:
            if i - m >= 0:
                seen.add(g[i - m])
        x = 0
        while x in seen:
            x += 1
        g[i] = x
    return g

print(grundy(12, [1, 2, 3]))

It prints

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

A rule where the values are not obvious at all

Takes of 1, 3 or 4 give values that repeat with period 7 and never get above 3.

So a heap of 5 under this rule plays exactly like a Nim heap of 3, and a heap of 7 is already lost.

Python

def grundy(n, moves):
    g = [0] * (n + 1)
    for i in range(1, n + 1):
        seen = set()
        for m in moves:
            if i - m >= 0:
                seen.add(g[i - m])
        x = 0
        while x in seen:
            x += 1
        g[i] = x
    return g

print(grundy(12, [1, 3, 4]))

It prints

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

And then you xor them, exactly like Nim

Several independent games played side by side: work out each one's Grundy value and xor them together. Zero means the player to move loses.

That is the Sprague–Grundy theorem, and it means every game of this kind is secretly Nim.

Now put the two ideas together

Three heaps — 5, 7 and 9 sticks — and on your turn you may take 1, 3 or 4 from one heap.

Neither lesson answers this alone. Lesson 3 gives each heap a Nim size; lesson 2 says what to do with several Nim heaps.

Python

def grundy(n, moves):
    g = [0] * (n + 1)
    for i in range(1, n + 1):
        seen = set()
        for m in moves:
            if i - m >= 0:
                seen.add(g[i - m])
        x = 0
        while x in seen:
            x += 1
        g[i] = x
    return g

g = grundy(9, [1, 3, 4])
piles = [5, 7, 9]
values = [g[p] for p in piles]

print(values)
print(values[0] ^ values[1] ^ values[2])

It prints

[3, 0, 0]
3

Three, so the first player wins

The heap of 5 behaves like a Nim heap of 3; the heaps of 7 and 9 are both worth 0 and might as well not be there.

So the whole position is a single Nim heap of 3 — and the winning move is whichever take makes the xor 0.

Checking the whole thing by brute force

Search the game tree of two small heaps and compare with the xor of the Grundy values. They agree on every position.

When a contest problem invents a new rule, this is the safety net: write the slow search, write the clever rule, and run them against each other before submitting.

Python

MOVES = [1, 3, 4]
LIMIT = 8

def grundy(n, moves):
    g = [0] * (n + 1)
    for i in range(1, n + 1):
        seen = set()
        for m in moves:
            if i - m >= 0:
                seen.add(g[i - m])
        x = 0
        while x in seen:
            x += 1
        g[i] = x
    return g

def winning(a, b, memo):
    if (a, b) in memo:
        return memo[(a, b)]
    result = False
    for take in MOVES:
        if a - take >= 0 and not winning(a - take, b, memo):
            result = True
        if b - take >= 0 and not winning(a, b - take, memo):
            result = True
    memo[(a, b)] = result
    return result

g = grundy(LIMIT, MOVES)
memo = {}
same = True
for a in range(LIMIT + 1):
    for b in range(LIMIT + 1):
        if winning(a, b, memo) != ((g[a] ^ g[b]) != 0):
            same = False

print(same)

It prints

True

What makes a game "of this kind"

Both players have the same moves available, the game always ends, and the last player to move wins. That is an impartial game, and Sprague–Grundy covers all of them.

Chess is not one — the players move different pieces. Nor is any game with a draw. Check that before reaching for xor.