超实数入门

超实数是极度冷门的算法。不到 CTS 级别看不到。OIer 学习前请仔细思考自己是否在浪费时间。

本文将简单写一下超实数和博弈基本概念的有关内容：

• 超现实数概念。
• 博弈概念。
• 组合博弈、博弈化简。
• 非公平博弈。
• 公平博弈。

博客中描述的内容都只是超实数的冰山一角，例如队爷的论文里，也还提到了“热博弈”、”小博弈“、“原子量”等内容，后续等我理解了也将会补充。

基础

超实数的概念

超实数也被叫作“超现实数”，本文中提到的所有“数”，在无特殊指明下，均指超实数。

在马耀华队爷的 2021 年集训队论文《浅谈超现实数与不平等博弈》一文中，将“超实数的定义”和“超实数的大小关系、运算”等统归为“定义”。在《On Numbers and Games》一书中 Conway 将“超实数的定义”标记为 “construction”（惯例、常规、公约），“超实数的大小关系、运算”等标记为 “definition”（解释、定义）。文本的标记以集训队论文内容为准。

（然后你会发现队爷的定义就是英文原著书中定义翻译成中文，所以没有必要纠结定义内容用哪个。）

定义一

对于两个数的集合 $L,R$，若 $\forall x\in L,\exist y\in R,x<y$，则 $\{L|R\}$ 是一个数。当 $L=R=\varnothing$ 时，记作 $0=\{|\}$，$0$ 是一个数。其它所有数都通过这种方法构造得到。

定义二

$x^L$ 表示数 $x=\{L|R\}$ 中，$L$ 集合中的任意某个数。$x^R$ 同理。

定义三

一个数可以被记作 $\{L|R\}$，也可以被记作 $\{a,b,c,\cdots|x,y,z\cdots\}$，其中 $L=\{a,b,c,\cdots\},R=\{x,y,z,\cdots\}$。

上文中提到了超实数的大小比较，而大小比较的定义为：

定义四

$x\geq y$ 当且仅当不存在 $x^R\leq y$ 且不存在 $x\leq y^L$。$x\leq y$ 当且仅当 $y\geq x$。

定义五

1. $x=y$ 当且仅当 $x\geq y,y\geq x$。
2. $x>y$ 当且仅当 $x\geq y,y\ngeq x$。
3. $x<y$ 当且仅当 $y>x$。
4. $x\neq y$ 当且仅当 $x>y$ 或 $y>x$。

超现实数的运算关系有：

定义六

1. $x+y = \{x^L+y,x+y^L | x^R+y,x+y^R\}$。
2. $-x = \{-x^R | -x^L\}$。
3. $x-y = x+(-y)$。
4. $xy = \{ x^Ly+xy^L-x^Ly^L,x^Ry+xy^R-x^Ry^R | x^Ly+xy^R-x^Ly^R,x^Ry+xy^L-x^Ry^L \}$。

定理一

超实数满足加法结合律和加法交换律。

前面我们构造出了超实数 $0$，现在来构造其它超实数：

$1=\{0|\}$

$-1=\{|0\}$

$\frac{1}{2}=\{0|1\}$

$-2-\{|-1\}$

$1-1=0$ 是否在超实数上成立？

$1+(-1) = \{ 0+(-1) | 1+0 \} = \{-1|1\}$

看起来并不是 $0$，但是根据大小比较的定义，可以发现 $1\nleq 0,0\nleq -1$，因此有 $\{-1|1\}\geq0,0\geq\{-1|1\}$，因此有 $\{-1|1\}=0$。

因此得到一个有趣的结论：两个形式不同的数可能相等。

定义七

无穷大 $\omega=\{0,1,2,4,8,\cdots|\}$，无穷小 $\frac{1}{\omega}=\{0|1,\frac{1}{2},\frac{1}{4}\cdots\}$。

可以发现我们可以递归得到所有形如 $\frac{p}{2^q}$ 的有理数（$p,q\in\mathbb Z$）。对于分母不是 $2$ 的幂的分数，需要用无限逼近的方式表示：

