Symmetry and strategy-stealing

Why this matters when you build with AI

Ask an AI tool who wins a symmetric board game and it often answers "the second player, by mirroring." Sometimes that is right. Sometimes the board has a center cell, and the mirror has no answer to a move in the center. The tool does not notice, and the answer reads as certain.

The check is the same as in the other lessons of this module. Write a search that tries every position on a small board, record the outcome, and compare it with the claim. A mirror claim is a claim about every position the mirror covers, so the search must check the reply to every move, not only the first one. Small boards are the best test, because a fault in the claim shows up at once there.

Some terms first. A board game here means two players alternately place a stone on an empty cell, under a fixed rule. A pairing strategy is a plan in which the second player answers each move with one partner move, so that the board is always split into pairs. A mirror is a map from cells to cells that the pairing uses. A position is symmetric when the set of stones is unchanged by the mirror. A strategy-stealing argument is a proof that does not name a winning move. It shows that one player cannot lose by assuming the other player has a winning plan and using that plan against it.

Two kinds of symmetry argument

A pairing strategy is constructive. It gives a move for every position, so you can play it. The second player is the one who uses it here: after every first-player move, the second player places a stone at the mirror cell of the move. If the stones form a symmetric set before the first move, they form a symmetric set again after the reply. The second player then always has a reply, and the game ends, so the first player is the one who runs out of moves.

A strategy-stealing argument is not constructive. It proves that some player cannot lose, using a contradiction. It does not tell you the move. You need a second kind of check for it: a search that confirms the claim on small boards.

For a board with R rows and C columns, the central mirror of cell (r, c) is (R - 1 - r, C - 1 - c). It is the reflection through the center of the board. Use zero-based coordinates, so the top left cell is (0, 0). Two cells touch when they share an edge, which means they are orthogonal neighbours.

The idea: a pairing strategy on a 4 by 4 board

Here is a game to analyse. The board is 4 by 4. Players alternately place a stone on an empty cell. A stone may not touch another stone along an edge. The player who cannot place a stone loses. Call it the lonely stones game.

The second player wins this game with the central mirror. Here is one play. The first player places at (0, 0), and the second player answers at its mirror (3, 3). The board is:

X . . .
. . . .
. . . .
. . . O

The first player then places at (1, 2), which touches nothing, and the second player answers at the mirror (2, 1):

X . . .
. . X .
. O . .
. . . O

Every position after a reply is symmetric, which means every stone has its mirror stone.

The proof

Here are three facts about the central mirror on a board where R and C are both even.

Fact 1: no cell is its own mirror. For a cell to be its own mirror, r must equal R - 1 - r, which means 2r = R - 1. That has no whole-number solution when R is even. The same holds for columns. So the first player's move always has a different mirror cell.

Fact 2: a cell and its mirror never touch. Two cells touch only if they share a row or a column, and differ by 1 in the other. The mirror changes the row to R - 1 - r, which differs from r, and it changes the column to C - 1 - c, which differs from c. So the cell and its mirror share neither a row nor a column, and they do not touch.

Fact 3: if the first player's move p is legal, then its mirror q is legal after p is placed. Here is why. First, q is empty. If q held a stone, then by symmetry p would hold a stone too, but p is empty. Second, q does not touch a stone. Suppose q touched a stone s. Touching is preserved by the mirror, so p would touch the mirror of s. The mirror of s is a stone, because the stone set is symmetric. Then p would touch a stone, which the rule forbids. So q is legal.

The invariant is: after each reply by the second player, the stone set is symmetric and no two stones touch. It holds for the empty board. Each round adds one legal pair of cells, so it holds after every round by Fact 3. The second player always has a reply. The game is finite, because every move adds one stone to a board of 16 cells. So the first player is the one who cannot move, and the second player wins from the empty board.

The proof needs both R and C to be even. With an odd dimension, a cell can share a row or a column with its mirror, and Fact 2 fails, as the 2 by 3 example in Practice 2 shows. On a board where both dimensions are odd, the center cell is its own mirror, which breaks Fact 1. The odd-board check below returns to this.

