Misere games

Why this matters when you build with AI

Many game problems have one twist: the player who takes the last object loses. Ask an AI tool to solve a game with that rule, and it often gives the normal-play answer instead. The answer looks confident and is wrong. The mistake shows up only in small cases, such as one pile of one stone, and those are exactly the cases a judge uses.

The way to catch this is the same as in the previous lessons. Write a brute force program that tries every move, run it on every small input, and compare. For misere games the brute force needs one changed base case, and that is easy to get backwards. A player with no legal move wins in misere play. If you copy the normal-play base case, every small answer flips, and a wrong program can still pass a few large hand-picked tests.

Some terms first. Normal play is the rule from lesson 01: a player who cannot move loses. Misere play is the opposite rule: the player who makes the last move loses, so a player who cannot move wins. Misere is the usual name for this rule. The labels from lesson 01 still apply. A P-position is a loss for the player to move, and an N-position is a win for the player to move.

The idea: the last mover loses

Take one pile of one stone. In normal play the player to move takes the stone, and the opponent has no move, so the player to move wins. The label is N. In misere play the player to move must take the stone, which makes them the last mover, so they lose. The label is P. The position is the same and the label flips.

Now take two piles of one stone each. In normal play the player to move takes one stone, leaving one pile of one. The opponent takes it and the first player cannot move, so the first player loses. The label is P. In misere play the player to move takes one stone, leaving one pile of one for the opponent. The opponent must take it and loses. The label is N.

The recurrence does not change. A position is winning when some move reaches a losing position. The only change is the label of the position with no moves at all. In normal play it is P, since the player to move loses. In misere play it is N, since the player to move wins. For a subtraction game, where the only moves remove a fixed set of amounts, this single change is the whole difference.

Here is the subtraction game with allowed amounts {1, 2, 5}, labelled once in normal play and once in misere play, for heap sizes 0 to 20. The program that prints these lines is in the machine check below.

normal 0..20: PNNPNNPNNPNNPNNPNNPNN
misere 0..20: NPNNPNNPNNPNNPNNPNNPN

The two rows are not related by a simple flip. Some labels match and some do not, so you cannot take a normal-play table and flip it. You need to compute the misere table separately.

Machine check of the tables

This Python program computes both tables, counts the misere Nim positions it checks against a full search, and prints the two-heap example from the Grundy section. It needs no input.

Python · editable

from functools import lru_cache
from itertools import combinations_with_replacement

def misere_win(piles):
    """True when the player to move wins misere Nim. Brute force over all moves."""
    return _mw(tuple(sorted(piles)))

@lru_cache(maxsize=None)
def _mw(piles):
    if all(p == 0 for p in piles):
        return True  # no move available: the player to move wins in misere play
    for i, p in enumerate(piles):
        for new in range(p):
            nxt = list(piles)
            nxt[i] = new
            if not _mw(tuple(sorted(nxt))):
                return True
    return False

def formula_win(piles):
    x = 0
    for p in piles:
        x ^= p
    if max(piles) >= 2:
        return x != 0
    return x == 0

def normal_win(piles):
    x = 0
    for p in piles:
        x ^= p
    return x != 0

bad = []
count = 0
for n in range(1, 5):
    for piles in combinations_with_replacement(range(0, 6), n):
        count += 1
        if misere_win(piles) != formula_win(piles):
            bad.append(piles)
print("misere Nim positions checked:", count, "mismatches:", len(bad))

# Where misere and normal play differ, all piles must be at most 1.
diff_all_small = True
for n in range(1, 5):
    for piles in combinations_with_replacement(range(0, 6), n):
        if misere_win(piles) != normal_win(piles) and max(piles) >= 2:
            diff_all_small = False
print("differ only when all piles <= 1:", diff_all_small)

# Misere subtraction game with moves {1, 2, 5}, normal and misere side by side.
moves = [1, 2, 5]
N = 20
norm = [False] * (N + 1)
mis = [False] * (N + 1)
mis[0] = True  # misere: no move means the player to move wins
for n in range(N + 1):
    if n > 0:
        norm[n] = any(k <= n and not norm[n - k] for k in moves)
        mis[n] = any(k <= n and not mis[n - k] for k in moves)
print("normal 0..20:", "".join("N" if norm[n] else "P" for n in range(N + 1)))
print("misere 0..20:", "".join("N" if mis[n] else "P" for n in range(N + 1)))

# Grundy failure: a heap of 1 is misere P, but two heaps of 1 are misere N.
print("misere heap 1 wins:", misere_win((1,)), " two heaps of 1 wins:", misere_win((1, 1)))

Real output, run with Python 3.14.4 on Linux:

