Document

シャノンのスイッチングゲームにおける
ペアリング戦略の複雑さについて
東北大学情報科学研究科
高橋良介
瀧本英二
本発表の流れ
① ペアリング戦略とは
② シャノンスイッチングゲーム
③ 禁止対回避路問題
NP完全
④ 完全禁止対問題
p2完全
ペアリング戦略
tic-tac-toe
ルール
N×N の盤面に２人のプレイヤーが
交互に○と×を置く
縦，横，斜めのいずれか一辺を
自分の石で独占したプレイヤーの勝ち
N ¸ 5のとき，後手はペアリング戦略に
よって必ず引き分けに持ち込める
tic-tac-toeにおけるペアリング戦略
ペアリング戦略
先手がここに
置いたら･･･
後手の戦略
先手が置いたマスの番号と
同じ番号のマスに置く
どの辺を見ても同じ番号が２個あるため
先手は一辺を独占できない
後手は必ず引き分け以上に持ち込める
11 1
8
1 12
6
2
9 10
2
3後手はここ
7
6
に置く
9
3
7
4
4 10
12 5
8
5 11
HEX
red side
blue side
blue side
red side
赤プレイヤーと青プレイヤーが自分の色でマスを交互に
埋めていき，自分のsideをつなげたプレイヤーの勝ち
HEX
red side
blue side
blue side
red side
HEXにおけるペアリング戦略
N×M ( M < N ) のHEXでは
自陣間の距離が短い方のプレイヤーに必勝戦略がある
0
1
0
6
1
6
2
7
3
8
4
9
5
10
11
12
14
12
15
17
5
9
16
18
4
13
18
19
3
8
15
16
10
14
17
19
20
20
（N－1）マス
7
11
13
2
N マス
HEXにおけるペアリング戦略
5
4
10
3
9
14
2
8
13
17
1
7
12
16
19
0
6
11
15
18
20
0
6
11
15
18
20
1
7
12
16
19
2
8
13
17
赤プレイヤーは
青プレイヤーが置いたマスと
同じ番号のマスに赤石を置く
3
9
14
4
10
5
青プレイヤーはパスを作る際
同じ番号のマスを必ず通る
赤プレイヤーは必ず勝つ！
HEXの盤面のグラフ表現
5
4
10
3
9
14
2
8
13
17
1
7
12
16
19
0
6
11
15
18
20
0
6
11
15
18
20
1
7
12
16
19
2
3
8
13
17
9
14
4
10
5
マス → 頂点
マス間の接続 → 辺
HEXの盤面と等価なグラフ
より一般的なグラフでもペアリング戦略は有効か？
シャノンスイッチングゲーム
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
3
s
9
5
4
10
6
禁止対集合 F = {{1, 8}, {2, 7}, {4, 5}, {3, 9}, {6, 10}}
ペアリング戦略
s と 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)
ペアリング戦略に関する諸定義
盤面のグラフをG = (V, E )，始点と終点を s, t ∈V，禁止対の集合F を
P はF の各禁止対の2頂点のうち
高々1頂点だけを含む
F ⊆{{u, v}⊂V-{s, t}| u≠v}（ただし∀A, B∈F，A∩B=φ）であるとする
パスP がFパスである
F が完全禁止対である
∀{u, v}∈F，|{u, v}∩P |≦1
G上において，s,t 間を結ぶ
全てのパスがFパスでない
ペアリング戦略の性質
相手による特定のパスの占有を阻止する戦略
最初に禁止対集合を決めてしまえば，あとは先手の手から
自動的に次の手が決まる
途中の盤面状況を調べる必要はなく，評価関数などもいらない
禁止対集合が完全禁止対であれば，後手必勝
どれくらいの計算
量で決定可能だろ
う？
ペアリング戦略に関する諸定義
先手の戦略
禁止対回避路問題
入力：グラフG，始点s，終点t，禁止対集合F
出力：G 上にFパスがあるかどうか
定理 [HAROLDら，1976]
禁止対回避路問題はNP完全
後手の戦略
完全禁止対問題
入力：グラフG，始点s，終点t
出力：G が完全禁止対を持つかどうか
定理
P
完全禁止対問題はΣ2 完全
禁止対回避路問題
定理 [HAROLDら，1976]
禁止対回避路問題はNP完全
〈証明〉
① 禁止対回避路問題 ∈ NP
② 3SAT が禁止対回避路問題に帰着可能
禁止対回避路問題
3SAT が禁止対回避路問題に帰着可能であることを示す
  ( x3  x2  x1 )  ( x1  x2  x4 )  ( x4  x3  x2 )  ( x2  x4  x1 )  ( x2  x3  x4 )
