Download presentation
Presentation is loading. Please wait.
1
シャノンのスイッチングゲームにおけるペアリング戦略について
東北大学 情報科学研究科 ○高橋 良介，瀧本 英二
2
発表の流れ ① tic-tac-toeゲーム ② ペアリング戦略について ③ HEXゲーム ④ シャノンスイッチングゲーム
⑤ PATH-WITH-FP問題のNP完全性 ⑥ 今後の課題
3
tic-tac-toeゲーム tic-tac-toe とは？ の盤面に2人のプレイヤーが 交互に○と×を置く 縦，横，斜めのいずれか一辺を
自分の石で独占したプレイヤーの勝ち
4
tic-tac-toeにおけるペアリング戦略
N ≧4 の場合 後手側は必ず引き分け以上にできる 後手の戦略： 先手が置いたマス番号と 同じ番号のマスに置く 11 1 8 12 6 2 9 10 3 7 4 5 全ての辺に同じ番号が2個あるため 先手は一辺を独占できない ペアリング戦略 先手が番号の付いていないマスに置いた場合 後手は適当なマスに置けばよい これによってペアリング戦略が崩れることはない
5
完全禁止対 同じ番号が振られているマスのペア・・・禁止対（forbidden pair） ペアリング戦略を成功させるような 禁止対の割当て
11 1 8 12 6 2 9 10 3 7 4 5 ・・・完全禁止対（perfect forbidden pairs）
6
完全禁止対の定義 禁止対の集合をP ，盤面のマス（頂点）の集合をV とする
P = { (p1, q1) ,･･･, (pk , qk) } (1≦k ≦ ) pi , qi ∈V (1≦i≦k) ただし，全ての頂点がdisjointであるとする どのwinning pathも必ず P 中のある禁止対 pi , qiを含む P が完全禁止対である
7
HEXゲーム red side blue side red player と blue player が自分の色でマスを交互に埋めていき
自分のsideをつなげたplayerが勝ち blue side red side
8
HEXゲーム red side blue side blue side red side
9
HEXの性質 引き分けはない 初期盤面では先手がwinning strategyを持つ
任意の盤面で，winning strategyを持つplayerを決定する問題 ・・・・PSPACE-complete
10
HEXにおけるペアリング戦略 の盤面 N マス （N－1）マス 1 1 6 2 2 6 7 3 3 7 11 8 4 4 8 11 12 9
1 1 6 2 2 6 7 3 3 7 11 8 4 4 8 11 12 9 5 5 9 12 15 13 10 10 13 15 16 14 14 16 18 17 17 18 19 19 20 20 N マス （N－1）マス
11
HEXにおけるペアリング戦略 の盤面 red playerは blue playerが置いたマスと 同じ番号のマスに赤石を置く
1 1 6 2 仮定に反する！ 2 6 7 3 3 7 11 8 4 4 8 11 12 9 5 blue player はパスを作る際 同じ番号のマスを必ず通る 5 9 12 15 13 10 10 13 15 16 14 14 16 18 17 17 18 19 19 20 red playerは必ず勝つ！ 20 同じ番号を1度までしか通らないパスが存在すると仮定
12
HEXのグラフによる表現 HEXの盤面と等価なグラフ より一般的なグラフでもペアリング戦略は有効か？ 5 2 3 4 1 10 7 8 9
10 7 8 9 6 14 11 12 13 17 15 16 19 18 20 HEXの盤面と等価なグラフ より一般的なグラフでもペアリング戦略は有効か？
13
シャノンのスイッチングゲーム G shannon vertex switching game
2人のプレイヤーが交互に無向グラフG =（V ,E ）の頂点を確保 先手の目標： s → t のパスを作る 後手の目標：先手のパス作成を阻止 G t s
14
シャノンのスイッチングゲーム G shannon vertex switching game
どちらのプレイヤーにwinning strategyがあるか決定する問題 ・・・・PSPACE-complete G t s
15
PERFECT-FP問題 PERFECT-FP ={(G, s, t ) | G has perfect forbidden pairs}
後手の戦略に対応 次のような問題を考える PERFECT-FP ={(G, s, t ) | G has perfect forbidden pairs} ただし G = (V, E) ，始点をs，終点をt とする 先手の戦略に対応 PATH-WITH-FP ={(G, s, t, P ) | G has a path from s to t that contains at most one vertex from each pair in P} ただし P = { (p1, q1) ,･･･, (pk , qk) } (1≦k ≦ ) , 与えられた禁止対の割当てが perfect forbidden pairs でないかどうか pi , qi ∈V (1≦i≦k) とする
16
PERFECT-FP問題 accept reject 入力:（G, s, t ） PERFECT-FP （G, s, t, P）
禁止対の割当てを非決定的に生成 PATH-WITH-FP accept reject （G, s, t, P） accept reject
17
PATH-WITH-FPのNP完全性 定理： PATH-WITH-FP はNP完全である ［HAROLDら，1976］
多項式時間 ① 非決定的にs-t間のパスを選ぶ ② そのパスが禁止対の頂点を両方通るかどうかを調べる 通らないなら受理，そうでなければ非受理 非決定性多項式時間で終了するので PATH-WITH-FP∈NP である
18
PATH-WITH-FPのNP完全性 定理： PATH-WITH-FP はNP完全である ［HAROLDら，1976］
２．『PATH-WITH-FP はNP-hard 』 の証明 3SAT から PATH-WITH-FP へ帰着
19
PATH-WITH-FPのNP完全性 変換 s t ノード をそれぞれm個に ノード をそれぞれn個に分身させる
CNF式に がn個， がm個ある
20
PATH-WITH-FPのNP完全性 s t ノード をそれぞれm個に ノード をそれぞれn個に分身させる CNF式に がn個， がm個ある
21
PATH-WITH-FPのNP完全性 s t 変数 x と を禁止対とする 全ての x と の組み合わせをカバーするように禁止対を割り当てる
22
PATH-WITH-FPのNP完全性 s t CNF式の変数 xi に 1が割り当てられる s-t間のパスが ノード xi を通る
φがsatisfiable s-t間に，どの禁止対も同時に 通らないパスが存在 PATH-WITH-FP であるので 例 x1 = 1, x2 = 0, x3 = 1, x4 = 0 の場合，φ= 1 PATH-WITH-FP はNP完全（証明終）
23
PERFECT-FP問題 PERFECT-FP∈NPNP accept reject 入力:（G, s, t ） PERFECT-FP
禁止対の割当てを非決定的に生成 PATH-WITH-FP accept reject （G, s, t, P） PERFECT-FP∈NPNP NPオラクル accept reject
24
今後の課題 PERFECT-FP問題の計算量は？ ペアリング戦略が可能なグラフにはどのようなものがあるか？
例. series-parallel graph
Similar presentations
