Clobber（クロバー）— 値が全部「無限小」になるゲームで原子量を計算するエンジンを書き、2005 年の論文を全項目検算したら、最後の図の説明だけ再現しなかった

**Clobber（クロバー）**をブラウザに実装した。盤に黒石（Left）と白石（Right）が並び、手番の人は自分の石を 1 つ持ち上げて、縦横に隣り合う相手の石の上に置く（相手の石は取られる）。動けなくなった方の負け。どの局面でも「片方だけが動ける」状態が起きないので、**値が全部無限小（all-small）になる。そこで標準形の値に加えて、局面を ↑ 何個ぶんかで数える原子量（atomic weight）**を出すようにした。検算は 3 本立て。1×10・2×5・3×4 以下の全 706,116 盤面で「値から読んだ勝敗」と「値を使わない勝敗探索」を突き合わせ（不一致 0）、7 頂点以下の連結グラフ 1,893,731 個で論文の補題 4.1（原子量 = 塞がった道の長さ − 2）を確かめ（不一致 0）、Albert・Grossman・Nowakowski・Wolfe の論文 "An introduction to Clobber"（2005）の 47 項目を再計算した。44 項目は一致。PDF で消えている記号（3 重・4 重の矢印）も、計算結果から復元できた。2002 年の作問コンテスト優勝作「黒先必勝」は、論文の手が 28 手中ただ 1 つの勝ち手だった。一致しなかった 3 項目は、すべて最後の Figure 3 の説明文で、値を使わない探索でも同じ結果になった。テスト 16 件。ソルバー内蔵パズル第 94 弾。

デモ: https://sen.ltd/portfolio/clobber/
リポジトリ: https://github.com/sen-ltd/clobber

ルール

• 盤のマスに黒石（●、Left）と白石（○、Right）が置かれている。空きマスがあってもよい。
• 手番の人は自分の石を 1 つ選び、縦横に隣接する相手の石の上に動かす。相手の石は盤から取り除かれ、元のマスは空く。
• 手番で動ける石がない方の負け（最後に動いた方の勝ち）。

2001 年に Albert・Grossman・Nowakowski・Wolfe が考案したゲームで、Computer Olympiad の種目にもなっている。実戦では市松模様に石を敷き詰めた盤から始める。

値が全部「無限小」になる

組合せゲーム理論では、局面を {Left が行ける局面 | Right が行ける局面} というゲームとみなして「値」を付け、勝敗を値と 0 の大小で読む。

値 G	意味
G > 0	黒の勝ち（どちらが先手でも）
G < 0	白の勝ち
G = 0	後手の勝ち
G ‖ 0（比べられない）	先手の勝ち

Clobber では、黒が動けるのは「黒石と白石が隣り合っている」ときで、そのときは白も動ける。片方だけが動ける局面が存在しないので、値は全部 all-small（どんな正の数よりも小さい無限小）になる。たとえば

• ○● = *（先に取った方の勝ち）
• ○●● = {0 | *} = ↑（黒が少しだけ有利）
• ○●●● = {0 | ↑} = ⇑*
• ●●○○●○●●○○ = *2

のように、↑（アップ）や *n（ニンバー）の組み合わせで書ける値が並ぶ。盤が大きくなると、デモの初期局面のように標準形が 120 個を超える部分ゲームを持つ巨大な無限小になる。

原子量（atomic weight）

無限小どうしの和の勝敗を見積もる道具が原子量。大ざっぱには「↑ 何個ぶんか」を数える量で、↑ の原子量は 1、* は 0、和に対して足し算になる。定義は再帰的で、論文の Definition 3.8 では

G0 = { aw(G^L) − 2 | aw(G^R) + 2 } とする。ただし G0 が整数で、G が ☆（far star）より大きい（小さい）ときは例外で、aw(G^R) + 2 のどれ以上でもない最大の整数（aw(G^L) − 2 のどれ以下でもない最小の整数）を取る。

