aiura/

ゲームの代数

2017-04-23 (Sun.)

数学 ゲーム理論

index

前提

ここではゲームとは組み合わせゲームを指します. 組み合わせゲームの帰結類 に組み合わせゲームの定義と帰結類についてまとめているのでここは読んだことを前提にします.

ゲームの和 (直和, 選択和)

2つのゲーム \(G\), \(H\) の和 \(G+H\) を次のように定める.

\(G\)\(H\) を横に並べた状態で、 二人がゲーム \(G+H\) をプレイする. 許される手は、\(G\) または \(H\) のどちらか一方を選択し、 そちらにとって許される手を1度打つ. これを先手と後手とが交互に繰り返す.

\(G\), \(H\) がともに最終局面の時が \(G+H\) の最終局面である (\(G=\{\} \land H=\{\} \iff G+H=\{\}\)). 一方が既に最終局面で、もう一方を最終局面にした (つまり最後の手を打った) 人の勝ちである.

不偏ゲームの和

形式的表現での定義を与える. 不偏ゲームの場合、ゲームとは単に選択肢 (ゲーム) の集合である.

右辺の \(G'+H\) なんかもゲーム同士の \(+\) であって、ここが再帰的定義になってる.

ところで不偏ゲームは非不偏ゲームはの特別な場合に過ぎないので、非不偏ゲームだけを考える.

非不偏ゲームの和

左右を別々に考えるだけで、不偏ゲームの場合と同様である.

\(G = \{\mathcal{G}^L | \mathcal{G}^R\}\), \(H = \{\mathcal{H}^L | \mathcal{H}^R\}\) について

ゼロ

最終局面 (\(\{\}\) または \(\{|\}\)) をゲーム \(0\) と呼ぶ. これは \(+\) の単位元である.

ゲームの反転

左右の立場を入れ替える操作を反転とし、ゲーム \(G\) に対して \(-G\) と表現する.

形式的には左選択肢と右選択肢を入れ替えればよいだけだが、再帰的に反転をシなければならないことに註意. つまり

二項演算 \(-\) を反転を使って定義する.

\[G - H = G + (-H)\]

ゲームの等価性 (\(=\), \(\ne\))

ゲームの等価性 (\(=\)) を次のように定める.

\(G = H\) とは、 任意のゲーム \(X\) について \(G+X\)\(H+X\) との帰結類が同じであること

これは 「任意の文脈 \(X\) について \(G\) な部分を \(H\) に置き換えてもゲーム全体の勝敗には差支えがない」 ということを言っている. 明らかにこの \(=\) は同値関係を与えている.

自然に \(\ne\) も定義する.

定理

\[G \in \mathcal{P} \iff G = 0\]

後手必勝のゲームに限って 0 と等価である.

\((\Leftarrow)\) の証明:

\(G\) が 0 と等価であるとは \(G+X\)\(0+X\) と同じ帰結類であるということ. \(X=0\) とすると、\(G+0=G\)\(0+0=0\) とが同じ帰結類であるということ. \(0\) の帰結類は \(\mathcal{P}\) であるので、\(G\) の帰結類も \(\mathcal{P}\).

\((\Rightarrow)\) の証明:

任意のゲーム \(X\) について、\(G+X\) の帰結類が \(0+X=X\) の帰結類と同じであることを示す. ゲームの帰結類は次の 4 ケース

  1. 左 が 攻で 右 が後攻のとき、 が必勝
  2. 左 が 攻で 右 が後攻のとき、右 が必勝
  3. 左 が後攻で 右 が先攻のとき、 が必勝
  4. 左 が後攻で 右 が先攻のとき、右 が必勝

の組み合わせで決まることは 以前 に書いた. この 4 ケースについて、\(X\)\(G+X\) とが一致することを言う.

\(X\) が左が先攻で左が勝つ場合 (ケース1)、\(G+X\) についても先攻で左が勝つ. 具体的には、左はまず \(G+X\)\(X\) 部分について正しく手を打つ. 右が \(X\) について打つならば正しく応じることで \(X\) について勝てる. \(G\) については左は自分からは打たず、右が打った場合に限って打てばよい. 右が先に打てば \(G\) については右が先攻になる. \(G\) は後攻必勝であるので、左が勝てる. 以上のようにして左は \(G\) についても \(X\) についても勝つので \(G+X\) でも勝つ.

他のケースも同様.

定理

\[G - G = 0\]

先の定理を使えば、\(0\) と等価であることを示すためには、後攻必勝であることを示せばよいことがわかる.

\(G - G = G + (-G)\) は後攻が先攻と同じ手を常に使う 物真似戦略 によって後攻必勝である.

具体的には、先攻が \(H - G\) (または \(G - H\)) にしたとき、後攻は \(H - H\) にできる. 符号が反転してる方を操作しているからこそ出来ることに註意. これを繰り返すことでいつか \(0 - 0 = 0\) にでき、後攻が勝つ.

これは先攻後攻を逆にした2つのチェス盤を並べて相手が片方に打った手をもう片方に打つことに相当する.

定理

\[G + J = H + J \iff G = H\]

当然成り立っていて欲しい性質であるが確かめておく.

\((\Leftarrow)\) だけを示す. 逆もほぼ同様であるので.

\(G=H\) を仮定する. 任意の \(X\)\(G+X\), \(H+X\) の帰結類が同じ. \(X=J+X'\) とすれば、\(G+J+X'\), \(H+J+X'\) の帰結類が同じ. これは任意の \(X'\) について \(X\)\(J+X'\) とすることで言える. というわけで \(G+J=H+J\).

\[G=G' \land H=H' \Rightarrow G+H = G'+H'\]

先の定理を使う.

半順序 (\(\geq, >, \|, \rhd, \unrhd\))

任意の文脈 \(X\) で部分 \(G\)\(H\) に置き換えても左にとっては差し支えないようなときを \(H \geq G\) という. 或いは「ゲーム \(H\) は左にとってゲーム \(G\) よりも有利である」とも言える.

以上を組み合わせて自然に次の比較演算子を定義する.

性質

定理

\[G + J \geq H + J \iff G \geq J\]

証明は \(=\) のときと同様.

\[G \geq H \iff G - H \geq 0\]

先の定理で \(J=-H\) とすると得られる.

半順序つきの群

以上から、ゲーム全体は、 可換群 であって 半順序 の構造を入れることができる.

帰結類

ゲームの標準形

全てのゲーム \(G\) について、それと等しい \(G=H\) となるような最小のゲーム \(H\) が存在し、 これを \(G\)標準形 という. \(G\) からそれの標準形を求める手順を考える.

片手枷原理 (One-hand-tied)

明らかにある手が、別な手に比べて劣位な場合、そのような手は初めから考える必要がない、という原理.

\[G=\{A,B,C,\ldots | H,I,J,\ldots\}\]

について \(B \geq A\) ならば

\[G = \{B,C,\ldots | H,I,J,\ldots\}.\]

としてよい. 或いは \(I \geq J\) ならば

\[G = \{A,B,C,\ldots | H,J,\ldots\}.\]

と考えてよい.

すなわち、

\(B \geq A\) のとき

に関して \(G=G'\) であることを示す. 直接的には、\(G-G'=0\) すなわち \(G-G'\) が後手必勝であることを示せば良い.

先手が \(B,C\ldots\) または \(H,I,J,\ldots\)\(G\) または \(-G'\) から選んだ場合、 後手は \(-G'\) または \(G\) から先手の打った手のマイナスを選ぶことで、 \((B-B=0),(C-C=0),\ldots,(H-H=0),\ldots\) に進んで後手必勝になる.

(e.g. 先手の右が \(G\) から \(I\) を選んだなら、後手の左は \(-G'\) から \(-I\) を選べる)

以上で網羅出来てない手としては、「先手の左が \(G\) から \(A\) を選択した場合」である. この場合、後手は \(-G'\) から \(-B\) を選べばよい. すると、ゲームは左手番の \(A-B\) である. 今 \(B \geq A\) であるので、これは右必勝.

以上から後手必勝.

打ち消し可能

左が打った手 \(A\) について、左にとって、現時点よりもさらに状況が悪くなる右の応手 \(A^R\) があるとき、 すなわち

\[G \geq A^R\]

のとき、 \(A^R\)\(A\) を打ち消す (reverse) 手といい、逆に \(A\) を打ち消し可能な手だと言う.

このような場合に左が \(A\) を打つのは、相手が \(A^R\) で応じて、 その左選択肢 \(A^{RL}\) (\(=(A^R)^L\)) を選ぶ場合だけである.

以上のことを短絡すると、 \(A\) という選択肢を、\(K^L\) で置き換えたゲームも等しそうである. すなわち、

について \(G=G'\) が成立する.

標準形

ゲーム \(G\)標準形 (canonical form) であるとは、 \(G\) 及び \(G\) から到達可能な全局面において、 片手枷原理で言及したような 劣位な手 が存在せず、また 打ち消し可能な手 も存在しないこと.

定理

\(G, H\) が共に標準形で \(G=H\) の場合、 集合 (あるいはゲーム木) として \(G \simeq H\).

すなわち同型を除いて標準形は一意.

誘因 (incentives)

ゲーム \(G\) に対して左選択肢 \(\mathcal{G}^L\) から \(G\) を引いた 集合 \(\mathcal{G}^L \setminus G\) を左誘因という. 同様に \(G \setminus \mathcal{G}^R\) を右誘因という.

あるいは \(G^L \in \mathcal{G}^L\) について ゲーム \(G^L - G\) を左誘因とも言う. 同様に \(G - G^R\) を右誘因という.

意味としては、左にとっては左誘因が正である選択をすべき、右にとっては右誘因が正である選択をすべき (このためにマイナスが逆) で、 後述する「ゲームの値」を使うと、差が最大となる選択をすべきことが分かる.