Chomp

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.

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">{{hint}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{status_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; }

// Code not found

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 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.

"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.

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.