实数、超实数和博弈游戏：数学的结构之美

（四）并行的棋局

事实上，这个全新的算术系统是 Knuth 从另一位数学大神 John Conway 那儿听来的。 Knuth 对此非常感兴趣，他把 TAOCP 的写作计划搁置了一周，完成了这部 100 多页的小说，并在 1974 年出版。“超实数”这个词是 Knuth 自己杜撰的。 Conway 非常喜欢这个词，并把它用到了他在 1976 年出版的专著 On Numbers and Games 中。这是一本非常有特色，非常 geek 的书。书的内容分成了第零部分 On Numbers 和第一部分 and Games ，全书的第一句是， This book is in two = {zero, one | } parts 。在这本书中， Conway 给出了超实数背后的直观意义：博弈游戏。

图 1	图 2	图 3	图 4	图 5

让我们来考虑这样一个游戏，游戏的名字叫做 Domineering 。两个玩家轮流在一个形状不规则的棋盘上放置多米诺骨牌。何不把这两个玩家分别记作“左玩家”和“右玩家”。左玩家只允许在棋盘上放置竖直的多米诺骨牌，右玩家只允许在棋盘上放置水平的多米诺骨牌。谁先不能放了，谁就输了。显然，有的棋局可能会对左玩家更有利，有的棋局可能会对右玩家更有利。让我们来分析几种局面吧。图 1 显示的是一个“空棋盘”。显然，这是一个“中立棋局”，先走的人直接就输了，后走的人直接就赢了。图 2 所示的棋局虽然与空棋盘不同，但本质上一样——这仍然是一个谁后走谁赢的公平局面。图 3 所示的棋局则明显对右玩家更有利一些，事实上不管谁先走，右玩家一定都会获胜。图 4 所示的棋局则偏向了左玩家，不管谁先走，左玩家都会获胜。

Conway 给出了两个棋局相加的含义。定义两个棋局的和为同时包含这两个棋局的新棋局。如果说有两个棋局，棋局 A 和棋局 B ，那么 A + B 的意思就是两个玩家同时在棋局 A 和棋局 B 上游戏。轮到某个玩家行动时，这个玩家可以选择在 A 上走一步，也可以选择在 B 上走一步，只要 A 和 B 当中至少一个还能走，他就不算输。例如，我们可以让两个玩家同时在图 3 和图 4 上游戏，这个游戏就记作

+

不难看出，它的效果等价于一个空的棋局——谁后走谁赢。

图 5 所示的 L 形棋盘就更有意思了。如果左玩家先行，他有两种走法。其中一种走法将刚好给右玩家留下一步，把自己送上了绝路；更聪明的走法则是把棋盘弄断，从而形成 □ + □ 的局面，让右玩家直接死掉。如果是右玩家先行，他只有一步可走，但走完之后就再也无计可施，而左玩家还能多走一步。因此，不管谁先走，这个 L 形棋盘都是左玩家必胜的。

一个有趣的问题：图 4 的 I 形棋盘和图 5 的 L 形棋盘都是左玩家必胜的局面，都是对左玩家有利的局面，那么哪个局面对左玩家更有利一些？换句话说，哪个局面会让左玩家赢得更爽一些？大家或许会说，当然是 I 形棋盘更爽。凭什么这么说？有什么理由吗？注意这里我们实际上在做的事情：我们希望能找出一种（对于左玩家来说）棋局优劣的判断标准。其中一种绝妙的想法是，让 I 和 L 两个棋局同时进行，不过左玩家要在 L 中扮演右玩家的角色。换句话说，考虑这样的复合棋盘：

两个玩家仍然轮流放置多米诺骨牌，不过规则稍有修改：在 I 形棋盘上，左玩家仍然竖直地放牌，右玩家仍然水平地放牌；但在 L 形棋盘上，两个玩家的身份颠倒了：左玩家只能放水平的牌，右玩家则改放竖直的牌。此时，左玩家在 I 形棋盘上有优势，右玩家在 L 形棋盘上有优势。最终整个棋局更偏向于谁？这显然是一场赤裸裸的“优势绝对值”之战。不难验证，事实上整个棋局仍然是左玩家必胜，不管谁先走谁后走。这说明，左玩家在 I 形棋盘中具有更大的优势，因而 I 形棋盘比 L 形棋盘更好。

