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

本発表の流れ ① ペアリング戦略とは ② シャノンスイッチングゲーム ③ 禁止対回避路問題 ④ 完全禁止対問題 NP完全 p2完全

ペアリング戦略

tic-tac-toe ルール N×N の盤面に２人のプレイヤーが 交互に○と×を置く 縦，横，斜めのいずれか一辺を 自分の石で独占したプレイヤーの勝ち N ¸ 5のとき，後手はペアリング戦略によって必ず引き分けに持ち込める

tic-tac-toeにおけるペアリング戦略 先手がここに置いたら･･･ 後手の戦略 先手が置いたマスの番号と 同じ番号のマスに置く　 11 1 8 12 6 2 9 10 3 7 4 5 どの辺を見ても同じ番号が２個あるため 先手は一辺を独占できない 後手はここに置く 後手は必ず引き分け以上に持ち込める

HEX 赤プレイヤーと青プレイヤーが自分の色でマスを交互に埋めていき，自分のsideをつなげたプレイヤーの勝ち red side blue side blue side red side 赤プレイヤーと青プレイヤーが自分の色でマスを交互に埋めていき，自分のsideをつなげたプレイヤーの勝ち　

HEX red side blue side blue side red side

HEXにおけるペアリング戦略 N×M ( M < N ) のHEXでは 自陣間の距離が短い方のプレイヤーに必勝戦略がある N マス 自陣間の距離が短い方のプレイヤーに必勝戦略がある　 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におけるペアリング戦略 赤プレイヤーは 青プレイヤーが置いたマスと 同じ番号のマスに赤石を置く 1 1 6 2 2 6 7 3 3 7 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

HEXの盤面のグラフ表現 より一般的なグラフでもペアリング戦略は有効か？ マス → 頂点 マス間の接続 → 辺 HEXの盤面と等価なグラフ 5 2 3 4 1 10 7 8 9 6 14 11 12 13 17 15 16 19 18 20 　　　　　　マス → 頂点 マス間の接続 → 辺 HEXの盤面と等価なグラフ より一般的なグラフでもペアリング戦略は有効か？

シャノンスイッチングゲーム G ［Even ら, 1976］ 2人のプレイヤーが交互に無向グラフG の頂点に石を置く 先手の目標：自分の石を通って s → t のパスを作る 後手の目標：先手のパス作成を阻止 G 2 7 1 t 8 3 s 9 5 4 10 6 『どちらのプレイヤーが勝つ？』・・・計算量はPSPACE完全 ［Even ら, 1976］

ペアリング戦略 G ペアリング戦略 頂点のペア（禁止対）の集合を作る 後手は、先手が石を置いた頂点とペアの頂点に石を置く 2 7 1 t 8 　　頂点のペア（禁止対）の集合を作る　 　　後手は、先手が石を置いた頂点とペアの頂点に石を置く G 2 7 1 t 8 3 s 9 5 4 10 6 禁止対集合 F = {{1, 8}, {2, 7}, {4, 5}, {3, 9}, {6, 10}}

ペアリング戦略 G Fパス s と t を結ぶ全てのパスが 必ず同じ色の頂点を通る ペアリング戦略が成功する （後手の勝ち） 2 7 1 t 　　（後手の勝ち） Fパス G 2 7 1 t 8 3 s 9 5 4 10 6 禁止対集合 F = {{1, 8}, {2, 7}, {4, 5}, {3, 9}, {6, 10}} ペアリング戦略を成功させるような禁止対集合・・・完全禁止対 (perfect forbidden pairs)

ペアリング戦略に関する諸定義 ∀{u, v}∈F，|{u, v}∩P |≦1 盤面のグラフをG = (V, E )，始点と終点を s, t ∈V，禁止対の集合F を P はF の各禁止対の2頂点のうち 高々1頂点だけを含む F ⊆{{u, v}⊂V-{s, t}| u≠v}（ただし∀A, B∈F，A∩B=φ） であるとする ∀{u, v}∈F，|{u, v}∩P |≦1 パスP がFパスである G上において，s,t 間を結ぶ 全てのパスがFパスでない F が完全禁止対である

