Sim（シム）をブラウザに実装した。6 個の点と、その間の 15 本の線。赤と青が交互に線を 1 本ずつ自分の色で塗り、自分の色だけで三角形を作った方が負け。ラムゼー数 R(3,3) = 6 なので引き分けはなく、完全にプレイすると後手が勝つ。コンピュータは全 1,350,022 局面をページを開いた瞬間に解き（約 0.5 秒）、ヒントを付けると全部の線に「勝ち・負け」と残り手数が付く。裏側では Wolfgang Slany の 1999 年の技術報告と、Weronika Wrzos-Kaminska の 2020 年の「人間でも覚えられる後手必勝法（3 つのルール）」を数字ごと確かめ直した。12 の主張のうち 10 は一致した。K18 の 57 桁の Pólya の数も、2×10⁵⁴ のモンテカルロ推定も合う。3 つのルールは全分岐で勝ち、どのルールを 1 つ外しても 2 手目で負ける。合わなかったのは 2 つで、Slany の「三角形を含まない 2,309 局面」は 2,250、Sim⁺ の「13,158」は再現できなかった。テスト 19 件。ソルバー内蔵パズル第 88 弾。
デモ: https://sen.ltd/portfolio/game-of-sim/
リポジトリ: https://github.com/sen-ltd/game-of-sim
ルール
Gustavus Simmons が 1969 年に発表した紙と鉛筆のゲーム。
- 正六角形の頂点に 6 個の点を打ち、全部の 2 点を線で結ぶ（完全グラフ K6、辺は 15 本）。
- 赤（先手）と青（後手）が交互に、まだ塗られていない線を 1 本選んで自分の色で塗る。
- 6 個の点のうち 3 個を頂点とする三角形の 3 辺を、全部自分の色で塗ってしまったら負け（線の交点は数えない）。
「6 人いれば、互いに知り合いの 3 人か、互いに知らない 3 人が必ずいる」という友人と他人の定理（R(3,3) = 6）があるので、15 本全部を 2 色で塗ると必ずどちらかの色の三角形ができる。だから引き分けはない。
1974 年に Mead・Rosa・Huang がコンピュータ探索で後手必勝を示した。1999 年に Wolfgang Slany が「Graph Ramsey games」という技術報告で Sim の局面数を数え、さらに大きな版（K18 の上で 4 頂点の完全グラフ K4 を避けるゲーム）の局面数を Pólya の数え上げとモンテカルロで見積もった。2020 年には Weronika Wrzos-Kaminska が、後手が覚えて使える 3 つのルールを 4 ページの論文で発表した。どちらも arXiv に TeX ソースがある。
今回の作業は 2 つ。
- 完全プレイヤーと対戦できるページを作る。
- 2 本の論文に書かれた数字と主張を、一つ残らず計算し直す。
ソルバー: 15 ビットのマスク 2 つと、3 進数の表
局面は「赤い線の集合」と「青い線の集合」の 2 つの 15 ビットのマスクで表せる。手番は本数で決まる（同数なら赤の番）。
各局面に、手番側から見た勝ち負けと、完全プレイで終局までの手数を 1 バイトで持たせる。表の添字は 3 進数で、線 e が赤なら 1、青なら 2 を e 桁目に置く。3¹⁵ ≈ 1,435 万バイト。赤マスクと青マスクから添字を出す計算は、マスクごとに「立っているビットの 3 のべき乗の和」を前計算しておけば pow3[red] + 2 * pow3[blue] の足し算 1 回で済む。
private solve(red: number, blue: number): number {
const idx = this.b.pow3[red] + 2 * this.b.pow3[blue];
if (this.table[idx]) return this.table[idx];
// 自分の三角形を閉じる手は「1 手で負け」。それ以外は子局面を再帰で
// 勝てる手があれば最短で勝ち、なければ最長で粘って負け
...
}
手数の付け方は「勝つ側は最短、負ける側は最長」。負けの手（三角形を閉じる手）もそれ自体 1 手と数える。深さ優先探索 1 回で、三角形のない到達可能局面 1,350,022 個が全部埋まる。Node で約 0.5 秒、ブラウザでも同じくらいで、ページを開くと毎回解き直している。
| 盤 | 局面 | 完全プレイの結果 |
|---|---|---|
| K3 | 13 | 引き分け |
| K4 | 247 | 引き分け |
| K5 | 11,793 | 引き分け |
| K6 | 1,350,022 | 後手勝ち（15 手目で決着） |
K5 までは 2 色で塗り切っても三角形のない塗り方（五角形とその星形）があるので、引き分けになりうる。実際に完全プレイでも引き分けになった。
K6 の空の盤の値は「赤の負け、15 手」。青は必ず勝てるが、赤は最後の 15 本目を塗らされるまで生き延びられる。Slany が報告の後半で「後手は 15 手目より前に勝ちを強制できない」と書いているのと一致する。青の最初の応手 14 通りはどれも勝ちで（14 手）、最初の 1 手はどうでもいい。
テストでは、この表を別に書いたソルバーと全局面で照合している。3 進数の表も対称性も使わず、文字列キーの Map に全局面を入れるだけの素朴なネガマックスで、1,350,022 局面すべての値と手数が一致する。
局面を同型で数える
局面数を論文と比べるには、点の番号の付け替え（6! = 720 通り）で移り合う局面を同じと見なして数える必要がある。
正規形は「720 通りの付け替えのうち、(赤マスク, 青マスク) が辞書順で最小になるもの」。付け替えごとに、マスクの下位 8 ビットと上位 7 ビットの写り先の表を作っておけば、1 回の付け替えは表引き 2 回と OR 1 回で済む。空の盤から 1 手ずつ、各段の代表元だけを持って進める。
| 手数 | 三角形なしの局面 | 同型類 | 終局した局面 | 同型類 |
|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 0 |
| 1 | 15 | 1 | 0 | 0 |
| 2 | 210 | 2 | 0 | 0 |
| 3 | 1,365 | 7 | 0 | 0 |
| 4 | 8,190 | 25 | 0 | 0 |
| 5 | 28,710 | 64 | 1,320 | 6 |
| 6 | 91,500 | 166 | 4,200 | 13 |
| 7 | 177,525 | 303 | 37,800 | 70 |
| 8 | 306,450 | 500 | 64,800 | 117 |
| 9 | 308,070 | 489 | 211,680 | 352 |
| 10 | 266,346 | 415 | 180,450 | 299 |
| 11 | 117,000 | 193 | 246,690 | 386 |
| 12 | 39,960 | 71 | 87,840 | 150 |
| 13 | 4,500 | 12 | 41,940 | 75 |
| 14 | 180 | 1 | 3,780 | 10 |
| 15 | 0 | 0 | 180 | 1 |
| 計 | 1,350,022 | 2,250 | 880,680 | 1,479 |
「終局した局面」は、直前の手で手番側が自分の三角形を閉じた局面。1 手目は 1 通り、2 手目は「隣り合う辺」か「離れた辺」の 2 通り、という Slany の観察もこの表の 1 行目と 2 行目そのままだ。
三角形なしの同型類 2,250 は、別の方法でも確かめた。Burnside の補題により、「付け替えで閉じた局面の集合の同型類の数」は「各局面を固定する付け替えの個数の合計 ÷ 720」に等しい。135 万局面 × 720 通りを 33 秒で回して、同じ 2,250 が出る。
Slany の 3,728 と 2,309
Slany の報告にはこうある。「単色の三角形を含む局面も含めた、同型でない合法な局面の数は 3,728。三角形を含む局面は保存しなくてよいので、2,309 まで減らせる」。
- 3,728 は一致する。2,250 + 1,479 = 3,729 から空の盤を除くと 3,728。
- 2,309 は合わない。三角形なしは空の盤を入れて 2,250、除いて 2,249。合計が同じなので、三角形ありの側は Slany では 3,728 − 2,309 = 1,419、こちらでは 1,479。60 類が線の反対側にいる。
ほかの数え方も試した。手番側に安全な手がなく三角形を閉じるしかない局面は 50 類。強制された手でしか到達しない終局は 28 類。1 手で 2 つの三角形を同時に閉じた終局は 240 類。どれも 60 にはならない。報告には定義がこれ以上書かれていないので、ここで止めた。
Pólya の数え上げ: 57 桁の数がそのまま出た
Slany は、K18 の上で K4 を避けるゲーム（R(4,4) = 18 に対応する、Sim の次の大きさ）の局面数を Pólya の数え上げで上から押さえている。脚注に、赤の本数が青と同じか 1 本多い部分彩色の同型類の数として、こう書いてある。
122817954504260150325481627994395745196940238595512818831
これを再現した。点の置換の巡回型（18 の分割、385 通り）ごとに、辺の上の巡回の長さを数える。長さ k の点の巡回 1 つの中の辺は、k が奇数なら長さ k の巡回 (k−1)/2 個、偶数なら長さ k の巡回 (k−2)/2 個と長さ k/2 の巡回 1 個。長さ i と j の 2 つの点の巡回にまたがる辺は、長さ lcm(i, j) の巡回が gcd(i, j) 個。辺の巡回 1 つは全部同じ色でないと置換で固定されないので、長さ l の巡回ごとに (1 + xˡ + yˡ) を掛ける。これを巡回型の置換の個数で重み付けして足し、18! で割る。
for (const l of edgeCycles(m)) {
// (1 + x^l + y^l) をその場で掛ける。降順に回せば参照先はまだ古い値
for (let r = top; r >= 0; r--)
for (let g = Math.min(top - r, E - r); g >= 0; g--)
P[r * W + g] += (r >= l ? P[(r - l) * W + g] : 0n) + (g >= l ? P[r * W + g - l] : 0n);
}
2 変数多項式（赤 r 本・青 g 本、r + g ≤ 153）を丸ごと BigInt で持つ。K18 で 4.4 秒。
- 脚注の 57 桁: 完全一致。
- 本文の「(77, 76) 彩色の同型類は 114722035311851620271616102401 個」: 完全一致。
- 全彩色の合計は OEIS A004102（符号付きグラフの数）の n = 18 の項と一致。K3〜K6 の 10, 66, 792, 25506 も同じ列の値で、K5 は総当たりの Burnside（3¹⁰ 彩色 × 120 置換）とも合う。
モンテカルロ: 2×10⁵⁴ も合う
Pólya の数は三角形（ここでは K4）を含む彩色も数えているので、上限でしかない。Slany は合法な局面（どちらの色にも K4 がない）の数をモンテカルロで約 2×10⁵⁴ と見積もった。2 つの方法のうち「方法 2」は、各 (r, g) について「Pólya の同型類の数 × 無作為な (r, g) 彩色のうち単色 K4 を含まないものの割合」を足すものだ。
同じことをした。(r, g) = (⌈t/2⌉, ⌊t/2⌋) の各クラスで、Fisher–Yates で無作為な彩色を 100 万個作り、色ごとに隣接ビットマスクで K4 を探す。246 秒。
- 推定値は 1.959×10⁵⁴、99% 区間は ±0.007×10⁵⁴。Slany の区間 [1.7, 2.7]×10⁵⁴（方法 1）と [0.19, 5.0]×10⁵⁴（方法 2）のどちらにも入る。
- 質量のピークは 95 本前後。120 本以降は 100 万個中 1 個も K4 なしが出ない。辺を 1 本足すと K4 なしの割合は増えない（足した彩色から 1 本抜くと、1 本少ない一様な彩色になる）ので、それ以降のクラス全部を合わせても寄与は 99% で 3.4×10⁴⁷ 以下。
なお Slany は「上限の 50 分の 1」と書いているが、自分の 2×10⁵⁴ で割っても 1.23×10⁵⁶ / 2×10⁵⁴ ≈ 61 なので、ここは大まかな言い方だろう。
Sim⁺ の 13,158
Slany は 1 手で何本でも塗れる変種 Sim⁺ も解いていて、「有向非巡回グラフは 13,158 エントリで、Sim の 5 倍以上」と書いている。こちらは再現できなかった。
- 両色とも三角形のない彩色の同型類（本数は自由）: 6,617
- 赤が先手のときに到達できる（彩色, 手番）: 13,122（赤の番なら両色とも 1 本以上か空の盤、青の番なら赤が 1 本以上）
- どちらの手番も許した場合: 13,234
どれも近いが一致しない。報告に定義がないので、どれが Slany の数え方なのかは決められない。Sim⁺ の勝敗（後手勝ち）そのものは今回は確かめていない。
2020 年の 3 つのルール
Wrzos-Kaminska の戦略はこうだ。青の番が来たら:
- ミニボード M を決める。塗られた線を全部含み、青が安全に塗れる線（自分の三角形を閉じない線）を少なくとも 1 本含む完全部分グラフのうち、包含について極小のもの。
- ルール 1: M の上の、青が安全に塗れる線だけを考える。
- ルール 2: その中で、「M の上で青が同時に安全に塗れる線の集合のうち最大のもの」に一番多く含まれる線を残す。
- ルール 3: さらに同点なら、「赤が同時に安全に塗れる線の最大集合」に一番多く含まれる線を残す。
- 残った線のどれを塗ってもよい。
論文は 4 ページで、「網羅的な計算機探索でこの戦略が青の勝ちであることを確かめた」とだけ書いてある。表もコードもない。だから全部書いた。
- ミニボードは 2⁶ 通りの頂点集合を総当たりして、条件を満たす極小なものを全部列挙する（「同型を除いて一意」という注記を仮定せずに確かめるため）。
- 最大の安全集合は、M の上の未着色の線の部分集合を枝刈り付きで列挙して、最大サイズと、線ごとに何個の最大集合に入っているかを数える。
- 検証は、赤は何を塗ってもよく、青はルールが残した線のどれを塗ってもよく、ミニボードもどれを選んでもよい、という木を最後まで全部たどる。
論文の図 1・図 2 は同じ局面（赤 14, 24, 34、青 12, 23）で、TeX ソースに付いている PNG を見て書き起こした。テストで図の主張を確かめている。{1,2,3,4} の K4 は、残る線 13 が青の三角形 1-2-3 を閉じるのでミニボードではなく、ミニボードは {1,2,3,4,5} と {1,2,3,4,6} の 2 つ。{35, 45} は青には安全だが赤には安全でない。M の上の青の最大安全集合は {15, 35, 45} ただ 1 つ。TeX ソースには \todo{Fix this caption} が無効化されたまま残っているが、キャプションの内容は正しかった。
結果:
| 版 | 戦略が手を指す局面（同型類） | 負ける手を許す類 | 最初の破綻 |
|---|---|---|---|
| ルール 1・2・3、ミニボード上 | 304 | 0 | — |
| ルール 1・2（3 なし） | 775 | 385 | 赤 14, 23／青 15 で 12 と 13 を許す。どちらも負け |
| ルール 1・3（2 なし） | 637 | 225 | 赤 12, 13／青 23 で残る 6 本が全部負け |
| ルール 1 だけ | 1,026 | 809 | 赤 12, 13／青 23 |
| ルール 1・2・3、K6 全体 | 588 | 102 | 赤 12, 13／青 23 で 45, 46, 56 を選ぶ。全部負け |
- 3 つのルールは全分岐で勝つ。最長の試合は 15 手。
- 「全ルールを適用しても複数の手が残るなら、どれでも勝てる」という論文の主張も正しい。複数残る類が 133 あり、その中に負ける手は 1 本もない。
- ミニボードが 2 つ以上ある類は 2 つで、どちらも局面の対称性で移り合う（「同型を除いて一意」の通り）。
- 304 類のうち、ルール 1 だけで 1 手に決まるのが 6、ルール 2 で決まるのが 82、ルール 3 で決まるのが 83、それでも複数残るのが 133。
そして、どのルールを外しても青の 2 手目で負けうる。どの版でも、最初の破綻局面で負ける手を選ぶと赤が 10 手で勝つ。いちばん分かりやすいのは「赤 12, 13／青 23」の局面だ。赤が頂点 1 から 2 本伸ばして、青の線 23 を挟んでいる。正解は頂点 1 から出る 14, 15, 16。頂点 2 か 3 から新しい点へ出る 6 本は全部負けで、新しい点どうしを結ぶ 45, 46, 56 も全部負け。ルール 2 を外すと前者の 6 本しか残らず、ミニボードをやめて K6 全体でルールを回すと後者の 3 本しか残らない。
デモでは、コンピュータの青を「2020 three rules」にすると、右上のパネルに毎手のミニボードと、各ルールのあとに残った線（下付きの数字は、その線が入っている最大集合の個数）が出る。
罠を張る先手
完全な青には赤は必ず負ける。では、青が人間で、ときどき間違えるならどうか。Slany は先手のコンピュータに「次に青が間違えられる手の数が一番多くなる手」を選ばせる発見的手法を書いている。
青を「自分の三角形を閉じない線の中から一様に無作為に選ぶ」モデルにして、赤の勝率を厳密に計算した（赤は勝ちの局面に入ったらそこからは完全にプレイする）。
| 赤の選び方 | 赤の勝率 |
|---|---|
| 無作為（安全な線から一様） | 89.03% |
| Slany の発見的手法（間違えられる応手の数が最大） | 99.69% |
| 間違えられる応手の割合が最大 | 99.69% |
| 厳密な最善（期待値最大化） | 99.85% |
| 参考: 両者とも無作為 | 50.31% |
青の勝ちはそれほど細い。無作為な青は、安全な線を無作為に選ぶだけの赤（勝ちが見えたらそこから完全プレイ）にさえ 89% 負ける。Slany の 1 手先読みは最善との差が 0.16 ポイントしかない。デモのコンピュータの赤は最善の罠を張り、ステータス欄に「無作為な青がここから間違える確率」を出す。
デモの使い方
- 「you play」で赤（先手）か青（後手）を選ぶ。線をクリックすると塗れる。
- ヒントを付けると、未着色の線に「W5」（5 手で勝ち）「L9」（9 手で負け）が付く。三角形を閉じる線は「L1」。
- 「computer's Blue」で、コンピュータの青を完全プレイ（solver）か 2020 年のルールに切り替えられる。
- 誰かが三角形を閉じると、その三角形を白い破線で囲む。
テスト
19 件。主なもの:
- R(3,3) = 6: K6 の 2¹⁵ 通りの 2 色彩色は全部単色三角形を含み、K5 には含まない彩色がある。
- 素朴なネガマックスとの全局面照合（値と手数）、空の盤が「赤の負け 15 手」、K3〜K5 が引き分け。
- 同型類 2,250 / 1,479、3,728、K5 での Burnside との一致。
- Pólya: OEIS A004102 の K3〜K6、K5 の総当たり Burnside、K18 の 57 桁・30 桁・A004102(18)。
- 2020 年の論文の図 1・図 2 の主張、3 ルールの全分岐の勝ち、ルールを外した版の破綻の局面。
- 罠の勝率の大小関係と、ページ用のプレイヤーが最善値を再現すること。
- K4 判定（Turán グラフに K4 がないことなど）と、乱数の種での再現性。
まとめ
- Sim の局面は 15 ビットのマスク 2 つ。3 進数の 1 バイト表で 135 万局面を 0.5 秒で解ける。後手勝ちで、決着は必ず 15 手目。
- Slany（1999）の数字は大部分が合う。3,728（空の盤を除く）、Pólya の 57 桁と 30 桁、モンテカルロの 2×10⁵⁴。合わないのは「三角形なし 2,309」（こちらは 2,250）と、Sim⁺ の 13,158。
- Wrzos-Kaminska（2020）の 3 つのルールは、全分岐・全ミニボード・全同点で後手が勝つ。どのルールを外しても 2 手目で負ける局面がある。
- 無作為な青を相手にすると、赤は最善の罠で 99.85% 勝つ。後手必勝のゲームなのに、後手が勝つには正確さが要る。
参考文献:
- W. Slany, "Graph Ramsey games", Technical Report DBAI-TR-99-34, TU Wien, 1999, arXiv:cs/9911004, https://arxiv.org/abs/cs/9911004（2026 年 10 月 18 日参照）
- W. Wrzos-Kaminska, "A simpler winning strategy for Sim", arXiv:2001.04024, 2020, https://arxiv.org/abs/2001.04024（2026 年 10 月 18 日参照）
- E. Mead, A. Rosa, C. Huang, "The game of SIM: A winning strategy for the second player", Mathematics Magazine 47(5), 1974, 243–247
- G. J. Simmons, "The game of SIM", J. Recreational Mathematics 2(2), 1969, 66
- OEIS A004102, https://oeis.org/A004102
デモ: https://sen.ltd/portfolio/game-of-sim/
リポジトリ: https://github.com/sen-ltd/game-of-sim