Snort（グラフを塗るゲーム）の温度を厳密に計算した — 論文 3 本を TeX から検算し、証明の中の写し間違いを 1 つ見つけ、「温度は次数以下」の最小の反例を全列挙で特定した

Snort（スノート）をブラウザに実装した。Simon Norton が考えた、グラフの頂点を塗るゲームだ。手番で青（Left）と赤（Right）が交互に頂点を 1 つ塗る。ただし相手の色の頂点の隣は塗れない。塗れなくなった人の負け。1 手で隣の頂点を自分専用に「予約」できるので、手を急ぐ価値が大きい。その急ぎ具合を測る数が組合せゲーム理論の温度だ。デモはどの局面でも標準形の値、サーモグラフ、温度を厳密に出し、合法手すべてに勝ち手 ✓／負け手 ✗ を付ける。論文 3 本を arXiv の TeX から読み込んで検算した。(1) Huntemann–Maciosowski（2024）の表 1、定理 3.7、証明の場合分けに出てくる値をすべて照合した。証明中の 1 か所だけ、選択肢の値が 1 ずれていた（結論には影響しない）。(2) Huntemann–Nowakowski–dos Santos（2021）のパスの温度表は 45 マスすべて一致した。TeX にコメントアウトで残っていた 2 列（8 マス）も一致した。(3)「温度は盤の最大次数以下」という予想の最小の反例は、連結グラフ全列挙で 7 頂点（2 個、t − deg = 1/4）、木では 8 頂点の二重星（t = 9/2、次数 4）だった。二重星 S(k,k) は t = 3k/2 なので、t − deg は k とともにいくらでも大きくなる。木 14 頂点・連結グラフ 9 頂点（261,080 個）までに、2024 年の予想 t ≤ deg + deg₂/2 の反例はなかった。テスト 19 件。ソルバー内蔵パズル第 103 弾。

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

ルール

• 盤は任意のグラフ。青（Left）と赤（Right）が交互に、まだ塗られていない頂点を 1 つ自分の色で塗る。
• 相手の色の頂点に隣接する頂点は塗れない。自分の色の隣なら塗ってよい。
• 塗れなくなった人の負け（正規形）。

名前の由来は考案者の Simon Norton。格子盤では「Cats and Dogs」の名前でも遊ばれていて、ポルトガルでは小学生の全国大会の種目になっているそうだ。

デモでは盤をプリセットから選ぶ。手番の人が塗れる頂点に ✓ か ✗ が付く。コンピュータは勝ち手があれば必ず指す。勝ち手がなければ、合法手から無作為に選ぶ。右のパネルには局面の値、温度、平均、サーモグラフ、成分ごとの値が出る。

塗られた頂点は「色付け（tint）」に置き換える

Snort の局面は、塗られた頂点そのものより「誰がどこに塗れるか」で決まる。青が頂点 v を塗ると、v はもう誰も使わない。v の隣の未塗りの頂点は、青しか塗れない頂点になる。そこで v を盤から消し、隣の頂点に青の印（tint）を付ける。

• 青と赤の両方の印が付いた頂点は誰も塗れないので消す。
• 同じ色の印が付いた 2 頂点を結ぶ辺は消してよい（Winning Ways にある観察）。どちらを塗っても、相手側に付く印はもともと付いている色だからだ。

これで局面は小さなグラフに分かれていく。分かれた成分の和が局面の値になる。デモの右下の表がその成分だ。

// 青が v を塗った後: v を消し、隣に青の印。両色の印が付いた頂点は消す
export function play(p: Position, v: number, side: Tint): Position {
  const tint = p.tint.slice() as number[];
  for (const u of p.adj[v]) tint[u] |= side;
  const keep: number[] = [];
  for (let u = 0; u < p.tint.length; u++) if (u !== v && tint[u] !== 3) keep.push(u);
  return induced(p.adj, tint, keep); // 同じ色の印どうしの辺はここで落とす
}

