スライド 1

Bridge It と Connections の
必勝法について
中央大学松井知己
1
Bridge It （Game of Gale）
右図のような盤
先手後手が交互に手を打つ
先手(黒)：隣り合う●を結ぶ
後手(白)：隣り合う○を結ぶ
（線が交差してはいけない）
勝利条件：
黒：左端と右端が連結
白：上端と下端が連結
by David Gale
M. Gardner, Recreational topology,
Mathematical Puzzles and Diversions, 1970.
2
Bridge It （例）
右図のような盤
先手後手が交互に手を打つ
黒の勝利
先手(黒)：隣り合う●を結ぶ
後手(白)：隣り合う○を結ぶ
（線が交差してはいけない）
勝利条件：
黒：左端と右端が連結
白：上端と下端が連結
by David Gale
M. Gardner, Recreational topology,
Mathematical Puzzles and Diversions, 1970.
3
Bridge It (性質)
完全情報ゲームである
有限手番で終わる
引き分けは無い
⇒ どちらかに必勝手順がある
自分の線が余分に引かれても
不利にはならない
⇒先手に必勝手順がある
Strategy Stealing (by Nash)
M. Gardner, The Game of Hex, Hexaflexagons,
Probability Paradoxes, and the Tower of
Hanoi, 1988.
pairing 戦略による
明示的な先手必勝手
順がある
4
Bridge It （必勝戦略）
先手(黒)：左端と右端をつなぐ
と勝利
pairing 戦略：
先手の第一手：左上の横棒
その後：両矢印の一端を相手
が選んだら，他方を選ぶ
by Oliver Gross
M. Gardner, Bridge-It and Other Games,
New Mathematical Diversions, 1966.
5
Connections
(はなやま玩具株式会社)
Connections International Ltd.
P.O. BOX 24-089, Oak Auckland, New Zealand.
Patent application No. 229978
6
八角形のコマを置く
7
Connections
Bridge It からの変更点
勝利条件：
黒：左端と右端が連結
または閉路を構成
白：上端と下端が連結
または閉路を構成
（先に条件を達成したら勝利）
8
Connections
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.
9
Inker-Eraser Game
board: 紙に鉛筆で書いた無向グラフG
Inker と Eraser が交互に手番を打つ
Eraser：鉛筆で描かれた枝を１本選んで消す
Inker：鉛筆で描かれた枝を１本選んでインクで描く
勝利条件：
Inker：インクの枝が元のグラフの全張木を含む
Eraser：Inkerが勝利しなければ勝ち
定理[Lehman]
元のグラフGが，枝素な全張木を２つ含むならば，
Eraser が先手のInker-Eraser game は，
後手のInker に必勝手順がある．
10
Inker-Eraser Game の必勝法
Gameの解釈
Inker：枝を短絡， Eraser：枝を除去，
Inkerの手番毎に頂点数減少（ループ？）．頂点が１つになれば
Inkerの勝利．グラフが非連結になればEraserの勝利．
証明：無向グラフGが枝素な全張木S,T を含むとする．
必勝戦略：Inker は，枝素な全張木を２つ保持し続ける．
（1）Eraser がS∪T外の枝を消したとき(略)
e
（２）Eraser がS中の枝を消したとき（略）
（３）Eraser がT中の枝eを消したとき
T1
T2
T-e は２つの部分木T1,T2 からなる
f
T1とT2をつなぐ枝ｆがS中に1本以上存在する．
Inker はｆを選んで短絡する．
最終的に頂点２つとその間の２本以上の平行辺となる．
Eraser が枝を消しても，Inkerが残った枝を短絡して勝利
11
Inker-Eraser Game の必勝法
Gameの解釈
Inker：枝を短絡， Eraser：枝を除去，
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が残った枝を短絡して勝利
12
Inker-Eraser Game と Connections
Connections
先手（黒）
後手（白）
Inker-Eraser
先手：Inker （短絡）
後手：Eraser （除去）
13
Inker-Eraser Game と Connections
Connections
先手（黒）
後手（白）
Inker-Eraser
先手：Inker （短絡）
後手：Eraser （除去）
性質：Inker-Eraser Game で Inker が勝てば，
Connectionsで先手が勝利している．
背理法で示す
（１）Connectionsで後手が上下をつないで勝利？
全張木無し⇒矛盾
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で先手が勝利している．
ゆえに，下記のグラフで，Inker 先手のInker-Eraser
Game で先手のInker が必勝戦略を持てば，
Connections で先手（黒）が必勝戦略を持つ．
定理[Lehman]
元のグラフGが，枝素な全張木を２つ含むならば，
Eraser が先手のInker-Eraser game は，
後手のInker に必勝手順がある．
16
Connections の必勝戦略
先手のInker は左上の枝を最初に短絡
得られたグラフは，枝素な全張木を２つ持つ
ここから，Eraser 先手，Inker 後手のInker-Eraser
Game を行う．
定理[Lehman]
元のグラフGが，枝素な
全張木を２つ含むならば，
Eraser が先手のInkerEraser game は，後手
のInker に必勝手順が
ある．
Inker は全張木を生成して勝利
→ 黒（先手）はConnections に勝利
17
END
18

Download Report