となっている。原子量が 2 以上なら黒の必勝、−2 以下なら白の必勝という定理があり、デモの右パネルにはこの判定も出している。原子量そのものは数とは限らず、1/8 や ↑ や ⧾(2)（tiny-two = {0 ‖ 0 | −2}）や {n − 3 | 2} のような熱いゲームにもなる。

エンジン

標準形（前回までのエンジンを流用）

src/cgt.ts は、ハッケンブッシュ・ヒキガエルとカエルで使ってきた標準形エンジン。支配される選択肢を消し、可逆な選択肢を迂回する、を不動点まで繰り返して形を一意にし、整数 id で intern する。値が等しいこと = id が等しいことなので、論文の値との照合も id の比較で済む。

盤を「つながった石のかたまり」の和に分ける

Clobber は石が触れていなければ互いに干渉しない。盤は「縦横につながった石のかたまり」の和で、黒だけ・白だけのかたまりは 0。そこで src/clobber.ts の Valuer は、かたまりを切り出して外接矩形に詰め、正方形の 8 つの対称（回転・反転）で最小になる文字列をキーにして値をメモ化する。

/** The same group under the 8 symmetries of the square; the key is the smallest. */
export function shapeKey(b: Board): string {
  let best = '';
  for (let t = 0; t < 8; t++) {
    const swap = t >= 4;              // 転置するか
    const w = swap ? b.h : b.w;
    const h = swap ? b.w : b.h;
    let s = `${w}:`;
    for (let y = 0; y < h; y++) for (let x = 0; x < w; x++) {
      let sx = swap ? y : x;
      let sy = swap ? x : y;
      if (t & 1) sx = b.w - 1 - sx;    // 左右反転
      if (t & 2) sy = b.h - 1 - sy;    // 上下反転
      s += b.cells[sy * b.w + sx];
    }
    if (best === '' || s < best) best = s;
  }
  return best;
}

1 つのかたまりの値は、各手のあとの盤（それ自体がまたかたまりの和）の値を選択肢にして標準形を作るだけ。(●○)ⁿ のような 1 列の盤では、かたまりの種類は n = 19 でも 172 個しかない。重いのは種類の数ではなく、かたまりどうしの和の標準形の方だった（後述）。

原子量と far star

src/atomic.ts は Definition 3.8 をそのまま書いたもの。例外の判定に要る「G と ☆ の比較」は、G のどの部分局面とも等しくないニンバー *m で代用できる（論文にもそう書いてある）。値が *m の局面は m 日目以降に生まれるので、m = （G の誕生日）+ 1 を取れば必ず条件を満たす。

export function farStarSide(g: GameId): 1 | -1 | 0 {
  const star = nimber(birthday(g) + 1);
  if (le(star, g)) return 1;   // G ≥ *m で、G ≠ *m なので G > *m
  if (le(g, star)) return -1;
  return 0;
}

原子量は標準形の選択肢から再帰で計算し、id でメモ化する。テストでは

• 和に対する加法性 aw(G + H) = aw(G) + aw(H)（10 × 10 組）
• 「G + ☆ ≥ 0 ⇔ aw(G) ≥ 1」（1×7 の全 2,187 盤）
• 「aw ≥ 2 なら黒必勝、aw ≤ −2 なら白必勝」（2×4 の全 6,561 盤）

を確かめている。どれも原子量の理論側の定理なので、実装の定義の読み違いがあればここで落ちる。

論文の記法を読むパーサ

照合のために、論文に印刷された値をそのままの記法で書き写してパースし、標準形の id で比べる。Clobber の論文は括弧の代わりに縦棒の本数で入れ子を表す（0 ‖ ⇓*, ⤋ | 5↓ は {0 | {⇓*, 3·↓ | 5·↓}}）。縦棒がいちばん多いところで先に分ける、という規則でパーサを書いた。8↓* のように数字の直後の矢印は「↓ の 8 倍」（Clobber の値は無限小なので、8 + ↓ の意味にはならない）。

検算 1: 全部の小さな盤

node tools/verify.mts boards は 1×1〜1×10、2×2〜2×5、3×3、3×4 の**すべての盤（各マスが空き・黒・白の 3 通り、計 706,116 盤）**について、

