Cram（クラム）をブラウザに実装した。格子にドミノを交互に置き、2 人とも縦にも横にも置ける。置けなくなった人の負け。前に作った Domineering（縦の人と横の人に分かれる版）から色を抜いたゲームで、両者の手が同じなので不偏ゲームになり、局面ごとに ニム数（Grundy 数）が 1 つ決まる。ドミノで壁ができると盤は独立した領域に割れ、局面の値は領域のニム数の XOR になる。コンピュータは完全にプレイし、領域ごとに色を付けてニム数を表示し、XOR を *0 にする手（勝ち手）を緑で示す。空の m × n 盤のニム数は Lemoine と Viennot の 2010 年の論文 "Nimbers are inevitable" に表があるので、3 通りの探索（全部の手を見る mex・ニム数を使わない勝敗探索・論文の方式）で計算し直して照合した。論文に載っている盤のうち計算が締切に間に合った 21 盤（3 × 13 まで、4 × 9、5 × 7 など）は全部一致。比べると、ニム数なしの探索は小さい盤では mex より少なく済むのに、3 × 9 あたりから逆転し、論文の方式は 3 × 12 でニム数なしの 0.30 倍のエントリで済んだ。テスト 14 件。ソルバー内蔵パズル第 90 弾。
デモ: https://sen.ltd/portfolio/cram/
リポジトリ: https://github.com/sen-ltd/cram
ルール
- m × n の格子の空いた 2 マス（縦か横に隣り合う）をドミノで覆う。どちらのプレイヤーも縦・横どちらに置いてもよい。
- 交互に置き、置ける場所がなくなった人が負け（ノーマルプレイ）。
Domineering では片方が縦だけ、もう片方が横だけを置く。Cram はそれを両者とも自由にしたもので、Winning Ways（Berlekamp, Conway, Guy）にも載っている。
Domineering との一番の違い: 盤の値が「ニムの山 1 つ」になる
両者が同じ手を持つゲーム（不偏ゲーム）には Sprague–Grundy の定理が効く。どの局面も、ちょうど 1 つのニムの山 *n と同じふるまいをする。この n がその局面のニム数で、
- 手が 1 つもない局面は *0
- 局面のニム数 = その局面から行ける局面のニム数に出てこない最小の非負整数（mex）
- 独立な局面の和のニム数 = それぞれのニム数の XOR
手番の人が勝つのは、局面全体のニム数が *0 でないとき。勝ち手は、全体を *0 にする手。
Cram では和が自然に出てくる。ドミノを置いていくと空きマスはいくつかの領域（つながった空きマスの塊）に分かれ、ドミノは領域をまたげないので、各領域は独立なゲームになる。スクリーンショットの局面がそれで、左の 12 マスが *5、右上の 4 マスが *2、右下の 2×2 が *0、全体は *5 ⊕ *2 ⊕ *0 = *7。*7 ≠ *0 なので手番（あなた）の勝ちで、勝ち手は「左の領域を *2 にする手」、つまり全体を *2 ⊕ *2 ⊕ *0 = *0 にする手。21 手のうち 2 手だけが緑になっている。
Domineering は縦と横で手が違う（党派的ゲーム）ので、和の値はニムの山では表せない。前に作った Domineering のソルバー（#367）は局面全体を 1 つとして探索していた。Cram では「領域ごとに数を 1 つ覚えておけば、和は XOR で一瞬」になる。
対称戦略: 偶数 × 偶数は後手勝ち、偶数 × 奇数は先手勝ち
計算の前に、半分の盤は答えが決まっている。
- 偶数 × 偶数: 後手は、先手の置いたドミノを盤の中心について点対称に写した位置に置き返せばよい。ドミノの中心は辺の中点、盤の中心は格子点なので、自分自身と重なる（点対称で自分に写る）ドミノはない。だから写した先は必ず空いていて、後手は必ず手がある。→ ニム数は *0。
- 偶数 × 奇数: 盤の中心が 2 マスの境目にあるので、先手がまずその 2 マスを覆い、あとは後手の立場で同じまねをする。→ ニム数は *0 でない（いくつかは分からない）。
奇数 × 奇数にはこの手が使えず、計算するしかない。論文の表も、テストもこの 2 つの性質を確かめる。
ソルバー
領域と形
空きマスは行ごとのビットマスク（rows[r] のビット c が (r, c)）で持つ。1 手打つたびに塗りつぶし（flood fill）で領域に分け、各領域を自分の外接長方形に切り出す。
export function components(rows: readonly number[]): Shape[] {
// … 種から 1 行ずつ広げる。行の中は (x | x<<1 | x>>>1) & left[r] を収束するまで
if (n < 2) continue; // 孤立した 1 マスは二度と覆えないので捨てる
out.push({ rows: out1, w, top: lo, left: shift });
}
隣に空きマスが無いマスは誰も覆えないので、その場で捨てる。だから領域はいつも 2 マス以上で、2〜3 マスの領域はどう打っても 1 マス以下しか残らないので *1 と即答できる。
表のキーは領域の形。正方形の 8 つの対称（回転・裏返し）で写した 8 通りの行リストのうち、行数 ≤ 列数のものの中で最小のものをキーにする。角にある 5 マスの L 字も、別の盤の真ん中にある裏返しの L 字も同じエントリになる。表は全部の盤で共有できる。
export function canonicalKey(s: Shape): string {
let best: number[] | null = null;
if (h <= w) best = bestMirror(s.rows, w, best); // 恒等・上下・左右・180°
if (h >= w) best = bestMirror(transpose(s.rows, w), h, best); // 転置してからの 4 つ
return best!.join(',');
}
方式 1: 全部の手を見る mex
定義そのまま。領域のニム数 = 全部の手について「打った後の領域たちのニム数の XOR」を集め、その mex。
shapeNimber(s: Shape): number {
// … 2〜3 マスは *1、表にあれば返す
const seen: boolean[] = [];
for (const m of movesOf(s.rows)) seen[this.value(play(s.rows, m))] = true;
let g = 0;
while (seen[g]) g++;
this.memo.set(key, g);
return g;
}
ページの完全プレイヤーはこれを Web Worker で動かしている。mex は全部の手の値を求めるので、ついでに「どの手が全体を *0 にするか」も全部分かる。表は訪問中ずっと持ち越すので、空の盤を一度解くと、そこから先の局面はほぼ表引きで済む。
方式 2: ニム数を使わない勝敗探索
対照実験。局面（領域の形の多重集合）について「相手を負けにする手が 1 つでもあれば勝ち」を普通に探索する。表のキーは和全体なので、領域の組み合わせが変わるたびに別のエントリになる。代わりに、勝ち手を 1 つ見つけた時点で打ち切れる。
方式 3: 論文の方式（組の探索）
Lemoine と Viennot の論文の中心はこう。
- 「P のニム数は n か？」は「P + *n で手番の人は負けか？」と同じ問い。後者は勝敗の探索なので、勝ち手を 1 つ見つけた時点で打ち切れる。
- 和を探索するときは、ニム数が分かっている領域を全部山に XOR で畳み込む。分からない領域が 2 つ以上残ったら、小さい方から順にニム数を計算し（n = 0, 1, 2, … と組 (P, n) が負けになるまで試す）、一番大きい 1 つだけを組 (P, n) として探索する。
- 表に残すのは組 (形, n) → 勝ち／負け。
論文の題の「ニム数は避けられない」は、「和の勝敗を求めるとき、ある成分のニム数を計算せずに済ませる方法はない」という定理のこと。ただし全部の手を展開する必要はなく、必要な分だけ組を調べればよい、というのがこの方式。
private winsCouple(s: Shape, key: string, heap: number): boolean {
// … 表にあれば返す
let win = false;
// 山から取る手: *heap → *m は、s のニム数が m なら勝ち
for (let m = 0; m < heap && !win; m++) if (!this.winsCouple(s, key, m)) win = true;
if (!win)
for (const mv of movesOf(s.rows))
if (!this.winsSum(components(play(s.rows, mv)), heap)) { win = true; break; }
this.couples.set(ck, win ? 1 : 0);
if (!win) this.nim.set(key, heap); // (s, heap) が負け ⇔ s のニム数は heap
return win;
}
結果 1: 論文の表を計算し直す
論文の表は TeX ソース（arXiv の e-print）から転記した（src/paper.ts）。PDF のテキストより、表の \nim{4} などをそのまま読める方が確実。
計算は Node 26、12 コアの Mac mini。盤の系列ごとに 1 プロセスで表を共有し、1 盤終わるごとに結果を 1 行ずつ runs/*.jsonl に追記する（途中で止めても終わった分は残る）。各プロセスには 45〜50 分の締切を付けた（後から足した 3 × 14 の勝敗だけの実行は 20 分）。
3 × n
| n | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 論文 | *0 | *1 | *1 | *4 | *1 | *3 | *1 | *2 | *0 | *1 | *2 | *3 | *1 | *4 | *0 | *1 |
| ここ | *0 | *1 | *1 | *4 | *1 | *3 | *1 | *2 | *0 | *1 | *2 | 先手勝ち | — | — | — | — |
3 × 13 まで全部一致。3 × 13 は全部の手を見る mex で新しい形 3,744,918 個（表全体で 5,234,658 個）。3 × 14 は mex では締切（新しい形 4,276,254 個の時点で打ち切り）に間に合わず、勝敗だけを組の探索で求めて先手勝ち（組 7,565,558 個）。論文の *3 は *0 でないので、勝敗としては一致。3 × 15 は組の探索でも締切に間に合わなかった。
4 × 4 以上
| 盤 | 論文 | ここ | 備考 |
|---|---|---|---|
| 4 × 4 | *0 | *0 | 対称戦略 |
| 4 × 5 | *2 | *2 | Schneider 2009 |
| 4 × 6 | *0 | *0 | 対称戦略 |
| 4 × 7 | *3 | *3 | 論文の新結果 |
| 4 × 8 | *0 | *0 | 対称戦略 |
| 4 × 9 | *1 | *1 | 論文の新結果 |
| 5 × 5 | *0 | *0 | Schneider 2009 |
| 5 × 6 | *2 | *2 | 論文の新結果 |
| 5 × 7 | *1 | *1 | Schneider 2009 |
| 5 × 8 | *1 | — | 論文の新結果 |
| 5 × 9 | 先手勝ち | — | 論文の新結果 |
| 6 × 6 | *0 | — | 対称戦略 |
| 6 × 7 | *3 より大 | — | 論文 |
| 7 × 7 | 先手勝ち | — | 論文の新結果 |
計算できた盤は全部論文と一致し、食い違いは 0。論文が 2010 年の新結果として挙げた 4 × 7、4 × 9、5 × 6 のニム数も同じ値になった。5 × 8 は組の探索で 50 分の締切に間に合わなかった（新しい組 9,915,560 個、表全体で 18,952,183 個の時点）。勝敗まで含めて論文と照合できた盤は 21 個で、食い違いは 0。
npm run table が全部の実行ログを 1 つの表（src/table.json）にまとめるとき、同じ盤で方式どうしの答えが食い違ったら書き出しを拒否する。ページの右の表はこれを読んでいて、論文にある盤は下線付き。
おまけ: 1 × n と 2 × n
1 × n の Cram は「並んだピンから隣り合う 2 本を取る」ゲームで、八進ゲームの 0.07（Dawson's Kayles）そのもの。n = 30 まで Dawson's Kayles の Grundy 数と一致することをテストで確かめている。
2 × n は n = 24 まで、n が偶数なら *0、奇数なら *1 だった。偶数で *0、奇数で *0 でないのは対称戦略から言えるが、奇数のときに値がいつも *1 になる理由はここでは示していない（計算で見ただけ）。
結果 2: ニム数を使わないと何が起きるか
同じ盤を 3 方式で、それぞれ新しい表から解き、解いたエントリ数を比べた（tools/run-ablation.mts）。mex は「形」の数、ニム数なしは「和」の数、組の探索は「(形, n) の組」の数。3 方式とも勝敗は全部一致した。
| 盤 | ニム数 | 全部の手を見る mex | ニム数なし（和ごと） | 組の探索（論文の方式） |
|---|---|---|---|---|
| 2 × 4 | *0 | 7 | 11 | 7 |
| 3 × 3 | *0 | 9 | 8 | 5 |
| 2 × 6 | *0 | 29 | 42 | 30 |
| 3 × 4 | *1 | 52 | 33 | 25 |
| 4 × 4 | *0 | 194 | 132 | 106 |
| 3 × 5 | *1 | 211 | 115 | 99 |
| 3 × 6 | *4 | 778 | 456 | 358 |
| 4 × 5 | *2 | 2,300 | 1,607 | 1,236 |
| 3 × 7 | *1 | 2,760 | 2,574 | 1,801 |
| 4 × 6 | *0 | 16,234 | 12,857 | 9,001 |
| 5 × 5 | *0 | 16,453 | 12,552 | 8,383 |
| 3 × 8 | *3 | 9,680 | 7,152 | 4,114 |
| 3 × 9 | *1 | 33,922 | 39,565 | 20,943 |
| 4 × 7 | *3 | 109,821 | 95,939 | 61,090 |
| 3 × 10 | *2 | 118,990 | 142,446 | 62,318 |
| 5 × 6 | *2 | 356,379 | 242,681 | 146,066 |
| 3 × 11 | *0 | 417,635 | 850,837 | 312,182 |
| 4 × 8 | *0 | 715,765 | 920,582 | 481,201 |
| 3 × 12 | *1 | 1,467,180 | 2,813,543 | 852,275 |
読み取れること:
- 小さい盤では、ニム数を使わない方が mex より少ない。 3 × 3〜3 × 8、4 × 4〜5 × 6 では、ニム数なしの探索は mex の 0.55〜0.93 倍で済む。勝ち手を 1 つ見つけたら打ち切れるからで、mex は全部の形の全部の手を見ないとニム数が決まらない。
- 盤が大きくなると逆転する。 3 × 9 で 1.17 倍、3 × 11 で 2.04 倍、3 × 12 で 1.92 倍、4 × 8 で 1.29 倍。ニム数なしの探索は「領域の組み合わせ」ごとに別エントリになるので、盤が早く細かく割れるほど組み合わせが増える。3 × n は幅 3 なので、縦に 1 本置くだけで左右に割れる。2 × n はもっと極端で、2 × 4 から既に 1.57 倍。
- 論文の方式は、ほぼ全部の盤で一番少ない。 3 行以上の盤では mex の 0.41〜0.75 倍。ニム数なしの探索と比べると、3 × n では 3 × 5 の 0.86 倍から 3 × 12 の 0.30 倍まで、盤が大きくなるほど差が開く。例外は 2 行の 2 つで、2 × 4 は mex と同じ 7、2 × 6 は mex の 29 に対して 30。
「ニム数は避けられない」は、和を扱う限り成分のニム数が必要になる、という主張で、表の数字はそのとおりに動いた。ただし同時に、「ニム数を求める」を「全部の手を展開する」と同じだと思うと、小さい盤ではニム数なしにさえ負ける。組 (P, n) の勝敗として求めて、打ち切りを効かせるところまでが論文の方式。
時間は載せていない。測っている途中、10 本のプロセスを同時に走らせたせいで macOS のメモリ圧縮が効き、全部のプロセスが CPU 30% 前後まで落ちていた（7 本止めたら残りは 99% に戻った）。その間の秒数は負荷の大きさで決まっていて方式の比較にならない。エントリ数は負荷に左右されない。
届かなかったところ
論文は 3 × 18 までと 5 × 9・7 × 7 の勝敗まで出しているが、ここでは 3 × 13 のニム数、3 × 14 の勝敗、5 × 7・4 × 9 のニム数までだった。
-
表の作り方。 形のキーは行のビットマスクを
join(',')した文字列で、JavaScript のMapに入れている。1 つのMapは 2^24 個ほどで RangeError になるので 16 個に分けた。5 × 8 で止まった時点の表は 1,895 万エントリ。キーを数値に詰めれば速く小さくなるはずだが、今回はやっていない。 - 割れる時期。 論文も「盤を少し大きくすると計算が急に難しくなる。盤が大きいほど、ゲーム木の中で局面が割れる時期が遅くなるから」と書いている。論文でも 3 × n は 18 まで出ているのに 5 × 9 や 7 × 7 は勝敗だけなのは、幅 3 ならすぐ割れるからだろう。
- 論文が最後に予告している Cram 専用の工夫（"The optimisations specific to the game of Cram will be the subject of a future article."）は入れていない。ここの組の探索は手の順序も素朴（左上から）。
- 並列の失敗。 最初に 10 本を同時に走らせたらメモリ圧縮で全部遅くなった。2 × 24 は形の数が 2 × 23 の 1.8 倍なのに時間は 15 倍かかった（58 秒 → 845 秒）。7 本止めたら残りは 99% に戻ったが、それまでの 25 分ほどは全部のプロセスの進みが大きく落ちていた。
テスト
src/cram.test.ts の 14 件。
- 領域分け（孤立マスを捨てる）、形のキーが 8 つの対称で同じになり、違う形では違うこと、手の数が m(n−1) + (m−1)n になること
- 定義そのままの Grundy 数（領域分けも対称も 2〜3 マスの近道も使わず、マスの集合をそのままメモする）と、12 マスまでの全部の盤、14 マスまでのランダムな形 300 個で一致すること
- 1 × n が n = 30 まで Dawson's Kayles（自前で計算した 0.07 の Grundy 数）と一致すること
- 対称戦略: 偶数 × 偶数は *0、偶数 × 奇数は *0 でないこと
- 2 × n が n = 16 まで偶数 *0・奇数 *1 であること
- 3 方式（mex・ニム数なし・組の探索）が 7 つの盤でニム数と勝敗とも一致すること
- 論文の値のうちテストで回せる 9 盤（3 × 3〜3 × 8、4 × 4、4 × 5、5 × 5）をその場で計算して一致すること
- 論文の表の転記が 3 × n で 16 個、それ以外で 17 個（7 × 9 は空欄）あり、偶数 × 偶数が全部 0 であること
-
src/table.json（長い計算の結果）のうち論文にある盤が全部一致し、計算した全部の盤が対称戦略と矛盾しないこと - スクリーンショットの局面で領域が *5・*2・*0、全体 *7、21 手のうち勝ち手がちょうど 2 つで、その 2 手の後はニム数なしの探索でも手番の負けになること
まとめ
- Cram は不偏ゲームなので局面はニムの山 1 つと同じ。盤はドミノで独立な領域に割れ、全体の値は領域のニム数の XOR。表は領域の「形」を 8 つの対称で揃えたキーで全部の盤が共有できる。
- Lemoine–Viennot（2010）の表は、3 × 3〜3 × 13、4 × 4〜4 × 9、5 × 5〜5 × 7 のニム数と 3 × 14 の勝敗、計 21 盤で一致した。食い違いは 0。2 × n は n = 24 まで偶数 *0・奇数 *1。
- ニム数を使わない探索は、小さい盤では全部の手を見る mex より少なく済むが、3 × 9 以降と 4 × 8 で逆転する（3 × 12 で 1.92 倍）。論文の「組 (P, n) の勝敗」の方式は 3 行以上の全部の盤で一番少なく、3 × 12 ではニム数なしの 0.30 倍。ニム数は避けられないが、全部の手を展開する必要もない。
参考文献:
- J. Lemoine, S. Viennot, "Nimbers are inevitable", arXiv:1011.5841, 2010, https://arxiv.org/abs/1011.5841（2026 年 10 月 20 日参照。表の値は TeX ソースから転記）
- M. Schneider, "Das Spiel Juvavum", Master's thesis, Universität Salzburg, 2009（論文が * で示している先行値）
- E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for your Mathematical Plays, A K Peters, 2001
デモ: https://sen.ltd/portfolio/cram/
リポジトリ: https://github.com/sen-ltd/cram