A check by exhaustive search

Here is a Python program that does the check for the 4 by 4 board and the 3 by 3 board. It tries every set of stones, which is 2 to the power 16 sets for the 4 by 4 board, and counts how many symmetric legal positions the claim covers. It also checks the reply to every legal first move. It needs no input.

Python · editable

from functools import lru_cache

def analyse(R, C):
    N = R * C
    nbr = []
    for p in range(N):
        r, c = divmod(p, C)
        m = 0
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            rr, cc = r + dr, c + dc
            if 0 <= rr < R and 0 <= cc < C:
                m |= 1 << (rr * C + cc)
        nbr.append(m)

def mirror(p):
        r, c = divmod(p, C)
        return (R - 1 - r) * C + (C - 1 - c)

def legal(mask, p):
        return ((mask >> p) & 1) == 0 and (nbr[p] & mask) == 0

@lru_cache(maxsize=None)
    def win(mask):
        # True when the player to move wins from this set of stones.
        return any(not win(mask | (1 << p)) for p in range(N) if legal(mask, p))

sym_legal = 0
    sym_losing = 0
    moves = 0
    replies_ok = 0
    for mask in range(1 << N):
        cells = [p for p in range(N) if (mask >> p) & 1]
        if any(((mask >> mirror(p)) & 1) == 0 for p in cells):
            continue
        if any(nbr[p] & mask for p in cells):
            continue
        sym_legal += 1
        if not win(mask):
            sym_losing += 1
        for p in range(N):
            if legal(mask, p):
                moves += 1
                q = mirror(p)
                if q != p and legal(mask | (1 << p), q):
                    replies_ok += 1
    print(f"{R}x{C} symmetric legal positions: {sym_legal}, first player loses in {sym_losing} of them")
    print(f"{R}x{C} first moves: {moves}, mirror replies legal: {replies_ok}")
    print(f"{R}x{C} empty board: first player", "wins" if win(0) else "loses")

analyse(4, 4)
analyse(3, 3)

Real output, run with Python 3.14.4 on Linux:

4x4 symmetric legal positions: 38, first player loses in 38 of them
4x4 first moves: 160, mirror replies legal: 160
4x4 empty board: first player loses
3x3 symmetric legal positions: 11, first player loses in 7 of them
3x3 first moves: 28, mirror replies legal: 24
3x3 empty board: first player wins

On the 4 by 4 board, every one of the 160 first moves across the 38 symmetric positions has a legal mirror reply. The first player loses in every symmetric position, which is what the pairing claims. On the 3 by 3 board the mirror covers only 24 of the 28 first moves. The 4 missing replies are the moves into the center, whose mirror is the cell itself, and the first player wins from the empty board by taking the center.

Standard technique in C++17

The same check in C++17 uses a bitmask for the stones. Bit p is set when cell p holds a stone. The program fills a table of outcomes for every mask, from the largest mask down, because a move only adds a stone. Then it checks the mirror for every symmetric legal position.

#include <bits/stdc++.h>
using namespace std;
 
// Board R x C with R * C <= 20. A stone may go on an empty cell with no orthogonal
// neighbour holding a stone. The player who cannot move loses.
// Bitmask DP over all 2^n sets of stones, then a check of the mirror pairing.
 
int R, C, n;
vector<unsigned> nbr;
 
bool legal(unsigned mask, int p) {
    return !((mask >> p) & 1u) && !(nbr[p] & mask);
}
 
int mirror(int p) {
    int r = p / C, c = p % C;
    return (R - 1 - r) * C + (C - 1 - c);
}
 