$\frac{1}{3} = \{0,\frac{1}{4},\frac{5}{16},\frac{21}{64}\cdots| \frac{1}{2},\frac{3}{8},\frac{11}{32},\frac{43}{128}\cdots \}$

你可以选择阅读《On Numbers and Games》的第零章获取更多详细内容。

博弈的概念

在《On Numbers and Games》中，博弈的定义如下：

定义八

一个游戏局面能被超实数 $\{L|R\}$ 表示的，称为博弈。

在这样的定义下得到，一个超现实数可以表示一个博弈，但不一定能表示所有的游戏。

定义九

1. 两个博弈 $A,B$ 相同（identical），为 $A$ 的所有元素和 $B$ 的所有元素均相同。记为 $A\equiv B$。
2. 两个博弈 $A,B$ 相等（equal），为 $A$ 和 $B$ 数值上相等。记为 $A=B$。

这个很好理解，前面我们据了超实数 $\{|\}$ 和 $\{-1|1\}$ 的例子。它们虽然形式不同，但数值是相等的。

定理二

对于任意博弈 $x$ 有 $x^L<x<x^R$。

定理三

若 $x\geq y,y\geq z$，则 $x\geq z$。

定理四

博弈的加法是保序的，$0$ 是加法单位元。

定理五

对于任意博弈 $x,y$：

1. $-(x+y) = (-x) + (-y)$。
2. $-(-x) = x$。
3. $x+(-x)=0$。

定理六

博弈的乘法满足 $0$ 是零因子，$1$ 是乘法单位元。满足交换律、结合律、关于加法的分配率。且 $(-x)y=x(-y)=-xy$。

定理七

若 $x,y$ 是超实数（或博弈），则 $x+y,-x,-y,xy$ 也是超实数（或博弈）。

定理八

对于超实数（或博弈）$x,y,z$：

1. 若 $x=y$ 则 $xz=yz$。
2. 若 $x>0,y>0$ 则 $xy>0$。
3. 若 $x\neq 0$ 则存在唯一的数 $y$，$xy=1$。$y=x^{-1}$ 是 $x$ 的乘法逆元。

综上所述：

定理九

实数域 $\mathbb R$ 是超实数域的子域，且对任意值是实数的超实数进行我们熟悉的实数运算，不会得到相异的结果。

当然上述是博弈的数值意义，还有博弈的组合意义：

定义十

一个（双人博弈）有两位玩家，分别记为 $L,R$。在博弈进行的某一状态下，$L$ 有若干（可以为 $0$）个可能的行动，$R$ 有若干（可以为 $0$）可能的行动，行动使博弈转移到另一状态。两名玩家从固定的初始状态开始，以最优策略交替行动。达到终止状态，不能行动的为输家。

定义十一

对于两个博弈 $A,B$，定义其和博弈 $A+B$ 为：有两个子博弈 $A,B$，两名玩家每次只能在恰好其中一个博弈中行动，无法行动为输家。

而本文讨论的博弈，是简单的有限博弈：

定义十二

满足以下条件的博弈称为有限博弈：

1. 状态数是有限的。
2. 每个状态能转移到的状态是有限的。
3. 不存在一个无限长的双方交替行动的序列。

定理十

一个有限博弈 $G$ 不可能出现平局，且博弈结果仅可能是以下四种之一：

1. $L$ 必胜。当且仅当 $G>0$。
2. $R$ 必胜。当且仅当 $G<0$。
3. 后手必胜。当且仅当 $G=0$。
4. 先手必胜。即不满足上述三种情况，记作 $G\parallel 0$。

你可以选择阅读《On Numbers and Games》的第一章获取更多详细内容。

简单博弈与博弈化简

简单博弈

给定一棵二叉树，初始时在根节点有一个棋子。$L$ 只能将棋子移动到该节点的左儿子，$R$ 只能将棋子移动到该节点的右儿子，两人交替行动。分析博弈局面。