CNFパート
x3
x1
x4
x2
x2
x2
x2
x3
x4
x3
x1
x4
x2
x1
x4
各頂点がリテラルを表す
t
禁止対回避路問題
  ( x3  x2  x1 )  ( x1  x2  x4 )  ( x4  x3  x2 )  ( x2  x4  x1 )  ( x2  x3  x4 )
変数パート
φ中の
xの数
i
xi
xi
・・・
xi
xi
xi
・・・
xi
φ中の xi の数
禁止対回避路問題
  ( x3  x2  x1 )  ( x1  x2  x4 )  ( x4  x3  x2 )  ( x2  x4  x1 )  ( x2  x3  x4 )
変数パート
x1
x2
x2
x2
x3
x3
x4
x4
x4
x4
s
x1
x1
x2
x2
x3
禁止対回避路問題
  ( x3  x2  x1 )  ( x1  x2  x4 )  ( x4  x3  x2 )  ( x2  x4  x1 )  ( x2  x3  x4 )
G( )
x1
x2
x2 x2
x3 x3
x4
x4
s
x1 x1
変数パート
x2
x2
x3
x4
x4
x3
x1
x4
x2
x2
x2
x2
x3
x4
x3
x1
x4
x2
x1
x4
t
CNFパート
変数パートとCNFパートの間で，否定の関係にある2頂点を禁止対にする
禁止対回避路問題
  ( x3  x2  x1 )  ( x1  x2  x4 )  ( x4  x3  x2 )  ( x2  x4  x1 )  ( x2  x3  x4 )
G( )
x1
x2
x2 x2
x3 x3
x4
x4
s
x1
x1
x2
x2
x3
x4
x4
x3
x1
x4
x2
x2
x2
x2
x3
x4
x3
x1
x4
x2
x1
x4
t
禁止対回避路問題
  ( x3  x2  x1 )  ( x1  x2  x4 )  ( x4  x3  x2 )  ( x2  x4  x1 )  ( x2  x3  x4 )
x1 = 1, x2 = 0, x3 = 1, x4 = 0 の場合，φ= 1
φが充足可能
x1
x2
×を通らずに
x2 x2
x3 x3
x4
x4
s
x1
x1
x2
x2
x3
x4
x4
t に辿り着くパスがある
x3
x1
x4
x2
x2
x2
x2
x3
x4
x3
x1
x4
x2
x1
x4
t
xi = 0
xi を通過
CNF式において 0 が割り当てられる
リテラルの頂点に×がつく
xi = 1
xi を通過
（×を通るパスはFパスではない）
禁止対回避路問題
定理 [HAROLDら，1976]
禁止対回避路問題はNP完全
〈証明〉
① 禁止対回避路問題 ∈ NP
② 3SAT が禁止対回避路問題に帰着可能
完全禁止対問題
定理
P
完全禁止対問題は∑2 完全
〈証明〉
① 完全禁止対問題

P
2
NPN
P
② QSAT2 が完全禁止対問題に帰着可能
完全禁止対問題
入力:（G, s, t ）
完全禁止対問題
禁止対の集合F を非決定的に生成
（G, s, t, F ）
禁止対回避路問題
NPオラクル
G 中にFパスは存在する？
reject
accept
（Fパスない）
（Fパスある）
accept
reject
完全禁止対問題
定理
P
完全禁止対問題は∑2 完全
〈証明〉
① 完全禁止対問題
 2P