成分ごとに値を 1 回だけ計算してメモ化する。木の成分は、中心を根にした AHU 符号（各頂点の印も含む）をキーにする。これなら同型な木は 1 回で済む。木でない成分は、ラベル付きの構造そのものをキーにする。値は #375 以来の部分ゲームエンジン（標準形を intern して id で比較する）で求める。温度は #376 で書いたサーモグラフ（区間ごとに線形な左右の壁）から読む。

エンジンを信用しないための検査も入れた。plainOutcome は値も成分分割も辺の削除も使わない素朴な勝ち負け探索だ。値から読んだ勝敗とこの探索の結果を、木 10 頂点までの 201 個と連結グラフ 7 頂点までの 996 個で突き合わせた。食い違いは 0 だった。

温度とは

組合せゲームの値 G = {G^L | G^R} では、左が先に指したときの到達点（左ストップ）と右が先のときの到達点（右ストップ）がずれることがある。そのずれを「手番を取るのに払う税 t」で冷やしていき、両者が一致する t が温度だ。サーモグラフは、横軸に値（正が左）、縦軸に t を取り、左右の壁が出会うところから垂直なマストが立つ図になる。

例えば星 K_{1,n}（中心 1 個と葉 n 枚）は ±n = {n | −n} で、温度は n だ。中心を塗れば葉を n 枚とも予約できるからだ。そこで「Snort の温度は盤の最大次数以下だろう」という予想が立った。Huntemann–Nowakowski–dos Santos（2021）の予想 30 である。

論文 1: Huntemann–Maciosowski（2024）を TeX から照合する

"Degrees are useless in Snort when measuring temperature"（arXiv:2406.02107）は、この予想を大きく破る族を作った論文だ。毛虫グラフ C(n+1, n, n+1) を使う。3 頂点のパス a − b − c の a と c に n+1 枚、b に n 枚の葉を付けたもので、温度は 2n + 1、次数は n + 2 になる。

照合は、論文の TeX ソース（arXiv の e-print）から表の行をそのまま正規表現で抜いて行った。\pm \{3*, \{\{5 \mid 4\} \mid *\}\} のような記法をパーサで標準形のゲームにし、エンジンの値と id で比較する。文字列比較ではない。

項目	範囲	結果
表 1（標準形・温度・次数・差）	n = 1…8 の 8 行	全行一致
定理 3.7 の標準形 ±{2n+1+s(n), {{3n+2 | 2n+2+s(n−1)} | s(n)}}	n = 1…20	全部一致
系：t = 2n+1、deg = n+2、deg₂ = 2n+2	n = 1…20	全部一致
補題 3.2（印付きの中心をもつ星）、3.3（K_{1,n} = ±n）、3.5（印の違う星 2 つ）	n ≤ 16〜30	全部一致
観察 3.4（同じ色の印どうしの辺は消せる）	n ≤ 4	素朴探索で一致
図 2 の 14 頂点の木（TikZ の \node ... edge から読む）	1 個	t = 11/2、次数 4、差 3/2 で一致

観察 3.4 だけは、エンジン自身がこの辺を落としているので、エンジンでは判定できない。そこで「G − H が後手必勝か」を素朴探索で決めた。差のゲームは、印を「塗られた葉を 1 本ぶら下げる」ことで実現し、H の色を反転して G と並べる。値を一切使わない判定になる。

証明の場合分けを 1 つずつ

定理 3.7 の証明では、左の手を 4 通りに場合分けし、各分岐の局面の値を書き下している。これを n = 1…12 で全部計算した。

• 場合 1（b を塗る）→ 2n + 1 + s(n)：一致
• 場合 2（a を塗る）の後の左の各手・右の各手の値、どれが支配されるか：一致
  • 論文が「メモはあるが書くと大変」とコメントアウトしている箇所（b の葉を塗る手は c を塗る手に支配される）も、差のゲームで確かめて成り立った
• 場合 3、場合 4 の値：一致

食い違いは 1 か所だった。場合 2 で、左が a を塗った後に右が c の葉を塗る手の値を、論文は

±(n + s(n)) + (n + 1) = {2n + s(n) | 1 + s(n)}

