Toppling Dominoes（ドミノ倒しゲーム）— 論文「Toppling Conjectures」の定理と予想を全列挙で検算したら、予想 39 だけは b = c のとき成り立たなかった

**Toppling Dominoes（トップリング・ドミノ）**をブラウザに実装した。一列に並んだ青（Left）・赤（Right）・緑（どちらでも）のドミノから、手番の人が自分の色のドミノを 1 枚選んで東か西へ倒す。倒したドミノと、その側にあるドミノは全部なくなる。動けなくなった方の負け。すべての列に組合せゲーム理論の正確な値（数・↑・⧾ タイニー・ニム数・熱いゲーム）を付け、倒し方ごとに勝ち筋か負け筋かを ✓／✗ で表示する。検算の対象は Fink・Nowakowski・Siegel・Wolfe の論文 "Toppling Conjectures"（Games of No Chance 4, 2015）で、定理と予想を、3 色で長さ 12 以下の全 797,161 列と、青赤だけで長さ 19 以下の全 1,048,575 列で総当たりした。数はどれも 1 列でしか作れず、その列は回文になる（定理 16）。⧿x は R L x L R で作れて、それ以外の列では作れない（予想 22。論文は長さ 15 まで確認、ここでは青赤の列で 19 まで）。*m の作り方はちょうど m 通り（定理 29）。このあたりは全部成り立った。成り立たなかったのは予想 39 で、ゲーム {a | b ‖ c | d} を作る列を b R L a L R d R L c としている。b > c なら 3,911 件すべてで正しかったが、b = c の 1,107 件はすべて外れた。b = c だと {a | b ‖ b | d} は数 b そのものになり、数を作る列は 1 本しかないからだ。図版のドミノは PDF から文字に落ちないので画像から書き写し、論文が演習問題として残した Figure 1 の値（3/8）も計算した。テスト 24 件。ソルバー内蔵パズル第 95 弾。

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

ルール

• ドミノが一列に立っている。色は青（Left）、赤（Right）、緑（Either、どちらの手番でも倒せる）の 3 つ。
• 手番の人は、自分が倒せる色のドミノを 1 枚選び、**東（右）か西（左）**へ倒す。倒したドミノと、倒した側にあるドミノは全部連鎖して倒れ、列から消える。
• 手番で倒せるドミノがない方の負け（最後に動いた方の勝ち）。

Albert・Nowakowski・Wolfe の教科書 Lessons in Play（2007）で導入されたゲームで、組合せゲーム理論の「おなじみの値がだいたい全部出てくる」例として知られている。論文では Left = 青（白黒印刷では黒）、Right = 赤（白）、Either = 緑（灰色）。この記事では列を L R E の文字列で、西から東の順に書く。

例として、論文 p.65 の LRLR で Left（青）が打てる手は 4 つある。

倒すドミノ	向き	残る列
1 枚目（青）	西	RLR
1 枚目（青）	東	（空）
3 枚目（青）	西	R
3 枚目（青）	東	LR

論文の A〜D と同じ 4 つが出る。この表は tools/verify.mts の項目 sec1-options で照合している。

どんな値が出てくるか

論文の Figure 2 は、おなじみの値を作る列の見本帳になっている。図はドミノの絵で、pdftotext では何も出てこない。そこで PDF を 400 dpi で画像化し、ドミノの色を目で読んで文字列に書き写した。

列	値	計算結果
LLLLL	5	5
LRL	1/2	1/2
LRLRL	1/4	1/4
LRLRLRL	1/8	1/8
EEEEE	*5	*5
LRRL	↑	↑
LRRRL	⧾(1)	⧾(1)
LRRRRL	⧾(2)	⧾(2)
LRRLRRL	⧾(1/2)	⧾(1/2)
LRLRE	*3	*3
LERE（予想 33）	{1 | 0, {0 | −1}}	{1 | 0, {0 | −1}}

11 個すべて一致した。論文には「Figure 1 の値は？」という演習問題もある。Figure 1 の列は LRLRLLRLRL で、値は 3/8。数なので、後で見る定理 16 によれば 3/8 になる列はこれ 1 本しかなく、実際に回文になっている。