② QSAT2 が完全禁止対問題に帰着可能
完全禁止対問題の∑2P-完全性
QSAT2
入力：変数集合X，Y上のCNF式  ( X , Y )
出力：  X Y , ( X , Y )  0 かどうか
X = {x1, x2}, Y = {y1, y2}
例.
 ( X , Y )  ( x1  x2 )  ( x1  y1  y2 )  ( x1  y2 )  ( x2  y1 )
定理 [Stockmeyer
x1= 0, x,21977
= 0 ]のとき, Y の全ての割当てについてφ= 0
( X ,Y ) 
P QSAT2
QSAT2 問題は 2 完全
 ( X , Y ) からグラフを作成し
完全禁止対問題に帰着
QSAT2 からの帰着
 ({x1,, xm},{ y1,, yn })
からグラフ作成
xi ブロック
φ中の x iの数
xi
・・・
xi
xi
xi
・・・
φ中の xi の数
xi
QSAT2 からの帰着
 ({x1,, xm},{ y1,, yn })
からグラフ作成
X パート
x1
・・
x1
x2
・・
x2
x1
s
x1
・・
x1
x2
x2
・・
x2
xm
・・
xm
xm
・・・
xm
・・
xm
QSAT2 からの帰着
 ({x1,, xm},{ y1,, yn })
Y パート
φ中の
yi
からグラフ作成
yの数
i
yi
・・・
yi
・・・
yi
yi
yi
yi
φ中の yi の数
QSAT2 からの帰着
 ({x1,, xm},{ y1,, yn })
をグラフに変換
Y パート
y1
・・・
y1
y2
y1
y1
・・・
・・・
y2
y2
y1
y2
・・・
yn
y3
y3
yn
yn
・・・・
y2
・・・
yn
・・・
yn
QSAT2 からの帰着
3CNFであるとする
 ({x1,, xm},{ y1,, yn })
をグラフに変換
CNFパート
w11
w21
w31
w12
w22
w32
w13
w23
w33
wk1
・・・・
各頂点がリテラルを表す
wk2
wk3
t
QSAT2 からの帰着
 ({x1,, xm},{ y1,, yn })
をグラフに変換
CNFパート
・・・・
t
QSAT2 からの帰着
 ({x1,, xm},{ y1,, yn })
をグラフに変換
CNFパート
・・・・
各頂点から辺を伸ばす
t
QSAT2 からの帰着
  ( y1  y2  x1)  ( x2  y2  y1)  ( x1  y1  x2 )  ( x2  y1  y2 )  ( y1  y2  x1)
x1
x2 x2
y1
y1
y2
y2
s
x1
x1
X パート
x2
y1 y1
y1
y2 y2
Y パート
X パート，Y パート，CNFパートを連結
y2
x2
x1
x2
y1
y1
y2
y1
y1
y2
x1
y1
x2
y2
x1
CNFパート
t
QSAT2 からの帰着
  ( y1  y2  x1)  ( x2  y2  y1)  ( x1  y1  x2 )  ( x2  y1  y2 )  ( y1  y2  x1)
（CNFパートの各リテラルから左上の3頂点への辺は省略）
x1
x2 x2
y1
y1
y2
y2
s
x1
x1
x2
y1 y1
y1
y2 y2
X パート，Y パート，CNFパートを連結
y2
x2
x1
x2
y1
y1
y2
y1
y1
y2
x1
y1
x2
y2
x1
t
QSAT2 からの帰着
  ( y1  y2  x1)  ( x2  y2  y1)  ( x1  y1  x2 )  ( x2  y1  y2 )  ( y1  y2  x1)
x1
x2 x2
y1
y1
y2
y2
s
x1
x1
x2
y1 y1
y1
y2 y2
X パートの頂点と終点 t を連結
y2
x2
x1
x2
y1
y1
y2
y1
y1
y2
x1
y1
x2
y2
x1
t
QSAT2 からの帰着
  ( y1  y2  x1)  ( x2  y2  y1)  ( x1  y1  x2 )  ( x2  y1  y2 )  ( y1  y2  x1)
