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

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

Voronoi Game on Graph and its Complexity 寺本 幸生 上原 隆平 (JAIST)
 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
Probabilistic Method 7.7
ハノイグラフの生成と最短経路の導出 東京電機大学 理工学部 村田和也 松浦昭洋
アルゴリズムとデータ構造 2011年7月7日
2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
Problem H: Queen’s case
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
ゲーム理論・ゲーム理論Ⅰ (第4回) 第3章 完全情報の展開形ゲーム
算法数理工学 第9回 定兼 邦彦.
    有限幾何学        第8回.
半順序集合ゲーム周期性定理の拡張 京都大学情報学研究科 ○後藤順一 伊藤大雄.
    有限幾何学        第5回.
飛び越しゲーム 計算数理2演習 課題1 2011年度(阿原).
Probabilistic Method.
JAG Regional Practice Contest 2012 問題C: Median Tree
アルゴリズムとデータ構造 2012年7月23日
    有限幾何学        第12回.
    有限幾何学        第13回.
アルゴリズムとデータ構造 2011年7月14日
A path to combinatorics 第6章前半(最初-Ex6.5)
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
Probabilistic method 輪講 第7回
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
碁石ゲームに関する考察 4目並べ講座 パターン生成ゲームの楽しみ 徳山 豪 (東北大学) .
近畿大学理工学部情報学科 情報論理研究室 井藤 雄太
s a b f c e d 2016年度 有限幾何学 期末試験 問1:15点
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
A First Course in Combinatorial Optimization Chapter 3(前半)
アルゴリズムとデータ構造 2012年7月12日
研究集会「組合せゲーム・パズル」,豊橋技術科学大学
シャノンのスイッチングゲームにおけるペアリング戦略について
シャノンのスイッチングゲームにおけるペアリング戦略の複雑さについて
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
平行四辺形の性質の逆 ~四角形が平行四辺形になる条件~ 練習問題
Bridge It と Connections の 必勝法について
算法数理工学 第8回 定兼 邦彦.
情報論理工学 研究室 第10回 完全解析されたゲーム.
佐藤のゲーム とその仲間たち (完全可解ゲームの話) 関西学院大学  川中 宣明 数理科学研究センター談話会    2011年6月29日.
Probabilistic Method 2007/11/02 岩間研究室M1 市場孝之.
7.4 Two General Settings D3 杉原堅也.
リーダー 亀山奈央 プレゼンター 橘貴志 アルゴリズム 古森愛美 プログラマー 中島宏基 パワーポイント 公文ゆい
G班メンバー リーダー 橋本望 SE 北本理紗と服部友哉 PPT作成 橋本望と山田侑加
京都大学大学院情報学研究科 宮川博光 伊藤大雄
b f c a d e g h a b c d e f g 図1 図2 2012年度 有限幾何学 期末試験
近畿大学理工学部情報学科 情報論理研究室 松浦 美里
離散数学 07. 木 五島.
Structural operational semantics
目標 問題を証明するために、中点連結定理を使うことができる!!
7 Calculating in Two Ways: Fubini’s Principle
5 Recursions 朴大地.
中点連結定理 本時の目標 「中点連結定理を理解する。」
色塗りゲームとゲームカラーリング数 慶應義塾大学大学院 理工学研究科   関口 陽介.
モンテカルロ法を用いた 立体四目並べの対戦プログラム
2016年度 有限幾何学 中間試験 問1 次のグラフを描け.(描けない場合は理由を述べよ) 各20点
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
第4章 データ構造 p.82 [誤] ハミルトニアン経路問題  [正] ハミルトン閉路問題 p.82,83 [誤] セールスパーソン問題
    有限幾何学        第5回.
F班 メンバー 班長 雨堤 智宏 アルゴリズム解析 角田 泰彬 竹林 秀高 ppt作成 清水 貴史
2009/11/27 グラフ (1) 第9講: 平成21年11月27日 (金) 4限 E252教室 コンピュータアルゴリズム.
d b c e a f 年度 有限幾何学 中間試験 問1 次の用語の定義をそれぞれ述べよ.
2017年度 有限幾何学 期末試験 注意:ループと多重辺がないグラフのみを扱う. 問1 次の定理と,その証明の概略を読み,各問に答えよ.
Othello G班         山崎 木下 山本 上手      .
情報論理工学 研究室 第8回: ミニマックス法.
4 図形の調べ方 1章 平行と合同 §3 三角形の合同         (2時間).
問2 次の問に答えよ. (ただし,握手補題,オイラーの定理,Oreの定理 は授業で紹介したものとする) (1) 握手補題を書け.
図2 x11 図1 x6 x10 x12 x3 x5 x7 x9 x13 x2 x4 x8 x14 (0,0) (1,0) x1 x15
人工知能概論 第4回 探索(3) ゲームの理論.
数学 A 3章 「図形の性質」 1節 三角形の性質.
Presentation transcript:

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