と書いている。しかし ±x + c = {x + c | c − x} なので、左辺を展開すると {2n + 1 + s(n) | 1 + s(n)} になる。エンジンの値もこちらで、n = 1…12 のすべてで後者と一致し、印刷された形とは一致しなかった。式の左辺は合っていて、右辺の展開で 1 を落とした写し間違いだろう。どちらの形でもこの手は右にとって c を塗る手より良くないので、定理の結論は変わらない。

論文 2: パスの温度表（2021）と、コメントアウトされた 2 列

"Bounding game temperature using confusion intervals"（Huntemann–Nowakowski–dos Santos、TCS 855、arXiv:1908.08471）の Snort の節には、パス P_n と、端に駒が置かれたパスの温度表がある。CGSuite で計算されたものだ。

• P_n：n 頂点のパス
• LP_{n−1}：n マスの左端に青の駒（残りは片端に青の印が付いた n − 1 頂点のパス）
• LP_{n−2}L、LP_{n−2}R：両端に駒

TeX を読むと、表の n = 13, 14 の列が % でコメントアウトされて残っていた。印刷版にはない 2 列だ。

	結果
印刷された表（n ≤ 12）	45 / 45 マス一致
コメントアウトされた列（n = 13, 14）	8 / 8 マス一致
2 × n 格子の温度（n = 2…7：−1, 9/4, −1, 5/2, −1, 1）	6 / 6 一致
命題：全頂点に隣接する頂点があれば ±n	8 頂点以下の連結グラフでこれに当たる 1,252 個すべてで一致

この論文は「パス上の Snort の温度は 2 を超えない」とも予想している（証明できたのは 7½ まで）。パス上の局面は、端に印が付いたパスの和にしかならない。そこで、両端の印の組（なし・なし、青・なし、青・青、青・赤。残りは色の反転）ごとに 20 頂点までの 80 本の温度を全部計算した。最大は 2 で、P3 で初めて現れた。予想に反する例はない。

「温度 ≤ 次数」の最小の反例

予想 30 は 2024 年の論文で破られた。ではいちばん小さい反例は何頂点か。全列挙で調べた。

木は葉を 1 枚ずつ付け足して作り、AHU 符号で同型を除く。連結グラフは頂点を 1 つずつ足して作り、次数で細分した頂点の分割の中で順列を全部試して、隣接行列の辞書順最小を同型の判定に使う。数は OEIS A000055（木）・A001349（連結グラフ）と一致する（9 頂点で 261,080 個）。

	頂点数	t > deg の個数	最大の t − deg
連結グラフ	≤ 6	0	0
連結グラフ	7	2	1/4
連結グラフ	8	24	1/2
連結グラフ	9	159	1/2
木	≤ 7	0	0
木	8	1	1/2
木	14	140	2

最小の反例は 7 頂点だった。4 頂点の閉路の 1 つの角に、葉を 2 枚持つ頂点がつながったグラフで、t = 13/4、次数 3。値は {{5 | {2 | 1}} | {{−1 | −2} | −5}}。デモのプリセットに入れてある。

木の最小は 8 頂点で、これは二重星 S(3,3)（辺で結んだ 2 つの中心に葉を 3 枚ずつ）だった。値は {{6 | 3} | {−3 | −6}}、t = 9/2、次数 4。

二重星は t = 3k/2

二重星 S(k,k) の値は ±{2k | k + s(k+1)} になる。ここで s(m) は m が偶数なら 0、奇数なら * だ。理由は短い。

• 左が中心 a を塗ると、a の葉 k 枚に青の印が付く（値 k）。もう一方の中心 b にも青の印が付き、b は「中心に青の印が付いた星」になる。2024 年の論文の補題 3.2 から、その値は {k | s(k+1)}。合わせて {2k | k + s(k+1)}。
• 葉を塗る手はこれに支配される。

外側の温度は 3k/2、次数は k + 1 なので、t − deg = k/2 − 1 はいくらでも大きくなる。k = 30（62 頂点）まで式どおりだった。論文の毛虫は t/deg → 2 で、二重星は 3/2 止まりだ。そのかわり二重星は手で 3 行で確かめられる。