x1
x2 x2
y1
y1
y2
y2
s
x1
x1
x2
y1 y1
y1
y2 y2
y2
x2
x1
x2
y1
y1
y2
y1
y1
y2
x1
y1
x2
y2
x1
X パートとCNFパートの間で否定の関係にある頂点を連結
t
QSAT2 からの帰着
  ( y1  y2  x1)  ( x2  y2  y1)  ( x1  y1  x2 )  ( x2  y1  y2 )  ( y1  y2  x1)
x1
x2 x2
y1
y1
y2
y2
s
x1
x1
x2
y1 y1
y1
y2 y2
y2
x2
x1
x2
y1
y1
y2
y1
y1
y2
x1
y1
x2
y2
x1
xi ブロックの右下の頂点とCNFパートの頂点 xi を連結
t
QSAT2 からの帰着
  ( y1  y2  x1)  ( x2  y2  y1)  ( x1  y1  x2 )  ( x2  y1  y2 )  ( y1  y2  x1)
x1
x2 x2
y1
y1
y2
y2
s
x1
x1
x2
y1 y1
y1
y2 y2
y2
x2
x1
x2
y1
y1
y2
y1
y1
y2
x1
y1
x2
y2
x1
Y パートとCNFパートの間で否定の関係にある頂点を連結
t
QSAT2 からの帰着
  ( y1  y2  x1)  ( x2  y2  y1)  ( x1  y1  x2 )  ( x2  y1  y2 )  ( y1  y2  x1)
G ' ( )
x1
x2 x2
y1
y1
y2
y2
s
x1
x1
x2
xi への割当てを表す部分

X Y , ( X ,Y )  0
y1 y1
y1
y2 y2
yi への割当てを表す部分
y2
x2
x1
x2
y1
y1
y2
y1
y1
y2
x1
y1
x2
y2
x1
CNF式を表す部分
∃禁止対集合F ∀s-t パスP , P はFパスでない
t
QSAT2 からの帰着

X Y , ( X ,Y )  0
∃禁止対集合F ∀s-t パスP , P はFパスでない
G ' ( )
x1
x2 x2
y1
y1
y2
y2
s
x1
x1
x2
y1 y1
y1
y2 y2
y2
x2
x1
x2
y1
y1
y2
y1
y1
y2
x1
y1
x2
y2
x1
t
QSAT2 からの帰着

X Y , ( X ,Y )  0
∃禁止対集合F ∀s-t パスP , P はFパスでない
G ' ( )
x1
x2 x2
y1
y1
y2
y2
s
x1
x1
x2
y1 y1
y1
y2 y2
y2
x2
x1
x2
y1
y1
y2
y1
y1
y2
x1
y1
x2
y2
x1
t
帰着の正当性

X Y , ( X ,Y )  0
∃禁止対集合F ∀s-t パスP , P はFパスでない
xi への割当てにしたがって禁止対をつくる
xi = 0 の場合
t
xi = 1 の場合
t
xi
・・・
xi
xi
・・・
xi
xi
・・・
xi
xi
・・・
xi
QSAT2 からの帰着

X Y , ( X ,Y )  0
∃禁止対集合F ∀s-t パスP , P はFパスでない
G ' ( )
x1
x2 x2
y1
y1
y2
y2
s
x1
x1
x2
y1 y1
y1
y2 y2
y2
x2
x1
x2
y1
y1
y2
y1
y1
y2
x1
y1
x2
y2
x1
t
  ( x1  y1  y2 )  ( y1  y2  x2 )  ( x2  y1  x1)  ( x2  y1  y2 )  ( x1  y2  y1)
x1 = 0，x2 = 1 のとき   ( y1  y2 )  ( y1  y2 )  ( y2  y1)  ( y2  y1)
全てのY の割当てについてφ= 0
QSAT2 からの帰着

X Y , ( X ,Y )  0
∃禁止対集合F ∀s-t パスP , P はFパスでない
仮定より，かならず×が縦に3個並ぶ場所がある
Fパスは存在しない
G ' ( )
x1
x2 x2
y1
y1
y2
y2
s
x1
x1
x2
y1 y1
y1
y2 y2
y2
x2
x1
x2
y1
y1
y2
y1
y1
y2
x1
y1
x2
y2
x1
t
CNF式において 0 が割り当てられる
リテラルの頂点に×がつく
（×を通るパスはFパスではない）
帰着の正当性