显然，这个博弈对于任意局面，$L,R$ 可以选择的行动数不超过 $1$。这无伤大雅，不影响它是有限博弈。考虑画出一些简单的情况：

前三个很好表示，分别为 $0=\{|\},1=\{0|\},-1=\{|0\}$。对于第四个 $\{0|0\}$，它并没有一个实数来表示。这没有问题，实数域只是超实数域的一个子域。我们用 $\ast = \{0|0\}$ 来描述这个局面。

接下来考虑一个更复杂的情况：

可以明确的是，所有的死局，即 $L,R$ 都不能移动时，状态为 $0=\{|\}$。从下往上递归即可，但是考虑这样一件事情：我们刚刚得到 $3,4$ 号点的状态应该为 $\ast$，但 $1,2$ 号点对应的 $\{0|\ast\},\{\ast|0\}$ 呢？不妨创造记号来表示：$\uparrow = \{0|\ast\},\downarrow=\{\ast|0\}$。

容易发现 $\uparrow>0,\downarrow<0,\uparrow=-\downarrow$。然而 $\uparrow$ 小于任意一个实正数，$\downarrow$ 小于任意一个实负数，可以理解为“实数”对答案造成的影响比“非实数”大。

定理十一

$\uparrow + \ast \parallel 0, \downarrow+\ast\parallel 0$。

定理十二

$\{\downarrow|\uparrow\},\{\ast|\uparrow\},{\downarrow|\ast}$ 是后手必胜的博弈，这些数值都为 $0$。

回到题目，$1$ 号点状态为 $\uparrow$，$2$ 号点状态为 $\downarrow$，$0$ 号点状态为 $\{\uparrow|\downarrow\}=\ast$，先手必胜。

博弈化简

这样的“二叉树博弈”问题就是一类非常简单的博弈问题。但是我们不是经常能遇到很显然的博弈问题，这就需要博弈化简。

给定一个 $n\times n$ 的棋盘，$L,R$ 两人轮流放骨牌，骨牌的大小为 $1\times 2$。$L$ 只能竖着放，$R$ 只能横着放，不能放骨牌的人为输家。分析博弈局面。

显然，当 $n=1$ 时，双方都不能放骨牌，局面为 $0$。$n=2$ 时，先手随便放，后手就放不了了，局面为 $\ast$。然而 $n=3$ 时，局势变得复杂，先手后手都有很多种方法，得到的状态也不简单。因此就需要考虑博弈的化简。

定理十三

若博弈 $\{a_1,a_2,\cdots,a_n | \cdots\}$ 满足 $a_2\leq a_1$，则称 $a_2$ 被 $a_1$ 优超。此博弈等于 $\{a_1,a_3,\cdots,a_n | \cdots\}$，右集合同理。即：被优超的行动可以直接删去而不改变其值。

感性理解就是，如果有两个状态，都能让你必胜，选赢得更快更爽的那个不比选赢得没那么快的劣。

于是通过不断删除被优超的操作，就可以达到博弈的化简。这个问题就可以做了。因为推导冗杂，故把推导过程删去了。大家可以自行手算一下，但是没这个必要……

从《On Numbers and Games》第七章开始往后可以了解到更多内容，后文不再提及。

博弈问题

组合博弈

对于多个博弈，每轮一个人可以选择其中恰好一个博弈并行动。在任意博弈局面都无法行动的人算输家。

不难发现这就是和博弈。而和博弈等于博弈的和。

组合博弈有一个例题福若格斯，但是原题还有数数环节，我们去掉那个部分，重点来分析局面：

一个长度为 $5$ 的棋盘，有两个 $L$ 棋子和两个 $R$ 棋子。$L$ 只能移动 $L$ 棋子右移，$R$ 只能移动 $R$ 棋子左移。每次只能向前移动到下一个空位上，或者跳过恰好一个棋子到达后面的空位。

现在有多个这样的博弈，每个博弈的初始情况不一定一样。分析博弈局面。