1. かたまりに分けて足した値 = 盤全体を 1 つのゲームとして再帰で出した値（9 マス以下）
2. 値から読んだ勝敗 = 値を使わない勝敗探索（Searcher、盤の文字列をキーにした素朴な再帰）

を確かめる。不一致は 0。3×4 の 531,441 盤は 47 秒（ほかの計算と並行して走らせたので目安）。

ちなみにこの照合のテストを書いたとき、Searcher のバグが 1 つ見つかった。メモのキーを盤の文字列だけにしていたので、1×8 の盤と 2×4 の盤（どちらも 8 文字）が同じキーで衝突していた。verify.mts は盤の形ごとに Searcher を作り直していたので結果に影響はなかったが、テストでは 1 つを使い回していて落ちた。キーに幅を入れて直した。

検算 2: 論文の Figure 1 と、PDF で消えている記号

論文の Figure 1 は、2×7 に収まる 9 つの局面の値と原子量の表。原子量は 0, 1/2, 1/4, 1/8, ↑, *, ⧾(1), −2 + ⧾(2), −2 + ⧾(1/2) と並び、9 個すべて一致した。

値の列は少し事情がある。PDF からテキストを抜くと、3 行目が {0 | } のように中身が空になっている。画像に描き出しても空白のまま。{0 | } は 1 という数なので all-small の Clobber に出てくるはずがなく、何かの記号が印刷されていない。計算した値と並べると、

局面	PDF に見える値	計算した値
○●●○○ / ・●○	⇑* | {*, ↓ | ⇓*}, {0 | }	{⇑* | {*, ↓ | ⇓*}, {0 | 3·↓}}
・○○○●○○ / ○●●○●	⇑ | 0, {0 ‖ ⇓*, | 5↓}	{⇑ | 0, {0 | {⇓*, 3·↓ | 5·↓}}}
●○●○●○ / ・●○・○	⇑ | 0, {0 | *}	{⇑ | 0, {0 | 4·↓*}}
○●○●○○ / ●○・○	⇑* | ↓, {0 | *, 5↓}	{⇑* | ↓, {0 | 4·↓*, 5·↓}}

となって、消えているのは**3 本矢印 ⤋（3·↓）と 4 本矢印 ⟱（4·↓）**だと読める。5↓ や 8↓ は数字で書いてあるのに 3 と 4 だけ専用のグリフを使い、そのフォントが PDF に埋め込まれていない、と考えると 4 行ともつじつまが合う。verify.mts では消えたところに ⤋・⟱ を補って書き写し、補ったことを注記した上で 4 行とも id が一致した。残りの値（*2、{⇑* | ↓*}、{⇑ | ⇓*}、8 行目の 4 重の入れ子 ↓, {⇑∗ | ↑ ‖ 0, {∗, ↑ | ∗, ↓} ||| ∗ | ↓} ‖ ⇓∗ | 8↓∗）は記号を補わずに一致。9 行目は論文で「extremely complex」とだけ書かれていて、計算すると名前が 630 文字になった。

図の読み方を計算で決める

p.6 には「n > 4 のとき、この局面の原子量は {0 | {0 | 4 − n}} = ⧾(n − 4)」という主張があり、局面は上の段 ●○○○ⁿ、下の段 ●○● という小さな図で描かれている。指数 n がどこにかかるかが図からは読み切れない。「●○○ のあとに ○ が n 個」と読むと n = 5〜14 の全部で ⧾(n − 4) になり、n = 4 で ↑ に変わる（「n > 4」という条件ともぴったり合う）。「● のあとに ○ が n 個」と読むと同じ値が 2 つ遅れて出る。前者を採用し、そう読んだことを注記した。

同じページの「○●○●ⁿ の原子量は {n − 3 | 2}」は n = 1〜20 の全部で成立。小さい n では {−2 | 2} = 0、{0 | 2} = 1、{1 | 2} = 3/2、{2 | 2} = 2* のように数や数 + * に簡約され、n ≥ 6 で熱いゲームになる。

検算 3: 2002 年の作問コンテスト優勝作

