シャノンのスイッチングゲームにおけるペアリング戦略について 東北大学 情報科学研究科 ○高橋 良介，瀧本 英二

発表の流れ ① tic-tac-toeゲーム ② ペアリング戦略について ③ HEXゲーム ④ シャノンスイッチングゲーム ⑤ PATH-WITH-FP問題のNP完全性 ⑥ 今後の課題

tic-tac-toeゲーム tic-tac-toe とは？ の盤面に2人のプレイヤーが 交互に○と×を置く 縦，横，斜めのいずれか一辺を 自分の石で独占したプレイヤーの勝ち

tic-tac-toeにおけるペアリング戦略 N ≧4 の場合 後手側は必ず引き分け以上にできる 後手の戦略： 　　先手が置いたマス番号と 　　同じ番号のマスに置く 11 1 8 12 6 2 9 10 3 7 4 5 全ての辺に同じ番号が2個あるため 先手は一辺を独占できない ペアリング戦略 先手が番号の付いていないマスに置いた場合 後手は適当なマスに置けばよい これによってペアリング戦略が崩れることはない

完全禁止対 同じ番号が振られているマスのペア・・・禁止対（forbidden pair） ペアリング戦略を成功させるような 禁止対の割当て 11 1 8 12 6 2 9 10 3 7 4 5 ・・・完全禁止対（perfect forbidden pairs）

完全禁止対の定義 禁止対の集合をP ，盤面のマス（頂点）の集合をV とする P = { (p1, q1) ,･･･, (pk , qk) } (1≦k ≦ ) pi , qi ∈V (1≦i≦k) ただし，全ての頂点がdisjointであるとする どのwinning pathも必ず P 中のある禁止対 pi , qiを含む P が完全禁止対である

HEXゲーム red side blue side red player と blue player が自分の色でマスを交互に埋めていき 自分のsideをつなげたplayerが勝ち blue side red side

HEXゲーム red side blue side blue side red side

HEXの性質 引き分けはない 初期盤面では先手がwinning strategyを持つ 任意の盤面で，winning strategyを持つplayerを決定する問題 ・・・・PSPACE-complete

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）マス

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度までしか通らないパスが存在すると仮定

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の盤面と等価なグラフ より一般的なグラフでもペアリング戦略は有効か？

シャノンのスイッチングゲーム G shannon vertex switching game 2人のプレイヤーが交互に無向グラフG =（V ,E ）の頂点を確保 先手の目標： s → t のパスを作る 後手の目標：先手のパス作成を阻止 G t s

シャノンのスイッチングゲーム G shannon vertex switching game どちらのプレイヤーにwinning strategyがあるか決定する問題 ・・・・PSPACE-complete G t s

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) とする

PERFECT-FP問題 accept reject 入力:（G, s, t ） PERFECT-FP （G, s, t, P） 禁止対の割当てを非決定的に生成 PATH-WITH-FP accept reject （G, s, t, P） accept reject

PATH-WITH-FPのNP完全性 定理： PATH-WITH-FP はNP完全である ［HAROLDら，1976］ 多項式時間 ① 非決定的にs-t間のパスを選ぶ ② そのパスが禁止対の頂点を両方通るかどうかを調べる 通らないなら受理，そうでなければ非受理 非決定性多項式時間で終了するので PATH-WITH-FP∈NP である

PATH-WITH-FPのNP完全性 定理： PATH-WITH-FP はNP完全である ［HAROLDら，1976］ ２．『PATH-WITH-FP はNP-hard 』 の証明 3SAT から PATH-WITH-FP へ帰着

PATH-WITH-FPのNP完全性 変換 s t ノード をそれぞれm個に ノード をそれぞれn個に分身させる CNF式に　 がn個， がm個ある

PATH-WITH-FPのNP完全性 s t ノード　をそれぞれm個に ノード　をそれぞれn個に分身させる CNF式に　 がn個， がm個ある

PATH-WITH-FPのNP完全性 s t 変数 x と を禁止対とする 全ての x と の組み合わせをカバーするように禁止対を割り当てる

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完全（証明終）

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

今後の課題 PERFECT-FP問題の計算量は？ ペアリング戦略が可能なグラフにはどのようなものがあるか？ 例. series-parallel graph