ペアリング戦略の性質 相手による特定のパスの占有を阻止する戦略 最初に禁止対集合を決めてしまえば，あとは先手の手から 自動的に次の手が決まる 途中の盤面状況を調べる必要はなく，評価関数などもいらない 禁止対集合が完全禁止対であれば，後手必勝 どれくらいの計算量で決定可能だろう？

ペアリング戦略に関する諸定義 定理 [HAROLDら，1976] 定理 先手の戦略 禁止対回避路問題 　 入力：グラフG，始点s，終点t，禁止対集合F 　 出力：G 上にFパスがあるかどうか 定理　[HAROLDら，1976] 禁止対回避路問題はNP完全 後手の戦略 完全禁止対問題 　 入力：グラフG，始点s，終点t 　 出力：G が完全禁止対を持つかどうか 定理 P 完全禁止対問題はΣ2 完全

禁止対回避路問題 定理 [HAROLDら，1976] 〈証明〉 ① 禁止対回避路問題 ∈ NP ② 3SAT が禁止対回避路問題に帰着可能

禁止対回避路問題 CNFパート t 3SAT が禁止対回避路問題に帰着可能であることを示す 各頂点がリテラルを表す x3 x1 x4 x2

禁止対回避路問題 変数パート φ中の 　 の数 xi xi ・・・ xi xi xi ・・・ xi φ中の xi の数

禁止対回避路問題 変数パート x1 x2 x2 x2 x3 x3 x4 x4 s x1 x1 x2 x2 x3 x4 x4

禁止対回避路問題 s t 変数パート CNFパート 変数パートとCNFパートの間で，否定の関係にある2頂点を禁止対にする x1 x2 x2

禁止対回避路問題 s t x1 x2 x2 x2 x3 x3 x4 x4 x3 x1 x4 x2 x2 x2 x2 x3 x4 x3 x1

禁止対回避路問題 x1 = 1, x2 = 0, x3 = 1, x4 = 0 の場合，φ= 1 t s t xi = 0 を通過 φが充足可能　　　　　×を通らずに　　 に辿り着くパスがある t x1 x2 x2 x2 x3 x3 x4 x4 x3 x1 x4 x2 x2 s x2 x2 x3 x4 x3 t x1 x1 x2 x2 x3 x4 x4 x1 x4 x2 x1 x4 CNF式において 0 が割り当てられる リテラルの頂点に×がつく xi = 0 を通過 xi xi = 1 を通過 xi （×を通るパスはFパスではない）

禁止対回避路問題 定理 [HAROLDら，1976] 〈証明〉 ① 禁止対回避路問題 ∈ NP ② 3SAT が禁止対回避路問題に帰着可能

完全禁止対問題 定理 P 完全禁止対問題は∑2 完全 〈証明〉 NPNP ① 完全禁止対問題 ② QSAT2　が完全禁止対問題に帰着可能

完全禁止対問題 accept reject 入力:（G, s, t ） 完全禁止対問題 NPオラクル G 中にFパスは存在する？ （G, s, t, F ） 禁止対回避路問題 NPオラクル G 中にFパスは存在する？ reject （Fパスない） accept （Fパスある） accept reject

完全禁止対問題 定理 P 完全禁止対問題は∑2 完全 〈証明〉 ① 完全禁止対問題 ② QSAT2　が完全禁止対問題に帰着可能

完全禁止対問題の∑2P-完全性 x1= 0, x2= 0 のとき, Y の全ての割当てについてφ= 0 QSAT2 問題は 完全 QSAT2 　　入力：変数集合X，Y上のCNF式 　　出力：　　　　　　　　　　　　 かどうか X = {x1, x2}, Y = {y1, y2} 例. 定理 [Stockmeyer, 1977] QSAT2 問題は 完全 x1= 0, x2= 0 のとき, Y の全ての割当てについてφ= 0 　　　　からグラフを作成し 完全禁止対問題に帰着