int main(int argc, char **argv) {
    R = argc > 1 ? atoi(argv[1]) : 4;
    C = argc > 2 ? atoi(argv[2]) : 4;
    n = R * C;
    nbr.assign(n, 0);
    for (int p = 0; p < n; ++p) {
        int r = p / C, c = p % C;
        int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
        for (int k = 0; k < 4; ++k) {
            int rr = r + dr[k], cc = c + dc[k];
            if (rr >= 0 && rr < R && cc >= 0 && cc < C) nbr[p] |= 1u << (rr * C + cc);
        }
    }
 
    const unsigned full = (n == 32) ? ~0u : ((1u << n) - 1);
    // win[mask] depends on masks with more stones, so fill from the largest mask down.
    vector<char> win(size_t(full) + 1, 0);
    for (long long m = full; m >= 0; --m) {
        unsigned mask = unsigned(m);
        bool w = false;
        for (int p = 0; p < n && !w; ++p)
            if (legal(mask, p) && !win[mask | (1u << p)]) w = true;
        win[mask] = w;
        if (m == 0) break;
    }
 
    long long sym_positions = 0, sym_losing = 0, replies_total = 0, replies_ok = 0;
    for (unsigned mask = 0; mask <= full; ++mask) {
        bool sym = true, independent = true;
        for (int p = 0; p < n; ++p) {
            if ((mask >> p) & 1u) {
                if (!((mask >> mirror(p)) & 1u)) sym = false;
                if (nbr[p] & mask) independent = false;
            }
        }
        if (!sym || !independent) continue;
        ++sym_positions;
        if (!win[mask]) ++sym_losing;
        for (int p = 0; p < n; ++p) {
            if (!legal(mask, p)) continue;
            ++replies_total;
            int q = mirror(p);
            unsigned after = mask | (1u << p);
            if (q != p && legal(after, q)) ++replies_ok;
        }
    }
 
    cout << R << "x" << C << " cells=" << n << "\n";
    cout << "symmetric legal positions: " << sym_positions << "\n";
    cout << "of which first player loses: " << sym_losing << "\n";
    cout << "first moves checked: " << replies_total << "\n";
    cout << "mirror replies legal: " << replies_ok << "\n";
    cout << "outcome from empty board: " << (win[0] ? "first player wins" : "first player loses") << "\n";
    return 0;
}

Real output of ./mirror_exhaustive 4 4, compiled with g++ -std=c++17 -O2 -Wall -Wextra on g++ 15.2.0 for Linux, with no warnings:

4x4 cells=16
symmetric legal positions: 38
of which first player loses: 38
first moves checked: 160
mirror replies legal: 160
outcome from empty board: first player loses

Real output of ./mirror_exhaustive 3 3 with the same build:

3x3 cells=9
symmetric legal positions: 11
of which first player loses: 7
first moves checked: 28
mirror replies legal: 24
outcome from empty board: first player wins

The C++ and Python programs agree on every number for the 4 by 4 and 3 by 3 boards. This is a cross-check of two separate implementations. In a separate run, both also agreed on the 2 by 2 and 2 by 4 boards, where the first player loses and the mirror covers every move.

Complexity: O(2^n * n) time and 2^n bytes of memory for n cells. For 4 by 4, that is 65536 masks. The table doubles with each cell, so the search is for small boards only, and the proof covers the general case.

Strategy stealing: the first player does not lose

Some games have no pairing. The strategy-stealing argument covers a family of games where extra stones never hurt. Here is the family in plain words. Each player places stones on an empty cell. A player wins by owning every cell of some winning set, such as a full row in tic-tac-toe. If there is no winner when the board is full, the game is a draw. The key property is that owning more stones never hurts: if a player owns a winning set, adding stones keeps that set.

Claim: in such a game the first player cannot lose. Here is the argument. Suppose the second player has a winning plan, called S. The first player makes any move x. Then the first player plays as if they were the second player in a second game, following S. In that second game, the stone x belongs to an imaginary first player, and the real second player plays the imaginary first player's moves. Whenever S says to place a stone on a cell that the real first player already owns, the real first player places a stone on any other empty cell instead. Those extra stones are harmless, because owning more stones never hurts.

