Skip to content
Embercode
✕
Game theoryLesson 1 of 9

40 min read

Winning and losing positions

Why this matters when you build with AI

Ask an AI tool for the winner of a small take-away game and it can give a short rule that sounds right: "the first player wins unless the count is a multiple of 3." That rule is true for some move sets and false for others. The tool does not check it, and the answer comes out with full confidence.

The way to catch this is to compute the answer for every small input with a brute force program. A brute force program tries every possibility with no clever shortcut, so it is slow but easy to trust. This lesson builds that tool. Every later lesson in this module uses the same idea: label positions, build a table, and compare the table with a plain search.

Some terms first. A position is the state of the game when one player is to move. A move takes the game from one position to a new one. The players alternate. A player who has no legal move loses. A game is finite when every play ends after a limited number of moves. The examples here are all of that kind.

The idea: winning and losing positions

Each position gets one of two labels.

  • A P-position is a losing position for the player to move. The letter P stands for "previous player wins", because the player who just moved is the one who wins.
  • An N-position is a winning position for the player to move. The letter N stands for "next player wins".

The labels follow from three rules.

  1. A position with no legal move is P. The player to move cannot move, so they lose.
  2. A position is N when some legal move reaches a P-position. The player to move makes that move and the opponent is stuck in a losing position.
  3. Otherwise the position is P. Every legal move reaches an N-position, so whatever the player does, the opponent can win from there.

Rule 2 is the important one. The phrase to remember is: a position is winning if some move reaches a losing one. You do not need to know who will play well. You only need the labels of the positions that the moves reach.

This works because the game is finite and has no cycles. A cycle would mean that a position can lead back to itself. If every move lowers a number, such as the stone count, then the label of a position depends only on smaller positions. You can compute the labels in order, from the smallest position upward. This is called backward induction: start at the end of the game and work back to the start.

A small example by hand

Take a heap of stones. A move removes 1 or 2 stones. The player who takes the last stone wins, so a heap of 0 is P, since the player to move cannot move. Here is the table for heaps up to 6.

  • Heap 0: no move, so P.
  • Heap 1: remove 1, leaving heap 0, which is P. So N.
  • Heap 2: remove 2, leaving heap 0, which is P. So N.
  • Heap 3: remove 1 leaves heap 2 (N), remove 2 leaves heap 1 (N). No move reaches a P-position, so P.
  • Heap 4: remove 1 leaves heap 3, which is P. So N.
  • Heap 5: remove 2 leaves heap 3, which is P. So N.
  • Heap 6: remove 1 leaves heap 5 (N), remove 2 leaves heap 4 (N). So P.

The P-positions are 0, 3 and 6, which are the multiples of 3. The reason is simple to check. From a multiple of 3, a move of 1 or 2 always leaves a number that is not a multiple of 3, and from any other number you can move to the nearest multiple of 3 below it. The hand table gives the same answer as this reason, and that is the kind of check you want.

A bigger example and a machine table

The next game uses a move set of {1, 3, 4}. That means a move removes 1, 3 or 4 stones. Doing this by hand up to 30 is slow and easy to get wrong, so a short program fills in the table. This Python program is self-contained and needs no input, so the site can run it.

Python · editable

Real output of that program, run with Python 3.14.4:

P-positions up to 40 : [0, 2, 7, 9, 14, 16, 21, 23, 28, 30, 35, 37]
outcomes 0..20: PNPNNNNPNPNNNNPNPNNNN
period 7 starts at 0

Read the output carefully. The P-positions are the numbers whose remainder mod 7 is 0 or 2. The table repeats every 7 positions, starting from 0. The program checks this only up to 40. The next section explains why the repeat continues forever.

The search for the period is a brute force. It tries every period p from 1 to 20 and keeps the first one where the labels match over a long enough tail. The check of 15 values is a safety margin, so a short accident cannot pass as a period.

Why the table must repeat

Let m be the largest move. Look at the label of a position n that is at least m. It depends only on the labels of the m positions just before it, from n - m up to n - 1. Every move from n lands in that range, and the label of n is decided by whether any of those landing positions is P.

