标签：xor 游戏博弈论后继异或初探 SG operatorname

博弈论基础

概念

先手：当前局面轮到谁操作，谁就是当前局面的先手。
P 点：当前先手必败点。
N 点：当前先手必胜点。

公平组合游戏（ICG）的性质

没有出边（无法操作）的点是 P 点（公理）。
N 点出边中至少有一条连到 P 点（理解：如果当前局面必胜，那么一定能通过某个操作使得下一局面对手必败）。
P 点出边只会连到 N 点（理解：如果当前局面必败，则不存在在下一局面中使得对手必败的操作）。

SG函数

定义

mex 函数的定义：

\[(1)\qquad\operatorname{mex}(S)=\min(\{k\mid k\not\in S,k\in\mathbb N\}) \]

它将一个数集映射到一个自然数。

SG 函数的定义：

\[(2)\qquad\operatorname{SG}(u)=\operatorname{mex}(\{\operatorname{SG}(v)\mid v\in T_u\}) \]

其中，$ T_u $ 表示从 $ u $ 点的所有后继组成的点集。

SG 定理（证明在性质后面）：

\[(3)\qquad\operatorname{SG}(x)=\operatorname{xor}_{y\in G_x}\operatorname{SG}(y) \]

其中，$ G_x $ 表示 $ x $ 游戏可拆分成的互不干涉的子游戏的集。

（我这么理解游戏的拆分：用一个 $ n $ 维向量 $ \mathbf{a}=(a_1,a_2,\cdots,a_n) $ 表示一个游戏状态。每个维度坐标代表一个子游戏的状态。该状态能到达的其他状态有且只有一个维度坐标发生变化。我们便可以把它拆成几个子游戏。对于每个子游戏，可以把在这个维度上产生变化的边拿出来单独生成一个图来计算。事实上，你可以认为它就是在多个有向无环图上的游戏。）

SG 函数将一个游戏状态（不一定是一个数）映射到一个自然数。

性质

对于当前状态 $ x $，若 $ \operatorname{SG}(x)=0 $ 则 $ x $ 为 P 点，否则为 N 点。

证明

在网上看了一些证明后，我决定自己编一下：

若 $ x $ 没有出边，则 $ \operatorname{SG}(x)=\operatorname{mex}(\varnothing)=0 $，该性质显然成立。
假设我们已经知道，对于 $ x $ 的所有出边连接到的点都满足此性质。
那么，如果 $ \operatorname{SG}(x)=0 $，说明 $ x $ 的所有后继中，没有 SG 函数值为零的。
因此，$ x $ 的所有后继都是 N 点，即 $ x $ 为 P 点。
如果 $ x $ 的 SG 函数值不为零，说明其后继中至少有一个 P 点，即 $ x $ 为 N 点。
应用归纳法即可。

对（3）式的证明：（为了简便，将 SG 函数值简称为 SG 值）

若 $ x $ 的所有子游戏必败，则它们的 SG 值异或和为零，$ x $ 显然为 P 点。
假设对于 $ x $ 的所有子游戏，（3）式成立。
若 $ \operatorname{xor}_{y\in G_x}\operatorname{SG}(y)=k>0 $，则 $ \exists t\in G_x,\operatorname{SG}(t) $ 在二进制下的最高位与 $ k $ 相同。此时，$ \operatorname{SG}(t) \operatorname{xor} k<\operatorname{SG}(t) $。
根据 mex 函数定义，$\forall i\in[0,\operatorname{SG}(t)),\exists s\in G_t,\operatorname{SG}(s)=i $。因此，一定存在 SG 值从 $ \operatorname{SG}(t) $ 转移到 $ \operatorname{SG}(t)\operatorname{xor}k $ 的边（这里的 SG 值指的是 $ t $ 在 $ x $ 子游戏异或和中的贡献）。
子游戏 $ t $ 的 SG 值从 $ \operatorname{SG}(t) $ 转移到 $ \operatorname{SG}(t)\operatorname{xor}k $ 后，$ x $ 子游戏的 SG 值异或和为 $ k\operatorname{xor}k=0 $，即存在有从“子游戏 SG 值异或和大于零”转移到 P 点的边。
综上，“子游戏 SG 值异或和大于零”的情况是一个 N 点。
若 $ \operatorname{xor}_{y\in G_x}\operatorname{SG}(y)=0 $，则无论走那条边都会改变其中一个子游戏的贡献，它是一个 P 点。所以它的 SG 值为 $ 0 $。
应用归纳法即可。

