ゲーム理論入門 ２

Graph Games

Impartial gameはグラフの頂点をゲームの中の状態、グラフの辺をゲームの動作と同一視す る事によって有向グラフで表せる。

Rules

有向グラフ G は、空集合でない頂点(状態)の集合 X と、各 $X ∋ x$ に対して、X の部分集 合 $X ⊃ F(x)$ を満たす関数 F を用いて $(X, F)$ と表される。X ∋ x に対して、$F(x)$ は、$x$ からプレイヤーが 動かせる状態を表している (x の follower と呼ばれる)。もし、F(x) が空集合なら、x は terminal position である。
2 人で行う勝敗のあるゲームは、最初の状態が X ∋ $x_0$ と規定され、次のルールを使って、$G = (X, F)$ の ようなグラフでプレーされる。
(1) プレイヤー問が $x_0$ から最初に動かす。
(2) プレイヤーは交互に動かす。
(3) 状態 x で、それを動かすプレイヤーは、次の状態 $y ∈ F(x)$ を選ぶ。

Sprague-Grundy 関数

グラフは、P-位置と N-位置が与えられることによって解析されるが、Sprague-Grundy 関数を通しても
また解析されている。

グラフ $(X, F)$ の Sprague-Grundy 関数は、X と非負整数の値で定義された関数 g であり、次のように定義される

g(x)=\min \{ n≥0:n ≠ g(y) : y∈F(x) \}

g(x) は、x の follower の Sprague-Grundy 値の中で見つからない最小の非負整数である。もし、集合の 中にない最小の非負整数としての、非負整数の集合を minimal excludent、または mex と定義すると、単純に

g(x)= mex \{ g(y) : y∈F(x) \}

g(x) は、x の全ての follower y に対する、g(y) によって定義される。のでterminal から逆算的に求めていける。
terminal である x は、F(x) が空集合なので、g(x) = 0 と定 義される。全ての x の follower が terminal である、terminal でない x は、g(x) = 1.

g(x) = 0 である状態 x は P-位置で、その他の状態は N-位置である。勝つ方法は、各動作において、 Sprague-Grundy 値が 0 になる頂点への動作を選ぶことである。

Prop

1. もし x が terminal position なら、g(x) = 0
2. g(x) = 0 である x からの全ての follower y は、g(y) ≠ 0 である。
3. g(x) ≠ 0 である x からは、g(y) = 0 となるような、follower y が少なくとも 1 つある。