xxxv. Chomp and Hex

Two games where a short strategy-stealing argument proves that the first player wins, while no explicit winning strategy is known in general.

Game	Rules	Known
Chomp (Gale, 1974)	$n\times m$ chocolate bar, the bottom-left square is poisoned; a move picks a square and eats it with everything above and to the right; whoever eats the poison loses	first player wins every board except $1\times 1$; explicit strategy for squares, $2\times n$, L-shapes; general $n\times m$ open
Hex (Hein 1942, Nash 1948)	rhombic $n\times n$ board of hexagons; Red joins top and bottom, Blue joins left and right; players alternately colour a cell	no draws (Hex theorem); first player wins (strategy stealing); explicit winning strategies known only for small boards (computer searches have solved boards up to $9\times 9$); deciding the winner of Hex on general graphs is PSPACE-complete (Reisch, 1981)

Strategy stealing. In a finite game without draws one player has a winning strategy (Zermelo). If an extra move can never hurt you, the second player cannot be the one: the first player makes an arbitrary move and then pretends to be the second player, following their winning strategy.

Chomp

// Chomp position: rows[i] = number of squares left in row i (non-increasing; rows[0][0] is the poison).
// Returns true iff the player to move wins (eating the poison loses). Memoized over Young diagrams.
map<vector<int>, bool> memoChomp;
bool chompWins(const vector<int>& rows) {
    if (rows.size() == 1 && rows[0] == 1) return false;          // only the poison is left: you must eat it
    auto it = memoChomp.find(rows); if (it != memoChomp.end()) return it->second;
    bool win = false;
    for (int i = 0; i < sz(rows) && !win; i++) for (int j = 0; j < rows[i] && !win; j++) {
        if (i == 0 && j == 0) continue;
        vector<int> nxt(rows.begin(), rows.begin() + i);         // rows below i untouched
        for (int r = i; r < sz(rows); r++) if (min(rows[r], j) > 0) nxt.push_back(min(rows[r], j));
        if (!chompWins(nxt)) win = true;
    }
    return memoChomp[rows] = win;
}

Board	First player’s winning move
$n\times n$, $n\ge 2$	eat at $(1,1)$, leaving an L with equal arms; then mirror the opponent
$2\times n$	eat the top-right square; afterwards keep the shape “bottom row one longer than the top row”
L-shape with arms $a,b$ (poison at the corner)	losing for the player to move iff $a=b$
$n\times m$ general	exists (strategy stealing), not known explicitly

Proof: first player wins Chomp, and the explicit strategies

Stealing. Take an $n\times m$ board other than $1\times 1$. Suppose eating only the top-right square were a losing move. Then the opponent has a winning reply, eating some square $s$. But eating $s$ also removes the top-right square, so the position after the reply is reachable from the full board in one move: the first player can play $s$ immediately and win. Either way the first player has a winning move.

L-shapes. A position consisting of the poison, $a$ squares to its right and $b$ above it allows only moves that shorten one arm. If $a=b$, every move makes the arms unequal and the opponent restores equality; the player facing $a=b=0$ must eat the poison. If $a\ne b$, shorten the longer arm to equality. Squares: eating $(1,1)$ leaves the L with arms $n-1,n-1$, a losing position for the opponent.

$2\times n$. Call a position “good” if the bottom row has exactly one more square than the top row. After eating the top-right square of the $2\times n$ board it is good. From a good position with rows $(k+1,k)$, any move either shortens the top row to $j<k$ (answer: shorten the bottom to $j+1$), or cuts the bottom row at $j\le k$, which also cuts the top to $\min (k,j)$; if $j\le k$ the rows become $(j,j)$ and we answer by eating the top-right square, giving $(j,j-1)$. The poison-only position $(1,0)$ is good and the opponent faces it. All claims were checked with the memoized search for every board up to $7\times 7$.

Hex

// Full Hex board: 'R' or 'B' in every cell; cell (r, c) touches (r-1,c), (r-1,c+1), (r,c-1), (r,c+1), (r+1,c-1), (r+1,c).
// Returns true iff Red's cells connect the top row to the bottom row.
bool redConnects(const vector<string>& b) {
    int n = sz(b); vector<vector<char>> vis(n, vector<char>(n, 0)); vector<pair<int, int>> st;
    for (int c = 0; c < n; c++) if (b[0][c] == 'R') vis[0][c] = 1, st.push_back({0, c});
    int dr[] = {-1, -1, 0, 0, 1, 1}, dc[] = {0, 1, -1, 1, -1, 0};
    while (!st.empty()) {
        auto [r, c] = st.back(); st.pop_back();
        if (r == n - 1) return true;
        for (int k = 0; k < 6; k++) {
            int x = r + dr[k], y = c + dc[k];
            if (x >= 0 && x < n && y >= 0 && y < n && !vis[x][y] && b[x][y] == 'R') vis[x][y] = 1, st.push_back({x, y});
        }
    }
    return false;
}

Proof: Hex has no draws, and exactly one player connects

Not both. A red top-bottom chain and a blue left-right chain would be two curves inside the rhombus joining opposite sides; by the Jordan curve theorem they cross. But the red curve can be drawn inside red cells (centre to centre through edges shared by two red cells) and the blue one inside blue cells, so they are disjoint.

At least one (Gale’s walk). Surround the board with four boundary regions: red above and below, blue left and right. Consider the edges of the hexagonal tiling that separate a red region from a blue one. At an interior vertex of the tiling exactly three cells meet; if all three have the same colour no separating edge touches it, otherwise exactly two of its three edges are separating. So every interior vertex has degree $0$ or $2$ in the graph of separating edges, while each of the four corners where a red boundary region meets a blue one has degree $1$. The component containing the top-left corner is therefore a simple path ending at another corner, with red cells all along one side and blue cells along the other (the side never switches: at each vertex the path turns away from the cell of the odd colour). The red cells touching the path form a connected red chain and likewise for blue. At the start the red side is the top region and the blue side is the left region. The path splits the rhombus into two parts; the red side stays in one part throughout. If the path ended at the bottom-right corner, the top region (red side at the start) and the bottom region (red side at the end) would lie on the same side of the path, but the path separates the top-and-right boundary from the left-and-bottom boundary: contradiction. If it ends at the bottom-left corner, the red chain joins top to bottom; if at the top-right corner, the blue chain joins left to right.

First player wins. No draws, finite, so someone has a winning strategy; an extra stone never hurts in Hex, so by strategy stealing it is not the second player. The function was checked on all $2^9$ and $2^{16}$ colourings of the $3\times 3$ and $4\times 4$ boards and on random $8\times 8$ boards: exactly one of “red connects top-bottom” and “blue connects left-right” holds every time.

Related notes

• Combinatorial Games and Nim
• Proof Techniques (strategy stealing)
• Wythoff’s Game