writing a perfect-play chomp solver

the board on my research page plays chomp perfectly. it is a tiny sibling of the exhaustive c++ solver behind my paper on 4×n chomp; the web version just plays small boards in the browser. here is how it works.

the state

chomp is played on a grid. a move eats a cell and everything below and to the right of it, and whoever is forced to eat the poisoned corner loses. the key observation is that every reachable position is a staircase, so it can be stored as a list of row lengths that only ever decreases. that makes each position a short, hashable key.

the search

with a small state you can just recurse. a position is a win for the player to move if some move hands the opponent a losing position. memoize on the key and the whole game tree collapses to a handful of distinct states.

function winning(pos) {
  if (onlyPoison(pos)) return false;      // forced to take poison
  const k = key(pos);
  if (cache.has(k)) return cache.get(k);
  let win = false;
  for (const m of moves(pos))
    if (!winning(applyMove(pos, m))) { win = true; break; }
  cache.set(k, win);
  return win;
}

from a winning position the solver picks any move to a losing one. from a losing position it stalls, taking the single cell that removes the least, so a careless opponent still has room to slip up.

at scale

• ·the paper tabulates over 961 million losing positions for boards up to 4×3000.
• ·that search produced a new integer sequence, oeis a395126.
• ·full write-up: arxiv:2604.25952.