Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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: 鉛筆で描かれた枝を1本選んで消す Inker: 鉛筆で描かれた枝を1本選んでインクで描く 勝利条件: Inker:インクの枝が元のグラフの全張木を含む Eraser:Inkerが勝利しなければ勝ち 定理[Lehman] 元のグラフGが,枝素な全張木を2つ含むならば,Eraser が先手のInker-Eraser game は, 後手のInker に必勝手順がある.

11 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

12 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

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で先手が勝利している. 背理法で示す (1)Connectionsで後手が上下をつないで勝利? 全張木無し⇒矛盾

15 Inker-Eraser Game と Connections
Connections Inker-Eraser 先手(黒) 先手:Inker (短絡) 後手(白) 後手:Eraser (除去) 性質:Inker-Eraser Game で Inker が勝てば,Connectionsで先手が勝利している. 背理法で示す (2)Connectionsで後手が閉路を構成して勝利? 全張木無し⇒矛盾

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

17 ここから,Eraser 先手,Inker 後手のInker-Eraser Game を行う.
Connections の必勝戦略 先手のInker は左上の枝を最初に短絡 得られたグラフは,枝素な全張木を2つ持つ ここから,Eraser 先手,Inker 後手のInker-Eraser Game を行う. 定理[Lehman] 元のグラフGが,枝素な全張木を2つ含むならば, 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


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

Similar presentations


Ads by Google