Why this matters when you build with AI
Ask an AI tool for a Nim solver and it can write code that passes the sample and fails on other inputs. Two errors are easy to make. The first is a rule based on the sum of the piles, which is wrong for most positions. The second is a move that picks a pile the wrong way, so the new pile is bigger than the old one. That second error prints a move the game does not allow, and nothing stops the program from printing it.
You catch both errors with a checker. The checker takes the program's answer, checks that the move is legal, and checks that the position it leaves has XOR zero. Then you run a brute force on small inputs, which tries every move, to confirm the rule itself. This lesson gives the rule, the proof, the code, and both checks.
Terms
Nim is a game with several piles of stones. A move takes one or more stones from exactly one pile. The player who cannot move loses. That happens when every pile is empty.
XOR is the bitwise exclusive or. It is written ^ in C++. For each bit position, the result bit is 1 when the two input bits differ, and 0 when they are the same. For example, 3 ^ 5 is 011 ^ 101 = 110, which is 6. XOR of more than two numbers is done one pair at a time, so 3 ^ 4 ^ 5 is 011 ^ 100 ^ 101 = 010, which is 2.
The highest set bit of a number is the largest bit position where it has a 1. The number 2 is 10 in binary, so its highest set bit is bit 1. The number 6 is 110, so its highest set bit is bit 2.
The P-positions and N-positions from the first lesson still apply. A P-position is a losing position for the player to move. An N-position is a winning one.
The rule: Bouton's theorem
Charles L. Bouton published the complete theory of Nim in 1901-1902, in Annals of Mathematics, under the title "Nim, a game with a complete mathematical theory." The result is the rule below. I read the publication record, not the full paper, so the proof given here is my own.
Bouton's theorem. A Nim position is a P-position, which means the player to move loses, exactly when the XOR of all pile sizes is 0.
Take the piles 3, 4 and 5. In binary they are 011, 100 and 101. Their XOR is 010, which is 2. The XOR is not 0, so the player to move wins. The rule also says how. The XOR has bit 1 set, and the pile of size 3 has bit 1 set too. So taking 2 stones from pile 3 leaves 1, 4 and 5, with XOR 001 ^ 100 ^ 101 = 000.
Take the piles 1, 2 and 3. The XOR is 0, so the player to move loses. Any move they make, the other player can answer and restore XOR 0. You will see the proof of this below.
Proof
Let X be the XOR of all the piles. The proof has two claims.
Claim A. If X is 0, every legal move makes the XOR nonzero. A move changes one pile from size a to a smaller size b. The XOR of the other piles is X ^ a, which is a because X is 0. After the move, the total XOR is a ^ b. Since a is not equal to b, the XOR a ^ b is not 0.
Example: from 1, 2, 3 take one stone from the pile of 3. The piles become 1, 2, 2 with XOR 1. The formula says 3 ^ 2 = 1, which matches.
Claim B. If X is not 0, some legal move makes the XOR 0. Let h be the highest set bit of X. The XOR has bit h set, so an odd number of piles have bit h set. Pick one such pile, with size a. Let b = a ^ X. Two facts follow.
- Bit
hofbis 0, becauseaandXboth have bithset, and the XOR of two 1s is 0. - Every bit above
his the same inaandb, becauseXhas no bits aboveh.
So b is smaller than a, since they agree above bit h and b has a 0 where a has a 1 at bit h. The move takes a - b stones from that pile, which is at least 1 and at most a, so it is legal. The new XOR is X ^ a ^ b = X ^ X = 0, because a ^ b = X.
Why the two claims prove the theorem
Label every position with XOR 0 as P, and every other position as N. The empty position has XOR 0 and no moves, so it is P, which is right. Claim A says that no move goes from one P-position to another. Claim B says that every N-position has a move to a P-position. These are exactly the two rules from the first lesson. The labels were built by working from smaller positions upward, since each move removes stones, so the labels are correct.
The winning move by hand
Here is the winning move for 3, 4, 5, written out in binary.
pile 1: 011 (3)
pile 2: 100 (4)
pile 3: 101 (5)
XOR: 010 (2) highest set bit is bit 1Only pile 1 has bit 1 set, so pile 1 is the one to change. Its new size is 3 ^ 2 = 1, so take 2 stones. The position becomes 1, 4, 5 with XOR 0.
The move is not always unique. For 3, 4 and 5 it is the only winning move, and a short check in the practice section explains why.
Standard technique in C++17
Put the rule, the winning move and the brute force in one header. The header uses __builtin_clz, a GCC and Clang built-in that counts leading zero bits of an unsigned int. It is undefined when its argument is 0, so the code checks for a zero XOR first.
#pragma once
#include <bits/stdc++.h>
using namespace std;
// A Nim position is a list of pile sizes. A move takes one or more stones from one pile.
// The player who cannot move (all piles empty) loses.
// Bouton's rule: a position is losing for the player to move exactly when the XOR of the piles is 0.
bool is_losing(const vector<int> &piles) {
int x = 0;
for (int a : piles) x ^= a;
return x == 0;
}
// Returns {pile index, new size} for a move that reaches a losing position.
// Returns {-1, -1} when the position is already losing (no such move is needed).
pair<int, int> winning_move(const vector<int> &piles) {
int x = 0;
for (int a : piles) x ^= a;
if (x == 0) return {-1, -1};
int h = 31 - __builtin_clz((unsigned)x); // highest set bit of x
for (int i = 0; i < (int)piles.size(); ++i) {
if ((piles[i] >> h) & 1) return {i, piles[i] ^ x};
}
return {-1, -1}; // not reached: some pile has bit h set when x != 0
}
// Every legal move, as the resulting position. A pile of size a can become any size t with 0 <= t < a.
vector<vector<int>> all_moves(const vector<int> &piles) {
vector<vector<int>> out;
for (int i = 0; i < (int)piles.size(); ++i) {
for (int t = 0; t < piles[i]; ++t) {
vector<int> next = piles;
next[i] = t;
out.push_back(next);
}
}
return out;
}
// Brute force: plain game search. Memo key is the sorted pile list, since the order of piles does not matter.
map<vector<int>, bool> brute_memo;
bool brute_win(vector<int> piles) {
sort(piles.begin(), piles.end());
auto it = brute_memo.find(piles);
if (it != brute_memo.end()) return it->second;
bool res = false;
for (const auto &nxt : all_moves(piles)) {
if (!brute_win(nxt)) {
res = true;
break;
}
}
brute_memo[piles] = res;
return res;
}The demo below uses the header on five positions. The output is real, from g++ 15.2.0 with -std=c++17 -O2 -Wall -Wextra.
#include "nim_core.hpp"
int main() {
vector<vector<int>> examples = {{3, 4, 5}, {1, 2, 3}, {7}, {0, 0}, {5, 5, 2}};
for (const auto &p : examples) {
int x = 0;
for (int a : p) x ^= a;
cout << "piles";
for (int a : p) cout << " " << a;
cout << " | xor " << x << " | losing " << (is_losing(p) ? "yes" : "no");
auto [i, t] = winning_move(p);
if (i >= 0) {
cout << " | take " << (p[i] - t) << " from pile " << (i + 1)
<< " (its new size " << t << ")";
}
cout << "\n";
}
return 0;
}piles 3 4 5 | xor 2 | losing no | take 2 from pile 1 (its new size 1)
piles 1 2 3 | xor 0 | losing yes
piles 7 | xor 7 | losing no | take 7 from pile 1 (its new size 0)
piles 0 0 | xor 0 | losing yes
piles 5 5 2 | xor 2 | losing no | take 2 from pile 3 (its new size 0)A Python version is short and fast enough for these sizes. It is self-contained, so the site can run it:
Real output, Python 3.14.4:
[3, 4, 5] xor 2 take 2 from pile 1
[1, 2, 3] xor 0 losing
[7] xor 7 take 7 from pile 1
[2, 2, 1] xor 1 take 1 from pile 3Complexity
The XOR and the winning move each take O(n) time for n piles, with O(1) extra memory. The move generator in all_moves returns one position per legal move. A position with piles summing to S has S legal moves, since a pile of size a has a possible new sizes. The brute force is much slower, since it visits every position reachable from the start, and it is only for small inputs.
Testing the rule against brute force
The brute force plays the game without any rule. The test below compares it with Bouton's rule on every position with 1 to 4 piles, each from 0 to 8. That is 7,380 positions. For each one it checks three things: the rule matches the brute force, a winning position has a winning move that is legal, and a losing position has no winning move.
#include "nim_core.hpp"
// Every ordered pile list with 1 to 4 piles, each pile from 0 to 8.
// For each position we check three things against the brute force.
int main() {
long long checked = 0, winners = 0, losers = 0;
for (int len = 1; len <= 4; ++len) {
int total = 1;
for (int i = 0; i < len; ++i) total *= 9;
for (int code = 0; code < total; ++code) {
vector<int> p(len);
int c = code;
for (int i = 0; i < len; ++i) {
p[i] = c % 9;
c /= 9;
}
bool win = brute_win(p);
if (win != !is_losing(p)) {
cout << "rule mismatch\n";
return 1;
}
if (win) {
++winners;
auto [i, t] = winning_move(p);
if (i < 0 || t < 0 || t >= p[i]) {
cout << "illegal or missing move\n";
return 1;
}
vector<int> next = p;
next[i] = t;
if (brute_win(next)) {
cout << "move does not reach a losing position\n";
return 1;
}
} else {
++losers;
if (winning_move(p).first != -1) {
cout << "losing position gave a move\n";
return 1;
}
}
++checked;
}
}
cout << "checked " << checked << " positions: " << winners << " winning, " << losers << " losing\n";
cout << "all match the brute force\n";
return 0;
}Real output, compiled with g++ -std=c++17 -O2 -Wall -Wextra:
checked 7380 positions: 6742 winning, 638 losing
all match the brute forceThe same header also ran a random check with up to 5 piles, each up to 15, on 3,000 positions, with no mismatches. The brute force memo keeps the work small for these sizes.
Worked original problem: Pile referee
A referee gives you several Nim positions. For each one, say whether the player to move loses, and if not, give a winning move.
Input:
- Line 1:
T, the number of positions, with 1 at mostTat most 10000. - For each position, a line with
n, the number of piles, then a line withnpile sizes. - The total of all
nover all positions is at most 200000. Each pile size is from 0 to 10^9.
Output: for each position, one line.
secondwhen the XOR of the piles is 0.first i kotherwise, whereiis the 1-based index of a pile andkis the number of stones to take from it, with 1 at mostkat most that pile's size, and the result having XOR 0.
Many winning moves can exist, so any valid winning move is accepted. A checker verifies each answer. The rule and the brute force are tested separately, as above.
Example input:
3
3
3 4 5
2
2 2
4
0 0 0 6Real output of the solution below on this input:
first 1 2
second
first 4 6Check the first line: 3, 4, 5 has XOR 2, the highest bit is 1, pile 1 is 3, and taking 2 leaves 1. Check the third line: 0, 0, 0, 6 has XOR 6, the highest bit is 2, pile 4 is 6, and taking all 6 stones leaves XOR 0.
The solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n);
int x = 0;
for (int &v : a) {
cin >> v;
x ^= v;
}
if (x == 0) {
cout << "second\n";
continue;
}
// Highest set bit of x. Some pile has this bit set, because the XOR has it.
int h = 31 - __builtin_clz((unsigned)x);
for (int i = 0; i < n; ++i) {
if ((a[i] >> h) & 1) {
int target = a[i] ^ x; // smaller than a[i], so the move is legal
cout << "first " << (i + 1) << " " << (a[i] - target) << "\n";
break;
}
}
}
return 0;
}Values up to 10^9 are below 2^30, so every XOR of them also fits in an int. If the values could reach 10^18, the code would need long long and __builtin_clzll.
How it was tested
The checker in Python generates 20,000 random positions, each with 1 to 6 piles of size 0 to 40. It runs the solution once on all of them, then checks every line. A second line must match an XOR of 0. A first i k line must have i in range, k between 1 and that pile's size, and an XOR of 0 after the move. All 20,000 passed, and the three sample positions passed too.
The checker proves that each answer is a legal winning move. It does not prove that the rule is right, since the rule decides whether second is correct. That part was checked by the exhaustive test above, with 7,380 positions and no mismatches.
Complexity
The solution reads all the input once and does O(n) work per position, so the total time is O(sum of n). Memory is O(n) for the largest position.
Common mistakes
Using the sum of the piles. A rule such as "sum even means losing" is wrong. The sample positions show it: 3, 4 and 5 sum to 12, which is even, but the demo prints losing no for them, with a winning move that takes 2 stones from pile 1.
Picking the pile by size instead of by bit. Here is a wrong version of the solution that picks the first pile larger than the XOR. It was compiled and run. The input was one position with piles 2, 2 and 1:
first 1 -1The XOR is 1. The first pile is 2, which is larger than 1, so the code chose it. The new size would be 2 ^ 1 = 3, which is larger than 2, so the move adds stones. The printed count -1 is not a legal number of stones to take. A checker rejects this at once. The correct answer is first 3 1, since pile 3 has bit 0 set and taking 1 stone leaves XOR 0.
Choosing the lowest set bit. The same problem happens with the lowest set bit of the XOR. Running that version on piles 2 and 1 printed first 2 -1, which is also illegal. The highest set bit is the one that makes a ^ X smaller than a.
Calling __builtin_clz on zero. The result is undefined when the argument is 0. Check that the XOR is nonzero before you find its highest bit, as the solution does.
Trusting a rule that was tested on one sample. Sample tests often include only the easy cases. Run the brute force on all small positions, as the test above does, before you trust a Nim solver.
Checklist to keep
- A Nim position is losing exactly when the XOR of the pile sizes is 0.
- A winning move uses the highest set bit of the XOR: pick a pile with that bit, and reduce it to
pile ^ XOR. - A move must take at least one stone, so the new size must be smaller than the old one.
- Check the XOR is not 0 before you find its highest bit.
- Use a checker for the answers and a brute force for the rule.
- Never trust a sum-based rule for Nim.
Hands-on exercise
Write a move generator in your own scratch folder. For a list of piles, it returns every legal next position, one for each pile and each smaller size. Check that for 3 4 5 it returns 12 positions, since the piles sum to 12.
Next, write a brute force that decides winning or losing with memoised recursion, and compare it with the XOR rule for every position with 1 to 3 piles, each from 0 to 6. You should see no mismatches. Then solve the Pile referee problem, and run it against the checker on your own random positions.
A good answer has the same numbers as the rule on every small position and a legal move on every winning one. A weak answer checks only the three sample positions. If your solver passes the sample but fails the checker on a random position, look at the pile selection first.
Prompt to try with an AI tool
Use this prompt, then check the answer with the steps above.
Write a Python function winning_move(piles) for Nim, where a move takes one or more stones
from exactly one pile. Return the pile index (0-based) and the new size of that pile as a
tuple, or None if the position is losing for the player to move. Use Bouton's rule, not
brute force. Then explain in two sentences why the pile you change must have a particular
bit set, and run it on [2, 2, 1].A good answer returns (2, 0) for [2, 2, 1], which means pile index 2, 0-based, is reduced to size 0, taking 1 stone. The explanation names the highest set bit of the XOR. Check the new size: it must be smaller than the old size. A common wrong answer returns (0, 3), which adds stones to the first pile, and the checker rejects it.
Practice
These take a few minutes each. Try them on paper or in your scratch folder before opening the answers.
Practice 1: a winning move for 6, 7, 9
Find the XOR of the piles 6, 7 and 9, and give a winning move.
Hint: Write each number in binary, then find the highest set bit of the XOR.
Show the answer
In binary, 6 is 0110, 7 is 0111, and 9 is 1001. The XOR is 0110 ^ 0111 ^ 1001 = 1000, which is 8. The highest set bit is bit 3. Only pile 9 has bit 3 set. Its new size is 9 ^ 8 = 1, so take 8 stones from pile 3. The position becomes 6, 7, 1 with XOR 0110 ^ 0111 ^ 0001 = 0000.
Practice 2: how many winning moves does 3, 4, 5 have?
Count every move that leaves XOR 0.
Hint: A move on pile i that leaves XOR 0 must make the pile equal to the XOR of the other piles.
Show the answer
Exactly one. For pile 1, the other piles have XOR 4 ^ 5 = 1, so the new size must be 1, which is less than 3, so that move is legal. For pile 2, the other piles have XOR 3 ^ 5 = 6, which is not less than 4. For pile 3, the other piles have XOR 3 ^ 4 = 7, which is not less than 5. So the only winning move is pile 1 to size 1. A script that tries every legal move finds only this one.
Practice 3: a winning move for 12, 10, 7
Find a winning move for piles 12, 10 and 7, and check it.
Hint: Compute the XOR of 12 and 10 first, then with 7.
Show the answer
12 ^ 10 = 6 and 6 ^ 7 = 1, so the XOR is 1. The highest set bit is bit 0. Piles with bit 0 set are 7 only, since 12 is 1100 and 10 is 1010. Its new size is 7 ^ 1 = 6, so take 1 stone from pile 3. The check is 12 ^ 10 ^ 6 = 0, since 12 ^ 10 = 6.
Practice 4: why no move from XOR 0 reaches XOR 0
Explain in a few sentences why a position with XOR 0 cannot have a move to another position with XOR 0.
Hint: A move changes one pile from a to b, where b is smaller than a.
Show the answer
Suppose the XOR of all piles is 0. A move changes one pile from a to b, with b not equal to a. The XOR of the other piles is a, because the total XOR is 0. So the new total is a ^ b. Since a is not equal to b, their XOR is not 0. So the new position has XOR not 0 and is not a P-position.
Practice 5: find the bug in the first 1 -1 output
The output first 1 -1 came from a version of the solver that picks the first pile larger than the XOR. Explain why -1 is impossible, and write the fixed condition.
Hint: The count of stones is a[i] - target. What must hold for target relative to a[i]?
Show the answer
The count of stones to take is a[i] - target, and it must be at least 1. Here target = a[i] ^ x. For the first pile, which has size 2, with XOR 1, the target is 3, which is larger than 2, so the count is -1. The fix is to pick a pile that has the highest set bit of the XOR, not a pile that is larger than the XOR. The condition is if ((a[i] >> h) & 1), where h is the highest set bit of x.
Summary
A Nim position is losing exactly when the XOR of its pile sizes is 0. The proof has two short claims: no move keeps the XOR at 0, and from any nonzero XOR there is a move to 0 using the highest set bit. The winning move reduces one pile with that bit to pile ^ XOR. Test the rule against a brute force on all small positions, and test answers against a checker that verifies each move.
Sources and scope
Charles L. Bouton, "Nim, a game with a complete mathematical theory," Annals of Mathematics, 1901-1902, is the original source of the theorem. The proof here is my own, and I checked it by the exhaustive test on 1 to 4 piles of size up to 8 and random tests with up to 5 piles of size up to 15. The solver and the checker were tested on 20,000 random positions with up to 6 piles of size up to 40. The output lines come from g++ 15.2.0 and Python 3.14.4 on Linux. The bugs shown in the mistakes section were run and their output is real.