緑だけの列 E…E は Nim の山と同じ（n 枚で *n）。青端と青端に挟まれた列は必ず Left の勝ち、といった勝敗の判定は、論文の補題 1 が「両端のドミノだけで決まる」と述べている。

• 空の列は 0（後手勝ち）
• 両端が青なら Left の勝ち、両端が赤なら Right の勝ち
• 両端の色が違う、または端に緑があれば先手の勝ち

最後の「端に緑」の行は論文に明示されていないが、緑の端を内側へ倒せば相手に何も残らないので明らか。これも全列挙で確かめた（後述）。

エンジン

局面は全部「部分文字列」

ドミノを西へ倒すと、それより西が全部消える。東へ倒すと、それより東が全部消える。つまり列 s から行ける局面は、接頭辞か接尾辞を削った s の部分文字列しかない。長さ n の列から出てくる局面は高々 n(n+1)/2 + 1 個で、Clobber（#377）のように盤を分割したり対称性でまとめたりする必要がない。値は列そのものをキーにメモ化する。

export function moves(s: string, p: Player): Move[] {
  const out: Move[] = [];
  for (let i = 0; i < s.length; i++) {
    if (!canTopple(s[i], p)) continue;
    out.push({ i, dir: 'W', to: s.slice(i + 1) });
    out.push({ i, dir: 'E', to: s.slice(0, i) });
  }
  return out;
}

export class Valuer {
  private memo = new Map<string, GameId>([['', ZERO]]);
  value(s: string): GameId {
    const hit = this.memo.get(s);
    if (hit !== undefined) return hit;
    const g = make(options(s, 'L').map((t) => this.value(t)), options(s, 'R').map((t) => this.value(t)));
    this.memo.set(s, g);
    return g;
  }
}

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

make(L, R) は #375 Hackenbush で作り、#377 Clobber で拡張した標準形のエンジンをそのまま使っている。支配される選択肢を消し、可逆な選択肢を迂回して標準形にし、その標準形を一度だけ intern する。こうすると値が等しいことと id が等しいことが同じになる。数は「間で最も単純な数」として直接作り、名前は ↑・⧾(x)・*m・±x などを id の表から引く。

値を使わない勝敗探索

エンジンの検算用に、値を一切使わない勝敗探索（Searcher）も持っている。「手番の人に、相手が負ける局面へ行く手があるか」を列ごとにメモ化して調べるだけのもの。全列挙では、すべての列について「値から読んだ勝敗」「補題 1 の端による判定」「素朴な探索」の 3 つが一致するかを見ている。

序数和 1:G

論文の柱になる定理 10 は「f(G) = 1:G」という形をしている。1:G は序数和で、G に「Left だけが一手で 0 へ行ける」という土台を付けたゲームだ。土台で動くと上の G ごと消える。

export function ordinalOne(g: GameId): GameId {
  return make([ZERO, ...leftOptions(g).map(ordinalOne)], rightOptions(g).map(ordinalOne));
}

（実装ではメモ化している。）f は「青の連（空の連も含む）すべてに青を 1 枚足す」写像で、f(RRLLRL) = LRLRLLLRLL（定義 9 の例。これも照合した）。

export const f = (s: string): string => 'L' + s.replace(/[RE]/g, (c) => c + 'L');

全列挙の設計

論文の定理や予想は「すべての列について」の主張が多い。そこで、長さ 0 から順に、全部の列を辞書順に値付けしていく。長さ n の列の選択肢は長さ n − 1 以下の部分文字列なので、一つ前までの長さでもうメモに入っている。値ごとに「その値になった列の数」と「鏡像を同一視した列の数」を数えておき、一意性の主張は最後にまとめて判定する。

各列では次を調べる。

• 補題 1（端で勝敗が決まる）と、素朴な探索との一致
• 定理 10: 列が f の像なら、f⁻¹ を求めて値 = 1:(f⁻¹ の値)
• 予想 34: 青を 1 枚挿入すると値が真に増える（x L y > x y）
• 補題 14: 正の数の列には青以外のドミノが 2 枚続かない
• 補題 30・31: 無限小の列の形と、ニム数への逃げ道

