SG函数

我们研究这样一种游戏，它满足以下三个性质：

由 2 名玩家交替行动
在游戏进程的任意时刻，可以执行的合法行动与这位玩家无关
不能行动的玩家判负

那么这个游戏被称为公平组合游戏。当两名玩家均采取最优策略时，游戏的胜负只和游戏的初始情况有关，和玩家的选择无关（在采取最优策略的情况下）。

我们发现，这类游戏由于性质2，所以游戏似乎可以不记录玩家的状态，只记录游戏目前的情况，那么我们似乎可以将其视为一种类 DP 问题，将游戏的状态使用多维数组甚至状压来保存下来，随后通过不断转移来求解。实际上，它们有一个更为抽象的表达形式：有向图游戏。

给定一个有向无环图，图中有一个唯一的起点，在起点上有一个棋子。两名玩家交替的把这枚棋子沿有向边移动，无法移动者判负。显然的，所有公平组合游戏都可以转化为有向图游戏。

根据前面知识，我们推测图上的每个点都具有必胜或者必败两种状态，可以进行黑白染色。显然，如果一个点可前往的任何点都是必胜点（或者没有点可走），那么它就是一个必败点；相反，如果它可以前往任意一个必败点，那么他就是一个必胜点。

我们有一个更好的方法来表示一个点的必胜或者必败：我们假设 $博弈论（SG函数） - 图1$ 是一个集合，那么定义 $博弈论（SG函数） - 图2$ #card=math&code=%5Coperatorname%7Bmex%7D%28S%29&id=RnnyU) 为求出不属于集合 $博弈论（SG函数） - 图3$ 的最小非负整数的运算，也就是

这时候，对于每个节点 $博弈论（SG函数） - 图4$ ，我们记它的所有后继节点为 $博弈论（SG函数） - 图5$ ，那么有

$博弈论（SG函数） - 图6$ %3D%5Coperatorname%7Bmex%7D%5C%7B%5Coperatorname%7BSG%7D(y_1)%2C%5Coperatorname%7BSG%7D(y_2)%2C%5Ccdots%2C%5Coperatorname%7BSG%7D(y_n)%5C%7D%0A#card=math&code=%5Coperatorname%7BSG%7D%28x%29%3D%5Coperatorname%7Bmex%7D%5C%7B%5Coperatorname%7BSG%7D%28y_1%29%2C%5Coperatorname%7BSG%7D%28y_2%29%2C%5Ccdots%2C%5Coperatorname%7BSG%7D%28y_n%29%5C%7D%0A&id=HQUB3)

特别的，整个有向图游戏的 SG 函数值为起点的 SG 函数值。

那么，我们不难得出定理：

有向图的某个局面必胜，但且仅当对应节点的 SG 函数值大于 0
有向图的某个局面必败，但且仅当对应节点的 SG 函数值为 0

Nim游戏

给定 $博弈论（SG函数） - 图7$ 堆石子，第 $博弈论（SG函数） - 图8$ 堆石子有 $博弈论（SG函数） - 图9$ 个石子。两名玩家轮流行动，每次可以任选一堆，从中拿走任意个石子（可以全部拿完，但不可以不拿）。取走最后的石子者获胜（也就是说无法再拿石子的人会输）。在两者均采取最优策略的情况下，问先手是否必胜。

如果使用朴素的转移方法，那么时空复杂度至少为 $博弈论（SG函数） - 图10$ #card=math&code=O%28%5Cprod%5Climits_%7Bi%3D1%7D%5Ena_i%29&id=gPYxm)，是比较难以承受的（还不太好写）。但庆幸的是，这题有一个很朴素的解法：

定理

Nim 博弈先手必胜，当且仅当
$博弈论（SG函数） - 图11$

证明

