Part 1 - ...and Games

Chapter 7 & 8

讨论游戏的概念。

一个游戏事实上就是解除了"不存在 $x_L\ge x_R$$x_L\ge x_R$"的数。比如说我们有如下的奇妙生物

为什么它叫游戏呢，因为如果我们可以把它看成一个抽象的，只记录了局面间转移关系的博弈游戏。对于 $x$$x$ 来说，$x_L$$x_L$ 集合是当前玩家 L 能操作达到的新局面，$x_R$$x_R$ 是玩家 R 能操作达到的新局面。

一般我们认为轮到一个玩家时游戏无法继续（没有后继局面）就算该玩家输。显然局面被分为四种：后手必胜，先手必胜，L 必胜，R 必胜。

比如：

• $0$$0$ 是一个后手必胜局面。

• $1$$1$ 是一个 L 必胜局面。

• $-1$$-1$ 是一个 R 必胜局面。

• $\ast$$*$ 是一个先手必胜局面。

• $\{\ast |\ast \}$$\{*|*\}$ 是一个后手必胜局面。

显然，现在原先那些 $\le ,\ge ,=,+$$\le,\ge,=,+$ 之类的有关"值"的概念现在对我们来说相当可疑（比如说，同一个数的不同表达方式是否还有同样的必胜性已经很不显然了！）。先让我们举点例子观察一下。

序关系 :

直觉来讲 $x\le y$$x\le y$ 应当代表，对玩家 L 来说，$y$$y$ 比 $x$$x$ "更有优势"。让我们看看是否如此。

• $x_L\ngeqq y$$x_L\not\ge y$ : $x$$x$ 下 L 玩家怎么走都无法比 $y$$y$ 更有优势；

• $y_R\nleqq x$$y_R\not\le x$ : $y$$y$ 下即使是 R 玩家走也不会搞出比 $x$$x$ 更坏的局势。

这很合理。

加法 :

仍是直觉来讲，$x+y$$x+y$ 应该是独立操作两个游戏的结果。

• $(x+y{)}_L=\{x_L+y,x+y_L\}$$(x+y)_L=\{x_L+y,x+y_L\}$ : L 玩家选一个动一步；

• $(x+y{)}_R=\{x_R+y,x+y_R\}$$(x+y)_R=\{x_R+y,x+y_R\}$ : R 玩家选一个动一步。

没法比这更合理了！

我猜有人在想 SG 函数 :

请不要把 SG 函数和游戏的值混淆。SG 函数讨论的实际上是游戏的一种特殊情况：$x_L=x_R$$x_L=x_R$。（$\ast$$*$ 那一类）当然那边的理论也有十分有趣的结果，不过我们最好还是暂时放一边。

那些值很奇怪的游戏真的有机会出现吗 :

• 其实 $\omega$$\omega$ 等超限序数的出现没有想象中那么刻意，你可以参考无限象棋的 $\omega$$\omega$ 步杀。

• $\frac{1}{2}$$\frac 12$ 等分数也很容易出现。参考如下游戏：L、R 玩家轮流在一片框定的区域中放置骨牌，L 玩家只能放水平的，R 玩家只能放竖直的。放过的区域视为删除。下图是一个 $\{-1,0|1\}$$\{-1,0|1\}$ 的局面，显然，值为 $\frac{1}{2}$$\frac12$。

另一些原书介绍的小游戏本文不再介绍。

Chapter 9（上）

发展一些关于不是数的游戏的理论。

考虑游戏 $\{1|-1\}$$\{1|-1\}$，正常的、在 $[-1,1]$$[-1,1]$ 之间的数都和它是不可比的，而 $>1$$>1$ 的数都大于它，$<-1$$<-1$ 的数都小于它。这提示我们关注：

• $L(G)$$L(G)$ : $G$$G$（在数集上的）的左偏分割。$x$$x$ 在 $L(G)$$L(G)$ 的右集合当且仅当 $x\ge G$$x\ge G$，否则在左集合。

• $R(G)$$R(G)$ : $G$$G$（在数集上的）的右偏分割。$x$$x$ 在 $R(G)$$R(G)$ 的左集合当且仅当 $x\le G$$x\le G$，否则在右集合。

分割上有显然的序关系。两个分割 $A<B$$A<B$ 表示存在 $x$$x$ 在 $A$$A$ 的右侧却在 $B$$B$ 的左侧。同样，我们也可以用 $x<A$$x<A$ 表示一个数在某分割的左侧。

考虑 $L(G)<R(G)$$L(G)<R(G)$ 的情况，也就是存在数 $x$$x$ 满足 $L(G)<x<R(G)$$L(G)<x<R(G)$。那么 $x\le G\le x$$x\le G\le x$，也即 $x=G$$x=G$。也即，这种情况等价于 $G$$G$ 就是数。

下面我们来证明有关 $L(G),R(G)$$L(G),R(G)$ 的一个（超限）归纳。

定理.

$$L(G)=supR(G_L)$$

$$R(G)=infL(G_R)$$

（当然，上下界是在刚才定义的序关系下取的。）

证明.

记 $L=supR(G_L),R=infL(G_R)$$L=\sup R(G_L),R=\inf L(G_R)$。