So the label row is decided by a window of the last m labels. A window is a string of m letters, and there are only 2^m such strings. Among any 2^m + 1 consecutive windows, two must be equal. Suppose the window at position i equals the window at position j, with i < j. Then the label at i equals the label at j, and the window one step later is also equal, and so on forever. The table is periodic from i on, with period j - i.

For {1, 3, 4} the largest move is 4, so there are at most 16 windows. The table must repeat within about 16 steps, and the program above found the period 7. The bound is what matters for a program. It tells you how far to compute before you can stop and reuse what you have.

One consequence matters for the worked problem below. If the largest move is 10, the window has 10 letters, so there are at most 1024 windows, and the table must repeat within 1034 steps. A table of 4096 entries is enough.

Standard technique in C++17

This is the backward induction in C++. The function fills the table in increasing order of heap size. Each win[n] reads only smaller entries.

#include <bits/stdc++.h>
using namespace std;
 
// moves: the allowed amounts, all at least 1.
// Returns win[0..N], where win[n] is true when the player to move with n stones wins.
vector<char> outcome_table(const vector<int> &moves, int N) {
    vector<char> win(N + 1, 0);
    for (int n = 0; n <= N; ++n) {
        for (int k : moves) {
            if (k <= n && !win[n - k]) {
                win[n] = 1;  // a move reaches a P-position
                break;
            }
        }
    }
    return win;
}

Real output of a call with moves {1, 3, 4} and N = 10, printing N for each winning heap and P for each losing heap, compiled with g++ -std=c++17 -O2 -Wall -Wextra:

PNPNNNNPNPN

Time is O(N * m) for m moves. Memory is O(N).

Two details are easy to get wrong. The first is that every move must be at least 1. A move of 0 leaves the heap unchanged. Then win[n - 0] is win[n], which has not been set yet, so the loop sets win[n] to true for every n. A move of 0 also means the game can go on forever, so backward induction does not apply.

The second is the break. It is not needed for the answer, but without it the loop still gives the right label while doing more work.

Worked original problem: Ladder of stones

Two players share one heap of stones. On a turn, the player to move removes k stones, where k is one of m allowed amounts. The player who cannot move loses. You get q heap sizes. For each heap, print First if the first player to move wins with perfect play, and Second if the first player loses.

Input:

  • Line 1: m, the number of allowed amounts, with 1 at most m at most 10.
  • Line 2: m distinct integers, each from 1 to 10.
  • Line 3: q, the number of heap sizes, with 1 at most q at most 100000.
  • The next q lines: one heap size n, with 0 at most n at most 10^18.

Output: q lines, each First or Second.

Example input:

3
1 3 4
7
0
1
2
7
1000000000000000000
5
99

Expected output, from the table above: heap 0 is P, heap 1 is N, heap 2 is P, heap 7 is P, and the rest are N.

The solution

The solution builds the table up to 4096 entries. It then finds the first repeated window, using an array indexed by the window value, since the window has at most 10 bits. A query with a large n maps to a position inside the first period, so 10^18 costs the same as 0.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int m;
    cin >> m;
    vector<int> moves(m);
    for (int &x : moves) cin >> x;
    int q;
    cin >> q;
 
    // Table up to L. The window below has maxk bits, so it repeats within 2^maxk + maxk steps,
    // which is at most 1034 when every move is at most 10. L = 4096 is far more than enough.
    const int L = 4096;
    int maxk = *max_element(moves.begin(), moves.end());
    vector<char> win(L, 0);
    for (int n = 0; n < L; ++n) {
        for (int k : moves) {
            if (k <= n && !win[n - k]) {
                win[n] = 1;
                break;
            }
        }
    }
 
    // For n >= maxk, win[n] depends only on the previous maxk values (the window).
    // The first repeated window at positions i < n gives: win is periodic from i with period n - i.
    vector<int> first_seen(1 << maxk, -1);
    int start = -1, period = -1;
    for (int n = maxk; n < L; ++n) {
        int key = 0;
        for (int j = n - maxk; j < n; ++j) key = key * 2 + win[j];
        if (first_seen[key] != -1) {
            start = first_seen[key];
            period = n - start;
            break;
        }
        first_seen[key] = n;
    }
    // Move the start back while the periodic pattern still holds.
    while (start > 0 && win[start - 1] == win[start - 1 + period]) --start;
 
    for (int i = 0; i < q; ++i) {
        long long n;
        cin >> n;
        long long idx = n;
        if (n >= start) idx = start + (n - start) % period;
        cout << (win[idx] ? "First" : "Second") << "\n";
    }
    return 0;
}

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