論文の Figure 2 は、2002 年の Computers and Games（エドモントン）で行われた Clobber の作問コンテストの優勝作（Duffy・Kolpin）。10×10 の盤に 6 つのかたまりが散らばっていて、黒先必勝。論文は「各かたまりの原子量の合計は −1 + ⧾(2)、*2 のかたまりを far star として扱うと先手が勝つ。黒は ●○●●○○○ / ○○○○・・○ のかたまりで最初の ● を動かして勝つ」と書いている。

計算すると

• 6 つのかたまりの原子量は ↓*、↓*、−2 + ⧾(2)、0（これが *2）、2 + ⇑、−1 で、合計 −1 + ⧾(2)。論文どおり。
• 盤全体の値は先手勝ち（‖ 0）。
• 黒の合法手 28 手のうち、勝つのは j3 → j4 の 1 手だけ（右端の列、上から 3 段目の ● で 4 段目の ○ を取る）。論文の手と一致し、しかも唯一解だった。

論文の図のかたまりは、盤上では右端の 2 列（j 列の 8 個と i 列の 4 個）に縦に並んでいる。図では横向きに、しかも末尾の ○ を折り曲げて描いてあるが、Clobber は石のつながり方（グラフ）だけで決まるので同じゲームになる。デモの初期局面がこの問題で、スクリーンショットは j3 の黒石を持ち上げたところ（j4 が ✓、i3 が ✗）。

検算 4: 補題 4.1（白石 1 個のグラフ）

論文の 4 章は、白石 1 個とそれ以外全部黒石の局面を任意のグラフ上で考える。黒の手は白石を取ることだけ（取ったら盤が黒一色になって終わり）、白の手は白石を黒石の上へ歩かせることだけなので、局面は「白石の位置と、通ってきて空いたマスの集合」で決まる。補題 4.1 は

aw(G_v) = l(G_v) − 2

で、l(G_v) は v から出る「これ以上延ばせない道（blocked path）」の最短の長さ（最後の 1 歩で枝分かれしている split path なら 1 短く数える）。これを使って「Clobber の勝敗判定は NP 困難」をハミルトン路問題からの帰着で示している。

src/graph.ts に白石 1 個のゲーム（oneWhite）と道の列挙（blockedLength）を書き、**2〜7 頂点のラベル付き連結グラフ全部（1,893,731 個、v は頂点 0。全ラベル付けを回すので根付きグラフは全部出る）**で原子量と l − 2 を比べた。不一致 0。7 頂点では原子量 −1〜5 が出て、いちばん多いのは 2（718,915 個）。

5 章の 3×7 のブロック（白石 1 個を黒石 20 個が囲む）は原子量 6 で、最短の塞がった道は U-R-R-D-D-L-U。論文の「白の手は U-R-R-D-D-L-U」と一致した。同じ G を盤のかたまりとして値を出しても、グラフとして出しても同じ id になる。

検算 5: Figure 3 の値 0 の局面と、再現しなかった 3 つの記述

Figure 3 は、上の 3×7 のブロック G と、白石 70 個が木のように伸びた中に黒石 1 個がいる H を並べた 11×18 の局面で、G + H = 0（後手必勝）。H の白石には L・R・U・D の文字が振ってあり、「黒が H でどの石を取ったら、白は G の白石をその方向に動かせば勝てる」という案内になっている。

計算すると:

• G + H = 0。H = −G（H の値は G の符号を反転したもの）も id で一致。
• 「H には支配される選択肢も可逆な選択肢もない（標準形になっている）」: H の 71 個の部分局面すべてで、標準形の選択肢が実際の手の行き先と一致。成立。
• 値を使わない探索（2 つのかたまりの状態の組を直接探索する sumOutcome）でも G + H は後手必勝。

ここまでは論文どおり。一致しなかったのは、その後の 3 つの文。

