無向ジオグラフィ（Undirected Vertex Geography）をブラウザに実装した。グラフの頂点に駒が 1 つあり、2 人が交互に駒を隣の頂点へ動かす。駒が出ていった頂点は消えるので、駒の通り道は二度と戻れない一本道になる。動かせなくなった人の負け。このゲームには、性質の違う 2 つの答えがある。どちらが勝つかは、駒のいる頂点がすべての最大マッチングに含まれるかどうかで決まる（Fraenkel–Scheinerman–Ullman 1993）。マッチングで判定できるので多項式時間だ。ところが、このゲームを他のゲームと並べて遊ぶ（和をとる）ときに必要な Grundy 値（ニム数）の計算は、PSPACE 完全であることが FOCS 2021 で証明された（Burke–Ferland–Teng）。デモは、マッチングを盤に重ねて勝敗の理由を見せ、合法手すべてに厳密な Grundy 値を付ける。論文を arXiv の TeX から読み込んで、構成と補題を全部計算し直した。辺のガジェット、補題、次数 3 での分枝限定法はすべて一致した。ただ 1 か所、任意の大きさのニム数を作る構成の Algorithm 1 は、印刷どおりに組むと N_n の値が *n にならず 0, *, *2, *, *2, * になった。図と補題が使っている辺 2 種類と木 1 つが、アルゴリズムの記述から抜けている。全部足すと n = 4…9 のすべてで *n になった。もう 1 つ、9 頂点までの連結グラフ 261,080 個とその全始点で、*k を作るのに必要な最少の頂点数を数えた。k = 0…4 で 1, 2, 4, 6, 8 だ。木なら 2^k 頂点が要る。*5 は 10 頂点で厳密、局所探索では *6 が 12 頂点、*7 が 14 頂点で見つかった。テスト 15 件。ソルバー内蔵パズル第 104 弾。
デモ: https://sen.ltd/portfolio/undirected-geography/
リポジトリ: https://github.com/sen-ltd/undirected-geography
ルール
- 盤は任意の無向グラフ。頂点の 1 つに駒を置く。
- 手番の人は、駒を隣の頂点に動かす。駒が出ていった頂点はグラフから消える（その頂点につながる辺も消える）。
- 動かせなくなった人の負け（正規形）。
もとは「しりとり」の地名版で、前の人が言った地名の最後の文字で始まる地名を答えていく遊びだ。Karp の提案でグラフ上の抽象ゲームになり、有向グラフ版（Generalized Geography）は PSPACE 完全であることが知られている（Schaefer 1978）。Lichtenstein–Sipser（1980）は、平面・2 部・最大次数 3 でも PSPACE 完全なままだと示し、それを使って囲碁の PSPACE 困難性を証明した。辺の向きを外した無向版は、一転して多項式時間で解ける。
デモでは盤をプリセットから選ぶ。駒の隣の頂点（打てる手）に、その手を指した後の局面の Grundy 値が出る。0 なら勝ち手だ。金色の線は、残っている盤の最大マッチングの 1 つを表す。赤い縁の頂点はそのマッチングに入っていない頂点だ。右のパネルには、局面の Grundy 値と、最大マッチングのサイズ ν を駒の頂点がある場合とない場合で並べて出す。盤の最大次数が 3 以下なら、論文の分枝限定法が出した値と、それに使った勝敗判定の回数も出る。
誰が勝つか：最大マッチング（1993）
Fraenkel–Scheinerman–Ullman の定理はこうだ。
駒が頂点 s にあるとき、手番の人が勝つ ⇔ s がグラフのすべての最大マッチングに含まれる。
「すべての最大マッチングに含まれる」かどうかは、s を消すと最大マッチングのサイズ ν が減るかで判定できる。減るなら s はどの最大マッチングにも入っている。減らないなら s を使わない最大マッチングがある。だから Edmonds の花（blossom）アルゴリズムを 2 回走らせれば勝敗がわかる。
勝ち方もマッチングから読める。s がすべての最大マッチングに入っているなら、最大マッチング M を 1 つとって、s の相手 M(s) へ動けばよい。M から辺 (s, M(s)) を除いたものは s を消したグラフの最大マッチングで、M(s) を含まない。つまり相手は「最大マッチングに含まれない頂点」に置かれる。相手がどこへ動いても、その先の頂点はすべての最大マッチングに入っているので、こちらはまたマッチングの辺に沿って動ける。これを繰り返すと、最後に動けなくなるのは相手のほうだ。デモのコンピュータはこの手順で指す。
検算として、9 頂点までの連結グラフすべて（OEIS A001349 の個数 1, 1, 2, 6, 21, 112, 853, 11117, 261080 と一致）と、そのすべての始点、合計 2,445,437 組で、全探索で求めた Grundy 値が 0 かどうかと、マッチングの判定を照合した。マッチング数 ν はビットマスクの全探索で求めたので、花のアルゴリズムは使っていない。例外は 0 件だった。さらに、8〜17 頂点のランダムなグラフで、勝てる始点から「マッチングどおりに動く側」と「でたらめに動く側」を 162 局対戦させ、マッチング側が全勝することも確かめた。
奇数頂点のグラフでは最大マッチングが必ずどこかの頂点を取り残すので、後手必勝の始点が多い。9 頂点では 2,349,720 組のうち 2,155,288 組（92%）が後手必勝だ。偶数頂点では逆に先手必勝がほとんどになる。完全マッチングがあれば、どの頂点から始めても先手必勝だ（ピーターセングラフがそう）。
何点の価値があるか：Grundy 値は PSPACE 完全（2021）
勝敗だけなら多項式時間で済む。でも、盤を 2 枚並べて「どちらか一方で 1 手指す」ゲームの和を考えると、勝敗だけでは足りない。必要なのは Grundy 値（ニム数）だ。和の勝敗は、各盤の Grundy 値の XOR が 0 かどうかで決まる（Sprague–Grundy の定理）。
Burke, Ferland, Teng "Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography"（FOCS 2021, arXiv:2106.02114）は、無向ジオグラフィの Grundy 値の計算は PSPACE 完全だと証明した。最大次数 4（平面・2 部グラフでも）で PSPACE 困難、最大次数 3 なら多項式時間という二分法になっている。勝敗が多項式時間で決まるゲームでも、ニム数は難しい。その帰結として、勝敗が多項式時間で決まる 2 つのゲームの和が PSPACE 困難になりうることも示している。
デモの Grundy 値は、駒の位置と「駒の頂点を含む連結成分」をキーにしたメモ化探索で厳密に求めている。駒は自分の成分から出られないので、他の成分は値に影響しない。
論文を TeX から検算する
arXiv の e-print から LaTeX ソースを取り、定理・補題・図（TikZ）・アルゴリズムを読んで、構成をすべてコードに起こした。結果は tools/verify.mts が runs/literature.json に書き出す。17 項目中 16 項目が一致した。
辺に向きを付けるガジェット
PSPACE 困難性の証明は、有向ジオグラフィからの帰着だ。各頂点 v に葉 v₀ を 1 枚ぶら下げ、各有向辺 x → y を 10 頂点のガジェット（x – a – b – c – d – y、a – a₀、c – c₀、d – d₀、b – f – d）に置き換える。論文の主張は「元の局面が後手必勝なら帰着後の値はちょうど *、先手必勝なら * 以外の非 0」というものだ。
- 3 頂点以下のすべての有向グラフと、4 頂点のランダムな有向グラフ 400 個の、全始点 1,801 局面で成立した（帰着後のグラフは最大 88 頂点）。
- 補題 "Wrong Way"（y から d へ逆走すると値は *2 か *3）：2,364 個のガジェットすべてで成立した。*2 と *3 の両方が実際に出る。
- 補題 "Correct Way"（d → y が * ⇔ x → a が *）：2,364 個すべてで成立した。
- 前置ガジェット（start – start₀、start – p – p₀、p – s）をつけると、start の値は「s が * なら *、それ以外なら *2」になる、という系：1,801 局面すべてで成立した。
次数 3 の分枝限定法
最大次数 3 での多項式時間アルゴリズムは、勝敗判定（マッチング）だけで値を決めていく。
- 選択肢が 1 つなら、値は「その手が勝ち手なら *、でなければ 0」。
- 選択肢が 2 つなら、行き先の勝敗が［先手必勝, 先手必勝］なら 0、［後手必勝, 後手必勝］なら *。片方だけが後手必勝なら、もう片方（値は * か *2）の値 x を再帰で求めて 3 − x を返す。再帰は 1 本道になる。
- 選択肢が 3 つなら、それぞれの行き先は次数 2 以下なので、上の手順で値を出して mex をとる。
これを、9 頂点以下の最大次数 3 の連結グラフ全 838 個（始点 7,036 個）と、12〜28 頂点のランダムな 3 次以下のグラフ 200 個で全探索と照合して、全部一致した。必要な勝敗判定は平均 5.5 回前後で、盤が大きくなってもほぼ一定だった。全探索のノード数は 28 頂点で平均 16,887 まで増える。三角形分割の双対（立方体、正十二面体）でも一致した。
実装で 1 回、自分が間違えた。選択肢が 1 つの場合に「その手の行き先が先手必勝なら *」と書いてしまい、全数照合で 2 頂点のグラフから食い違いが出た。正しくは、行き先が後手必勝（＝相手が負ける）なら * だ。全数照合はこういう取り違えをすぐに見つけてくれる。
任意の大きさのニム数を作る構成：印刷どおりでは動かない
論文の第 5 節は、*n の値を持つ局面を多項式サイズで作る構成を与えている。木なら t(n)（根の子が t(n−1), …, t(0)）で *n が作れるが、頂点数が 2^n になる。そこで、頂点 N_4, …, N_n を完全グラフでつなぎ、各 N_i に * のガジェット M_i、*2 のガジェット P_i、値 0 の頂点 R_i、*3 の木をつける。下位の N が消えるとガジェットの値が *3 に変わるように、R_k から上位の M_i、P_i へ長さ 4〜6 の鎖を張る。こうして「上位の N へ逆戻りすると値が * か *2 にしかならない」ように仕掛ける。
この構成は、図 3 枚と、形式的な Algorithm 1 の 2 通りで書かれている。両方をコードに起こして値を計算した。
| 構成 | n=4 | n=5 | n=6 | n=7 | n=8 | n=9 |
|---|---|---|---|---|---|---|
| 図どおり | *4 | *5 | *6 | *7 | *8 | *9 |
| Algorithm 1 を印刷どおり | 0 | * | *2 | * | *2 | * |
図どおりに組むと n = 4…9 のすべてで *n になった。第 5 節の補題（Grounded、R_p → N_p、Skip *2、Skip *、「*4 以上」、Parity、定理の帰納法の段）も、n = 8 で N 頂点の消え方 32 通りすべてについて成立した。
Algorithm 1 のほうは、印刷どおりに組むと *n にならない。図と見比べると、アルゴリズムの記述から次の 3 つが抜けている。
- N_i – M_i と N_i – P_i の辺（i ≥ 5）。頂点 M_i, P_i は作られ、そこから下へ鎖も張られるが、N_i からつながる辺が追加されない。図 3 には「N_i は自分の * ガジェット・*2 ガジェットにつながる」とある。
- N_4 – R_4 の辺。ループは i = 5 から始まり、辺 (N_i, R_i) もそこで足される。N_4 と R_4 は頂点として追加されるだけで、辺がない。
- N_4 の *3 の木。*3 の木もループの中（i ≥ 5）でしか作られない。定理の基底の段は「N_4 は構成により 0 から *3 への手を持つ」と書いている。
どれか 1 つでも欠けると構成は壊れる。図どおりの構成から 1 つずつ外した結果がこれだ。
| 構成 | n=4 | n=5 | n=6 | n=7 | n=8 | n=9 |
|---|---|---|---|---|---|---|
| 図どおり − N_4–R_4 | 0 | * | *2 | * | *2 | * |
| 図どおり − N_4 の *3 の木 | *3 | *4 | *5 | *6 | *7 | *8 |
| 図どおり − N_i–M_i, N_i–P_i | *4 | * | *2 | * | *2 | * |
*3 の木だけが欠けた場合は、値がきれいに 1 ずつずれる（N_4 が *3 になり、帰納法の段がそのまま 1 段ずつ下がる）。N_i – M_i, N_i – P_i の辺が欠けた場合は、N_i から * と *2 への手がなくなる。n = 5 では N_5 の行き先が R_5（0）、*3 の木、N_4（*4）だけになるので、N_5 は mex{0, *3, *4} = * になる。そこから先は * と *2 を交互にとる。N_4 – R_4 が欠けた場合は、N_4 に 0 への手がなくなるので、n = 4 からいきなり 0 になる。
図と補題の議論は正しいので、論文の結論（多項式サイズで *n が作れる）は揺るがない。ただ、Algorithm 1 をそのまま実装すると動かない。図どおりの構成は 5n² − 15n − 4 頂点で、n = 4 では木 t(4) と同じ 16 頂点、n = 8 からは木（2^n）より小さくなる。
*k を作るのに最少で何頂点要るか
論文の観察では、木で *k を作るには 2^k 頂点が必要だ（根には値 0, …, k−1 の部分木がそれぞれ要るので、f(k) = 1 + f(0) + … + f(k−1) = 2^k）。一般のグラフならどうなるかを数えた。
9 頂点までの連結グラフの全始点で値を数えた結果がこれだ。
| 頂点数 | グラフ | (グラフ, 始点) | 0 | * | *2 | *3 | *4 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | ||||
| 2 | 1 | 2 | 2 | ||||
| 3 | 2 | 6 | 5 | 1 | |||
| 4 | 6 | 24 | 3 | 14 | 7 | ||
| 5 | 21 | 105 | 83 | 11 | 11 | ||
| 6 | 112 | 672 | 70 | 424 | 156 | 22 | |
| 7 | 853 | 5,971 | 4,898 | 667 | 372 | 34 | |
| 8 | 11,117 | 88,936 | 4,357 | 59,405 | 18,880 | 5,854 | 440 |
| 9 | 261,080 | 2,349,720 | 2,155,288 | 98,997 | 67,971 | 26,483 | 981 |
*k が最初に現れる頂点数は 1, 2, 4, 6, 8（k = 0…4）で、木の 1, 2, 4, 8, 16 よりずっと少ない。*3 の最小例は 6 頂点・6 辺で、デモに入れてある。9 頂点以下には *5 が 1 つもない。そこで 10 頂点以上は、辺を 1 本ずつ反転させる局所探索で探した（見つかった例は src/ の独立な探索で値を再確認している）。
- *5：10 頂点で見つかった。9 頂点以下にないことは全数で確かめてあるので、最少は 10 頂点で厳密。
- *6：12 頂点で見つかった（上界）。
- *7：14 頂点で見つかった（上界）。
一方、*6 を 11 頂点で 240 秒、*7 を 13 頂点で 150 秒、*8 を 16 頂点で 319 秒探したが、どれも見つからなかった。見つからなかったことは、存在しないことの証明ではない。
ここまでは「*k は 2k 頂点で作れる」がずっと成り立っている。もしこれが一般に成り立つ族があれば、論文の 5n² 頂点の構成よりずっと小さい。ただ、ここで示せたのは k ≤ 5 の厳密値と k ≤ 7 の上界だけで、一般の族は見つけていない。
実装メモ
-
src/geography.ts：ルール、厳密な Grundy 値（駒と成分をキーにしたメモ化探索）、Edmonds の花アルゴリズム（O(V³)）、マッチングによる勝敗判定と勝ち手、次数 3 の分枝限定法。 -
src/constructions.ts：論文の構成をラベル付きの頂点で組み立てる。t(k)、有向辺ガジェットと前置ガジェット、第 5 節の構成。第 5 節の構成は、印刷どおり・図どおり・その中間をフラグで切り替えられる。 -
tools/graphs.mts：連結グラフの全列挙。頂点を 1 つずつ足し、正準形（次数で細分した後の順序の中で最小の隣接文字列）で同型を除く。正準形は最初、最小値を更新した後も古い比較結果を使い回すバグがあって、7 頂点で 853 個のところ 894 個になった。OEIS の個数と照合して気づいた。 -
tools/sweep.mts：全連結グラフの全始点。Grundy 値はビットマスクの表、ν もビットマスクの全探索で、src/の実装とは独立。tools/smallest.mts：局所探索。tools/report.mts：README の表をruns/から作るので、表の数字は手で書き写していない。 - 9 頂点の全列挙（26 万グラフ・235 万始点）は、グラフの生成込みで約 2 分半。構成の値は n = 9（266 頂点）で 155 万ノード・27 秒。n = 10 はメモが数 GB になりそうなので止めた。
- デモは依存ゼロの TypeScript + Vite。
まとめ
- 無向ジオグラフィの勝敗は「駒の頂点を消すと最大マッチングが小さくなるか」で決まる。9 頂点までの全 2,445,437 局面で例外はなかった。
- Grundy 値は PSPACE 完全だが、次数 3 なら勝敗判定だけで求まる。論文の分枝限定法は全数照合とランダムなグラフで全探索と一致し、勝敗判定は平均 5.5 回程度で済んだ。
- 論文の有向辺ガジェットと補題はすべて成立した。高いニム数の構成は図どおりなら *n になるが、Algorithm 1 を印刷どおりに組むと 0, *, *2, * … になる。辺 2 種類と木 1 つが記述から抜けていて、どれが欠けても壊れる。
- *k を作る最少の頂点数は 1, 2, 4, 6, 8, 10（k ≤ 5 で厳密）。木なら 2^k が要る。