QSAT2 からの帰着 からグラフ作成 xi ブロック φ中の 　 の数 xi ・・・ xi xi xi ・・・ xi φ中の xi の数

QSAT2 からの帰着 x1 x2 xm X パート s からグラフ作成 x1 x1 x2 x2 xm xm ・・・ x1 x1 x2 x2

QSAT2 からの帰着 yi Y パート からグラフ作成 yi yi yi yi yi yi φ中の の数 ・・・ ・・・ φ中の の数 yi yi ・・・ yi yi yi yi ・・・ yi φ中の yi の数

QSAT2 からの帰着 y1 y2 yn Y パート をグラフに変換 y1 y1 y2 y2 y3 yn yn ・・・・ y1 y1 y2

QSAT2 からの帰着 CNFパート t 3CNFであるとする をグラフに変換 ・・・・ 各頂点がリテラルを表す w11 w21 w31 wk1 w12 w22 w32 ・・・・ wk2 t w13 w23 w33 wk3 各頂点がリテラルを表す

QSAT2 からの帰着 をグラフに変換 CNFパート ・・・・ t

QSAT2 からの帰着 をグラフに変換 CNFパート ・・・・ t 各頂点から辺を伸ばす

QSAT2 からの帰着 s t X パート Y パート CNFパート X パート，Y パート，CNFパートを連結 x1 x2 x2 y1

QSAT2 からの帰着 s t X パート，Y パート，CNFパートを連結 （CNFパートの各リテラルから左上の3頂点への辺は省略） x1

QSAT2 からの帰着 s t X パートの頂点と終点 t を連結 x1 x2 x2 y1 y1 y2 y2 y2 x2 x1 x2 y1

QSAT2 からの帰着 s t X パートとCNFパートの間で否定の関係にある頂点を連結 x1 x2 x2 y1 y1 y2 y2 y2

QSAT2 からの帰着 s t xi ブロックの右下の頂点とCNFパートの頂点 xi を連結 x1 x2 x2 y1 y1 y2 y2 y2

QSAT2 からの帰着 s t Y パートとCNFパートの間で否定の関係にある頂点を連結 x1 x2 x2 y1 y1 y2 y2 y2

QSAT2 からの帰着 ∃禁止対集合F ∀s-t パスP , P はFパスでない s t xi への割当てを表す部分 y1 y1 y2 y2 y2 x2 x1 x2 y1 s y1 y2 y1 y1 y2 t x1 x1 x2 y1 y1 y1 y2 y2 x1 y1 x2 y2 x1 xi への割当てを表す部分 yi への割当てを表す部分 CNF式を表す部分 ∃禁止対集合F ∀s-t パスP , P はFパスでない

QSAT2 からの帰着 ∃禁止対集合F ∀s-t パスP , P はFパスでない s t x1 x1 x2 x2 y1 y1 y2 y2

QSAT2 からの帰着 ∃禁止対集合F ∀s-t パスP , P はFパスでない s t x1 x2 x2 y1 y1 y2 y2 y2

帰着の正当性 ∃禁止対集合F ∀s-t パスP , P はFパスでない xi への割当てにしたがって禁止対をつくる xi = 0 の場合 ・・・ xi xi ・・・ xi xi ・・・ xi xi ・・・ xi

QSAT2 からの帰着 ∃禁止対集合F ∀s-t パスP , P はFパスでない s t x1 = 0，x2 = 1 のとき y1 y1 y2 y2 y2 x2 x1 x2 y1 s y1 y2 y1 y1 y2 t x1 x1 x2 y1 y1 y1 y2 y2 x1 y1 x2 y2 x1 x1 = 0，x2 = 1 のとき 全てのY の割当てについてφ= 0