X Y , ( X ,Y )  0
∃禁止対集合F ∀s-t パスP , P はFパスでない
対偶

X Y , ( X ,Y )  1
∀禁止対集合F ∃s-t パスP , P はFパスである
どんな禁止対集合においても，
G(φ)上に必ずFパスが存在
帰着の正当性

X Y , ( X ,Y )  1
∀禁止対集合F ∃s-t パスP , P はFパスである
正規の禁止対割当て
① XパートとCNFパート間で接続している頂点同士を禁止対
② xiブロックの4頂点は以下のように禁止対を割り当てる
・・・
or
・・・
or
・・・
③ YパートとCNFパート間で接続している頂点同士を禁止対
④ CNFパートの最初の6頂点は縦に繋がっている頂点同士を禁止対
帰着の正当性

X Y , ( X ,Y )  1
∀禁止対集合F ∃s-t パスP , P はFパスである
正規の禁止対を割り当てると・・・
 1
Fパスが存在
『それ以外の禁止対を割り当てると，必ずFパスが存在』することを証明
G ' ( )
x1
x2 x2
y1
y1
y2
y2
s
x1
x1
x2
y1 y1
y1
y2 y2
y2
x2
x1
x2
y1
y1
y2
y1
y1
y2
x1
y1
x2
y2
x1
t
帰着の正当性

X Y , ( X ,Y )  1
∀禁止対集合F ∃s-t パスP , P はFパスである
正規の禁止対割当て
① XパートとCNFパート間で接続している頂点同士を禁止対
② xiブロックの4頂点は以下のように禁止対を割り当てる
・・・
or
・・・
or
・・・
③ YパートとCNFパート間で接続している頂点同士を禁止対
④ CNFパートの最初の6頂点は縦に繋がっている頂点同士を禁止対
帰着の正当性
case.1 X パートとCNFパート間で接続している2頂点が禁止対でない場合
始点からここまでは
正規の禁止対であると仮定
xi
・・
xi
・・・
xi
・・
xi
xi
・・・
xi
・・・
・・・
・・・
xi
t
帰着の正当性
case.2 xi ブロックの4頂点に正規の禁止対が割り当てられていない場合
始点からここまでは
正規の禁止対であると仮定
xi
・・
xi
・・・
xi
・・
xi
xi
・・・
xi
・・・
・・・
・・・
xi
t
帰着の正当性
case.3 Y パートとCNFパート間で接続している2頂点が禁止対でない場合
始点からここまでは
正規の禁止対であると仮定
yi
・・・
yi
yi
・・・
yi
yi
・・・
yi
・・・
・・・
・・・
yi
t
帰着の正当性
case.4 CNF パートの最初の6頂点が正規の禁止対でない場合
始点からここまでは
正規の禁止対であると仮定
yi
・・・
yi
yi
・・・
yi
yi
・・・
yi
・・・
・・・
・・・
yi
t
帰着の正当性
φ= 1 で，正規の禁止対集合が割り当てられた場合・・・・・ Fパスが存在
正規でない禁止対集合が割り当てられた場合・・・・・ Fパスが存在

X Y , ( X ,Y )  1

X Y , ( X ,Y )  0
∀禁止対集合F ∃s-t
パスP , P はFパスである
G ' ( ) は完全禁止対を持つ
完全禁止対問題の∑2P-完全性
定理
P
完全禁止対問題は∑2 完全
〈証明〉
① 完全禁止対問題  2
P
② QSAT2 が完全禁止対問題に帰着可能
まとめ
結果
シャノンスイッチングゲームにおいて，後手の戦略をペアリング戦略に
限定した場合の計算量
→ 先手はNP完全, 後手はΣ2P完全
（ペアリング戦略に限定しない場合はPSPACE完全）
今後の課題
平面グラフ上のゲームは？

Download Report