node tools/verify.mts sweep LRE 12   # 3 色、長さ 12 以下の全 797,161 列
node tools/verify.mts sweep LR 19    # 青赤だけ、長さ 19 以下の全 1,048,575 列
node tools/report.mts 19 12          # 表と src/findings.json を runs/ から生成

長さごとの経過は runs/sweep-*.jsonl に 1 行ずつ追記される。記事の表と数字は runs/ の JSON から機械的に埋め込んだもので、手で書き写したものはない（node tools/report.mts 19 12 で同じ表が出る）。

3 色

長さ	列の数	新しく出た値	数	熱い	無限小	時間
0	1	1	1	0	1	1 ms
1	3	3	2	0	1	0 ms
2	9	5	2	4	3	0 ms
3	27	14	4	14	7	1 ms
4	81	30	2	52	21	3 ms
5	243	88	6	164	61	7 ms
6	729	224	4	500	183	42 ms
7	2,187	683	6	1,514	547	119 ms
8	6,561	1,953	4	4,564	1,641	451 ms
9	19,683	5,953	10	13,696	4,921	2.5 s
10	59,049	17,733	4	41,116	14,763	14.6 s
11	177,147	54,014	12	123,374	44,287	143.1 s
12	531,441	163,216	6	370,124	132,861	649.5 s

青赤だけ

長さ	列の数	新しく出た値	数	熱い	無限小	時間
0	1	1	1	0	1	2 ms
1	2	2	2	0	0	1 ms
2	4	3	2	0	2	1 ms
3	8	6	4	4	0	1 ms
4	16	10	2	6	4	0 ms
5	32	20	6	24	2	2 ms
6	64	36	4	44	10	3 ms
7	128	72	6	100	12	6 ms
8	256	135	4	202	32	20 ms
9	512	272	10	424	54	33 ms
10	1,024	527	4	832	118	114 ms
11	2,048	1,056	12	1,708	224	289 ms
12	4,096	2,079	6	3,398	460	642 ms
13	8,192	4,158	8	6,816	906	1.4 s
14	16,384	8,253	8	13,648	1,826	3.5 s
15	32,768	16,512	16	27,328	3,636	9.2 s
16	65,536	32,892	6	54,626	7,288	21.0 s
17	131,072	65,792	18	109,324	14,558	75.6 s
18	262,144	131,323	8	218,604	29,134	287.8 s
19	524,288	262,654	12	437,268	58,248	966.6 s

時間は 3 本の全列挙を同じマシンで並行に走らせたときのもので、目安にとどまる。最後の 1 段で、3 色は 4.5 倍、青赤だけは 3.4 倍に伸びた。3 色の長さ 13 も走らせたが、この伸び方では制限時間内に終わらないので途中で打ち切り、3 色は長さ 12 までとした。

検算 1: 数は 1 列だけ、しかも回文（定理 10・16、系 17）

論文の第一の結果は「どの 2 進有理数 x にも、値が x になる列がちょうど 1 本ある。その列は回文」というもの。証明は構成的で、次の 2 つを使う。

1. 定理 10: f(G) = 1:G
2. Berlekamp–Conway–Guy の事実 7: 正の数 x は、より単純な数 y を使って 1:y と書ける

なので x > 0 の列は f(x の y に当たる列)、x < 0 の列は色を反転したもの、と再帰的に作れる。y を逆算する部分は次のとおり。

/** The number y with 1:y = x, for a dyadic x > 0 (Fact 7). */
export function ordinalOneInverse(x: number): number {
  if (Number.isInteger(x)) return x - 1;          // 1:n = n + 1
  let d = 2;
  while (!Number.isInteger(x * d)) d *= 2;
  const lo = x - 1 / d;
  const hi = x + 1 / d;
  if (lo === 0) return -Math.log2(d);             // 1:(−n) = 2^−n
  return simplestBetween(ordinalOneInverse(lo), ordinalOneInverse(hi));
}

export function numberRow(x: number): string {
  if (x === 0) return '';
  if (x < 0) return negate(numberRow(-x));
  return f(numberRow(ordinalOneInverse(x)));
}

numberRow(3/8) = LRLRLLRLRL（Figure 1）、numberRow(3/4) = LRLLRL、numberRow(5/8) = LRLLRLRLLRL。