当 $博弈论（SG函数） - 图12$ 均为 0 时，此时所有物品被取光，此时 $博弈论（SG函数） - 图13$ 。
对于某个局面，倘若 $博弈论（SG函数） - 图14$ ，我们记 $博弈论（SG函数） - 图15$ 的二进制表示下 1 的最高位在第 k 位，那么至少存在一堆石子 $博弈论（SG函数） - 图16$ ，使得其二进制下第 k 位为 1。显然 $博弈论（SG函数） - 图17$ ，所以我们只需要将这对石子拿到 $博弈论（SG函数） - 图18$ 个，那么就可以使得 $博弈论（SG函数） - 图19$ 。
相反，对于某个局面，如果 $博弈论（SG函数） - 图20$ ，那么无论怎么取，新的 $博弈论（SG函数） - 图21$ 都一定不为 0（涉及亦或的相关知识，可以使用反证法证明）。
根据数学归纳法，我们发现当 $博弈论（SG函数） - 图22$ 时先手必败，因为无论怎么走都会使得下一个状态的 $博弈论（SG函数） - 图23$ 不为 0；反之， $博弈论（SG函数） - 图24$ 时先手必胜，因为必然存在一种使下一个状态的 $博弈论（SG函数） - 图25$ 为 0 的状态。

与 SG 函数的关系

不难发现， $博弈论（SG函数） - 图26$ 就是这个游戏的 SG 函数。

多个有向图游戏

假设 $博弈论（SG函数） - 图27$ 是 $博弈论（SG函数） - 图28$ 个有向图游戏，他们共同组成了一个大有向图游戏 $博弈论（SG函数） - 图29$ 。两名玩家轮流进行，每次选一个子游戏来玩一把，当某个人无法进行任何子游戏时，他将输掉总游戏 $博弈论（SG函数） - 图30$ 。
有向图游戏的和的 SG 函数值等于各个子游戏的 SG 函数值的异或和，也就是

$博弈论（SG函数） - 图31$ %3D%5Coperatorname%7BSG%7D(G_1)%5Coperatorname%7Bxor%7D%5Coperatorname%7BSG%7D(G_2)%5Coperatorname%7Bxor%7D%5Ccdots%5Coperatorname%7Bxor%7D%5Coperatorname%7BSG%7D(G_n)%0A#card=math&code=%5Coperatorname%7BSG%7D%28G%29%3D%5Coperatorname%7BSG%7D%28G_1%29%5Coperatorname%7Bxor%7D%5Coperatorname%7BSG%7D%28G_2%29%5Coperatorname%7Bxor%7D%5Ccdots%5Coperatorname%7Bxor%7D%5Coperatorname%7BSG%7D%28G_n%29%0A&id=o3SaQ)

证明方法和 Nim 游戏的证明方式类似，不再赘述（其实我也一时不知道咋证明）。

用子游戏的性质来证明 Nim 游戏定理

我们发现，Nim 游戏就可以视作 $博弈论（SG函数） - 图32$ 个子游戏：假设在每某子游戏中，有 $博弈论（SG函数） - 图33$ 个石子，每次可以选取拿走任意数量的石子，那么我们不难发现，有

$博弈论（SG函数） - 图34$ %3D%5Coperatorname%7BSG%7D(m-1)%5Coperatorname%7Bxor%7D%5Coperatorname%7BSG%7D(m-2)%5Coperatorname%7Bxor%7D%5Ccdots%5Coperatorname%7Bxor%7D%5Coperatorname%7BSG%7D(0)%0A#card=math&code=%5Coperatorname%7BSG%7D%28m%29%3D%5Coperatorname%7BSG%7D%28m-1%29%5Coperatorname%7Bxor%7D%5Coperatorname%7BSG%7D%28m-2%29%5Coperatorname%7Bxor%7D%5Ccdots%5Coperatorname%7Bxor%7D%5Coperatorname%7BSG%7D%280%29%0A&id=wGvT1)

通过逆推发现， $博弈论（SG函数） - 图35$ %3Dx#card=math&code=%5Coperatorname%7BSG%7D%28x%29%3Dx&id=v8tal)，所以第 i 个游戏中，石子堆有 $博弈论（SG函数） - 图36$ 个石子，这个子游戏的 SG 值为 $博弈论（SG函数） - 图37$ ，所以总游戏的 SG 值就是 $博弈论（SG函数） - 图38$ 。通过这种方法，我们从另一角度得到了 Nim 定理。