QSAT2 からの帰着 ∃禁止対集合F ∀s-t パスP , P はFパスでない s t 仮定より，かならず×が縦に3個並ぶ場所がある x1 x2 x2 y1 y1 y2 y2 y2 x2 x1 x2 y1 s y1 y2 y1 y1 y2 t x1 x1 x2 y1 y1 y1 y2 y2 x1 y1 x2 y2 x1 CNF式において 0 が割り当てられる リテラルの頂点に×がつく （×を通るパスはFパスではない）

帰着の正当性 ∃禁止対集合F ∀s-t パスP , P はFパスでない ∀禁止対集合F ∃s-t パスP , P はFパスである 対偶 どんな禁止対集合においても， G(φ)上に必ずFパスが存在

帰着の正当性 ∀禁止対集合F ∃s-t パスP , P はFパスである or ・・・ or ・・・ 正規の禁止対割当て ① XパートとCNFパート間で接続している頂点同士を禁止対 ② xiブロックの4頂点は以下のように禁止対を割り当てる ・・・ or ・・・ or ・・・ ③ YパートとCNFパート間で接続している頂点同士を禁止対 ④ CNFパートの最初の6頂点は縦に繋がっている頂点同士を禁止対

帰着の正当性 ∀禁止対集合F ∃s-t パスP , P はFパスである s t 正規の禁止対を割り当てると・・・ Fパスが存在 x1 x2 x2 y1 y1 y2 y2 y2 x2 x1 x2 y1 s y1 y2 y1 y1 y2 t x1 x1 x2 y1 y1 y1 y2 y2 x1 y1 x2 y2 x1

帰着の正当性 ∀禁止対集合F ∃s-t パスP , P はFパスである or ・・・ or ・・・ 正規の禁止対割当て ① XパートとCNFパート間で接続している頂点同士を禁止対 ② xiブロックの4頂点は以下のように禁止対を割り当てる ・・・ or ・・・ or ・・・ ③ YパートとCNFパート間で接続している頂点同士を禁止対 ④ CNFパートの最初の6頂点は縦に繋がっている頂点同士を禁止対

帰着の正当性 xi case.1 X パートとCNFパート間で接続している2頂点が禁止対でない場合 t xi xi xi ・・・ ・・・ 始点からここまでは 正規の禁止対であると仮定 xi xi ・・ xi xi ・・・ ・・・ ・・・ ・・・ ・・・ t xi ・・ xi xi

帰着の正当性 xi case.2 xi ブロックの4頂点に正規の禁止対が割り当てられていない場合 t xi xi xi ・・・ ・・・ 始点からここまでは 正規の禁止対であると仮定 xi xi ・・ xi xi ・・・ ・・・ ・・・ ・・・ ・・・ t xi ・・ xi xi

帰着の正当性 yi case.3 Y パートとCNFパート間で接続している2頂点が禁止対でない場合 t yi yi yi ・・・ ・・・ 始点からここまでは 正規の禁止対であると仮定 yi yi ・・・ yi yi ・・・ ・・・ ・・・ ・・・ t yi ・・・ yi yi

帰着の正当性 yi case.4 CNF パートの最初の6頂点が正規の禁止対でない場合 t yi yi yi ・・・ ・・・ ・・・ ・・・ 始点からここまでは 正規の禁止対であると仮定 yi yi ・・・ yi yi ・・・ ・・・ ・・・ ・・・ t yi ・・・ yi yi

帰着の正当性 ∀禁止対集合F ∃s-t パスP , P はFパスである は完全禁止対を持つ

完全禁止対問題の∑2P-完全性 定理 完全禁止対問題は∑2 完全 〈証明〉 ① 完全禁止対問題 ② QSAT2 が完全禁止対問題に帰着可能

まとめ 結果 今後の課題 シャノンスイッチングゲームにおいて，後手の戦略をペアリング戦略に 限定した場合の計算量 　　　　→ 先手はNP完全, 後手はΣ2完全 P （ペアリング戦略に限定しない場合はPSPACE完全） 今後の課題 平面グラフ上のゲームは？