博弈论变形

· · 个人记录

博弈论虽然冷门，但是各种奇奇怪怪的基础变形要是考了考场上肯定推不出来（至少我是这样的）。我脑子又不好使，容易忘事，写个东西心里踏实。

全文由 《组合游戏略述——浅谈SG游戏的若干拓展及变形-贾志豪》 整理补充。

Anti-SG

定义

Anti-SG 游戏规定，决策集合为空的游戏者赢。且其他规则与 SG 游戏相同。

结论（SJ 定理）

需要注意的是，下述结论只在保证了对于任意一个 SG 函数为 0 的单一游戏，它最多只能修改成一个 SG 函数为 1 的游戏时有效。

举个栗子， Anti-Nim 是符合要求的。

先手必胜当且仅当:

(1) 游戏的 SG 函数不为 0 且游戏中某个单一游戏的 SG 函数大于 1 。

(2) 游戏的 SG 函数为 0 且游戏中没有单一游戏的 SG 函数大于 1 。

证明

证明以下两点即可：

(1) 游戏中的任何一个先手必败局一定只能够转移到先手必胜局。

(2) 游戏中的任何一个先手必胜局一定能够转移到至少一个先手必败局。

先看先手必败局：

  1. 当前游戏的 SG 函数为 0 且游戏中某个单一游戏的 SG 函数大于 1 。

因为当前游戏的 SG 函数为 0，所以它所能转移到的任何一个局面的 SG 函数值不为 0 。

因为当前游戏的 SG 函数为 0，且游戏中某个单一游戏的 SG 函数大于 1 ，所以它一定至少有两个单一游戏的 SG 函数大于 1，所以它所能转移到的任何一个局面都至少有一个单一游戏的 SG 值大于 1。

因此，当前游戏必定转移到先手必胜状态的 (1)。

  1. 局面的 SG 函数不为 0 且游戏中没有单一游戏的 SG 函数大于 1。

如果将某个单一游戏的 SG 值修改为大于 1 的数，那么修改后，它的 SG 函数值一定不为 0 ，而且就会有某个单一游戏的 SG 函数大于 1 ，即先手必胜状态的 (1)。

如果将某个单一游戏的 SG 值修改为 0，那么修改后，它的 SG 函数值为 0，且没有单一游戏的 SG 函数大于 1，即先手必胜状态的 (2)。

因此，当前游戏必定转移到任意一个先手必胜状态。

再看先手必胜局：

  1. 游戏的 SG 函数不为 0 且游戏中某个单一游戏的 SG 函数大于 1 。

如果当前局面只有一个单一游戏的 SG 值大于 1 ，那么我们就可以修改这个单一游戏到 0 或 1，来使它变成没有一个单一游戏的 SG 值大于 1 且所有游戏总的 SG 值为 1 的一个局面。

如果当前局面有至少两个单一游戏的 SG 值大于 1，那么我们就可以把当前局面修改成一个 SG 值为 0 的局面，并且至少有两个单一游戏的 SG 值大于 1 。（当至少有一个游戏的大于 1 且 SG 值为 0 的时候，不可能只有一个单一游戏的 SG 值大于 1）

因此，当前游戏必定转移到任意一个先手必败状态。

  1. 游戏的 SG 函数为 0 且游戏中没有单一游戏的 SG 函数大于 1 。

如果决策集合为空就赢了。

反之可以修改一个单一游戏，使得局面变成没有一个单一游戏的 SG 值大于 1 且所有游戏总的 SG 值为 1 的一个局面。

因此，当前游戏必定转移到任意一个先手必败状态。

综上，即可证。

Multi-SG

定义：

Multi-SG 游戏规定，在符合拓扑原则的前提下（即该游戏图不会出现环），一个单一游戏 的后继可以为多个单一游戏。且其他规则与 SG 游戏相同。

结论：

一个游戏的 SG 函数，等于 \text{mex}\{\text{ 后继状态的 SG 和（即异或和） }\} 。

形式化的 \text{mex}_S\{\text{XOR}_{k\in S} SG_k\}~~\text{（S 是一个后继状态）}

证明

感性证明一波。

考虑普通的 SG 游戏，其 SG 值为 \text{mex}\{\text {后继状态 k 的 SG 值 } \} 。

对于 \text{mex} 中的每一项，实际上是丢给了对方一个 SG 函数为 SG_k 的游戏。

那么对于 Multi-SG，实际上是丢给的对方一个 SG 值为 \text{XOR}_{k\in S} SG_k 的游戏。

类似的就可以这么做了。