Since S is a winning plan, the imaginary game ends with the imaginary second player, who is the real first player, owning a winning set. That set is also owned in the real game, since the real first player owns everything the imaginary one does, plus extra stones. So the real first player wins. That contradicts the assumption that the second player had a winning plan, because a game has only one winner. So the second player has no winning plan, and the first player does not lose.

Notice what the argument does not say. It does not say which first move wins, and it does not say that the first player wins. It says only that the first player cannot lose. Here is a check. Tic-tac-toe is in this family, since owning a full line is the win and extra marks never hurt. The exhaustive search below gives the value 0, which is a draw. That agrees with the claim that the first player does not lose, and it shows no first move wins.

Python · editable

from functools import lru_cache

LINES = [
    (0, 1, 2), (3, 4, 5), (6, 7, 8),
    (0, 3, 6), (1, 4, 7), (2, 5, 8),
    (0, 4, 8), (2, 4, 6),
]

def winner(board):
    for a, b, c in LINES:
        if board[a] != "." and board[a] == board[b] == board[c]:
            return board[a]
    return None

@lru_cache(maxsize=None)
def value(board, turn):
    # Game value for X: +1 X wins, 0 draw, -1 O wins, with perfect play.
    w = winner(board)
    if w == "X":
        return 1
    if w == "O":
        return -1
    if "." not in board:
        return 0
    results = []
    for i, ch in enumerate(board):
        if ch == ".":
            nxt = board[:i] + turn + board[i + 1:]
            results.append(value(nxt, "O" if turn == "X" else "X"))
    return max(results) if turn == "X" else min(results)

print("value from the empty board for X (1 win, 0 draw, -1 loss):", value("." * 9, "X"))
print("cells that are a winning first move for X:", [
    i for i in range(9)
    if value("." * i + "X" + "." * (8 - i), "O") == 1
])

Real output, run with Python 3.14.4 on Linux:

value from the empty board for X (1 win, 0 draw, -1 loss): 0
cells that are a winning first move for X: []

The strategy-stealing argument does not apply to the lonely stones game. In that game an extra stone can block a cell, since a stone forbids its neighbours. So owning more stones can hurt, and the argument breaks. The search above shows that the first player loses there, so the conclusion "the first player does not lose" would be false for that game. The lesson is that every strategy-stealing claim needs its own check of the property that extra stones never hurt.

Worked original problem: Mirror referee

A judge plays the first player on an even board. The board has R rows and C columns, with R and C both even, and the judge sends the first player's moves one at a time. Your program is the second player. For each move it must check that the first player's move is legal, then print the reply by the central mirror. If a move is illegal, print Illegal once and stop.

Input:

Line 1: R, C and m, with 2 at most R and C at most 8, both even, and 1 at most m at most R * C.
The next m lines: the first player's move as r c, with zero-based row r and column c.

Output: one line per move. For a legal move, print the reply as r c. For an illegal move, print Illegal and stop. A move is illegal when its cell is outside the board, already holds a stone, or touches a stone along an edge.

Example input:

Expected output: 3 3, 2 1, then Illegal. The third move is illegal because (3, 3) already holds the reply to the first move.

The solution

The solution keeps a grid of stones. For each move it checks legality, places the stone, computes the mirror, checks that the mirror is legal too, and places it. The mirror check is a safety net, because the proof says it always passes. If it ever fails, the program prints Bug.

#include <bits/stdc++.h>
using namespace std;
 
