Col（コル。John Conway の地図塗りゲーム）と、その有向版 Myopic Col をブラウザに実装した。青（Left）と赤（Right）が交互に頂点を 1 つ塗り、自分と同じ色の隣は塗れない。塗れなくなった人の負け。Myopic Col は Bovee・Burke・Tennenhouse の論文「Games from Basic Data Structures」（arXiv:1605.06327、2016）で導入されたゲームで、盤は有向グラフ（連結リストや二分木）、頂点は矢印の先だけを見る。二分木なら、ノードは子の色に縛られるが親の色には縛られない。論文はリスト上の値を補題で決め、二分木について「根と 2 つの子が未着色なら G(T) = * + G(T₁) + G(T₂)」という予想を残している。組合せゲーム理論の厳密なエンジンを書いて、補題と系をすべての着色で確かめ、予想を **11 ノード以下のすべての二分木・すべての着色（3,147 万局面、予想の対象 188 万件）で調べた。例外は 0 件。さらに、予想は特別な場合で、「誰にも見られていない未着色の頂点は、見ている先がすべて未着色なら、独立な * として切り離せる」**が、子が 1 個でも 3 個以上でも、木でない有向グラフでも、測った範囲で例外 0 件だった（証明はしていない）。値はすべて「数」か「数 + *」（cold）で、二分木では分母が 4 を超えない。一方 Col は 8 頂点で ±3/16 まで出る。テスト 14 件。ソルバー内蔵パズル第 105 弾。
デモ: https://sen.ltd/portfolio/col-game/
リポジトリ: https://github.com/sen-ltd/col-game
ルール
- 盤はグラフ。青（Left）と赤（Right）が交互に、未着色の頂点を 1 つ自分の色で塗る。
- Col：塗ろうとする頂点の隣に自分の色があるなら塗れない。相手の色の隣は塗ってよい。
- Myopic Col：盤は有向グラフ。頂点 u は、u から出る矢印の先に自分の色があると塗れない。矢印の根元側（u を指している頂点）の色は関係ない。
- 塗れなくなった人の負け（正規形）。
Col は Conway の『On Numbers and Games』（ONAG）に出てくる古典で、Winning Ways でも Snort と並んで最初の方に登場する。Snort は「相手の色の隣は塗れない」で、Col とちょうど逆だ（Snort は前回の #386 で実装した）。逆にしただけで性格がまるで変わる。Snort では先に塗ると隣を自分専用に確保できるので急ぐ価値がある（熱い）。Col では塗ると隣を自分が使えなくなるので、どの手も自分の首を絞める。その結果、Conway が示したとおり Col のどの局面の値も「数 x」か「x + *」になる（cold）。
Myopic Col は、データ構造の授業で習う構造（配列・スタック・キュー・リスト・二分木）の上にゲームを作ろうという論文の中で、連結リストと二分木のために作られた。リストのノードは次のノードへの参照を持つが、前のノードは知らない。その「片側しか見えない」を Col に持ち込んだのが Myopic（近視の）Col だ。
1 つの構造で 2 つのゲームを扱う
実装では、各頂点 u に「u が見ている頂点のリスト look[u]」を持たせる。u は、look[u] のどれかがすでに持っている色を取れない。
- Col：look[u] は u の隣接頂点すべて（無向グラフを両向きの矢印として持つ）
- Myopic Col：look[u] は u から出る矢印の先
塗られた頂点そのものはゲームから消え、「その頂点を見ている頂点」からその色が奪われる。そこで局面は、着色を覚える代わりに次の形に縮める。
- 各頂点にまだ使える色の集合（青だけ・赤だけ・両方）を持たせる。どちらも使えない頂点は消す。
- 矢印 u → w は、u と w に共通して使える色がなくなったら捨ててよい。w に何を塗っても、u から奪われるのは u がもう使えない色だけだからだ。
- 残りは（弱）連結成分に分かれ、局面の値は成分の値の和になる。成分は一度ずつ値を求めて標準形（canonical form）に縮め、メモする。無向の木は中心からの AHU コード、有向の木（根から子へ矢印が出ている木）は根からのコードで同型をまとめる。
Snort の実装を流用しようとして最初に引っかかったのが、矢印を捨てる条件だ。Snort では「同じ色に染まった 2 頂点の間の辺」は捨ててよかった（片方に塗っても、もう片方を同じ色に染め直すだけ）。Col ではそれが捨てられない。赤しか使えない頂点 2 つが隣り合っているとき、赤が片方を塗るともう片方は赤も使えなくなって死ぬ。だから値は −2 ではなく −1 だ。Col で捨ててよいのは逆に「使える色が重ならない」2 頂点の間の辺だ。
エンジンの検算として、値も成分分割も矢印の削除も使わない素朴な勝敗探索と突き合わせた。6 頂点以下の連結グラフの Col 全 18,037 局面、4 頂点以下のすべての有向グラフ（2 頂点の組ごとに「矢印なし・→・←・両方」）の Myopic Col 全 333,540 局面で、勝敗はすべて一致した。
論文のリストの結果：印刷どおり成立
論文の補題はこうだ。n 個の未着色ノードが並んだリスト（矢印は先頭から末尾へ）は
- 末尾の後ろに何もない：n·*（n 個の * の和。n が奇数なら *、偶数なら 0）
- 末尾の後ろに青のノード：(n−1)·* − 1
- 末尾の後ろに赤のノード：(n−1)·* + 1
証明の要点は「先頭を塗るのが常に最善」で、どの手も先頭以外は劣ることを帰納法で示している。系として、リストの集まりの値は a·* + b − c になる。a は「矢印の先が未着色（または矢印がない）」未着色ノードの数、b は「矢印の先が赤」の未着色ノードの数、c は「矢印の先が青」の数だ。
- 補題：n ≤ 400 で 3 通りとも成立
- 系：13 ノード以下のリストのすべての着色 2,391,483 局面、2〜4 本のリストからなる 9 ノード以下の森のすべての着色 2,336,130 局面で成立
有向グラフのどんな着色も実際のプレイで作れることにも注意しておく。塗られた部分をトポロジカル順（矢印の先から順）に塗れば、塗る瞬間には矢印の先はまだ空いている。なので「すべての着色」で調べるのは、「到達可能なすべての局面」で調べるのと同じだ（Col では同じ色の隣接は作れないので、それを除いた着色だけを数えている）。
二分木の予想：11 ノードまで例外なし
論文は二分木では値が整数や整数 + * に限らず、1/2 や −3/4 のような二進分数も出ると述べたうえで、次の予想を立てている。
根 r が未着色で、r の 2 つの子の部分木 T₁, T₂ がどちらも空でなく根が未着色なら、G(T₀) = * + G(T₁) + G(T₂)。
つまり「根は、他と独立な * 1 個分として切り離せる」という主張だ。リストの補題で「先頭が * として剥がれる」のと同じ形をしている。
二分木（子の順序を区別しない。各ノードの子は 0〜2 個）を全列挙し（個数は OEIS A001190 の 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451 と一致）、根を未着色にしたすべての着色で値を求めた。
| ノード数 | 木の数 | 局面 | 予想の対象 | 例外 |
|---|---|---|---|---|
| 3 | 2 | 18 | 1 | 0 |
| 5 | 6 | 486 | 27 | 0 |
| 7 | 23 | 16,767 | 972 | 0 |
| 9 | 98 | 642,978 | 37,908 | 0 |
| 10 | 207 | 4,074,381 | 238,383 | 0 |
| 11 | 451 | 26,631,099 | 1,600,884 | 0 |
| 計（1〜11） | 31,469,089 | 1,883,902 | 0 |
11 ノードまでで予想の例外は 0 件。計算は 11 ノードまで全部で約 3 分（node 1 プロセス）。
論文が言及した 1/2 と −3/4 の最小例
- −1/2（3 ノード）：根と葉 2 枚、片方の葉が青。根は青い子を見ているので赤しか塗れない。青にできるのはもう一方の葉だけで、塗ると根は赤専用のまま残り −1。赤は根を塗ると葉が残って *、もう一方の葉を塗ると根の赤も奪われて根が死に 0。よって {−1 | 0, *}。赤の選択肢 * は青の応手 0 で −1/2 以上に戻される（reversible）ので消え、{−1 | 0} = −1/2。
- −3/4（5 ノード）：根の子の 1 つが青い葉、もう 1 つの子が葉 2 枚を持つ。
- **1/4（7 ノード）**もデモのプリセットに入れた。
11 ノード以下の二分木の局面に現れる値は 66 種類で、分母は最大 4（1/2・1/4・3/4 …）だった。1/8 は一度も出ない。比べると、無向の Col は 8 頂点の連結グラフで ±3/16 まで出る。木で矢印が子の方向にしか向かない制約が、値の細かさを抑えているように見える（理由は調べていない）。
予想はもっと広い規則の特別な場合だった
予想の主張を「根が * として切り離せる」と読むと、二分木である必要も子が 2 つである必要もなさそうに見える。そこで条件を 1 つずつ外して測った。
子の数を変える
任意の個数の子を持つ根付き木（OEIS A000081）の 10 ノード以下、根を未着色にしたすべての着色（計 1,632 万局面）で、根の子がすべて未着色の場合に G = * + Σ G(子の部分木) を調べた。
| 根の子の数 | 対象 | 例外 |
|---|---|---|
| 1（リストの補題を一般の木に広げたもの） | 2,168,662 | 0 |
| 2（論文の予想） | 603,157 | 0 |
| 3 以上 | 112,615 | 0 |
木でなくする
木であることをやめて、一般の有向グラフで次を調べた。
頂点 r が未着色で、r を見ている頂点が（まだ盤に残っている中に）1 つもなく、r が見ている頂点がすべて未着色なら、G = * + G(r を取り除いた盤)。
- 4 頂点以下のすべての有向グラフ・すべての着色（全数）：対象 23,430 件、例外 0
- 8 頂点のランダムな有向グラフ 20 万個（2 頂点の組ごとに矢印なし .55・→ .2・← .2・両方 .05、各頂点は未着色 1/2・青 1/4・赤 1/4）：対象 67,481 件、例外 0
子同士が同じ孫を共有していても、r と関係ない場所に閉路があっても成り立つ。誰かが r を見ていると壊れる。同じ 4 頂点以下の全数で、r を見ている頂点がある場合は 52,686 件中 34,960 件で式が外れた。最小の例は 3 頂点の 0 → 1, 0 → 2, 1 → 0（頂点 0 と 1 が互いに見ている）で、値は 0、式は * + * + * = * になる。デモの「watched」プリセットがこれだ。
直感としては、誰にも見られていない頂点を塗っても誰の邪魔もしないので、その頂点は「いつでも 1 手パスできる場所」として盤の残りから独立している。r が見ている先が塗られると r の色が 1 つ奪われて * が ±1 に変わってしまうが、自分の色を奪うのは自分の手だけ（Col は自分の色の隣が塗れないゲーム）なので、それは塗った側にとって損になる。そのため相手はそれを当てにしなくてよい、という形の議論で証明できそうに見える。ただしここで示せたのは計算での確認だけで、証明はしていない。
論文の未解決問題「二分木上の Myopic Col の計算量は？」にもこの規則は効く。根と子が未着色の間は根を * として剥がし続けられるので、着色のない木は値がノード数・* で決まる。ただ、子の 1 つが塗られて根が片方の色しか使えなくなると、この規則は使えない。なので、これだけでは計算量の問題は解けない。
Col は cold（Conway の定理）
ONAG の定理「Col の値はすべて x か x + *」を、8 頂点以下のすべての連結グラフ（OEIS A001349 と同じ 1, 1, 2, 6, 21, 112, 853, 11,117 個）のすべての着色（同じ色の隣接を除く）、計 6,172,661 局面で確かめた。例外 0、計算は約 43 秒。
空の盤だけで調べても、この定理はほとんど何も確かめられない。空の盤は青と赤を入れ替えても同じなので G = −G で、cold な値で自分の符号反転と等しいのは 0 か * しかない。8 頂点の連結グラフ 11,117 個では、空の盤が 0（後手必勝）なのが 7,360 個、*（先手必勝）が 3,757 個だった。
Myopic Col についても、4 頂点以下のすべての有向グラフのすべての着色（333,540 局面）と、上の二分木の全局面で、cold でない値は 1 つも出なかった。論文は Myopic Col が cold かどうかには触れていない。
実装メモ
-
src/col.ts：look リストでの 2 ゲーム共通のルール、局面の縮約、成分分割、値（標準形のメモ化）、素朴な勝敗探索、論文の系の数え方、誰にも見られていない頂点を探すfreeSources。 -
src/cgt.ts：短いゲームの標準形（支配される選択肢の削除、reversible な選択肢のバイパス）。同じゲームは同じ id になるように intern する。#375 以来のエンジンをそのまま使っている。 -
tools/conjecture.mts（予想）、tools/variants.mts（子の数）、tools/sources.mts（一般の有向グラフ）、tools/cold.mts（cold）、tools/verify.mts（素朴探索との照合・補題・系）。tools/report.mtsがruns/の JSON から README の数字を集計するので、表の数字は手で書き写していない。 - 予想の検算で、最初は「根が
freeSourcesに含まれる」ことも一緒に確かめていて、テストが落ちた。根の 2 つの子がどちらも死んでいる（それぞれ青い子と赤い子を持つ）と、根を見る矢印も根から出る矢印もなくなり、根はただの孤立した * になる。式は成り立っているので、テストの方を直した。 - デモは依存ゼロの TypeScript + Vite。値の計算は Web Worker で、成分の表はセッション中ずっと使い回す。
まとめ
- Myopic Col（Bovee–Burke–Tennenhouse 2016）のリストの補題と系は、印刷どおり成立した（補題 n ≤ 400、系 473 万局面）。
- 二分木の予想 G(T) = * + G(T₁) + G(T₂) は、11 ノード以下の 3,147 万局面中の対象 188 万件で例外 0。
- 予想は「誰にも見られていない未着色の頂点は、見ている先が未着色なら独立な *」という規則の特別な場合で、子が 1 個でも 3 個以上でも、一般の有向グラフでも、測った範囲で例外 0。誰かに見られていると壊れる（最小 3 頂点）。証明はしていない。
- Col は 8 頂点以下の全局面で cold（Conway の定理どおり）。Myopic Col も測った範囲ではすべて cold で、二分木の値の分母は 4 止まり、Col は 8 頂点で 3/16 まで出る。