然而你会发现，上面的证明中没有证当“子游戏 SG 值异或和大于零”时，SG 定理成立（$ \operatorname{SG}(x)=k $）。这就是下面我们要证明的。

这等同于：

\[\forall i\in[0,k)\cup\mathbb Z,\exists u\in G_x,v\in T_u,k \operatorname{xor}\operatorname{SG}(u)\operatorname{xor}\operatorname{SG}(v)=i \]

且

\[\nexists u\in G_x,v\in T_u,k \operatorname{xor}\operatorname{SG}(u)\operatorname{xor}\operatorname{SG}(v)=k \]

对于第二个式子，由于一个状态的 SG 值一定不出现在它的后继，显然成立。
推一下第一个式子：

\[\operatorname{SG}(v)=\operatorname{SG}(u)\operatorname{xor}k\operatorname{xor}i\quad(i\in[0,k)\cup\mathbb Z,u\in G_x,v\in T_u) \]

问题变为：证明 $ \exists u\in G_x,\operatorname{SG}(u)\operatorname{xor}k\operatorname{xor}i<\operatorname{SG}(u) $。
问题又变为：证明无论 $ k\operatorname{xor}i $ 最高在哪一位，总存在一个 $ u $，其 SG 值在那一位上是 1。
若 $ k $ 在那一位上是 1，则上述命题显然成立。
否则， $ k $ 在那一位上是 0，$ i $ 在那一位上是 1。如果 $ k $ 在那一位前面与 $ i $ 在那一位前面的数字完全相同，则不满足 $ i<k $ 的条件。但如果有区别，则 $ k\operatorname{xor}i $ 的最高位不是那一位，矛盾。因此，不存在这种情况。

证毕。

Anti-SG 游戏

性质

胜利条件与 ICG 相反，不能行动的玩家判胜。ICG 的性质 2 和 3 仍适用。

SJ 定理

先手必胜条件（二选一）：

游戏的 SG 值不为零，且存在一个单一游戏的 SG 值大于一。
游戏的 SG 值为零，且不存在一个单一游戏的 SG 值大于一。

注意，“单一游戏”不是后继！

如果你觉得用文字语言难以理解，你可以看看我翻译的数学语言：

点 $ x $ 是 N 点，当且仅当：

\[\operatorname{SG}(x)\ne 0,\exists u\in G_x,\operatorname{SG}(u)>1 \]
或

\[\operatorname{SG}(x)=0,\nexists u\in G_x,\operatorname{SG}(u)>1 \]

证明（待添加）

Multi-SG 游戏

性质

无出边的点是 P 点（与 ICG 相同）。
一个单一游戏的后继可以是多个单一游戏（一个一维向量的后继可以是多维向量）。
先手必胜、必败条件与 ICG 相同。
对每次拆分成两堆的游戏有如下性质：

\[\operatorname{SG}(x)=\begin{cases}x-1&4|x\\x&x\equiv1,2\pmod4\\x+1&x\equiv3\pmod4\end{cases} \]

Every-SG 游戏

性质

对没有结束的任何一个单一游戏，操作者必须对其进行一步操作，不能操作判负。

标签：xor,游戏,博弈论,后继,异或,初探,SG,operatorname
From： https://www.cnblogs.com/hihihi198/p/16882051.html

博弈论初探