考虑 $L<R$$L<R$ 的情况。（请，暂时，不要把它们和 $L(G),R(G)$$L(G),R(G)$ 混淆。）

• 自然存在 $L<x<R$$L<x<R$。令 $x$$x$ 是其中最早出生的那个（希望你还记得这个概念。），那么就有 $x_L<L<x<R<x_R$$x_L<L<x<R<x_R$。

• 现在考虑游戏 $G-x$$G-x$。由于刚才的序关系，$G-x_R<0$$G-x_R<0$，而根据 $L$$L$ 的定义 $x>L\ge G_L$$x>L\ge G_L$，也有 $G_L-x<0$$G_L-x<0$。而对 R 来说情况完全对称。因此，$G-x=0$$G-x=0$。

• 由此，$G$$G$ 是一个数，$L(G)=L$$L(G)=L$ 也就显然了。

现在考虑 $L\ge R$$L\ge R$。

• 同上，对于 $x>L$$x>L$，仍有 $G_L-x<0,G-x_R<0$$G_L-x<0,G-x_R<0$，故 $x\ge G$$x\ge G$。反方向亦可推……吧 Conway 你 tm 没写啊啊啊啊。换句话说 $L$$L$ 就是 $L(G)$$L(G)$。R 方向亦然。

接下来的叙述还将揭示 $L(G),R(G)$$L(G),R(G)$ 的更深刻意义。

当游戏已经是数的时候，任何一方都不希望移动：L 玩家移动只会使值减小，R 玩家移动只会使值增大。因此我们可以考虑游戏停止时的停止值。

如果是 L 先手，那么他自然会尽量使停止值大，而 R 自然会尽量使停止值小。我们称 L 先手时的停止值是 L 停止值，R 先手时的停止值则是 R 停止值。熟悉博弈论的我们马上可以看出它们有一个显然的递推：

靠这不就是左右偏分割吗。

略微注意的是左右偏分割与 LR 停止值略微不同，我们可能在其中遇到需要区别单个元素在左还是在右的情况，因此更好的做法是给 LR 停止值一个新记号 $L_0(G),R_0(G)$$L_0(G),R_0(G)$。

现在来看几个例子。

$L(\ast )=R(0),R(\ast )=L(0)$$L(*)=R(0),R(*)=L(0)$，因此 $\ast$$*$ 大于所有负数，小于所有正数，但和 $0$$0$ 无法比较。

对于 $\uparrow =\{0|\ast \}$$\uparrow=\{0|*\}$ 有 $L(\uparrow )=R(0),R(\uparrow )=R(0)$$L(\uparrow)=R(0),R(\uparrow)=R(0)$，因此很怪的是 $\uparrow >0$$\uparrow>0$ 但是却小于所有正数！要知道数里面可是有 $\frac{1}{\omega },\frac{1}{{\epsilon }_0}$$\frac1\omega,\frac{1}{\varepsilon_0}$ 等等妖魔鬼怪，因此这个性质可没有看起来那么平凡。

Chapter 9（下）

定理.

$$\begin{array}{r}{R}_0(G)+R_0(H)\\ & \le R_0(G+H)\\ & \le R_0(G)+L_0(H)\\ & \le L_0(G+H)\\ & \le L_0(G)+L_0(H)\end{array}$$

在策略上这坨不等式是显然的。

这个定理没有看上去那么厉害，但是它可以给出一个很厉害的结论：

定理. (期望值定理)

对于游戏 $G$$G$，总存在两个数 $m(G)$$m(G)$ 和 $t$$t$，使得对于任意有限正整数 $n$$n$，

$$nm(G)-t\le nG\le nm(G)+t$$

证明 1.

我们有

$$R_0(nG)\le L_0(nG)=R_0((n-1)G+G_L)$$

利用前面的定理，有

$$\text{RHS}\le R_0(nG)+L_0(G-G_L)$$

因此，我们得到

$$R_0(nG)\le L_0(nG)\le R_0(nG)+L_0(G-G_L)$$

也就是 $R_0(nG)$$R_0(nG)$ 和 $L_0(nG)$$L_0(nG)$ 的差距不超过 $L_0(G-G_L)$$L_0(G-G_L)$。

但同时

$$\begin{array}{c}{R}_0(G)\le {\displaystyle \frac{R_0((n-1)G)+R_0(G)}{n}}\le \\ {\displaystyle \frac{R_0(nG)}{n}}\le {\displaystyle \frac{L_0(nG)}{n}}\\ \le {\displaystyle \frac{L_0((n-1)G)+L_0(G)}{n}}\le L_0(G)\end{array}$$

也就有

$${\displaystyle \frac{R_0((n-1)G}{n-1}}\le {\displaystyle \frac{R_0(nG)}{n}}\le {\displaystyle \frac{L_0(nG)}{n}}\le {\displaystyle \frac{L_0((n-1)G)}{n-1}}$$

因此根据闭区间套引理，它们一定收敛到某个 $m(G)$$m(G)$ 上。

Conway 你这 tm 算个毛的一行证明！把你跳步的补出来有这么多啊！

除非有读者对如何确定 $m(G)$$m(G)$ 和 $t$$t$ 有兴趣，否则本文将不对 Chapter 9 的剩余部分进行介绍。