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: 鉛筆で描かれた枝を1本選んで消す Inker: 鉛筆で描かれた枝を1本選んでインクで描く 勝利条件: Inker:インクの枝が元のグラフの全張木を含む Eraser:Inkerが勝利しなければ勝ち 定理[Lehman] 元のグラフGが,枝素な全張木を2つ含むならば,Eraser が先手のInker-Eraser game は, 後手のInker に必勝手順がある.
Inker-Eraser Game の必勝法 Inkerの手番毎に頂点数減少(ループ?).頂点が1つになれば Inkerの勝利.グラフが非連結になればEraserの勝利. 証明: 無向グラフGが枝素な全張木S,T を含むとする. 必勝戦略:Inker は,枝素な全張木を2つ保持し続ける. (1)Eraser がS∪T外の枝を消したとき(略) (2)Eraser がS中の枝を消したとき(略) (3)Eraser がT中の枝eを消したとき T-e は2つの部分木T1,T2 からなる T1とT2をつなぐ枝f がS中に1本以上存在する. Inker はf を選んで短絡する. 最終的に頂点2つとその間の2本以上の平行辺となる. Eraser が枝を消しても,Inkerが残った枝を短絡して勝利 T1 T2 e f
Inker-Eraser Game の必勝法 Inkerの手番毎に頂点数減少(ループ?).頂点が1つになれば Inkerの勝利.グラフが非連結になればEraserの勝利. 証明: 無向グラフGが枝素な全張木S,T を含むとする. 必勝戦略:Inker は,枝素な全張木を2つ保持し続ける. (1)Eraser がS∪T外の枝を消したとき(略) (2)Eraser がS中の枝を消したとき(略) (3)Eraser がT中の枝eを消したとき T-e は2つの部分木T1,T2 からなる T1とT2をつなぐ枝f がS中に1本以上存在する. Inker はf を選んで短絡する. 最終的に頂点2つとその間の2本以上の平行辺となる. 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で先手が勝利している. 背理法で示す (1)Connectionsで後手が上下をつないで勝利? 全張木無し⇒矛盾
Inker-Eraser Game と Connections Connections Inker-Eraser 先手(黒) 先手:Inker (短絡) 後手(白) 後手:Eraser (除去) 性質:Inker-Eraser Game で Inker が勝てば,Connectionsで先手が勝利している. 背理法で示す (2)Connectionsで後手が閉路を構成して勝利? 全張木無し⇒矛盾
Inker-Eraser Game と Connections Connections Inker-Eraser 先手(黒) 先手:Inker (短絡) 後手(白) 後手:Eraser (除去) 性質:Inker-Eraser Game で Inker が勝てば,Connectionsで先手が勝利している. ゆえに,下記のグラフで,Inker 先手のInker-Eraser Game で 先手のInker が必勝戦略を持てば,Connections で先手(黒)が必勝戦略を持つ. 定理[Lehman] 元のグラフGが,枝素な全張木を2つ含むならば,Eraser が先手のInker-Eraser game は, 後手のInker に必勝手順がある.
ここから,Eraser 先手,Inker 後手のInker-Eraser Game を行う. Connections の必勝戦略 先手のInker は左上の枝を最初に短絡 得られたグラフは,枝素な全張木を2つ持つ ここから,Eraser 先手,Inker 後手のInker-Eraser Game を行う. 定理[Lehman] 元のグラフGが,枝素な全張木を2つ含むならば, Eraser が先手のInker-Eraser game は,後手のInker に必勝手順がある. Inker は全張木を生成して勝利 → 黒(先手)はConnections に勝利
END