Chomp（チョンプ）をブラウザに実装した。チョコレートの板の左下 1 マスに毒が入っている。手番では好きなマスを 1 つ選び、そのマスとその右と上にあるマス全部を食べる。毒を食べさせられた方の負け。長方形の板なら先手必勝であることは「戦略泥棒」の論法ですぐ証明できるが、この証明はどこを食べれば勝てるかを教えてくれない。コンピュータは対局前に板の全局面を解いているので、それを知っている。ヒントを付けると勝てるマスが緑で囲まれる。裏側では Chomp について公表されている数字を一から計算し直した。Andries Brouwer の「The game of Chomp」のページにある 3 行 Chomp の表、Gabriel Nivasch による r ≤ 10,000 の周期行の一覧（周期 2 が 141 行、3 が 7 行、4 が 54 行、9 が 2 行）、パターン表 19 行、OEIS の Chomp 数列 8 本はすべて一致した。ただし 1 つだけ例外があり、Brouwer の「p − q が定数に落ち着く行」の一覧にある 95 は 94 の誤りだった（本人の別の一覧と、総当たりのソルバーの両方がそう言っている）。14 行までの長方形 823 個を全部解くと、勝ち手が 2 つある板は 7 個見つかった。有名な 8×10 は 10×10 に収まる中では最小だが、面積なら 6×13（78 マス）の方が小さい。テスト 12 件。ソルバー内蔵パズル第 86 弾。
デモ: https://sen.ltd/portfolio/chomp/
リポジトリ: https://github.com/sen-ltd/chomp
ルール
m 行 n 列のチョコレートの板。左下の 1 マスに毒が入っている。
- 2 人が交互に、残っているマスを 1 つ選ぶ。
- 選んだマスと、そのマスから見て右にも上にもあるマス（行も列も選んだマス以上のマス）をまとめて食べる。
- 毒のマスを食べた方の負け。毒だけが残った局面で手番が来たら、その人の負けが決まる。
ゲーム自体は Fred. Schuh が 1952 年に「約数のゲーム」として考え、David Gale が 1974 年にチョコレートの板の形で再発明し、Martin Gardner が 1973 年の Scientific American のコラムで "Chomp" と名付けて広めた。
先手必勝なのに、勝ち方が分からない
長方形の板では先手が必ず勝てる。証明は数行で済む。
先手がまず右上の角の 1 マスだけを食べたとする。これで先手が勝てるならそれでよい。勝てないなら、後手には勝てる返し手 a がある。ところが「右上の角を食べたあとに a を食べた局面」は「最初からいきなり a を食べた局面」と同じになる（a を食べれば右上の角も一緒に消えるので）。だから先手は最初から a を食べればよい。
これは「戦略泥棒（strategy stealing）」と呼ばれる論法で、勝ち手が存在することは言えるが、どれかは言っていない。一般の m×n で勝ち手を決める公式は今も見つかっていない。分かっているのは次のような特別な場合だけだ。
- n×n の正方形: 毒の斜め右上のマス (1, 1) を食べると、残りは同じ長さの腕 2 本の L 字になる。あとは相手の手を鏡映しに返せばよい。
- 2×n: 右上の角を 1 マス食べる。2 行の長さの差がちょうど 1 の局面が負け局面（P 局面）になる。
- 3×n: 公式はないが、Zeilberger（2001）以降、規則性がかなり調べられている（後述）。
そこでこのページでは、板の全局面をコンピュータに解かせる。
ソルバー: 階段を番号付けして 1 回なめる
局面は必ず階段の形になる。毒のある行を 0 行目として下から数え、k 行目に r_k マス残っているとすると、r_0 ≥ r_1 ≥ … ≥ r_{m−1} が成り立つ。m×n の板の中にある階段は全部で C(m+n, m) 個あり、8×10 なら 43,758 個、14×14 でも 40,116,600 個だ。
組合せ数系で隙間なく番号を振る
非増加列 r_0 ≥ … ≥ r_{m−1}（各値 0〜n）は、s = r_k + (m−1−k) と置くと {0, …, n+m−1} から m 個を選んだ集合に 1 対 1 で対応する。この集合に**組合せ数系（combinatorial number system）**で番号を付けると、0 から C(n+m, m) − 1 までが隙間なく埋まる。
// rank = Σ_k C(r_k + (m-1-k), m-k)
private term(k: number, r: number): number {
const a = r + this.m - 1 - k;
const b = this.m - k;
return a < b ? 0 : this.C[a][b];
}
ハッシュ表が要らないので、局面の勝ち負けは 1 局面 1 バイトの Uint8Array に入る。
辞書式順で前から 1 回なめれば済む
(i, j) を食べると、k ≥ i の行が min(r_k, j) になり、i より下の行は変わらない。つまり手を指した後の局面は、最初に変わる i 行目で必ず小さくなる。行の並びを辞書式に比べると、どの手の行き先も元の局面より前に来る。
だから辞書式の小さい順に局面を並べて、前から順に「行き先に負け局面（P）が 1 つでもあれば勝ち（N）、なければ負け（P）」と書いていけば、再帰もメモ化もなしに 1 回のスイープで全局面が決まる。
for (;;) {
// prefix[k] = 行 0..k-1 の番号の寄与
let win = false;
for (let i = 0; i < m && !win; i++)
for (let j = i === 0 ? 1 : 0; j < rows[i]; j++) {
let s = prefix[i];
for (let k = i; k < m; k++) s += this.term(k, rows[k] < j ? rows[k] : j);
if (this.value[s] === P) { win = true; break; }
}
this.value[prefix[m]] = win ? N : P;
// 次の局面（辞書式）へ
}
毒 (0, 0) を食べる手は最初から除いてある。毒だけの局面 [1, 0, …] は合法手がないので自動的に P になり、「毒しか残っていない局面で手番が来た人は負け」がそのまま表現される。
テストでは、4×5 と 3×7 の板の全局面を素朴なゲーム木探索と突き合わせている。
3 行 Chomp: Brouwer の漸化式
3 行に限ると、ずっと速い方法がある。局面を (p, q, r)（下の行から順に長さ、p ≥ q ≥ r）と書く。q と r を決めると、(p, q, r) が P 局面になる p はちょうど 1 つしかない（P 局面同士は 1 手で移り合えないので、同じ (q, r) に p が 2 つあると、長い方から短い方へ 1 手で行けてしまう）。この p を f(q, r) と書くと、Brouwer のページには次の漸化式が載っている。
- r > q なら f(q, r) = f(q, q)
- f(q−1, r) < q なら f(q, r) = f(q−1, r)（その行はそこから定数）
- それ以外は、f(a, r)（a < q）にも f(q, b)（b < r）にも現れない最小の正の整数
最後の「最小の除外値（mex）」を素直に 1 つずつ探すと、Q = 3,000 で 68 秒かかり、時間は Q³ に比例して増えた。f(q, r) − q は r の 0.6 倍くらいまで大きくなるので、行 r の空きを先頭から順に見ていくと、そこを列 q の値がびっしり塞いでいて、毎回 O(r) 回の空振りをする。
そこで「行 r で使った値」と「列 q で使った値」をどちらもビット集合で持ち、~(row | col) で 32 個ずつまとめて空きを探すようにした。
let w = rowMex[r] >>> 5;
let free = ~(used[base + w] | colBits[w]) & (~0 << (rowMex[r] & 31));
while (free === 0) { w++; free = ~(used[base + w] | colBits[w]); }
v = (w << 5) | (31 - Math.clz32(free & -free));
これで Q = 3,000 が 1.4 秒になり、q, r ≤ 16,000 の全部が 168 秒で計算できた。漸化式そのものが正しいかどうかは、テストで p ≤ 120 の 3 行の全局面を総当たりのソルバーと突き合わせて確かめている。
公表されている数字と突き合わせる
npm run literature で Brouwer のページと OEIS の b-file を取ってきて、比較に使う数字を src/literature.json に入れる。重い計算は 1 ジョブ 1 プロセスで 7 本並列に走らせた（12 コアの Mac mini、Node 26、全体で約 4 分）。
| 比べたもの | 結果 |
|---|---|
| Brouwer の f(q, r) の表（q, r ≤ 24）と、本文に載っている r = 120 の行 | 一致 |
| 3×p の板の勝ち手が 1 つだけか | p ≤ 16,000 の全部で 1 つ（Brouwer は p ≤ 130,000 まで確認済み） |
| Nivasch の「p − q が周期的になる行」の一覧（r ≤ 10,000） | 一致。周期 2 が 141 行、3 が 7 行、4 が 54 行、9 が 2 行で、ほかの周期は出てこない |
| Brouwer のパターン表 19 行（開始位置・周期・パターン） | 19 行とも、開始位置と位相まで一致 |
| Brouwer の「f(q, r) = q + c に落ち着く行」の一覧（r ≤ 130 の 54 行。r、c、q₀ の 3 列） | c と q₀ は 54 行全部一致、r は 53 行一致。95 が 94 になる |
| OEIS A029899（n ≤ 400）、A029900、A029901、A029902 | 一致 |
| OEIS A112470（n マスの局面のうち負け局面の数、n ≤ 60） | 一致 |
| OEIS A112471〜A112473（勝ち / 勝ち手 1 つ / 勝ち手 2 つ以上、n ≤ 40） | 一致 |
r ≤ 10,000 の 10,001 行の内訳は、どこかで f が定数になる行が 5,858、f = q + c に落ち着く行が 3,939、周期 2 / 3 / 4 / 9 が 141 / 7 / 54 / 2 だった。
周期行のパターン
r = 120 の行では、q が大きいところで p = q + 定数 + (−1)^q になる。Brouwer の表ではこれを「周期 2、パターン 1 −1」と書いている。この「パターン」が何を表すかはページに書かれていないが、1 周期分の d(q) = f(q, r) − q から平均を引いたものと解釈すると、19 行全部が開始位置と位相まで合った。たとえば r = 6541（周期 9、開始 9250）は d = 3833, 3833, 3833, 3829, 3832, 3833, 3833, 3833, 3829 で、平均 3832 を引くと 1 1 1 −3 0 1 1 1 −3 になる。表とまったく同じだ。
周期の検出は、各行について周期 k = 1〜12 ごとに「d(q) = d(q−k) が途切れずに続いている開始位置」をストリーミングで持っておき、最後の max(200, 20k) 列以上続いている最小の k を採る。Q = 16,000 では r = 11,172 から上の行はまだ判定がつかない（開始位置がだいたい 1.41r なので、16,000 では足りない）。比較は r ≤ 10,000 だけで行っている。
1 つだけ合わなかった: 95 は 94
Brouwer のページには、f(q, r) = q + c（q ≥ q₀）に落ち着く行について、(a) r の一覧、(b) c の一覧、(c) q₀ の一覧が 54 項ずつ載っている。計算結果を並べると、次の 1 か所だけが食い違った。
| 何番目か | Brouwer の r | 計算した r | c | q₀ |
|---|---|---|---|---|
| 39 | 91 | 91 | 54 | 129 |
| 40 | 95 | 94 | 56 | 133 |
| 41 | 97 | 97 | 58 | 138 |
c = 56、q₀ = 133 は一致しているので、行番号だけがずれている。95 ではありえない理由も分かる。
- (135, 135, 95) は P 局面で、そうなると f(q, 95) は q ≥ 135 で 135 のまま変わらない。つまり行 95 は「定数になる行」の側に入る。
- 行 94 では、q ≥ 133 のすべてで (q + 56, q, 94) が P 局面になり、q = 132 では P にならない。
この 2 つは漸化式を使わず、3×200 の板を総当たりで解いた結果でも確認した（テストに入れてある）。さらに、Brouwer 自身のページにある別の一覧「P 局面 (p, p, r) を持つ r」は「…, 92, 93, 95, 96, …」となっていて、94 を飛ばして 95 を含んでいる。OEIS の A029902 には、この 2 つの一覧は互いに補集合になると予想されている、と書かれている。95 が両方に入っていて 94 がどちらにも入っていないのは、その予想とも合わない。OEIS 側の A029905 は先頭 20 項（r = 45 まで）しかないので、この食い違いは表に出ていなかった。
勝ち手が 2 つある板
Gale は「3×n（n ≤ 100）、2×n、n×n、4×5、4×6 では勝ち手が 1 つ」と報告していて、Gardner はコラムで「勝ち手はいつも 1 つか」と問いかけた。これに Ken Thompson と M. Beeler が反例を見つけた。それが 8×10 で、Brouwer のページは「知られている最小の反例」と書いている。
1×200、2×200、3×200、4×80、5×50、6×36、7×28、8×24、9×20、10×18、11×16、12×15、13×14、14×14 の板をそれぞれ解けば、その中に収まる長方形は全部片付く。行 ≤ 列の長方形 823 個のうち、勝ち手が 2 つあるものは 7 個で、3 つ以上あるものはなかった。
| 板 | マス数 | 勝ち手（行, 列。どちらも毒から 0 始まり） |
|---|---|---|
| 6×13 | 78 | (3, 11), (4, 8) |
| 8×10 | 80 | (3, 8), (4, 5) |
| 9×10 | 90 | (6, 7), (8, 4) |
| 10×14 | 140 | (4, 12), (6, 8) |
| 12×13 | 156 | (9, 10), (10, 8) |
| 8×22 | 176 | (1, 8), (2, 6) |
| 8×23 | 184 | (6, 17), (7, 15) |
8×10 は「10×10 の正方形に収まる中では最小」（10×10 以内で勝ち手が 2 つあるのは 8×10 と 9×10 だけ）だが、面積で比べると 6×13 の方が小さい（78 マス対 80 マス）。80 マス以下の長方形を全部調べると、勝ち手が 2 つあるのは 6×13 と 8×10 だけだった。Brouwer のページの「最小」がどちらの意味かは書かれていない。
検算として、m×n と n×m の両方が計算範囲に入っている長方形が 91 組あり、別々の箱で解いた結果の勝ち手が 91 組とも鏡映しになっていた。n×n が (1, 1)、2×n が右上の角、Gale の 4×5 と 4×6 も 1 つ（それぞれ (2, 2) と (1, 2)）で、これも報告どおりだった。
マス数ごとの局面: 41 マスで「勝ち手が複数」が逆転する
板の形を決めず、「マスが s 個の階段」を全部数えることもできる。階段は s の分割そのものなので、分割の個数を数える漸化式で番号を付ける。s ≤ 60 の 6,639,348 局面を 89 秒で分類した。
OEIS の A112471〜A112473 の b-file は 40 マスで終わっている。その先も計算すると、41 マスで初めて「勝ち手が 2 つ以上」の局面が「勝ち手が 1 つ」の局面より多くなった（21,908 対 21,454。40 マスでは 18,144 対 18,172）。60 マスでは、負け 20,106、勝ち手 1 つ 401,905、勝ち手 2 つ以上 544,456 だった。長方形では勝ち手が 1 つのことがほとんどなのに、局面全体で見ると、大きくなるにつれて勝ち手が複数ある方が普通になっていく。
対戦画面
- 行数（1〜12）と列数（1〜20）を選ぶ。局面数が 100 万以下の板なら、ブラウザがその場で全部解く（10×12 で約 65 万局面、1〜2 秒）。
- マスにマウスを乗せると、食べられる範囲が明るくなる。
- ヒントを付けると、勝てるマスが緑の枠で囲まれる。勝てない局面ではそう表示される。
- コンピュータは勝てる局面では勝ち手を選び、負けている局面では角の 1 マスだけを食べてミスを待つ。
- 右の表から、勝ち手が 2 つある板（ブラウザで解ける大きさのもの）をそのまま呼び出せる。初期表示は 8×10 で、勝ち手 2 つが枠で示される。
ホバーのたびに SVG を作り直していたら、Playwright でクリックが通らなかった。マウスが乗った瞬間に要素が差し替わり、クリックが空振りするためだ。盤の DOM は対局開始時に 1 回だけ作り、その後はクラスの付け替えだけにした。
テスト
npm test で 12 件。
- 4×5、3×7 の全局面を素朴なゲーム木探索と比較
- 5×6 の番号付けが 0〜C(11, 5)−1 を重複なく埋める
- 2×n の P 局面と勝ち手、n×n の勝ち手 (1, 1)
- 80 マス以下で勝ち手が 2 つあるのは 6×13 と 8×10 だけ、10×10 以内では 8×10 と 9×10、10×8 の勝ち手は 8×10 の鏡映し
- OEIS A112470〜A112473（40 マスまで）
- 3 行の漸化式と総当たりの一致、Brouwer の 25×25 の表と r = 120 の行、A029899〜A029902、3×p の勝ち手が一意（p ≤ 1,000）
- Brouwer の一定行の一覧（95 → 94 だけ置き換えて一致）と、(135, 135, 95) と (q+56, q, 94) を総当たりで確認
まとめ
- Chomp の局面は階段なので、組合せ数系で隙間なく番号を付け、辞書式順に 1 回なめるだけで板の全局面が解ける。14×14（4,000 万局面）で 2 分。
- 3 行 Chomp は Brouwer の漸化式で、mex をビット集合で 32 個ずつ探すと q, r ≤ 16,000 まで 3 分かからない。
- Brouwer の表、Nivasch の周期行（204 行）、パターン表 19 行、OEIS 8 本は全部一致した。例外は 1 つで、一定行の一覧の 95 は 94。
- 勝ち手が 2 つある長方形は 14 行まででは 7 個。面積最小は 8×10 ではなく 6×13。
- マス数で数えると、41 マスから勝ち手が複数ある局面の方が多くなる。
参考文献:
- Andries E. Brouwer, "The game of Chomp", https://www.win.tue.nl/~aeb/games/chomp.html（2026 年 10 月 16 日参照）
- D. Gale, "A curious Nim-type game", Amer. Math. Monthly 81, pp. 876–879, 1974
- M. Gardner, "Mathematical Games", Scientific American, 1973 年 1 月
- D. Zeilberger, "Three-Rowed CHOMP", Adv. Applied Math. 26, pp. 168–179, 2001
- S. Byrnes, "Poset game periodicity", INTEGERS 3, 2003
- OEIS A029899〜A029905, A112470〜A112473, https://oeis.org/
デモ: https://sen.ltd/portfolio/chomp/
リポジトリ: https://github.com/sen-ltd/chomp