1. 「H の触手（tendril）のどれかを 1 つ伸ばすと、G + H′ は 0 と比べられない（先手勝ち）」 → 16 本の触手のどれを 1 つ伸ばしても、白がどちらの手番からでも勝つ（G + H′ < 0）。16 本中 16 本。
2. 「1 つ縮めても先手勝ち」 → 16 本中 15 本で白の必勝、先手勝ちになるのは 1 本だけ。
3. 「印の方向が白の勝ち手で、G が対称なとき以外は唯一」 → 印をたどって到達する 70 局面すべてで印の手は勝ち手だったが、うち 2 局面では G が対称でないのにもう 1 つ勝ち手がある（9 段目 2 列目の L の石を取られたとき、L のほかに D でも勝つ。7 段目 18 列目の R の石では R のほかに U でも勝つ）。

一方、同じ段落の「2 つ伸ばすと白がどちらの手番からでも勝つ」は 16 本中 16 本で成立した。

触手の伸び縮みは、盤の上で石を 1 つ足す・消す（グリッドのかたまりとして値を出す）、グラフの葉に頂点を足す・消す（oneWhite で値を出す）、値を使わない探索、の 3 通りで計算して、48 局面すべてで同じ結果になった。G + H = 0 が成り立っているので H の書き写しは合っている（1 つでも石を写し間違えれば 0 にはならないはず）。触手を「葉で終わる枝」と読んだが、どの葉で試しても論文の主張どおりにならないので、少なくともこの読み方では 1 と 2 は成り立たない。

論文の予想を計算機で

node tools/series.mts は論文の 3 つの予想を 1 つずつ n を増やして確かめ、1 行ずつ runs/ に追記する。

族	論文が計算機で確かめた範囲	ここで確かめた範囲
(●○)n は n ≠ 3 で先手勝ち（予想 3.2）	n ≤ 19	n ≤ 19
(●●○)n = ⌊(n+1)/2⌋·↑（予想 3.3）	n ≤ 17	n ≤ 120（例外 0）
2×n の帯は奇数 n で先手勝ち（予想 3.5）	n ≤ 13	n ≤ 11（n = 12 は 0）

(●○)ⁿ の内訳（勝てる初手の数は黒・白とも同じなので黒だけ載せる）:

n	勝敗	勝てる初手	誕生日	部分ゲーム	時間
1	N	1 / 1	1	2	235 ms
2	N	2 / 3	3	5	1 ms
3	P	0 / 5	0	1	1 ms
4	N	4 / 7	5	14	2 ms
5	N	2 / 9	5	14	3 ms
6	N	1 / 11	3	5	8 ms
7	N	4 / 13	7	75	9 ms
8	N	3 / 15	7	31	15 ms
9	N	6 / 17	9	160	42 ms
10	N	7 / 19	10	214	68 ms
11	N	8 / 21	11	402	103 ms
12	N	7 / 23	12	943	265 ms
13	N	8 / 25	13	1,328	722 ms
14	N	16 / 27	15	3,048	1.2 秒
15	N	7 / 29	15	4,251	2.1 秒
16	N	10 / 31	17	7,260	5.5 秒
17	N	21 / 33	17	13,226	17.4 秒
18	N	16 / 35	19	18,966	116.7 秒
19	N	16 / 37	19	35,399	1381.6 秒

2×n の帯（上の段が白、下の段が黒）:

n	勝敗	勝てる初手	時間
1	N	1 / 1	244 ms
2	P	0 / 2	0 ms
3	N	2 / 3	2 ms
4	P	0 / 4	6 ms
5	N	1 / 5	12 ms
6	P	0 / 6	45 ms
7	N	2 / 7	123 ms
8	P	0 / 8	451 ms
9	N	3 / 9	1.4 秒
10	P	0 / 10	3.5 秒
11	N	4 / 11	18.5 秒
12	P	0 / 12	395.8 秒

(●●○)ⁿ は n = 120 まで予想どおりで、一番重い n でも 2 秒かからない。値が ↑ の倍数のまま増えるだけなので和の標準形が小さい。

(●○)ⁿ は逆で、値の標準形が n とともに爆発する。n = 19 で部分ゲーム 35,399 個・誕生日 19、1 つの n に 23 分。論文の「先手が負ける手は少ない」は、表の「勝てる初手」の数を見ると n によってまちまちで（n = 15 では 29 手中 7 手しか勝たない）、文字どおりには読みにくい。黒と白で勝ち手の数がいつも同じなのは、(●○)ⁿ を左右反転すると色を入れ替えた局面になる（値の符号が反転する）から。