misere Nim positions checked: 209 mismatches: 0
differ only when all piles <= 1: True
normal 0..20: PNNPNNPNNPNNPNNPNNPNN
misere 0..20: NPNNPNNPNNPNNPNNPNNPN
misere heap 1 wins: False  two heaps of 1 wins: True

The program checks 209 multisets of up to four piles, each size from 0 to 5. The count 209 is the number of ways to choose 1, 2, 3 or 4 piles from the sizes 0 to 5 with repetition allowed.

Misere Nim: the rule

Nim has any number of piles. A move takes at least one stone from one pile, and any number up to the whole pile is allowed. Let x be the XOR of all pile sizes. XOR, written ^ in C++, combines numbers bit by bit: 1 ^ 1 is 0, and 2 ^ 3 is 1. Let big be the number of piles with at least 2 stones.

The rule for misere Nim is:

If some pile has at least 2 stones, the player to move loses exactly when x is 0.
If every pile has at most 1 stone, the player to move loses exactly when the number of 1-piles is odd.

Compare this with normal Nim, where the player to move loses exactly when x is 0. The two rules agree whenever some pile has at least 2 stones. They differ only when every pile has at most 1 stone. This is the claim the module asks you to check.

Here is a worked example. Piles (3, 1): big is 1 and x is 3 ^ 1 = 2, which is not 0, so the player to move wins. To find the winning move, look for a move that leaves all piles at most 1 with an odd number of 1-piles. Take the pile of 3 down to 0. The remaining piles are (0, 1), one 1-pile, which is odd. The opponent must take that last stone and loses. It is the only winning move: lowering the 3 to 2 or 1, or taking the 1-pile, leaves the opponent a winning position.

Proof

The proof uses induction on the total number of stones. Assume the rule holds for every smaller position. Write L for the set of losing positions the rule describes: positions with big at least 1 and x equal to 0, or with big equal to 0 and an odd number of 1-piles. Every other position must have a winning move into L.

First, a fact used twice: if big is at least 1 and x is 0, then big is at least 2. Here is why. If there were exactly one pile a with at least 2 stones, the other piles would all be 0 or 1, and their XOR y is 0 or 1. The total XOR is a ^ y. That cannot be 0, because a is at least 2 and y is at most 1, so they differ. So big = 1 with x = 0 is impossible.

Case A: big is at least 1 and x is 0. Any move changes one pile, so the new x is not 0. A move changes only one pile, and there are at least two large piles, so at least one pile still has 2 or more stones. So the new position has big at least 1 and x not 0. By the rule it is a winning position, which means every move from a losing position leads to a win. Case A is therefore consistent with the rule.

Case B: big is at least 2 and x is not 0. Take a pile a where a ^ x is smaller than a. This pile exists because the highest set bit of x is set in some pile. Reduce that pile to a ^ x. The new XOR is 0. Another pile with 2 or more stones is untouched, so the new position has big at least 1 and x equal to 0. It is in L, so the position is winning.

Case C: big is 1 and x is not 0. Let c be the number of 1-piles among the other piles. Reduce the large pile to 0 if c is odd, or to 1 if c is even. Either target is smaller than the large pile because the large pile has at least 2 stones. The new position has only piles of 0 and 1, and the number of 1-piles is c plus one when the target is 1. In both choices the number of 1-piles becomes odd, so the new position is in L.

Case D: every pile is 0 or 1. Let k be the number of 1-piles. A move takes one 1-pile to 0, so the count drops by one. If k is odd, every move leads to an even count, which is not in L, so it is a win for the opponent. The position is a loss, as the rule says. If k is even, including k = 0, then k is at least 2 whenever there is a move, and taking one 1-pile leaves an odd count, which is in L. The position is a win, as the rule says.

Those four cases cover every position, so the rule holds. The induction also covers the empty position with no piles: it has big = 0 and zero 1-piles, which is even, so the player to move wins. That matches the misere base case.

The proof shows why only the all-ones case differs. In Case A and Case B the winning moves match normal Nim, and they keep a pile of at least 2 stones in play. In Case C and Case D the normal-play rule would ask only for the XOR, and the XOR does not decide the outcome once the last object is a loss.

Why Grundy values fail in general

Lesson 03 uses Grundy values for normal play. A position's Grundy value is a number, and a sum of independent games has the XOR of the values. That rule is a theorem for normal play. It does not carry over to misere play.

The simplest case shows it. Take a single heap of 1. In misere play, its only move takes the last stone, so the player to move loses. The heap is a P-position. Take two heaps of 1. The player to move takes one, leaving one heap of 1 for the opponent, who must take the last stone and lose. The two heaps form an N-position. Two P-positions added together gave an N-position, so the outcome of a sum cannot be read off the outcomes of its parts.