Second
First
Second
Second
First
First
First

Each line matches the table. Heap 7 is Second because 7 is a P-position: its remainder mod 7 is 0.

How it was tested

The brute force is a different program. It walks down from n by recursion with a memo, and it never builds a table. So it does not share the table logic, and a bug in one is unlikely to hide the same bug in the other.

The solution was compared with that brute force on 600 random cases, each with 1 to 6 moves chosen from 1 to 10 and queries from 0 to 3000. It was also compared on 200 cases with 7 to 10 moves and queries every 7th value up to 2499. There were 0 mismatches.

The brute force cannot be run with n near 10^18. Its recursion goes n levels deep, and the program crashed with a segmentation fault (exit code 139 on this Linux machine). So the brute force was used only up to 3000, and the large queries were checked by the period rule.

Complexity

Building the table costs O(L * m), which is about 40,000 steps for L = 4096. The window search costs O(L * maxk). Each query costs O(1). Memory is O(L + 2^maxk), a few kilobytes.

Common mistakes

Setting the window to the number of moves instead of the largest move. A window of length |S| looks natural, since there are |S| moves. It is wrong. For the move set {2, 5}, a window of length 2 says the table repeats with period 3 from position 3 on. The check against the table fails. The comparison printed [2, 5] max window: (5, 7) True | |S| window: (3, 3) False, so the claimed pattern did not hold. The window must cover the largest move, which is 5 here.

Using a move of 0. As explained above, win[n] gets set to true at once, so every heap looks winning. Check that every move is at least 1 before you trust the table.

Reading the heap size into an int. The heap can be 10^18, which does not fit in a 32-bit int. The value wraps around and the query gives the answer for some other heap. Read n as long long.

Using brute force for large heaps. A recursive search of depth n crashes near n = 10^18. Use the table for small values and the period for large ones.

Trusting a period from a short table. A period found from 20 values can be a coincidence. The window argument is what makes the period certain, so compute the window repeat, not only the pattern.

Checklist to keep

  • A position with no legal move is P.
  • A position is N when some move reaches a P-position, and P otherwise.
  • Every move must remove at least one stone, or the labels are meaningless.
  • The window that decides a label has the length of the largest move.
  • Read big sizes as long long.
  • Compare any formula or table with a brute force on small inputs before you trust it.

Hands-on exercise

Write two programs in your own scratch folder. The first is the table builder from the standard technique. The second is a brute force that walks down from n with a memo, with no table at all.

Run both on the move set {1, 2, 5} for heap sizes 0 to 200. Print the heap sizes where they differ. There should be none. Then change one line in the table builder so that the loop tries k only when k is less than n, not when k is at most n. Run the comparison again and read the first heap size where the two programs disagree.

Finally, use the window idea to write down the period of the table for {1, 2, 5} by hand, then check it with the program. A good answer lists the first repeated window and its period. A weak answer only says the period looks like some number.

Prompt to try with an AI tool

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

Write a C++17 program. The first line has m, the number of allowed amounts (1 to 10). The second
line has m distinct amounts, each from 1 to 10. Then q (up to 100000) heap sizes follow, each up
to 10^18. A move removes one allowed amount from a heap. The player who cannot move loses.
For each heap, print First if the first player to move wins, else Second. Use backward
induction with a table, and explain in two sentences why the table repeats. Then show the
output for moves 1 3 4 and heaps 0 1 2 7.