全列挙では、数になった列を値ごとに集めて「1 本だけか」「回文か」「numberRow が作る列と同じか」を見た。3 色の長さ 12 以下に数は 63 個、青赤の長さ 19 以下に 139 個あり、例外はなかった。定理 10 そのもの（f(G) の値 = 1:G）は、3 色で 2,730 列、青赤で 10,945 列について確かめた（f(G) が全列挙の範囲に収まる G すべて）。

検算 2: タイニー（定理 21、予想 22）

論文の第二の結果は、x > 0 の数の列を挟んだ R L x L R が ⧿x（マイニー x = {x | 0 ‖ 0}）になるというもの。色を反転すれば L R (−x) R L = ⧾x（タイニー x）。Figure 2 の右列 LRRRL = ⧾(1)、LRRLRRL = ⧾(1/2) がこの形をしている。

論文は「⧿x になる列はこれだけか」を予想 22 として残し、長さ 15 まで確認と書いている。全列挙では、⧿x・⧾x になる列を値の索引から数えた。

• 3 色・長さ 12 以下: 30 個のタイニー／マイニーすべて、その値になる列は 1 本だけ
• 青赤・長さ 19 以下: 94 個すべて、青赤の列では 1 本だけ

青赤の列に限れば、論文の 15 を 19 まで延ばしたことになる。ただし緑を含む列については長さ 12 までしか見ていない。

検算 3: *m の作り方はちょうど m 通り（定理 29）

ニム数は数と違って作り方が複数ある。論文の定理 29 は、青赤の列で *m になるのは (LR)^a (RL)^m (LR)^a（0 ≤ a < m）とその鏡像だけ、つまり鏡像を同一視して m 通り、というもの。

m	長さ 19 以下で見つかった列（鏡像込み）	定理 29 から予想される列（長さ 19 以下）
*1	2	2
*2	4	4
*3	6	6
*4	6	6
*5	6	6
*6	4	4
*7	4	4
*8	2	2
*9	2	2

全部一致した。a を 1 増やすと長さが 4 増えるので、長さ 19 では m 通り全部が揃うのは小さい m だけになる。緑を許すとニム数の作り方は一気に増え、たとえば *2 は 3 色・長さ 12 以下で 9 本の列がある（EE、LRE、ELR、…）。

検算 4: 無限小の形（補題 30・31）と、再計算しなかった定理 32

論文の最後の定理 32 は「無限小の列の原子量は 0、1、−1 のどれか」。証明は補題 30・31 に乗っている。

• 補題 30: 青で始まる無限小の列は (LR)^n、(LR)^n E x、(LR)^n R x のどれか
• 補題 31: 無限小の列では、先手は必ずニム数へ行ける。先手がニム数以外へ行ったら、後手はニム数で応じられる

この 2 つは列と値だけで判定できるので、3 色・長さ 12 以下の無限小 199,296 列すべてで調べ、例外はなかった。

定理 32 そのものは再計算していない。原子量の再帰式（#377 Clobber で実装した Definition 3.8）は all-small なゲーム、つまり「片方だけが動ける局面がない」ゲームのためのものだ。Toppling Dominoes の無限小は L（= 1）のような数を部分局面に含むので all-small ではない。論文は「数の停止点を別の記号に置き換えて all-small に直す」と書いているが、置き換え先の記号が PDF で消えていて、手順もスケッチにとどまっている。推測で実装して「一致した」と書くことはしなかった。

検算 5: 予想 33・34・35

• 予想 33: 値 {1 | 0, {0 | −1}}（LERE）は青赤の列には出てこない。→ 青赤・長さ 19 以下で 0 本。緑を許すと長さ 12 以下で 4 本ある（LERE、EREL、LLRRE、…）。
• 予想 34: どんな列 x, y でも、間に青を 1 枚挟むと値が真に増える（x L y > x y）。→ 全列挙の全列・全挿入位置、計 12,492,971 通りで成立。
• 予想 35: 青赤の回文の値は、ほかの青赤の列には出てこない。→ 長さ 19 以下の回文 3,069 本すべてで成立。