The machine check above prints the two outcomes:

misere heap 1 wins: False  two heaps of 1 wins: True

Honest scope: this lesson gives the rule for misere Nim and checks it, but it does not give a general theory for every misere game. Most misere games need their own analysis. The method that works is the same as before: write the brute force first, look at the table, guess a rule from the table, prove it by induction, and then check it against the brute force.

Standard technique in C++17

The rule is a single pass over the piles. It computes the XOR and whether any pile has at least 2 stones. It answers First wins when the player to move wins, and Second wins otherwise.

#include <bits/stdc++.h>
using namespace std;
 
// True when the player to move wins misere Nim (last mover loses).
bool misere_first_wins(const vector<long long> &piles) {
    long long x = 0;
    bool some_pile_at_least_two = false;
    for (long long a : piles) {
        x ^= a;
        if (a >= 2) some_pile_at_least_two = true;
    }
    if (some_pile_at_least_two) return x != 0;
    return x == 0;  // every pile is 0 or 1: win when the count of 1s is even
}
 
int main() {
    int n;
    cin >> n;
    vector<long long> piles(n);
    for (auto &a : piles) cin >> a;
    cout << (misere_first_wins(piles) ? "First wins" : "Second wins") << "\n";
    return 0;
}

Real output with input 2 and piles 1 1, compiled with g++ -std=c++17 -O2 -Wall -Wextra on g++ 15.2.0 for Linux, with no warnings:

First wins

This matches the table: two piles of one stone is a win for the player to move in misere play. The function was also compared with a full game search on all 209 multisets of up to four piles, each size from 0 to 5. There were 0 mismatches.

Complexity: one pass over the piles, so O(n) time and O(1) extra memory.

Worked original problem: Ballast piles

Two players share several piles of stones. On a turn, the player to move takes at least one stone from one pile. The player who takes the last stone loses. Each test case asks who wins with perfect play. If the first player wins, also print one winning move that the judge can check.

Input:

Line 1: t, the number of test cases, with 1 at most t at most 10000.
For each test case, line 1: n, the number of piles, with 1 at most n at most 200000.
The next line: n pile sizes a_1 to a_n, each from 1 to 10^9.
The sum of n over all test cases is at most 200000.

Output, one line per test case:

Second if the player to move loses.
First i v if the player to move wins. Here i is the 1-based index of the pile, and v is the new size of that pile, with 0 at most v less than a_i. After the move, the position must be a loss for the opponent.

The judge accepts any winning move, so the output is checked, not compared with one fixed answer.

Example input:

Expected output: Second, Second, First 1 0, Second, First 1 0, First 1 1, First 1 3, First 2 2. Each First line is a winning move, and the solution below prints one of them.

The solution

The solution uses the three cases from the proof. If every pile is 1, the count decides. If some pile is large and the XOR is 0, the player to move loses. If there are at least two large piles, use the normal Nim move. If there is exactly one large pile, reduce it to leave an odd count of 1-piles.

#include <bits/stdc++.h>
using namespace std;
 
// Misere Nim: the player who takes the last object loses.
// Input: t, then for each test: n, then n pile sizes a_i (1 <= a_i <= 1e9).
// Output per test: "Second" if the player to move loses, else "First i v"
// meaning: take from pile i (1-based) so that it becomes v.
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (auto &x : a) cin >> x;
 
        long long x = 0;
        int big = 0;        // number of piles with at least 2 objects
        int ones = 0;       // number of piles with exactly 1 object
        int big_idx = -1;   // index of the last pile with at least 2 objects
        for (int i = 0; i < n; ++i) {
            x ^= a[i];
            if (a[i] >= 2) {
                ++big;
                big_idx = i;
            } else {
                ++ones;
            }
        }
 
        if (big == 0) {
            // Every pile is 1. The player to move wins exactly when the count is even.
            if (ones % 2 == 1) {
                cout << "Second\n";
            } else {
                // Make the count odd by taking one pile of size 1 to 0.
                int i = 0;
                while (a[i] != 1) ++i;
                cout << "First " << i + 1 << " 0\n";
            }
            continue;
        }
 
        if (x == 0) {
            // Some pile is at least 2 and the XOR is 0: a losing position.
            cout << "Second\n";
            continue;
        }
 
        if (big >= 2) {
            // Ordinary Nim move: fix the XOR. Another pile of at least 2 stays, so the rule still applies.
            for (int i = 0; i < n; ++i) {
                long long target = a[i] ^ x;
                if (target < a[i]) {
                    cout << "First " << i + 1 << " " << target << "\n";
                    break;
                }
            }
        } else {
            // Exactly one big pile. Leave only piles of size 0 or 1, with an odd number of 1s.
            int v = (ones % 2 == 0) ? 1 : 0;
            cout << "First " << big_idx + 1 << " " << v << "\n";
        }
    }
    return 0;
}

