Bridg-It（David Gale のゲーム、1958 年に Gardner が Scientific American で紹介）をブラウザに実装した。赤と青の点が互い違いに並んだ盤で、赤は隣り合う赤い点どうしに橋を架けて左右の辺をつなぎ、青は上下をつなぐ。橋は交差できないので、交点は先に取った方のものになる。この盤から見えるのは Shannon のスイッチングゲームで、Lehman の定理（1964）が全部のグラフについて勝敗を決めている：相手の手番で、両方のゴールを含むどこかの頂点集合に辺を共有しない全域木が 2 本あれば勝ち、なければ負け。デモでは交点ごとに勝ち筋 ✓／負け筋 ✗ を出し、✓ にマウスを載せるとその手のあとに残る 2 本の木を盤に描く。判定は探索ではなく (2,2) ペブルゲーム（Lee & Streinu）で、5 × 6 盤でも一瞬で終わる。数えてみると、n × (n+1) 盤の赤のグラフは頂点 n(n−1)+2、辺 n²+(n−1)² で、2 本の全域木に必要な 2(V−1) よりちょうど 1 本少ない。そしてどの初手のあとも、辺はちょうど 2 本の全域木に割れる。5 × 6 盤の初手 41 通りすべてが勝ち手で、これは 14 × 15 盤まで全部の盤で同じだった。理論を信じずに、(1) 頂点 6 個までの全ラベル付きグラフ 33,866 個を素朴な minimax で解き、途中で通った 80,590 局面すべてで Lehman の判定と一致（7・8 頂点はランダム抽出）、(2) 4 × 5 盤までは Bridg-It そのものを minimax で解いて「先手必勝・初手すべて勝ち」を確認、(3) 赤から見た勝敗と青から見た勝敗が 85,708 局面で一度も食い違わない（引き分けがない）ことを確かめた。テスト 12 件。ソルバー内蔵パズル第 100 弾。
デモ: https://sen.ltd/portfolio/bridg-it/
リポジトリ: https://github.com/sen-ltd/bridg-it
ルール
- 赤い点が n 行 × (n+1) 列、青い点が (n+1) 行 × n 列、互い違いに並ぶ。市販の Bridg-It は n = 5（5 × 6 と 6 × 5）。
- 手番の人は、自分の色の隣り合う 2 点に橋を 1 本架ける。
- 橋は交差できない。赤の橋と青の橋はちょうど 1 か所ずつで交差するので、交点 1 つにつき、先に取った方だけが橋を架けられる。
- 赤は左の列と右の列を、青は上の行と下の行を、自分の橋でつないだら勝ち。
- 引き分けはない（赤の道がなければ、それを遮る青の道がある。Hex と同じ理屈）。
同じゴール辺に並ぶ 2 点をつなぐ橋（左端の列の縦の橋など）は役に立たないので省いた。すると交点は n² + (n−1)² 個、5 × 6 盤では 41 個になる。
デモでは交点をクリックして橋を架ける。自分の手番には交点ごとに ✓（相手がどう応じても勝てる）／✗ が付き、✓ にマウスを載せるとその手で残る 2 本の木（実線と金色の点線）が出る。コンピュータは勝ち手があればそれを指し（盤の中央寄りを優先）、なければ相手の勝ち手がいちばん少なくなる手で粘る。
Shannon のスイッチングゲームに直す
赤の側だけを見る。赤い点を頂点にし、左の列をまとめて 1 頂点 s、右の列をまとめて 1 頂点 t にする。交点は赤のグラフの辺 1 本に当たる。
- 赤が橋を架ける ＝ その辺を自分のものにする。両端はもうつながったので、辺を縮約（2 頂点を 1 つに）してよい。
- 青が交点を取る ＝ 赤はそこに架けられなくなる。赤のグラフから辺を削除する。
- 赤の勝ち ＝ s と t が 1 点に縮む。青の勝ち ＝ s と t が非連結になる。
これは Shannon が 1950 年ごろに考えたスイッチングゲームそのもので、つなぐ側を Short、切る側を Cut と呼ぶ。青から見ても同じで、青のグラフ（上の行を s、下の行を t）で青が Short、赤が Cut になる。
Lehman の定理：2 本の木
Lehman（A solution of the Shannon switching game, 1964）は、どんなグラフでも勝敗が決まることを示した。
Cut の手番のとき、Short が勝つ ⇔ s と t を含むある頂点集合 S があって、S に誘導される部分グラフが辺を共有しない全域木を 2 本持つ。
勝ち方は短い。2 本の木 T₁、T₂ を持っているとする。Cut が T₁ の辺 e を消すと、T₁ は 2 つに割れる。T₂ は全域木なので、その 2 つをまたぐ T₂ の辺 f が必ずある。Short は f を取って縮約する。T₁ − e + f はまた全域木になり、T₂ も f を縮約した全域木のままになる。Cut がどちらの木にも入っていない辺を消したら、Short は好きな木の辺を取ればよい。頂点が 1 つ減るたびに木の辺も 1 本ずつ減り、最後は S が 1 点に縮んで s と t がつながる。
Short の手番なら、「縮約すると条件が成り立つ辺がある」かどうかで決まる。デモの ✓／✗ はこれを交点ごとに判定している。
盤は辺が 1 本足りない
数える。n × (n+1) 盤の赤のグラフは
- 頂点：内側の赤い点 n(n−1) 個 ＋ s ＋ t で V = n(n−1) + 2
- 辺：横の橋 n² 本 ＋ 内側の縦の橋 (n−1)² 本で E = 2n² − 2n + 1
全域木 2 本には 2(V − 1) = 2n² − 2n + 2 本の辺が要るので、ちょうど 1 本足りない。だから後手は 2 本の木を持てず、先手が勝つ（盤は 90° 回すと赤と青が入れ替わるので、青から見ても同じ）。
初手は辺 1 本を縮約するので、頂点も辺も 1 つずつ減って E = 2(V − 1) になり、過不足がなくなる。このとき辺が 2 本の全域木にちょうど割れるかどうかを、すべての初手について Edmonds のマトロイド分割で調べた。
| 盤 | 頂点 V | 辺 E | 2(V−1) | 勝つ初手 | ちょうど 2 本の木に割れる初手 |
|---|---|---|---|---|---|
| 1 × 2 | 2 | 1 | 2 | 1 / 1 | 1 / 1 |
| 2 × 3 | 4 | 5 | 6 | 5 / 5 | 5 / 5 |
| 3 × 4 | 8 | 13 | 14 | 13 / 13 | 13 / 13 |
| 4 × 5 | 14 | 25 | 26 | 25 / 25 | 25 / 25 |
| 5 × 6 | 22 | 41 | 42 | 41 / 41 | 41 / 41 |
| 6 × 7 | 32 | 61 | 62 | 61 / 61 | 61 / 61 |
| 7 × 8 | 44 | 85 | 86 | 85 / 85 | 85 / 85 |
| 8 × 9 | 58 | 113 | 114 | 113 / 113 | 113 / 113 |
| 9 × 10 | 74 | 145 | 146 | 145 / 145 | 145 / 145 |
| 10 × 11 | 92 | 181 | 182 | 181 / 181 | 181 / 181 |
| 11 × 12 | 112 | 221 | 222 | 221 / 221 | 221 / 221 |
| 12 × 13 | 134 | 265 | 266 | 265 / 265 | 265 / 265 |
| 13 × 14 | 158 | 313 | 314 | 313 / 313 | 313 / 313 |
| 14 × 15 | 184 | 365 | 366 | 365 / 365 | 365 / 365 |
5 × 6 盤では 41 通りの初手がすべて勝ちで、どれを選んでも残りの辺が過不足なく 2 本の全域木になる。14 × 15 盤まで例外はなかった。先手必勝であることは知られているが、計算の上では 1 手目はどこでもよい。
判定は探索しない：(2,2) ペブルゲーム
「s, t を含む部分グラフに 2 本の木があるか」を、部分集合を全部試さずに決めたい。使ったのは剛性理論で使われる (k, l) ペブルゲーム（Lee & Streinu, 2008）の k = l = 2 版。
- 各頂点にペブルを 2 個置く。
- 辺 uv を 1 本ずつ見る。u と v の上にペブルを 3 個集められたら辺を採用し、u か v のペブルを 1 個使って辺に向き（ペブルを使った側から出る向き）を付ける。集められなければ捨てる。
- ペブルを集めるときは、採用済みの辺を逆向きにたどってペブルのある頂点を探し、見つかったら道の向きを全部ひっくり返してペブルを 1 個運ぶ。
採用された辺の集合は「どの k′ 頂点の部分グラフにも辺が 2k′ − 2 本以下」という疎さを保つ最大の集合（(2,2) 疎性マトロイドの基）になる。辺が 2k′ − 2 本ちょうどの部分グラフは、Nash-Williams の定理でちょうど 2 本の全域木に分かれる。だから
最後に s と t の上にペブルを 3 個集められなければ、s と t を含む「2 本の木の部分グラフ」がある。
ループ（縮約で両端が同じ頂点になった辺）は 1 頂点にペブル 3 個が要るので、必ず捨てられる。役に立たない辺が自動で落ちるのがうれしい。
/** Lehman's criterion with Cut to move, by the pebble game. */
export function secondWins(g: Graph, s: number, t: number): boolean {
if (s === t) return true;
const p = pebbleGame(g);
return p.gather(s, t) < 3;
}
Short の手番の判定は「縮約して secondWins が真になる辺があるか」で、辺の本数ぶんペブルゲームを回す。5 × 6 盤の 41 手でもブラウザで一瞬だった。
盤に描く 2 本の木は別に作る。ペブルゲームが教えるのは「あるかどうか」だけなので、Edmonds のマトロイド分割で 2 つの森を最大にする。辺を 1 本ずつ入れ、どちらの森にも入らなければ、森の閉路上の辺を押し出してもう一方の森へ回す交換の列を BFS で探す（最短の交換列を使えば、全部を同時に入れ替えても森のまま）。
確かめ方 1：全グラフを minimax で解く
Lehman の定理もペブルゲームの実装も信じずに、ゲームそのものを解いて比べた。Minimax は辺の多重集合をキーにメモ化した素朴な探索で、Short は辺を縮約し、Cut は辺を削除する。頂点 k 個のラベル付き単純グラフを全部（s = 0, t = 1 固定）、Short が先手と後手の両方で解いた。
| 頂点 | グラフ | s–t 連結 | Short が先手でも後手でも勝つ | Cut が先手でも後手でも勝つ | 先手が勝つ |
|---|---|---|---|---|---|
| 2 | 2 | 1 | 0 | 1 | 1 |
| 3 | 8 | 5 | 0 | 4 | 4 |
| 4 | 64 | 48 | 1 | 31 | 32 |
| 5 | 1,024 | 874 | 71 | 451 | 502 |
| 6 | 32,768 | 30,264 | 6,252 | 11,733 | 14,783 |
| 7（抽出） | 30,000 | — | 11,611 | 7,452 | 10,937 |
| 8（抽出） | 1,000 | — | 600 | 148 | 252 |
「後手だけが勝つ」グラフは 0 個（手番を持つことが損にならないゲームなので当然だが、数えて確認した）。そのうえで、探索が通った 80,590 局面すべて（縮約で生まれる多重グラフを含む）で、探索の答えとペブルゲームの判定を照合して不一致 0。このうち Cut の手番の 42,854 局面では、Nash-Williams–Tutte の条件（S の分割 P すべてで、P をまたぐ辺が 2(|P| − 1) 本以上）を、s, t を含む頂点集合と分割を総当たりして調べ、これも全部一致した。
7 頂点の全グラフ（2²¹ = 2,097,152 個）もやるつもりだったが、メモが冷えた状態で 1 グラフ 5.8 ms かかり、見積もりで 3 時間を超えたのでやめた。代わりに 7 頂点 30,000 個と 8 頂点 1,000 個をランダムに選び、到達した 1,232,460 局面でペブルゲームと照合した（不一致 0、表の「抽出」の行）。総当たりの方も 7 頂点では 1 局面ごとに頂点集合 32 通り × 分割 877 通り（ベル数 B₇）を回すことになるので、ランダムな多重グラフ（頂点 7〜9 個）20,000 個でペブルゲームとだけ比べた（不一致 0）。
木の描画に使うマトロイド分割も、15,414 個の多重グラフで「2 つの森の大きさの和 ＝ 2 重和マトロイドの階数 min_X (|E∖X| + 2 r(X))」を辺の部分集合の総当たりと比べて全部一致した。
テストを書いていて、自分の直感の方が間違っていた例が 1 つある。4 頂点の輪 s–a–t–b–s は s から t への道が 2 本あるので、先手の Short なら勝てると思って期待値を書いたら、探索もペブルゲームも「Cut の勝ち」と言う。Short が s–a を取れば Cut は a–t を消し、もう 1 本の道でも同じことをされる。道が 2 本あっても、辺を共有しない木が 2 本なければ守れない。
確かめ方 2：Bridg-It そのものを解く
小さい盤は、赤のグラフの上でゲームを最後まで探索した。
| 盤 | 交点 | 先手の赤が勝つ | 後手の赤が勝つ | 勝つ初手（探索） | Lehman と一致 | 局面数 |
|---|---|---|---|---|---|---|
| 1 × 2 | 1 | はい | いいえ | 1 / 1 | 1 / 1 | 2 |
| 2 × 3 | 5 | はい | いいえ | 5 / 5 | 5 / 5 | 26 |
| 3 × 4 | 13 | はい | いいえ | 13 / 13 | 13 / 13 | 5,233 |
| 4 × 5 | 25 | はい | いいえ | 25 / 25 | 25 / 25 | 1,777,255 |
4 × 5 盤（交点 25）はそのままでは 8 分たっても初手 1 つ目が終わらなかった。そこで 2 つの工夫を入れた。
- 死に辺を落とす：s から t への単純な道に乗らない辺は、縮約しても削除しても二度と道に乗らない。そこに打つのはパスと同じで、このゲームではパスが本物の手より得になることはない。s–t の仮想辺を足して二重連結成分（Tarjan）を求め、仮想辺と同じブロックの辺だけを残す。
- Short の手を並べ替える：Short の手番では、Lehman の判定で勝ちと出る手から試す。勝ち手を最初に引けば、負け手の反証探索をしなくて済む。
どちらも探索の速さにしか効かず、答えは探索が出す。それでも念のため、頂点 6 個までの全グラフで「落とさない探索」「落とす探索」の答えが一致すること、テストでは 5 頂点の全グラフで並べ替えありの探索も一致することを確かめた。
確かめ方 3：引き分けがない
赤のグラフと青のグラフは別々のグラフで、ペブルゲームもそれぞれに回る。盤の上では「赤が勝つ」と「青が勝つ」のどちらか一方しか起きないので、
- 赤の手番：赤のグラフで「先手 Short が勝つ」 ⇔ 青のグラフで「後手 Short が勝たない」
- 青の手番：その逆
が成り立つはずだ。ランダムに打ち進めた 2 × 3 〜 9 × 10 盤の 85,708 局面で、2 つの判定が両方勝ち・両方負けになったことは一度もなかった。赤と青の判定は平面双対の関係にあるが、コード上は何も共有していないので、良い検算になる。
コンピュータどうしの対戦と、ランダムに打つ相手との対戦（3 × 4 〜 7 × 8 盤、計 1,060 局）では、先手のコンピュータは一度も負けなかった。
実装メモ
-
src/graph.ts：多重グラフ、(2,2) ペブルゲーム（secondWins）、Short の手番の判定（firstWins）、Nash-Williams–Tutte の総当たり、メモ化 minimax（死に辺の除去と手の並べ替えはオプション）、Edmonds のマトロイド分割（treePacking）。 -
src/bridgit.ts：盤（交点ごとに赤の辺と青の辺）、各プレイヤーのグラフ（自分の橋は union–find で縮約、相手の橋は削除）、勝ち手、2 本の木、コンピュータ。 -
tools/compute.mts：記事の表をまとめて計算し、ジョブごとにruns/compute.jsonを書き直す。tools/exact.mtsが 4 × 5 盤の探索。 -
tools/report.mts：デモの右パネル（src/findings.json）を作る。
まとめ
- Bridg-It の盤は、赤のグラフで見ると Shannon のスイッチングゲームで、Lehman の定理が「辺を共有しない 2 本の全域木」で勝敗を決める。
- 盤の辺は 2 本の全域木に 1 本足りない。初手で過不足がなくなり、どの初手のあとも辺はちょうど 2 本の木に割れる。5 × 6 盤の初手 41 通りはすべて勝ち。
- 判定は (2,2) ペブルゲームで探索なしにでき、木は Edmonds のマトロイド分割で描ける。
- 頂点 6 個までの全グラフ 33,866 個と途中の 80,590 局面（7・8 頂点は抽出で 1,232,460 局面）、4 × 5 盤までの Bridg-It の全探索、85,708 局面の双対検算で、どこにも食い違いはなかった。