aiura/

ゲームの値

2016-11-23 (Wed.)

数学 ゲーム理論

これは game-class.html とか game-algebra.html の続き

INDEX

参考文献

整数

いくつかのゲームと整数を次のように対応付ける.

すなわち、正の \(n\) について \(\bar{n}\) とは、左が \(n\) 手自由に打つことができ、右が手を打てないゲームのことである. 負はそのゲームのマイナスである.

ゲームの代数との対応

前回、ゲームの和や大小比較を定義したが、 これが今回定義した整数の上の和や大小比較と一致する.

ゲームを大文字、数は小文字とする. また数 \(n\) を持つゲームを \(\bar{n}\) と表記する.

例えば \(\bar{n} + \bar{m} = \bar{n + m}\) (ゲームの \(=\)) は自明.

整数 \(a,b,c\) があって、 ゲーム \(A=\bar{a}\), \(B=\bar{b}\), \(C=\bar{c}\) があるとする.

2進有理数

分母が (2以上の) 2の冪数である有理数を2進有理数と呼ぶ.

今度は、整数と対応付けられなかったゲームのうちの幾つかを2進有理数と対応付ける.

\(j \geq 1\)、奇数 \(m\) について

\[\bar{~\frac{m}{2^j}~} = \left\{~ \bar{~\frac{(m-1)/2}{2^{j-1}}~} ~|~ \bar{~\frac{(m+1)/2}{2^{j-1}}~} ~\right\}\]

右辺には分母が \(2^0=1\) となることがあるが、これは先述の整数とみなす. 例えば、 \(\bar{1/2} = \{0|1\}\).

例題

\(\bar{1/2} + \bar{1/2} = \bar{~1~}\) が成立する.

これを示すのに、 \(\bar{1/2} + \bar{1/2} - \bar{~1~} = 0\) すなわち \(\bar{1/2} + \bar{1/2} - \bar{~1~}\) が後手必勝であることを言えばいい.

先手が \(1/2\) について打って \(0\) (左) または \(1\) (右) になったら後手はもう一つの \(1/2\) について \(1\) または \(0\) にすることで、 ゲームは \(\bar{~1~} - \bar{~1~}\) になる. これが後手必勝なのは自明.

先手が右で \(-\bar{1}\) \((=\bar{-1})\) を打ったらゲームは \(1/2 + 1/2\) になる. これはどう転んでも左必勝. 従って後手必勝.

ゲームの代数との対応

整数と同様.

\(+, \geq\) がゲームについて言ってるのか、整数・2進有理数について言ってるのかの区別は必要ない.

面倒なので \(\bar{n}\) も単に \(n\) と書いて、 数とゲームを混ぜて足したりする (ゲームであるほうにキャストする).

弱数避定理 (Weak Number-Avoidance)

以上の、整数または2進有理数に対応づくゲームを「数である」という. 数 \(x\) であるゲームと、数でないゲーム \(G\) との和 \(G+x\) について、 先手の左が \(x\) に手を打って勝つならば、 代わりに \(G\) に手を打っても勝つ.

\(G\) で左が先手で勝つ」を「\(G^L\) で左または後手が勝つ」と読み替えると、 \(G^L \geq 0\) と容易に書き直せる.

定理の主張を言い換えると、 \(G+x^L \geq 0\) ならば、 \(G^L+x \geq 0\) と言っている.

\(G\) が数でないので、\(G+x^L=0 \iff G=-x^L\) とあることはない. 従って、 \(G+x^L \geq 0\) ならば \(G+x^L > 0\). すなわち \(G+x^L\) は左必勝. ここから左が \(G\) が打った局面でも左必勝、または後手必勝で、 \(G^L + x^L \geq 0\).

さて数の定義から、 \(x^L < x\).

これを推移させると \(G^L + x > G^L + x^L \geq 0\). 以上から主張は正しい.

誘因

左誘因も右も等しく、 \[G^L - G = G - G^R = -\frac{1}{2^j} < 0\] となる.