Real output on the example input above, compiled with g++ -std=c++17 -O2 -Wall -Wextra on g++ 15.2.0 for Linux, with no warnings:

Second
Second
First 1 0
Second
First 1 0
First 1 1
First 1 3
First 2 2

Check two lines by hand. The seventh test is piles 5 2 1: the XOR is 6. The move First 1 3 leaves 3 2 1, which has two large piles and XOR 3 ^ 2 ^ 1 = 0, so it is a loss for the opponent. The last test is piles 2 3: the XOR is 1, and the move First 2 2 leaves 2 2, whose XOR is 0.

How it was tested

The checker is a separate program. It generates random test cases with 1 to 4 piles, each size from 1 to 4, plus a short list of hand-picked cases such as [2] and [2, 1]. For each case it computes the true answer with a full game search, memoised on the sorted pile list, and it does not use the rule. It then runs the solution once on all cases.

For each First line, the checker applies the printed move and confirms that the result is a loss for the opponent in the full search. For each Second line, it confirms that the position is a loss in the full search.

Two runs were made, with random seeds 7 and 99. Each had 1508 cases. Seed 7 verified 1240 winning moves with 0 errors. Seed 99 verified 1199 winning moves with 0 errors.

The first version of the solution failed. In the single-large-pile case it chose v = 0 when the count of 1-piles was even. For input [2] it printed First 1 0, which takes the last stone and loses. The checker reported:

MOVE DOES NOT WIN [2] First 1 0

The fix is the line int v = (ones % 2 == 0) ? 1 : 0;. After the fix the errors dropped to 0.

Complexity

Each test case takes O(n) time, with one pass to compute the XOR and the counts, and one more pass in the normal Nim case. Memory is O(n) for the piles.

Common mistakes

Using the normal-play XOR rule. The normal rule says the first player wins when the XOR is not 0. For a single pile of 1 the normal rule says the first player wins, and the misere answer is the reverse. The symptom is a First line on input 1 and 1 where the right output is Second.

Forgetting the all-ones case. The only place misere Nim differs from normal Nim is when every pile has at most 1 stone. A solution that uses the normal rule is right on every position with a pile of at least 2 stones, so random tests with large piles will not expose it. Test the one-pile and two-pile cases by hand.

Using the normal base case in a brute force. If the empty position is labelled as a loss for the player to move, the brute force gives the normal-play answer. The symptom is that the brute force and the formula agree on some inputs and disagree on [1].

Taking the last object as a winning move. The move from [2] to [0] looks like progress, since the pile is empty, but the mover took the last stone. The checker showed this as MOVE DOES NOT WIN [2] First 1 0.

Getting the parity wrong after the move. When one big pile is left, the count of 1-piles must be odd after the move, not even. A check on the sample input catches it, because [3, 1, 1] must print First 1 1, which leaves three 1-piles.

Assuming Grundy values work for misere play. The XOR of Grundy values is a theorem for normal play. Two heaps of 1, each a misere P-position, form a misere N-position. Use the misere analysis instead.

Checklist to keep

In misere play, a player with no legal move wins. The base case is the opposite of normal play.
Misere Nim differs from normal Nim only when every pile has at most 1 stone.
With a pile of at least 2 stones, a position is losing exactly when the XOR is 0.
With every pile at most 1, a position is losing exactly when the count of 1-piles is odd.
The winning move from one big pile leaves an odd count of 1-piles, not an even one.
Check the smallest inputs by hand, since misere errors usually show up there.
Compare any misere rule with a brute force on all small inputs before you trust it.

Hands-on exercise

Work in your own scratch folder. You need Python 3.14 or newer and g++ with C++17 support.

Step 1. Write a Python program that prints the normal and misere tables for the subtraction game with allowed amounts {1, 3, 4}, for heap sizes 0 to 20. Use one loop for each table. The only difference is the base case for heap 0.

Step 2. Find the first heap size where the two tables differ. Explain the result in one sentence, using the base case and the move that causes it.

Step 3. Write a brute force for misere Nim with at most 3 piles, each at most 4 stones, and compare it with the rule from the standard technique. The two should agree on every position.

Step 4. Compile the C++ rule function and feed it the piles 3 1 1. Predict the output before you run it, then check your prediction.

Prompt to try with an AI tool

