Bridge It と Connections の 必勝法について 中央大学 松井知己

Bridge It （Game of Gale） 右図のような盤 先手後手が交互に手を打つ 先手(黒)：隣り合う●を結ぶ 後手(白)：隣り合う○を結ぶ （線が交差してはいけない） 勝利条件： 黒：左端と右端が連結 白：上端と下端が連結 by David Gale M. Gardner, Recreational topology, Mathematical Puzzles and Diversions, 1970.

Bridge It （例） 右図のような盤 先手後手が交互に手を打つ 先手(黒)：隣り合う●を結ぶ 後手(白)：隣り合う○を結ぶ 黒の勝利 右図のような盤 先手後手が交互に手を打つ 先手(黒)：隣り合う●を結ぶ 後手(白)：隣り合う○を結ぶ （線が交差してはいけない） 勝利条件： 黒：左端と右端が連結 白：上端と下端が連結 by David Gale M. Gardner, Recreational topology, Mathematical Puzzles and Diversions, 1970.

Strategy Stealing (by Nash) Bridge It (性質) 完全情報ゲームである 有限手番で終わる 引き分けは無い ⇒ どちらかに必勝手順がある 自分の線が余分に引かれても 不利にはならない ⇒先手に必勝手順がある Strategy Stealing (by Nash) M. Gardner, The Game of Hex, Hexaflexagons, Probability Paradoxes, and the Tower of Hanoi, 1988. pairing 戦略による 明示的な先手必勝手順がある

その後：両矢印の一端を相手が選んだら，他方を選ぶ by Oliver Gross Bridge It （必勝戦略） 先手(黒)：左端と右端をつなぐ と勝利 pairing 戦略： 先手の第一手：左上の横棒 その後：両矢印の一端を相手が選んだら，他方を選ぶ by Oliver Gross M. Gardner, Bridge-It and Other Games, New Mathematical Diversions, 1966.

Connections (はなやま玩具株式会社) Connections International Ltd. P.O. BOX 24-089, Oak Auckland, New Zealand. Patent application No. 229978

八角形のコマを置く

Connections Bridge It からの変更点 勝利条件： 黒：左端と右端が連結 または閉路を構成 白：上端と下端が連結 （先に条件を達成したら勝利）

Connections は先手の必勝戦略がある （strategy stealing） 前出のpairing 戦略は 先手必勝ではない Our Result Lehman’ Theorem を用いた明示的な 先手の必勝戦略 A. Lehman, A solution to the Shannon switching game, SIAM J. Appl. Math., 12 (1964), 687－725.

Inker-Eraser Game board: 紙に鉛筆で書いた無向グラフG Inker と Eraser が交互に手番を打つ Eraser： 鉛筆で描かれた枝を１本選んで消す Inker： 鉛筆で描かれた枝を１本選んでインクで描く 勝利条件： Inker：インクの枝が元のグラフの全張木を含む Eraser：Inkerが勝利しなければ勝ち 定理[Lehman] 元のグラフGが，枝素な全張木を２つ含むならば，Eraser が先手のInker-Eraser game は， 後手のInker に必勝手順がある．

Inker-Eraser Game の必勝法 Inkerの手番毎に頂点数減少（ループ？）．頂点が１つになれば Inkerの勝利．グラフが非連結になればEraserの勝利． 証明： 無向グラフGが枝素な全張木S,T を含むとする． 必勝戦略：Inker は，枝素な全張木を２つ保持し続ける． （1）Eraser がS∪T外の枝を消したとき(略) （２）Eraser がS中の枝を消したとき（略） （３）Eraser がT中の枝eを消したとき T-e は２つの部分木T1,T2 からなる T1とT2をつなぐ枝ｆ がS中に1本以上存在する． Inker はｆ を選んで短絡する． 最終的に頂点２つとその間の２本以上の平行辺となる． Eraser が枝を消しても，Inkerが残った枝を短絡して勝利 T1 T2 e f

Inker-Eraser Game の必勝法 Inkerの手番毎に頂点数減少（ループ？）．頂点が１つになれば Inkerの勝利．グラフが非連結になればEraserの勝利． 証明： 無向グラフGが枝素な全張木S,T を含むとする． 必勝戦略：Inker は，枝素な全張木を２つ保持し続ける． （1）Eraser がS∪T外の枝を消したとき(略) （２）Eraser がS中の枝を消したとき（略） （３）Eraser がT中の枝eを消したとき T-e は２つの部分木T1,T2 からなる T1とT2をつなぐ枝ｆ がS中に1本以上存在する． Inker はｆ を選んで短絡する． 最終的に頂点２つとその間の２本以上の平行辺となる． Eraser が枝を消しても，Inkerが残った枝を短絡して勝利 T1 T2

Inker-Eraser Game と Connections Connections Inker-Eraser 先手（黒） 先手：Inker （短絡） 後手（白） 後手：Eraser （除去）

Inker-Eraser Game と Connections Connections Inker-Eraser 先手（黒） 先手：Inker （短絡） 後手（白） 後手：Eraser （除去） 性質：Inker-Eraser Game で Inker が勝てば，Connectionsで先手が勝利している． 背理法で示す （１）Connectionsで後手が上下をつないで勝利？ 全張木無し⇒矛盾

Inker-Eraser Game と Connections Connections Inker-Eraser 先手（黒） 先手：Inker （短絡） 後手（白） 後手：Eraser （除去） 性質：Inker-Eraser Game で Inker が勝てば，Connectionsで先手が勝利している． 背理法で示す （２）Connectionsで後手が閉路を構成して勝利？ 全張木無し⇒矛盾

Inker-Eraser Game と Connections Connections Inker-Eraser 先手（黒） 先手：Inker （短絡） 後手（白） 後手：Eraser （除去） 性質：Inker-Eraser Game で Inker が勝てば，Connectionsで先手が勝利している． ゆえに，下記のグラフで，Inker 先手のInker-Eraser Game で 先手のInker が必勝戦略を持てば，Connections で先手（黒）が必勝戦略を持つ． 定理[Lehman] 元のグラフGが，枝素な全張木を２つ含むならば，Eraser が先手のInker-Eraser game は， 後手のInker に必勝手順がある．

ここから，Eraser 先手，Inker 後手のInker-Eraser Game を行う． Connections の必勝戦略 先手のInker は左上の枝を最初に短絡 得られたグラフは，枝素な全張木を２つ持つ ここから，Eraser 先手，Inker 後手のInker-Eraser Game を行う． 定理[Lehman] 元のグラフGが，枝素な全張木を２つ含むならば， Eraser が先手のInker-Eraser game は，後手のInker に必勝手順がある． Inker は全張木を生成して勝利 → 黒（先手）はConnections に勝利

END

u v e T2 T2╲ {e}

e T1╲ {e} パス u v u v T11 T12 f G G’

(a) G1 (b) (c) G2

P