パリティゲームを解く再帰的なアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/11/21 13:23 UTC 版)
「パリティゲーム」の記事における「パリティゲームを解く再帰的なアルゴリズム」の解説
パリティゲームを解くための再帰的なアルゴリズムが、Zielonkaにより説明されている。 G = ( V , V 0 , V 1 , E , Ω ) {\displaystyle G=(V,V_{0},V_{1},E,\Omega )} をパリティゲームとする。ここで、 V 0 {\displaystyle V_{0}} と V 1 {\displaystyle V_{1}} はそれぞれプレイヤー0とプレイヤー1の手番になるノードの集合、 V = V 0 ∪ V 1 {\displaystyle V=V_{0}\cup V_{1}} はノード全体の集合、 E ⊆ V × V {\displaystyle E\subseteq V\times V} は辺の集合、 Ω : V → N {\displaystyle \Omega :V\rightarrow \mathbb {N} } は優先度を割り当てる関数とする。 Eはtotalであるとする。つまり、どのノードからも1本以上の辺が出ていると仮定する。 Zielonkaのアルゴリズムはアトラクタの概念に基づいている。 U ⊆ V {\displaystyle U\subseteq V} をノードの集合とし、 i = 0 , 1 {\displaystyle i=0,1} をプレイヤーの番号とする。Uのi-アトラクタ A t t r i ( U ) {\displaystyle Attr_{i}(U)} とは、プレイヤー(1-i)の選択にかかわらず有限回でUに到達するようプレイヤーiが誘導できるようなノードの集合である。これは以下のような不動点計算により定義できる: A t t r i ( U ) 0 := U A t t r i ( U ) j + 1 := A t t r i ( U ) j ∪ { v ∈ V i ∣ ∃ ( v , w ) ∈ E : w ∈ A t t r i ( U ) j } ∪ { v ∈ V 1 − i ∣ ∀ ( v , w ) ∈ E : w ∈ A t t r i ( U ) j } A t t r i ( U ) := ⋃ j = 0 ∞ A t t r i ( U ) j {\displaystyle {\begin{aligned}Attr_{i}(U)^{0}&:=U\\Attr_{i}(U)^{j+1}&:=Attr_{i}(U)^{j}\cup \{v\in V_{i}\mid \exists (v,w)\in E:w\in Attr_{i}(U)^{j}\}\cup \{v\in V_{1-i}\mid \forall (v,w)\in E:w\in Attr_{i}(U)^{j}\}\\Attr_{i}(U)&:=\bigcup _{j=0}^{\infty }Attr_{i}(U)^{j}\end{aligned}}} 別の言い方をすれば、初期集合 U から開始して、「プレイヤー0の手番となるノードで、 U に一歩で到達できるノード」と「プレイヤー1の手番となるノードで、プレイヤー1がどのように選択しても U に入ってしまうノード」をUに追加していく。これを繰り返して止まったときのUがAttr0(U)である。 Zielonkaのアルゴリズムは、優先度の値に関する再帰降下に基づいている。最大優先度が0のときは、どんな戦略であってもプレイヤー0が勝つのは明らかである。それ以外のときは、 p を最大優先度とし、 i = p mod 2 {\displaystyle i=p{\bmod {2}}} をその優先度に紐付けられたプレイヤーの番号とする。また、 U = { v ∣ Ω ( v ) = p } {\displaystyle U=\{v\mid \Omega (v)=p\}} を優先度が p であるようなノード全体の集合、 A = A t t r i ( U ) {\displaystyle A=Attr_{i}(U)} をプレイヤー i のアトラクタとおく。このとき、プレイヤー i はうまく戦略を選ぶことで、 A を無限回訪問するようなプレイでは必ずプレイヤー i が勝つようにできる。 G ′ = G ∖ A {\displaystyle G'=G\setminus A} を考える。このゲーム G ′ {\displaystyle G'} は元のゲームより真に小さいから再帰的に解くことができ、それにより各プレイヤーの勝利領域 W i ′ , W 1 − i ′ {\displaystyle W'_{i},W'_{1-i}} がわかる。ここでもし W 1 − i ′ {\displaystyle W'_{1-i}} が空ならば、元のゲームGの対応する勝利領域 W 1 − i {\displaystyle W_{1-i}} も空である。なぜならば、プレイヤー 1 − i {\displaystyle 1-i} が W i {\displaystyle W_{i}} から抜ける唯一の方法は A に行くことで、この場合もプレイヤー i の勝利が確定するからである。 いっぽう、もし W 1 − i ′ {\displaystyle W'_{1-i}} が空ではなかった場合、プレイヤー 1 − i {\displaystyle 1-i} は少なくとも W 1 − i ′ {\displaystyle W'_{1-i}} では勝利することができる。なぜならば、プレイヤー i が W 1 − i ′ {\displaystyle W'_{1-i}} から A に逃げることはできない (さもなくば A がアトラクタであることに反する) からである。しかしそれ以外のノードでの必勝性は明らかではないので、プレイヤー 1 − i {\displaystyle 1-i} のアトラクタ B = A t t r 1 − i ( W 1 − i ′ ) {\displaystyle B=Attr_{1-i}(W'_{1-i})} を計算し、これを G から取り除いた、より小さいゲーム G ″ = G ∖ B {\displaystyle G''=G\setminus B} を得る。するとやはりこのゲームの必勝性を再帰的に解くことができ、各プレイヤーの勝利領域 W i ″ , W 1 − i ″ {\displaystyle W''_{i},W''_{1-i}} がわかる。このとき W i = W i ″ {\displaystyle W_{i}=W''_{i}} かつ W 1 − i = W 1 − i ″ ∪ B {\displaystyle W_{1-i}=W''_{1-i}\cup B} であることがわかる。 このアルゴリズムは、擬似コードでは以下のように書ける: function s o l v e ( G ) {\displaystyle solve(G)} p := G の最大優先度 if p = 0 {\displaystyle p=0} return W 0 , W 1 := V , { } {\displaystyle W_{0},W_{1}:=V,\{\}} else U := G のノードで優先度 p のもの全体 i := p mod 2 {\displaystyle i:=p{\bmod {2}}} A := A t t r i ( U ) {\displaystyle A:=Attr_{i}(U)} W 0 ′ , W 1 ′ := s o l v e ( G ∖ A ) {\displaystyle W_{0}',W_{1}':=solve(G\setminus A)} if W i ′ = V {\displaystyle W_{i}'=V} return W i , W 1 − i := V , { } {\displaystyle W_{i},W_{1-i}:=V,\{\}} B := A t t r 1 − i ( W 1 − i ′ ) {\displaystyle B:=Attr_{1-i}(W_{1-i}')} W 0 ″ , W 1 ″ := s o l v e ( G ∖ B ) {\displaystyle W_{0}'',W_{1}'':=solve(G\setminus B)} return W i , W 1 − i := W i ″ , W 1 − i ″ ∪ B {\displaystyle W_{i},W_{1-i}:=W_{i}'',W_{1-i}''\cup B}
※この「パリティゲームを解く再帰的なアルゴリズム」の解説は、「パリティゲーム」の解説の一部です。
「パリティゲームを解く再帰的なアルゴリズム」を含む「パリティゲーム」の記事については、「パリティゲーム」の概要を参照ください。
- パリティゲームを解く再帰的なアルゴリズムのページへのリンク