Use this prompt, then check the answer with the steps above.

Solve misere Nim in C++17. The first line has t (up to 10000 test cases). Each test case
has n (up to 200000 piles) on one line and then n pile sizes up to 10^9 on the next line.
A move takes at least one stone from one pile. The player who takes the last stone loses.
For each test case print Second if the player to move loses, else print First i v, where
i is the 1-based pile and v is the new size of that pile after a move that leaves a losing
position. Explain in three sentences why the rule differs from normal Nim, then give the
output for these piles: [1], [2], [1, 1], [3, 1, 1].

A good answer uses the XOR and a count of piles with at least 2 stones, and it treats the all-ones case as a separate rule. For [1] it prints Second. For [2] it prints First 1 1, leaving one stone for the opponent. For [1, 1] it prints First 1 0. For [3, 1, 1] it prints First 1 1. Check the single-pile lines first. A common wrong answer prints First 1 0 for [2], which takes the last stone, and the brute force in step 3 catches it.

Practice

These take a few minutes each. Try them on paper or in your scratch folder before opening the answers.

Practice 1: one pile of 1, two piles of 1, three piles of 1

Find the outcome for the player to move in misere Nim when the piles are (1), (1, 1) and (1, 1, 1).

Hint: Use the all-ones rule. Count the 1-piles and ask whether the count is odd.

Show the answer

(1) is a loss for the player to move, since they must take the last stone. (1, 1) is a win, since they take one and leave one for the opponent. (1, 1, 1) is a loss, since the count is odd: after any move the count is even, and an even count is a win for the opponent.

Practice 2: the winning move for piles 3 and 1

For the piles (3, 1), name a winning move, and show that the result is a loss for the opponent.

Hint: The position has exactly one pile with at least 2 stones. Leave only piles of size 0 and 1 with an odd count of 1s.

Show the answer

Take the pile of 3 down to 0. The position becomes (0, 1), which has one 1-pile, an odd count. The opponent must take that stone, and that makes them the last mover, so they lose. Taking the pile of 3 down to 1 gives (1, 1), which has two 1-piles, an even count, and is a win for the opponent, so that move is wrong.

Practice 3: the misere subtraction table for 5

For the subtraction game with allowed amounts {1, 2, 5}, find whether heap 5 is a win or a loss for the player to move in misere play. Use the misere table in this lesson.

Hint: Heap 0 is a win for the player to move in misere play, because there is no move. Look for a move from 5 to a heap that is a loss.

Show the answer

Heap 5 is a win in misere play. Take 1 stone, leaving heap 4. The misere table gives heap 4 as P, a loss for the player to move. The table row starts NPNNP, so heap 4 is the fifth letter, which is P.

Practice 4: why three heaps of 1 are not a sum rule

Show that the sum of two misere P-positions can be an N-position, using heaps of one stone, then explain why three heaps of one stone do not break the rule for the same reason.

Hint: Use the rule for piles of 1 and count the piles.

Show the answer

One heap of 1 is a P-position in misere play. Two heaps of 1 together form an N-position, since the count is even. Three heaps of 1 are a P-position, since the count is odd, so the sum of three P-positions is still P here. The rule breaks in the two-heap case, and the three-heap case happens to agree. A single counterexample is enough to show that the sum rule fails in general.

Practice 5: find the bug in a two-line change

A solution uses int v = (ones % 2 == 0) ? 0 : 1; in the single-large-pile case. For input 1 and 2, it prints First 1 0. Explain why this is wrong and say what the correct line is.

Hint: After the move, the position must have an odd number of 1-piles.

Show the answer

Taking the pile of 2 down to 0 leaves no stones. The opponent has no move and wins, because the last mover is now the first player. The correct choice is v = 1, which leaves one 1-pile. The opponent must take it, and they lose.

Summary

Misere play changes one base case, and that changes the answer. For misere Nim, the XOR rule still decides every position with a pile of at least 2 stones, while the all-ones positions follow the parity of the count of 1-piles. Grundy values from normal play do not add up for misere games, so each misere game needs its own check. Write the brute force first, with the correct base case, and compare every rule against it on small inputs.

Sources and scope

No books, papers or histories are named here. Every claim is either derived in the text or checked by the programs described above.

The rule, the proof and the claim about normal and misere differences were checked by a full game search on all 209 multisets of up to four piles, each size up to 5, in Python 3.14.4 on Linux. The C++ function was compiled with g++ 15.2.0 and checked on the same 209 positions. The worked solution was checked on 3016 random and hand-picked cases over two seeds, with 0 errors. Other pile sizes and move sets give other answers, so rerun the checks for your own inputs.