首先长度固定，而且长度为五，两人不能回退。所以单独一个跳棋游戏是一个有限博弈，而且状态很少。所以爆搜+手算就得到了这样的状态表：

可是这只是一个单个局面的情况表。现在有很多个博弈……

现在假设有两个博弈组合，一个 $L$ 必胜，一个 $R$ 必胜，用超实数表示为 $1,-1$，则博弈情况，根据和博弈的定义，显然是 $0$，即后手必胜。

如何让电脑去计算一些超实数的和？别急着马上手写类，注意到本题的局面只存在 $0,1,-1,0.5,-0.5,\ast,\uparrow,\downarrow$ 这几种。$0$ 不用管，$0.5,-0.5,1,-1$ 可以直接按数值加起来，$\uparrow,\downarrow$ 两两抵消，$\ast+\ast=0$ 也可以两两抵消。若实数部分不为 $0$ 则结果取实数部分，否则根据是否存在 $\ast$ 和箭头分类讨论即可。

公平博弈

超实数的确大多用于解决不平等博弈问题，但是这并不代表其不能解决公平博弈问题，虽然有时候没必要。

定义十三

一个博弈 $G$ 时公平的，当且仅当 $G$ 和 $G$ 的所有后继状态中，双方的行动集合 $L,R$ 完全相同。

定理十四

任意公平博弈 $G$ 满足 $G+G=0$（证明则考虑先手在一个博弈行动时，后手在另一个博弈进行相同的行动）。

很显然，Nim 游戏是公平博弈游戏，双方能进行的操作是完全一样的。

这里并没有找到什么公平博弈的例题，所以只能放一下集训队论文的例题（相对简单，作引导性），当作博弈化简的问题：

单堆石子（不妨设有 $n$ 个）的 Nim 游戏（每人可以在一堆石子里取任意数量个石子，不能取者判负）。分析博弈局面。

非常显然 $n=0$ 时后手必胜，否则先手必胜，把所有石子取完即可。我们尝试分析一下博弈的局面。

若 $n=1$ 则双方行动后都会变成没有石子的情况，博弈局面 $\ast = \{0|0\}$，考虑 $n>1$ 时，设 $\ast_i$ 表示恰好有 $i$ 个石子剩余，则：

$\ast_n = \{0,\ast_1,\ast_2\cdots,\ast_{n-1} | 0,\ast_1,\ast_2\cdots,\ast_{n-1} \}$

以 $\ast_2 = \{0,\ast_1 | 0,\ast_1\}$ 为例子，$0$ 显然优超 $\ast_1$。依次类推发现对于任意 $\ast_n(n>1)$ 的可选决策内，$0$ 优超所有决策。因此任意情况下把石子全部取完一定是最优策略。

进一步，有 $\ast_n\parallel 0,\ast_n = -\ast_n$。

定义十四

称 $0,\ast,\ast_2,\cdots$ 为 Nimber。

定理十五

任意有限公平博弈的值一定是某个 Nimber。

现在我们考虑多个公平游戏的组合，于是就有了大家熟知的……

给定 $n$ 堆石子，每堆石子数量分别为 $a_1,a_2,\cdots,a_n$。两人轮流取石子，每人每次可以选择一堆石子，并取走任意多个石子（不能为 $0$），不能取者判负。分析博弈局面。

注意到和博弈是博弈的和，因此博弈局面是 $\sum \ast_{a_i}$。然而我们都知道 Nim 游戏的胜负判定：所有石子数量的异或和为 $0$ 则后手必胜，否则先手必胜。Nimber 和这个有什么关系呢。

大家都知道 SG 函数，事实上，SG 函数就基于这样的 SG 定理：

定理十六

两个公平博弈 $G=\ast_n,H=\ast_m$ 的和博弈 $(G+H) = \ast_{n\oplus m}$，其中 $\oplus$ 为二进制异或。

于是我们就知道了，这里超实数里的 Nimber，其实就对应 SG 函数啊。