論文は第 3 の問いとして「正の 2 進有理数 d を与えたとき、t − deg = d の盤を見つけよ」と書いている。木で各 d が最初に現れる頂点数を数えた。

t − deg	最初に現れる木の頂点数
1/16	13
1/8	11
1/4	10
1/2	8
3/4	13
1	10
3/2	12

14 頂点で 3/8 と 2 が加わる。

2024 年の予想 t ≤ deg + deg₂/2

2024 年の論文は、代わりの上界として t(G) ≤ deg(G) + deg₂(G)/2 を予想している（deg₂ は距離ちょうど 2 の頂点の数の最大）。木 14 頂点まで（計 5,447 個）と連結グラフ 9 頂点まで（計 273,193 個）のすべてで成り立った。等号は完全グラフや星で成り立つ（t = deg、deg₂ = 0）。Siegel が出した「t/deg は有界か」という問いについては、14 頂点までの木の最大が 7/5 で、論文の毛虫 C(4,3,4) がそれに当たる。

後手必勝の木

副産物として、空の木の盤で後手が勝つ（値 0）ものは珍しかった。14 頂点までで 12 頂点に 1 個、14 頂点に 4 個しかない（13 頂点は 0 個）。最小の 12 頂点の木はデモに入れてある。値 0 であることは素朴探索でも確かめた。連結グラフでは C4 をはじめ、9 頂点までに 440 個ある。

論文 3: 三角格子（2024）

Gauthier–Huntemann "Snort played on triangular grids"（arXiv:2412.00849）は、三角形が 1 段・2 段並んだ三角格子 T_{n,2}、T_{n,3} が先手必勝だと証明している。値を計算して確かめると、T_{n,2} は n ≤ 16、T_{n,3} は n ≤ 8 ですべて先手必勝（N）だった。論文が今後の課題に挙げた盤も計算した。T_{n,4} は n ≤ 6、論文が「予備的には先手必勝らしい」と書いている菱形 T_{n,n} は n ≤ 4 で、どれも先手必勝だった。T_{5,5}（25 頂点）は 20 分で終わらなかったので打ち切った。小さい盤（T2,2・T3,2・T4,2・T2,3・T3,3）は素朴探索でも先手必勝を確認した。

実装メモ

• src/snort.ts：ルール、印への置き換え、成分分割、木の AHU キー、Valuer、値を使わない plainOutcome、盤の生成（パス・閉路・星・毛虫・三角格子・格子）。
• src/cgt.ts・src/thermo.ts・src/notation.ts：部分ゲームの標準形、サーモグラフ、論文記法のパーサ（#377・#376 から流用）。
• tools/verify.mts：3 本の論文を arXiv の e-print から取得して表と図を読み、全項目を照合する。結果は runs/literature.json。
• tools/sweep.mts・tools/graphs.mts：木と連結グラフの全列挙と温度。tools/extremes.mts：最小の例と二重星。tools/report.mts が README の表を runs/ から作るので、表の数字は手で書き写していない。
• デモは依存ゼロの TypeScript + Vite。計算は Web Worker で行い、成分の表はセッション中ずっと使い回す。

まとめ

• Snort は、塗った頂点を消して隣に印を付けると、小さなグラフの和に分かれる。成分ごとに標準形を求め、サーモグラフから温度を読める。
• 2024 年の論文の表 1・定理 3.7・証明の各分岐は、1 か所を除いて一致した。その 1 か所（右が c の葉を塗る手）は展開での写し間違いで、正しくは {2n + 1 + s(n) | 1 + s(n)}。結論には影響しない。
• 2021 年の論文のパスの温度表は、TeX にコメントアウトで残った 2 列を含めて 53 マスすべて一致した。パスの温度は 20 頂点まで 2 を超えなかった。
• 「温度 ≤ 次数」の最小の反例は、連結グラフで 7 頂点、木で 8 頂点（二重星）。二重星だけで t − deg はいくらでも大きくできる。