予想 35 については、もっと強いことが観察できた。青赤の列は、鏡像を除くとほとんど値を共有しない。長さ 19 以下の全 1,048,575 列で、鏡像でない 2 本以上の列に共有されている値は 16 個しかなく、うち 6 個は定理 29 のニム数だった。ニム数以外の値は次のとおり（短い順）。

• 1*2: LLRLLRL, LLRLRLLRLLLRL (2 up to reversal)
• −1*2: RLRRLRR, RLRRRLRRLRLRR (2 up to reversal)
• 2*2: LLLRLLLRLL, LLLRLLRLLLRLLLLRLL (2 up to reversal)
• 1*3: LLRLLRLLRL, LLRLRLLRLLRLLLRL (2 up to reversal)
• {*, *2, {0 | *, *2} | *, *2, {*, *2 | 0}}: LRLRRLLRLR, LRRLRLLRRLRLLR (2 up to reversal)
• −1*3: RLRRLRRLRR, RLRRRLRRLRRLRLRR (2 up to reversal)
• −2*2: RRLRRRLRRR, RRLRRRRLRRRLRRLRRR (2 up to reversal)
• 1*4: LLRLLRLLRLLRL, LLRLRLLRLLRLLRLLLRL (2 up to reversal)
• −1*4: RLRRLRRLRRLRR, RLRRRLRRLRRLRRLRLRR (2 up to reversal)
• {*, *3, {0 | *, *3} | *, *3, {*, *3 | 0}}: LRLRLRRLLRLRLR, LRRLRLRLLRRLRLRLLR (2 up to reversal)

ほとんどが 1*2、2*2、1*3 のような「整数 + ニム数」で、ニム数に複数の作り方がある（定理 29）ことと関係していそうだが、そこまでは確かめていない。

LLRLLRL と LLRLRLLRLLLRL はどちらも 1*2 で、互いに鏡像ではない。緑を許すと事情はまったく違い、LE と LLR がどちらも {1 | 0} になるように、短い列からどんどん値が重なる。

本題: 予想 37〜39 と、b = c のときの反例

論文の最後に、数 a ≥ b ≥ c ≥ d を使って熱いゲームを作る列の予想が並んでいる（数 x の列も x と書く）。

• 定理 36: 数 x = {xL | xR}（標準形）は xL L R xR
• 予想 37: {a | b} は a L R b
• 予想 38: {a ‖ b | c} は a L R c R L b
• 予想 39: {a | b ‖ c | d} は b R L a L R d R L c

全列挙の範囲に収まる (a, b, c, d) の組をすべて作り、列の値が主張どおりか、その値になる青赤の列がほかにないか（鏡像は除く）を調べた。

• 定理 36: 100 組すべて成立
• 予想 37: 1,544 組すべて成立（a = b の {a | a} = a* を含む）
• 予想 38: 4,440 組すべて成立（等号を含む組も全部）
• 予想 39: 5,018 組中 1,107 組で値が違った

予想 39 を等号の入り方で分けると、外れ方がはっきりする。

等号の入り方	組	値が主張どおり	主張されたゲームが数
a=b=c=d	9	0	9
a=b=c>d	128	0	128
a=b>c=d	68	68	0
a=b>c>d	647	647	0
a>b=c=d	128	0	128
a>b=c>d	842	0	842
a>b>c=d	647	647	0
a>b>c>d	2549	2549	0

外れたのは b = c の組だけで、b = c の組は全部外れた。b > c なら、a = b や c = d の等号があっても全部成り立っている。最後の列は「主張されたゲームを標準形にすると数になる組の数」で、外れた件数と一致する。

なぜ b = c だと成り立たないか

b = c のとき、主張されたゲームは G = {a | b ‖ b | d}（a ≥ b ≥ d）。G − b = {a − b | 0 ‖ 0 | d − b} を考えると、

• Left が先に動くと {a − b | 0} へ行くしかなく、Right が 0 へ応じて Left の負け
• Right が先に動くと {0 | d − b} へ行くしかなく、Left が 0 へ応じて Right の負け

となって後手必勝、つまり G − b = 0。主張されたゲームは数 b そのものになる。ところが定理 16 により、b になる列は numberRow(b) の 1 本しかなく、b R L a L R d R L b は b の列を含んだうえで 6 枚以上長い、別の列だ。だから値が一致することはありえない。