// Input: R C m, then m lines "r c" (0-based) with the first player's moves in order.
// The board has R and C even, 2 <= R, C <= 8.
// Output: for each move, the second player's reply "r c", using central symmetry.
// If a first-player move breaks the rules, print "Illegal" and stop.
int main() {
    int R, C, m;
    cin >> R >> C >> m;
    vector<vector<char>> occ(R, vector<char>(C, 0));
 
    auto legal = [&](int r, int c) {
        if (r < 0 || r >= R || c < 0 || c >= C) return false;
        if (occ[r][c]) return false;
        if (r > 0 && occ[r - 1][c]) return false;
        if (r + 1 < R && occ[r + 1][c]) return false;
        if (c > 0 && occ[r][c - 1]) return false;
        if (c + 1 < C && occ[r][c + 1]) return false;
        return true;
    };
 
    for (int k = 0; k < m; ++k) {
        int r, c;
        cin >> r >> c;
        if (!legal(r, c)) {
            cout << "Illegal\n";
            return 0;
        }
        occ[r][c] = 1;
        int qr = R - 1 - r, qc = C - 1 - c;
        // Proof in the lesson: the mirror cell is always empty and legal here.
        if (!legal(qr, qc)) {
            cout << "Bug\n";
            return 1;
        }
        occ[qr][qc] = 1;
        cout << qr << " " << qc << "\n";
    }
    return 0;
}

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

3 3
2 1
Illegal

How it was tested

The tester is a separate Python program. It draws random boards with both sides even, from 2 by 2 up to 8 by 8. It plays random legal first moves, and with a small chance it sends an illegal move, either onto an occupied cell or onto a cell that touches a stone. Its expected output is the mirror of each legal move, and it stops at the first illegal move.

The generator also asserts that every mirror is legal after the first player's move, so the claim is checked on the generator side too.

Two runs were made, with seeds 5 and 11. Each had 400 cases. Seed 5 had 16 cases with an illegal move and 0 mismatches. Seed 11 had 27 cases with an illegal move and 0 mismatches. The Bug branch never printed.

Complexity

Each move costs O(1) for the check and the placement, so the whole input costs O(m). Memory is the board, at most 64 cells.

Common mistakes

Forgetting the center cell on an odd board. On a 3 by 3 board the center is its own mirror. The search shows the symptom directly: first moves: 28, mirror replies legal: 24. Four first moves have no mirror reply, and the first player wins from the empty board. Check the fixed-cell case before you claim a mirror works.

Checking only that the reply cell is empty. A mirror reply must also be legal, which means it must not touch a stone. On the even board this never fails, by Fact 3. On other boards or other rules it can fail, so test the full legality of the reply, as the referee does.

Assuming a symmetric board means a mirror wins. The mirror must also respect the rule. The 3 by 3 board is symmetric too, and the same rule there gives a first-player win, as the search shows.

Forgetting that the game must end. The pairing argument needs every game to finish. If a move can be undone, or the game can go on forever, the second player may never run out of moves to match, and the argument proves nothing.

Reading strategy stealing as a winning move. The argument proves that the first player does not lose. It does not give a move. The tic-tac-toe search shows a draw with no winning first move, which is the same statement from the other side.

Applying strategy stealing to a game without the monotone property. The argument needs extra stones to never hurt. In the lonely stones game they do, so the claim does not hold there. Check the property before you use the argument.

Checklist to keep

A pairing strategy needs a mirror that has no fixed cell, which means no cell is its own partner.
The mirror reply must be empty and legal, not only empty.
On an odd board, check the center cell by hand before you claim a mirror.
The game must end, so the first player runs out of moves first.
Strategy stealing proves only that one player does not lose, and it needs extra stones to never hurt.
Check a symmetry claim with exhaustive search on small boards, and check every reply, not only the first move.

Hands-on exercise

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

Step 1. Run the Python check above and confirm the six lines it prints.

Step 2. Change the Python check to run the 2 by 2, 2 by 4 and 4 by 2 boards. Predict each result before you run it. Each even board should show a mirror that covers every move.

Step 3. Write a search for the lonely stones game on a 3 by 4 board. Find whether the first player wins from the empty board. Then say which cell the central mirror would answer with, and whether that reply is always legal.

Step 4. Compile the referee and run it on the sample input. Then write one more input with a legal move sequence of length 5 on a 4 by 6 board, predict the output by hand, and compare it.

Prompt to try with an AI tool

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