2×n の帯は、偶数 n では補題 3.4 どおり 0、奇数 n では先手勝ち。n = 12 は 0 と分かるまでに 396 秒かかった。n = 11 → 12 で時間が 21 倍になっていて n = 13 は数時間かかる見込みだったので、19 分走らせたところで打ち切った。論文の n = 13 には届いていない。(●○)ⁿ も n = 18 → 19 で 12 倍になっていて、n = 20 は走らせていない。表の時間は 2〜4 本の計算を同じマシンで並行して走らせたときの値なので目安。

計算量と Map の上限

最初の (●○)ⁿ の計算は n = 18 の途中で RangeError: Map maximum size exceeded で落ちた。比較 le と和 add のメモを Map<number, …> 1 つに入れていて、V8 の Map は約 1,670 万件が上限。比較のメモは id の組がキーなので、標準形が大きくなると組の数が急に増える。キーの剰余で 64 個の Map に分ける PairCache にして解決した。

class PairCache<V> {
  private shards: Map<number, V>[] = Array.from({ length: 64 }, () => new Map<number, V>());
  get(k: number): V | undefined { return this.shards[k % 64].get(k); }
  set(k: number, v: V): void { this.shards[k % 64].set(k, v); }
}

もう 1 つの落とし穴は表示。(●○)ⁿ の値は、名前の文字列にすると計算そのものより文字列を作る時間の方が長くなった（入れ子の同じ部分ゲームを何度も書き出すため、文字数は部分ゲームの数よりずっと速く増える）。部分ゲームが一定数を超えたら名前を作らず「部分ゲーム N 個の標準形」とだけ出すようにした。

デモ

• 局面は選択式: 優勝作（黒先必勝）、Figure 3 の G + H = 0（11×18）、(●○)⁸、例外の (●○)³ = 0、(●●○)⁶ = 3·↑、2×5 と 2×6 の帯、3×4 の市松、3×7 のブロック（原子量 6）、Figure 1 の原子量 −2 + ⧾(2) の局面。編集モードで 18×18 まで自由に作れる（xoxo/oxox のように打ち込んでもよい）。
• ヒントを付けると、勝ちを保つ手が緑の矢印で出る。石を持ち上げると、取れる相手の石に ✓ / ✗ が付く。
• 右のパネルには値（大きすぎるときは部分ゲームの数）、勝敗、原子量、かたまりごとの値・原子量・勝敗。
• 計算は Web Worker で、ページを開いている間はかたまりの表を使い回す。4×4 の市松でもう 30 秒以上かかるので、大きな盤は重い。

まとめ

1. Clobber の値は全部無限小になる。標準形のエンジンに、盤をかたまりに分けて形の対称でメモ化する Valuer と、far star を誕生日 + 1 のニンバーで代用する原子量を載せた。
2. 706,116 盤で値と素朴な探索が一致し、補題 4.1 は 1,893,731 個のグラフで成立した。
3. 論文の 47 項目のうち 44 項目が一致。PDF で消えている 3 本・4 本矢印も計算から復元できた。優勝作の黒の勝ち手は論文の 1 手だけだった。
4. 一致しなかったのは Figure 3 の触手の伸び縮みと印の唯一性の 3 つの記述で、値を使わない探索でも同じ結果になった。

参考文献:

• M. H. Albert, J. P. Grossman, R. J. Nowakowski, D. Wolfe, An introduction to Clobber, INTEGERS 5(2) (2005), #A01
• E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for your Mathematical Plays, 2nd ed., A K Peters, 2001（原子量、ch. 8）
• M. H. Albert, R. J. Nowakowski, D. Wolfe, Lessons in Play, A K Peters, 2007
• A. N. Siegel, Combinatorial Game Theory, Graduate Studies in Mathematics 146, AMS, 2013

デモ: https://sen.ltd/portfolio/clobber/
リポジトリ: https://github.com/sen-ltd/clobber