具体例を挙げる。a = 2、b = c = 1、d = 0 なら予想の列は LRLLLLRRLL で、主張されたゲーム {2 | 1 ‖ 1 | 0} は 1。実際の値は

LRLLLLRRLL = {{2 | {1 | 0}}, {2 | 1} | {1 | 0}, {{2 | 1} | 0}}

で、Left の停止点も Right の停止点も 1 だが、1 ではない（1 との差は無限小で、Blue が先手でも後手でも勝つ。1 なら後手勝ちのはず）。d を −1 にずらして b > c にした LRLLLLRRRL は、予想どおり {{2 | 1} | {0 | −1}} = {2 | 1 ‖ 0 | −1} になる。

予想 39 は「a ≥ b ≥ c ≥ d」ではなく「a ≥ b > c ≥ d」と読むべきだった、ということになる。b > c に直した形なら、全列挙の範囲（3,911 組）では反例がなかった。ほかの予想（37・38）は等号を含めて全部成り立つので、39 だけ不等号の条件が 1 か所ゆるかったのだと思う。

テストでは、b > c の 3 例が成り立つことと、b = c の LRLLLLRRLL で「主張されたゲーム = 数 1」「列の値は数ではない」の 2 点を固定している。

予想 40: 現れないゲーム

予想 40 は「Toppling Dominoes に現れないゲームがある」。比較として Hackenbush には熱いゲームが一切出てこないことが挙げられている。誕生日 2 までに生まれるゲームは 22 個あるので、それぞれがどの列で最初に出てくるかを数えた。

3 色・長さ 12 以下で、22 個中 18 個が現れ、↓、↑、{0, * | −1}、{1 | 0, } は現れなかった*。↑ は LRRL で出てくるのに、↑* は長さ 12 までどこにも出てこない。これは予想 40 の具体的な候補になるが、もちろん長さ 12 までの観察で、証明ではない。

デモ

• 上段の「row」から論文の図の列（Figure 1、↑、⧾(1/2)、*3）、予想 39 が成り立つ列と外れる列、予想 33 の LERE、鏡像でないのに値が同じ 1*2 の列などを選べる。
• 自分の色のドミノの上に ← → のボタンが出る。ヒントをオンにすると、その方向へ倒したあと自分が勝てるなら ✓、負けるなら ✗。
• 相手はコンピュータで、勝てる手があればその中から選び、なければドミノをなるべく多く残す手を選ぶ。
• 「Edit」で列を作れる。ドミノをクリックすると青 → 赤 → 緑と色が変わる。L R E の文字列で入力することもできる（24 枚まで）。
• 右側に列の値・勝敗・数／ニム数／タイニーなどの分類・標準形と、論文の検算結果の一覧を表示する。

まとめ

1. Toppling Dominoes の局面は全部部分文字列なので、列そのものをキーにしたメモ化で値が出る。標準形のエンジンは #375・#377 のものを流用した。
2. 論文 "Toppling Conjectures" の図の値（PDF の画像から書き写した 11 列）、Figure 1 の演習問題（3/8）、定理 10・16・21・29、補題 1・14・30・31、予想 22・33・34・35・37・38 は、3 色で長さ 12、青赤で長さ 19 までの全列で成り立った。予想 22 は論文の長さ 15 を、青赤の列に限って 19 まで延ばした。
3. 予想 39 は b = c の 1,107 組すべてで外れた。b = c だと主張されたゲームが数 b に潰れるので、数の一意性（定理 16）と両立しない。b > c なら 3,911 組すべてで成立した。
4. 定理 32（原子量）は、all-small でないゲームへの原子量の拡張が論文でスケッチだけなので、再計算していない。

参考文献:

• A. Fink, R. J. Nowakowski, A. N. Siegel, D. Wolfe, Toppling Conjectures, Games of No Chance 4, MSRI Publications 63 (2015), 65–76
• M. H. Albert, R. J. Nowakowski, D. Wolfe, Lessons in Play, A K Peters, 2007
• E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for your Mathematical Plays, 2nd ed., A K Peters, 2001
• A. N. Siegel, Combinatorial Game Theory, Graduate Studies in Mathematics 146, AMS, 2013

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