对于一个棋局 A ，如果我们完全交换左玩家和右玩家的地位，得到的新棋局就叫做棋局 A 的“反棋局”，记作 -A 。我们规定，对于棋局 A 和棋局 B 来说，如果棋局 A 和棋局 B 的反棋局同时进行（即游戏在 A + (-B) 上进行），左玩家必胜（不管谁先走），那么对于左玩家来说，棋局 A 比棋局 B 更好，或者说棋局 A 优于棋局 B ；反之，如果右玩家必胜（不管谁先走），那么对于左玩家来说，棋局 A 比棋局 B 更差，或者说棋局 A 劣于棋局 B 。如果 A + (-B) 是一个谁后走谁必胜的中立局面，我们就认为，棋局 A 和棋局 B 对于左玩家来说优劣相同，或者说棋局 A 平于棋局 B 。注意，今后不做特殊说明时，棋盘的优劣都是针对左玩家所说的。

棋局 A 劣于棋局 B 的另一个等价的定义就是，如果棋局 B 优于棋局 A ，我们就说棋局 A 劣于棋局 B 。如果棋局 B 优于棋局 A ，说明 B + (-A) 是左玩家必胜的，因而整个复合棋局的反棋局将会是右玩家必胜的。整个复合棋局的反棋局是什么？就是 B 的反棋局，加上 A 的反棋局的反棋局，也就是 A + (-B) 了。而 A + (-B) 对于右玩家必胜，这正好符合之前给出的 A 劣于 B 的定义。

不过目前，没有任何东西可以向我们保证，这些定义是合理的。按照这个优劣定义，没准会出现 A 优于 B 、 B 优于 C 、 C 优于 A 的荒唐一幕，或者棋局 A 优于棋局 B 但 A + C 劣于 B + C 的悖理情形。不过，或许我们能证明，这些情况都不会出现。至少我们可以证明一些最基本的事实，例如根据上面的定义，一个棋局一定和它自身的优劣程度相同。为此，我们只需要说明棋局 A + (-A) 是一个中立局面即可。其实， A + (-A) 显然是谁后走谁必胜的，因为后走的人有一个绝妙的无敌必胜招数：它只需要完全模仿对方的行为即可。先走的人每走一步，他都能在另一个棋盘上照着走一步，从而永远不可能先无路可走。

左玩家必胜（不管谁先走）的棋局 A 也一定优于任意一个中立棋局。我们也可以证明这一点，只需要说明棋局 A 加上中立棋局的反棋局后，左玩家能必胜即可。他显然是能获胜的，他可以在 A 上该怎么走就怎么走，除非回应右玩家在中立棋局上的行动。反过来，右玩家必胜（不管谁先走）的棋局也就一定劣于中立棋局。

现在开始，就是真正神奇的地方了。我们把左玩家走一步之后可能形成的所有局面构成的集合叫做左集合，把右玩家走一步之后可能形成的所有局面构成的集合叫做右集合。看看图 4 的 I 形棋盘：左玩家无论走哪一步，剩余的棋盘都是图 2 的样子；同时，右玩家没有可以走的空间，右集合是一个空集。一个棋局的左集合和右集合完整地描述了再走一步之后这个棋局所有可能的结果，于是我们可以用这两个集合来刻画该棋局。我们就说：

= {| }

 

声明: 除非转自他站（如有侵权，请联系处理）外，本文采用 BY-NC-SA 协议进行授权 | 智乐兔
转载请注明：转自《实数、超实数和博弈游戏：数学的结构之美》
本文地址：https://www.zhiletu.com/archives-3260.html
关注公众号：