Bridge It と Connections の 必勝法について

Presentation on theme: "Bridge It と Connections の 必勝法について"— Presentation transcript:

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

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

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

4 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 戦略による 明示的な先手必勝手順がある

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

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

7 八角形のコマを置く

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

9 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.

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

11 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

12 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

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

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

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

16 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 に必勝手順がある．

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

18 END

19

20

21 u v e T2 T2╲ {e}

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

23 (a) G1 (b) (c) G2

24

25

26

27 P

28