2017-04-23 (Sun.)
ここではゲームとは組み合わせゲームを指します. 組み合わせゲームの帰結類 に組み合わせゲームの定義と帰結類についてまとめているのでここは読んだことを前提にします.
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)\]
ゲームの等価性 (\(=\)) を次のように定める.
\(G = H\) とは、 任意のゲーム \(X\) について \(G+X\) と \(H+X\) との帰結類が同じであること
これは 「任意の文脈 \(X\) について \(G\) な部分を \(H\) に置き換えてもゲーム全体の勝敗には差支えがない」 ということを言っている. 明らかにこの \(=\) は同値関係を与えている.
自然に \(\ne\) も定義する.
\[G \in \mathcal{P} \iff G = 0\]
後手必勝のゲームに限って 0 と等価である.
\(G\) が 0 と等価であるとは \(G+X\) が \(0+X\) と同じ帰結類であるということ. \(X=0\) とすると、\(G+0=G\) と \(0+0=0\) とが同じ帰結類であるということ. \(0\) の帰結類は \(\mathcal{P}\) であるので、\(G\) の帰結類も \(\mathcal{P}\).
任意のゲーム \(X\) について、\(G+X\) の帰結類が \(0+X=X\) の帰結類と同じであることを示す. ゲームの帰結類は次の 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'\]
先の定理を使う.
任意の文脈 \(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\) からそれの標準形を求めるための具体的な手順として 片手枷原理 と 打ち消し原理 という2つの簡約原理を考える.
明らかにある手が、別な手に比べて劣位な場合、そのような手は初めから考える必要がない、という原理. 具体的には、
\[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'\) が後手必勝であることを示せば良い.
先手が \(A\) 以外の選択肢を \(G, G'\) の中から選んだ場合、 後手はもう一方から同じ選択肢を選べる. \(G\) と \(G'\) の符号が逆転してるので左右が同じ選択肢を選べることに注意.
例えば左の先手が \(G\) から \(B\) を選んだ場合、右の後手は \(G'\) から \(B\) を選ぶことができる. \[G - G' \to B - G' \to B - B = 0\] こうするとゲームは \(0\) に出来、後手必勝のゲームになることがわかる. 従って後手が勝つ.
次に、左の先手が \(G\) から \(A\) を選択する場合、 後手は \(G'\) から \(B\) を選択すればよい. するとゲームは \(A - B\) になるわけだが、仮定から \[A - B \leq 0.\] なので、ゲームは後手または右必勝.
以上から \(G-G'\) は後手必勝. 従って \[G = G'\] がわかった.
ゲーム \(G\) の左選択肢 \(A \in \mathcal{G}^L\) のその右選択肢に左にとって元のゲーム \(G\) よりも状況が悪くなるような右の応手 \(A^R\) があるとする. つまり、
\[G \geq A^R\]
のとき、 \(A^R\) を \(A\) を打ち消す (reverse) 手であるという. 逆に \(A\) を打ち消し可能な手だと言う.
打ち消し可能な手 \(A\) が選択肢にある場合、 \(A^R\) で即座に打ち消される. ゲームの状況は一般にはより悪くなっているのだから、 \(A\) を選択する以上、さらに \(A^R\) について何か \((A^R)^L\) で応じるつもりでいなければならない. これは即座に選択するべきで、そうでないなら初めから \(A\) を選択してはいけない.
以上のように \[G \to A \to A^R \to (A^R)^L\] は間に他の手を挟まずに速やかに実行される.
ならば初めから、\(A\) という選択肢を \((A^R)^L\) で置き換えておいてもゲームは等価である、というのが 打ち消し原理 である.
ただし \((A^R)^L\) は一つとは限らないので、選択肢 \(A\) を消して、 左選択肢の集合を結合することになる.
について \(G=G'\) が成立する.
今更だけど記号について.
ゲームを単にアルファベット (e.g. \(A, B, G\)) と書いている.
その選択肢として、右肩に \(L, R\) を載せたのは単に選択肢の中の一つ (代表) のこと (e.g. \(A^L, B^R, G^L\)).
選択肢 全体 (つまり集合) を表すのに、アルファベットをまず script alphabet にしてから右肩に \(L, R\) を載せて表していている (e.g. \(\mathcal{A}^L, \mathcal{B}^R, \mathcal{G}^L\)).
(\(G^L \in \mathcal{G}^L, G^R \in \mathcal{G}^R\).)
ゲーム \(G\) が 標準形 (canonical form) であるとは、 \(G\) 及び \(G\) から到達可能な全局面において、 片手枷原理で言及したような 劣位な手 が存在せず、また 打ち消し可能な手 も存在しないこと.
\(G, H\) が共に標準形で \(G=H\) の場合、 集合 (あるいはゲーム木) として \(G \simeq H\).
すなわち同型を除いて標準形は一意.
ゲーム \(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\) を右誘因という.
意味としては、左にとっては左誘因が正である選択をすべき、右にとっては右誘因が正である選択をすべき (このためにマイナスが逆) で、 後述する「ゲームの値」を使うと、差が最大となる選択をすべきことが分かる.