A board has R rows and C columns, both even, with R and C at most 8. Two players alternately
place a stone on an empty cell. A stone may not touch another stone along an edge. The
player who cannot place a stone loses. Show that the second player wins with a central mirror
strategy, and prove that the mirror reply is always legal. Then write a C++17 program that
reads R, C and a list of first-player moves, and prints the second player's reply to each,
or Illegal for the first bad move. Check the program on the input 4 4 3 with moves 0 0,
1 2 and 3 3.

A good answer proves three facts: no cell is its own mirror, a cell and its mirror never share a row or column, and the mirror of a legal move is legal after it. It also prints 3 3, 2 1 and Illegal for the sample. A common wrong answer says the mirror works for any board, which fails for odd sizes, or checks only that the mirror cell is empty. Check the odd-board case and the sample first.

Practice

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

Practice 1: the mirror on a 6 by 4 board

On a board with 6 rows and 4 columns, find the central mirror of cell (1, 0).

Hint: Use (R - 1 - r, C - 1 - c) with R = 6 and C = 4.

Show the answer

The mirror is (4, 3). It is (6 - 1 - 1, 4 - 1 - 0).

Practice 2: a move the mirror cannot answer

On a board with 2 rows and 3 columns, find a first move that the central mirror cannot answer legally, and explain why.

Hint: Here R is even but C is odd. Check which cell is the mirror of (0, 1), and whether it touches (0, 1).

Show the answer

Take the first move at (0, 1). Its mirror is (1, 1), which is directly below it, so the two cells touch. The mirror reply is illegal, so the pairing fails. The odd column count is the reason: column 1 is the middle column, and the cell above and below it touch.

Practice 3: why an even board has no fixed cell

Prove that when R is even, no cell (r, c) equals its central mirror.

Hint: The mirror has row R - 1 - r. Set it equal to r and solve for r.

Show the answer

Setting R - 1 - r = r gives 2r = R - 1. The right side is odd when R is even, and the left side is even, so there is no whole-number solution. So the mirror of a cell always has a different row, and so always a different cell.

Practice 4: count the symmetric positions on a 2 by 2 board

On a 2 by 2 board, list every symmetric set of stones that obeys the no-touch rule. The search gives 3. Check the list by hand.

Hint: A symmetric set is empty, or it holds a pair of mirror cells. Check each pair for touching.

Show the answer

The three sets are the empty set, the pair (0, 0) and (1, 1), and the pair (0, 1) and (1, 0). The first pair does not touch, since the two cells are diagonal. The second pair does not touch either, for the same reason. Each set is symmetric and legal, so there are 3.

Practice 5: why strategy stealing says nothing about the lonely stones game

Explain why the strategy-stealing argument does not prove that the first player cannot lose in the lonely stones game, even though the argument works for tic-tac-toe.

Hint: The argument needs extra stones never to hurt. Look at what a stone does to its neighbours.

Show the answer

In the lonely stones game a stone forbids its four neighbours. So an extra stone placed by the first player can make a cell that the second player's plan needs illegal. The phantom stone then breaks the copy of the second player's plan, and the argument fails. The exhaustive search shows the first player loses on the 4 by 4 board, which is consistent with the argument failing.

Summary

A mirror strategy works when the board has no fixed cell, the mirror of a legal move is legal, and the game ends. The second player answers each move with its mirror, and the first player runs out of moves first. On a board with a center cell, the mirror fails for the center, and the first player may win. Strategy stealing proves only that the first player cannot lose, in games where extra stones never hurt, and it gives no move. Check every claim by exhaustive search on small boards.

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 4 by 4 and 3 by 3 results come from both the Python and the C++ search, run in Python 3.14.4 and g++ 15.2.0 on Linux, and they agree on every number. The 2 by 2 and 2 by 4 boards were checked by the same search. The referee was tested on 800 random games with seeds 5 and 11, with 0 mismatches. The general proof for even boards is a derivation in the text, and the search covers only the boards named above. Other board shapes and rules give other answers, so rerun the checks for your own inputs.