A good answer uses the largest move to size the window, reads the heap sizes as long long, and prints Second First Second Second for the last check. Check the window line first. A common wrong answer uses the number of moves for the window length, and the test in the common mistakes section catches it.

Practice

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

Practice 1: the table for moves 1 and 2

Build the table for heap sizes 0 to 6 when a move removes 1 or 2 stones. List the P-positions.

Hint: Start with heap 0 and label each heap from the smallest up.

Show the answer

The P-positions are 0, 3 and 6. Heaps 1, 2, 4 and 5 are N, because each can move to a P-position: 1 and 2 reach 0, and 4 and 5 reach 3. This is the multiple-of-3 pattern from the hand example.

Practice 2: the table for moves 2 and 5

Find the P-positions up to heap size 12 when the moves remove 2 or 5 stones.

Hint: A P-position has no move to another P-position. Check each heap against heaps that are 2 or 5 smaller.

Show the answer

The P-positions are 0, 1, 4, 7, 8 and 11. Check heap 4: its moves reach heap 2, which is N, so 4 is P. Heap 7 moves to heap 5 (N) and heap 2 (N), so 7 is P. The labels repeat with period 7 from heap 5 on. For example, heap 12 is N like heap 5, and heap 11 is P like heap 4.

Practice 3: the period of moves 1, 4 and 6

The P-positions for moves 1, 4 and 6 up to heap size 30 are 0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 25, 27 and 30. Find the period, and say why the table must repeat.

Hint: Look at the gaps between consecutive P-positions. Then count the largest move to get the window size.

Show the answer

The gaps alternate 2 and 3, so the period is 5, and the P-positions are the numbers whose remainder mod 5 is 0 or 2. The largest move is 6, so the window has 6 letters, and there are at most 64 windows. The table must repeat within 70 steps. A program that checks win[n] == win[n + 5] for every n from 0 to 294 finds that it holds.

Practice 4: the window length mistake

For the move set {3, 5}, the table for heaps 0 to 12 is FFFTTTTTFFFTT (F for P, T for N in this line). Show that a window of length 2, which is the number of moves, claims the table is constant from heap 2 on, and find the first heap where that claim is wrong.

Hint: A window of length 2 at position 2 is the labels of heaps 0 and 1. Compare it with the window at position 3.

Show the answer

The labels of heaps 0 and 1 are both F. The window at position 3 is the labels of heaps 1 and 2, which are also both F. So the claim is that heap 3 has the same label as heap 2, which is F. But heap 3 is T, because it can remove 3 stones and reach heap 0, which is P. The first wrong heap is 3. The window must have length 5, the largest move.

Practice 5: the size of the table

Explain why a table of 4096 entries is enough for every move set with moves at most 10, without running any program.

Hint: Count the windows of length 10 and multiply by the number of steps it takes to repeat one.

Show the answer

A window of 10 labels has at most 2^10 = 1024 values. Among the windows starting at positions 10, 11, and so on, the first repeat must happen by position 10 + 1024 = 1034, since there are only 1024 different windows. So the table is periodic from some point before 1034 on, and a table of 4096 entries holds the whole cycle plus the start.

Summary

A position is P when the player to move loses, and N when they win. A position is N exactly when some move reaches a P-position. Backward induction fills these labels from small heaps upward. The label of a heap depends only on the labels of the last few heaps, as many as the largest move, so the table must repeat, and the period is found by checking for a repeated window. Use a brute force to check every formula, and never trust a rule that was only tested on a few values.

Sources and scope

Backward induction on finite games with no cycles is standard material in combinatorial game theory. The window argument and the period bound were derived here and checked on the move sets shown above. The table and period results come from Python 3.14.4 and g++ 15.2.0 on Linux. The random comparison (600 plus 200 cases) and the window-length check were run by scripts on the same machine. Other move sets give other numbers, and the learner should rerun the programs to see them.

Practice this topic: coding problems for Game theory →