Every-SG

定义：

Every-SG 游戏规定，对于还没有结束的单一游戏，游戏者必须对该游戏进行一步决策。且其他规则与普通 SG 游戏相同。

结论

设 \text{step(v)} 表示当前状态最慢几步进入终止状态。那么贪心的，有：

\text{step(v)}= \begin{cases} 0, & \text{v 为终止状态} \\ \max\{\text{step(u)}\}+1, & \text{v 为必胜状态，u 为 v 的后继状态，u 是必败状态}\\ \min\{\text{step(v)}\}+1, & \text{v 为必败状态，u 为 v 的后继状态} \end{cases}

证明如下：

式 1 显然。

式 2 因为当前是必胜状态，那么先手肯定想晚一点结束这个游戏，而且不会走到一个状态让对手必胜，因为这样不会更优。

式 3 因为当前是必败状态，那么先手肯定想快一点结束这个游戏，而且这个状态因为是必败状态，所以后继状态一定都必胜。

对于 Every-SG 游戏先手必胜当且仅当单一游戏中最大的 \text{step} 为奇数。

证明

首先证明所有的单一游戏，如果 \text{step} 为奇数，那么先手必胜，否则先手必败。

显然 \text{step} 为 0 时先手必败。

假设已经证明了所有 \text{step} 小于等于 K 的状态符合要求。

那么对于一个状态，如果它是先手必败状态，那么它的后继状态全部是先手必胜状态，而先手必胜状态的 \text{step} 全部为奇数，那么它的 \text{step} 为偶数。

如果一个状态是先手必胜状态，那么它一定存在至少一个后继状态是先手必败状态，而先手必败状态的 \text{step} 全部为偶数，那么它的 \text{step} 为奇数。

那么根据上述 \text{step} 的定义，它是某个单一游戏在双方都采取最优策略的时候结束的步数，那么最后结束的游戏就是 \text{step} 最大的那个，所以如果那个为奇数，先手必胜，否则先手必败。

翻硬币游戏

定义：

#### 结论： 局面的 SG 值为局面中每个正面朝上的棋子单一存在时的 SG 值的异或和。 #### 证明： 先假设从左往右数第 $k$ 个硬币的分值是 $2^k$ 。 那么对于任意一个局面，其后继状态的分值一定小于它。 考虑用增量法证明，显然分值为 $0$ 和 $1$ 的局面符合上述结论。 假设分值小于等于 $K$ 的局面都证明了符合上述结论，考虑证明分值等于 $K+1$ 的局面符合上述结论。 首先把最右边的硬币单独取出，那么剩下的局面的分值是小于等于 $K$ 的，符合上述结论。那枚最右边的硬币的 SG 值是 $\text{mex}\{\text {后继状态的 SG 和}\}$ 。而它所有的后继状态都是小于等于 $K$ 的，也是符合上述结论的。那么这两个游戏的 SG 和是他们的异或和，即得证。 ### 树的删边游戏 #### 定义： 给出一个有 $N$ 个点的树，有一个点作为树的根节点。游戏者轮流从树中删去边，删去一条边后，不与根节点相连的部分将被移走。谁无路可走谁输。 #### 结论： 叶子节点的 SG 值为 $0$。中间节点的 SG 值为它的所有子节点的 SG 值加 $1$ 后的异或和。 #### 证明： 考虑用增量法证明。 一个节点和两个节点的情况显然成立。 假设节点数小于等于 $K$ 的局面都证明符合上述结论，考虑证明节点数为 $K+1$ 的局面符合上述结论。 > 1. 如果根节点只有一个儿子。设根为 Root，其唯一的儿子为 Son 。那么如果切掉 Root 和 Son 的连边，那么就得到了一个 SG 值为 $0$ 的局面。如果切掉 Son 中任意的一条边，那么切完之后的节点数是小于等于 $K$ 的，而小于等于 $K$ 的局面已经证明了符合上述结论，那么如果切完之后 Son 的 SG 值为 $x$ ，Root 的 SG 值就是 $x+1$ 。因为知道了 Son 的 SG 值为 $SG(Son)$ ，那么它存在 SG 值为 $[0,SG(Son)-1]$ 的后继状态，那么 Root 的后继状态的 SG 值就可以为 $[1,SG(Son)]$ 那么 Root 的 SG 值就为 $SG(Son)+1$ 。 > > 2. 如果根节点有多个儿子。那么对于每个儿子都存在上述结论。那么把这些子游戏结合到一起，就是 SG 游戏的和，即异或和。 即得证。