Introduction

Picture a rectangular tray of cookies. Two players take turns; on your turn you point at any remaining cookie and eat it together with every cookie above and to the right of it. There is one rule that makes the whole thing tense: the top-left cookie is poisoned. Whoever is forced to eat that cookie loses.

That is Chomp, invented by David Gale in 1974. The rules fit in a sentence, and the board can be as small as a 2x2 square. Yet it hides something genuinely strange.

There is a short, airtight proof that on any board bigger than 1x1 the first player can force a win. The catch: the proof never tells you a single move. It guarantees the victory exists while leaving you completely in the dark about how to claim it.

Play the Game

Here is a Chomp board. Click any cookie to eat it along with everything above and to its right. The poison cookie sits in the top-left corner — don't be the one who eats it.

<p class="hint">Click any cookie to eat it together with every cookie <b>above and to the right</b> of it. The <b>poison</b> cookie is the top-left one — whoever eats it loses. The computer moves first and plays <b>perfectly</b>, so the theorem says it always wins.</p>
<div id="board" class="board"></div>
<div class="status" id="status">The computer (player 1) is thinking…</div>
<div class="btns">
  <button id="reset" type="button">New game</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.board { display: grid; grid-template-columns: repeat(4, 52px); gap: 5px; margin: .4rem 0; }
.cell { width: 52px; height: 52px; display: flex; align-items: center; justify-content: center;
        font-size: 24px; border-radius: 50%; user-select: none; transition: all .12s; }
.cookie { background: #d8a45a; border: 2px solid #b9842f; cursor: pointer; }
.cookie:hover { background: #e6b873; transform: scale(1.06); }
.cookie.preview { background: #f0c89a; border-style: dashed; }
.poison { background: #2b2b2b; border: 2px solid #000; color: #e63946; cursor: pointer; }
.poison::after { content: "☠"; }
.gone { background: transparent; border: 2px dashed #e2e2e2; cursor: default; }
.gone:hover { transform: none; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.win { color: #0a7d33; }
.status.lose { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }

// Chomp on a 4x4 grid. Cell (r,c): r = row (0 = top), c = column (0 = left).
// (0,0) is POISON. A move at (r,c) eats every cell (i,j) with i>=r AND j>=c.
// Whoever is forced to eat (0,0) loses. Gale (1974) proved the FIRST player wins on any rectangle bigger than 1x1 — by a nonconstructive strategy-stealing
// argument that never names a move. Here we just brute-force the small game tree, so the computer (player 1) provably never loses.
const M = 4, N = 4;
// Position = boolean grid of which cells remain (true = present).
function fullBoard() { return Array.from({length:M}, () => Array(N).fill(true)); }
function clone(b) { return b.map(row => row.slice()); }
function eat(b, r, c) { const nb = clone(b);
  for (let i=r;i<M;i++) for (let j=c;j<N;j++) nb[i][j]=false; return nb; }
function cells(b) { const out=[]; for (let i=0;i<M;i++) for (let j=0;j<N;j++) if (b[i][j]) out.push([i,j]); return out; }
function key(b) { return b.map(row => row.map(x=>x?1:0).join('')).join(''); }

// win(b) = true if the player TO MOVE on b can force a win.
// Terminal: only the poison cell (0,0) remains -> player to move must eat it -> loses.
const memo = new Map();
function win(b) {
  const cs = cells(b);
  if (cs.length === 1 && b[0][0]) return false; // only poison left -> to-move loses
  const k = key(b); if (memo.has(k)) return memo.get(k);
  let res = false;
  for (const [r,c] of cs) {
    const nb = eat(b, r, c);
    if (cells(nb).length === 0) continue; // ate the poison too -> this move loses
    if (!win(nb)) { res = true; break; }   // opponent loses -> winning move
  }
  memo.set(k, res); return res;
}
// The computer's perfect move: pick any move leaving the opponent in a losing spot.
function bestMove(b) {
  for (const [r,c] of cells(b)) {
    const nb = eat(b, r, c);
    if (cells(nb).length === 0) continue;
    if (!win(nb)) return [r,c];
  }
  return cells(b)[0]; // unreachable when computer is in a winning position
}

let board, over;
const boardEl = document.getElementById('board');
const statusEl = document.getElementById('status');
function setStatus(t, cls) { statusEl.textContent = t; statusEl.className = 'status ' + (cls||''); }

function render() {
  boardEl.innerHTML = '';
  for (let i=0;i<M;i++) for (let j=0;j<N;j++) {
    const d = document.createElement('div');
    if (!board[i][j]) { d.className = 'cell gone'; }
    else if (i===0 && j===0) {
      d.className = 'cell poison';
      if (!over) d.addEventListener('click', () => humanMove(0,0));
    } else {
      d.className = 'cell cookie';
      if (!over) {
        d.addEventListener('mouseenter', () => preview(i,j,true));
        d.addEventListener('mouseleave', () => preview(i,j,false));
        d.addEventListener('click', () => humanMove(i,j));
      }
    }
    boardEl.appendChild(d);
  }
}
function preview(r,c,on) {
  const idx = (i,j) => i*N + j;
  for (let i=r;i<M;i++) for (let j=c;j<N;j++) if (board[i][j]) {
    const el = boardEl.children[idx(i,j)];
    if (!el.classList.contains('poison')) el.classList.toggle('preview', on);
  }
}
function humanMove(r,c) {
  if (over) return;
  if (r===0 && c===0) { board = eat(board,0,0); over=true; render(); setStatus('You ate the poison — you lose. The theorem held.', 'lose'); return; }
  board = eat(board, r, c);
  render();
  // did the human's move leave only poison for the computer? then computer is forced to eat it.
  if (cells(board).length === 1) { over=true; setStatus('Only poison remains for the computer — you win! (It misplayed, or you found a flaw.)', 'win'); return; }
  setTimeout(computerMove, 350);
}
function computerMove() {
  const [r,c] = bestMove(board);
  board = eat(board, r, c);
  render();
  if (cells(board).length === 1) { over=true; setStatus('Only the poison is left for you. The computer wins — exactly as proven.', 'lose'); return; }
  setStatus('Your turn. Eat a cookie (not the poison!).', '');
}
function reset() {
  board = fullBoard(); over=false;
  render();
  setStatus('The computer (player 1) opens…', '');
  setTimeout(computerMove, 400);
}
document.getElementById('reset').addEventListener('click', reset);
reset();
Result
Console

The computer always moves first and plays perfectly, so it should win every game. On this small board it finds its moves by searching the full game tree. Now the unsettling part: the strategy-stealing proof guarantees the first player wins on every rectangle, but it does so without computing anything — it never hands you the winning move. For boards just slightly larger, no one has ever written that strategy down.

The Real Complexity

The proof is a gem. Suppose, for contradiction, that the second player had a winning strategy. The first player could then make a tiny "throwaway" move — eat just the single bottom-right cookie. Now the board is in some position P. By assumption the second player has a winning reply to P. But here is the trick: that very reply was also a legal first move from the original full board. So the first player could have just played it on move one — stealing the second player's strategy. This means a second-player winning strategy can never exist, so the first player must have one.

Look closely and you'll see what the argument never does: it never says which first move wins. It only proves a winning move exists. This is a nonconstructive proof.

  • The status is settled and open at the same time. That the first player wins is proven (David Gale, 1974). The winning strategy itself is unknown for almost all boards — explicit strategies are known only for special cases like single rows, single columns, and square boards.
  • Verifying a full game is easy: just replay the moves and see who ate the poison.
  • Finding the winning move means searching a game tree that explodes with board size — and even general-grid Chomp's strategy has no known shortcut.

It is one of the cleanest real examples of the gap between knowing that and knowing how — closely related to the same hardness that makes problems like P vs NP so stubborn.

Where It Matters

"We can prove a solution exists without showing you one" is a recurring and powerful idea, and Chomp is its friendliest illustration:

  • Other games: the same strategy-stealing trick proves the first player can't lose at Hex and at tic-tac-toe — again without naming the moves.
  • Nonconstructive mathematics: huge swaths of math prove things exist (a number, a coloring, a path) without building them, which shapes what "a proof" is even allowed to be.
  • Algorithms vs. existence: knowing an answer exists is very different from being able to compute it efficiently — the heart of complexity theory.
  • Teaching: because Chomp is so simple to play, it is a perfect on-ramp to the difference between an existence proof and an algorithm.

Understand Chomp and you've met one of the deepest distinctions in mathematics: the chasm between proving and producing — the same chasm that runs under Nim and the whole study of computational hardness.

Conclusion

Chomp leaves us with a beautiful paradox. We can be completely certain the first player wins on any board bigger than 1x1 — the strategy-stealing proof is airtight. And yet, for almost every board, no one on Earth can tell you the winning move.

So the next time someone insists a proof must come with instructions, hand them a tray of cookies. Chomp is a guaranteed victory with the manual missing — a living reminder that in mathematics, knowing that and knowing how are two very different things, and the distance between them is exactly where problems like P vs NP live.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/chomp/Content licensed under CC BY-NC 4.0.