【博弈论】SG(Sprague–Grundy)定理证明和Nim游戏正确性证明

网上好像都是引用的维基，或者证的很不严谨

这里提供一个稍微严谨一点的证明，SG的部分基本上参考了维基 （自己想过，没想出来www）

要转载的话随便转载，就是不知道这垃圾玩意有没有转载的必要啊

定义

公平组合游戏，Nim游戏

满足如下条件的游戏被称为公平组合游戏：

• 两人轮流操作
• 如果有人不能操作，那么他就输了
• 对于当前状态，可以做的决策只与状态有关，和哪个人操作无关

Nim游戏：有 $n$ 堆石子，二人轮流操作，每人可以在某堆中任意取若干个，但不能不取。如果某人不能取了那么它就输了。

常见的棋类就不是公平组合游戏，因为你不可以动别人的棋子。但Nim就是公平组合游戏，因为任何一方都可以拿任何一堆中的石子。

描述一个局面

对于一个局面，我们其实只关心它能到达哪些局面，因此我们用集合来描述一个局面，集合中包含它能到达的后继局面。 （因此你如果要展开这个集合，你会看到很多集合套集合）。如果它没有后继局面（即无法操作），我们用空集描述它。

特殊地，我们记 $\ast n$ 表示一堆含有 $n$ 个石子的Nim局面。容易发现 ∗ n = { ∗ 0 , ∗ 1... ∗ ( n − 1 ) } *n=\{*0,*1...*(n-1)\} ∗n={∗0,∗1...∗(n−1)}，是一个递归的结构。如果要展开就会变成集合套集合。

比如 ∗ 4 = { ∅ , { ∅ } , { ∅ , { ∅ } } } *4=\{\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\}\} ∗4={∅,{∅},{∅,{∅}}}。

对于一个局面，如果是先手必胜，我们说它是 $N$ 的，否则就是 $P$ 的。

关于胜负情况，好像没有找到相关的函数描述。这里我们用 $win(S)$ 表示局面 $S$ 的胜负情况，其值为 $P$ 或者 $N$。

判定局面的胜负性：

• 如果当前局面可以到达 至少一个 $P$ 局面，那当前是 $N$ 局面
• 如果当前局面后继 全部都是 $N$ 局面，那当前是 $P$ 局面

局面间的关系

局面的和：对于两个局面 $S,S^{\prime }$，定义 $S+S^{\prime }$ 表示：现在同时进行 $S$ 和 $S^{\prime }$ 两个游戏，两边都不能操作就算输，这样的一个局面。如何描述它呢？

很明显，如果你要走一步，要么走 $S$ 的一个后继，要么走 $S^{\prime }$ 的一个后继。比如说你走了 $S$ 的后继 $s$，那接下来就是 $s$ 和 $S^{\prime }$ 两个游戏同时进行，是一个子结构。另一边同理。因此我们可以写出这样的定义式：

S + S ′ = { s + S ′ ∣ s ∈ S } ∪ { S + s ′ ∣ s ′ ∈ S ′ } S+S'=\{s+S'|s\in S\}\cup\{S+s'|s'\in S'\} S+S′={s+S′∣s∈S}∪{S+s′∣s′∈S′}

把它递归展开就可以得到 $S+S^{\prime }$ 局面的集合表达了。当然，这一般只用于给出形式化的定义，实际上不会用，因为复杂度爆炸。当我们需要考虑两个局面相加时，通常我们是根据意义来理解这件事情，想象发生了什么，并描述出关系，而不会用它来暴力展开。比如说你可以很容易发现，局面的相加满足交换律和结合律。

局面的等价性：通常在我们研究问题的过程中，如果有两个东西，把一个换成另一个不会影响问题，我们就说它俩等价

局面的等价怎么描述？如果根据输赢，你会发现，只要 $n>0$，$\ast n$ 就是 $N$ 的。但显然我们很有必要关心每一堆里具体有多少石子。因此只根据输赢描述肯定不行。

我们发现问题出在把局面组合起来的时候。因此我们这样描述：对于局面 $G,G^{\prime }$，$\forall H,win(G+H)=win(G^{\prime }+H)$ （这里的等于是指输赢情况相等），则我们说 $G$ 和 $G^{\prime }$ 等价，记作 $G\approx G^{\prime }$。

SG 定理

SG 定理是说，对于每个局面 $S$，都存在恰好一个 $n$ 使得 $S\approx \ast n$。并且 $n$ 的值为所有 $S$ 的后继状态 $n$ 值的 mex。这个 $n$ 值就是 $SG$ 函数的值 $SG(S)$。

SG 的另一个性质是，若 $S=A_1+A_2...+A_n$，则 $SG(S)=SG(A_1)\oplus SG(A_2)\oplus ...\oplus SG(A_N)$，其中 $\oplus$ 为 Nim 和，也就是我们熟悉的异或和。关于这个的证明：首先使用 SG 定理，然后参考【Nim游戏的正确性证明】，得到它是对的。这个放在 SG 定理证明的后面。

证明

引理1

对于一个 $P$ 的局面 $A$ 和任意局面 $G$，$G\approx G+A$。

对于任意 $H$，需要满足 $win(G+H)=win(G+H+A)$。分类讨论。

如果 $win(G+H)=P$，那么 $win(G+H+A)$ 一定也是 $P$。为什么呢？整个局面可以看成 $(G+H)+A$，由两个后手必胜的局面组成。无论先手在哪个部分操作，后手都可以用对应的必胜策略来应对。两边后手都不会输，因此总局面也一定是后手必胜。

如果 $win(G+H)=N$，那么 $win(G+H+A)$ 一定也是 $N$。同样分成 $G+H$ 和 $A$ 两部分，$G+H$ 是先手必胜的，先手按必胜策略在这里操作一步后，就形成两个先手必败的局面给后手。按照上一种情况中的讨论可知，操作完这一步后的先手（即原来的后手）必败。 那也就是原来的先手必胜，就是

引理2

$win(G+G^{\prime })=P⟺G\approx G^{\prime }$

考虑 $G+G+G^{\prime }$。

一方面它等于 $(G+G)+G^{\prime }$。发现 $G+G$ 一定是后手必胜的，因为后手可以和先手做对称的操作，只要先手能走，后手就一定能走，后手永远不会输。因此它是一个 $P$ 的局面 $+G^{\prime }$，根据引理1知它等价于 $G^{\prime }$

另一方面它等于 $G+(G+G^{\prime })$，由于 $G+G^{\prime }$ 是 $P$ 的，所以它等价于 $G$。

从而 $G\approx G+G+G^{\prime }\approx G^{\prime }$。

前置知识：结构归纳法

结构归纳法可以看成是数学归纳法在DAG上的拓展：我们先说明一些命题是对的，然后命题之间存在依赖关系（无环），对于每个依赖关系证明：若前置命题对，则某命题对，从而推得所有命题都对。

数学归纳法可以看成是对一条退化成链的DAG进行结构归纳法

SG定理的证明

我们使用结构归纳法证明：首先没有后继状态的局面等价于 $\ast 0$，然后对于局面 $S$，我们证明：如果它的后继中SG定理成立，那么 $S$ 中SG定理成立。

即，设：对于局面 S = { S 1 , S 2 . . . S k } S=\{S_1,S_2...S_k\} S={S1​,S2​...Sk​}，假设 $S_1,S_2...S_k$ 都等价于一些单堆 Nim 游戏，设它们为 $\ast n_1,\ast n_2...\ast n_k$，那么存在 $m$ 使得 $S\approx \ast m$，并且我们知道 m = m e x { n 1 , n 2 . . . n k } m=mex\{n_1,n_2...n_k\} m=mex{n1​,n2​...nk​}

显然 S ≈ S ′ = { ∗ n 1 , ∗ n 2 . . . ∗ n k } S\approx S'=\{*n_1,*n_2...*n_k\} S≈S′={∗n1​,∗n2​...∗nk​}。 考虑证明 $S^{\prime }\approx \ast m$。

根据引理2，这件事情等价于 $win(S^{\prime }+\ast m)=P$。分类讨论

1. 假设先手在 $S^{\prime }$ 中操作，走到了 $\ast x$。若 $x<m$，显然后手可以在 $\ast m$ 中也走到 $\ast x$，变成两个相同局面同时进行，显然是后手必胜。如果 $x>m$，那么后手可以继续在 $\ast x$ 中操作，走到 $\ast m$，又变成两个相同局面，后手必胜。
2. 假设先手在 $\ast m$ 中操作，走到了 $\ast x$，那显然后手就在 $S^{\prime }$ 中走，走到 $\ast x$，后手必胜

综上，$win(S^{\prime }+\ast m)=P$，从而 $S^{\prime }\approx \ast m$。又因为 $S\approx S^{\prime }$，从而 $S\approx \ast m$。

Nim游戏正确性证明

我们知道，取 $a_i$ 的异或和，大于 $0$ 就是先手必胜，为 $0$ 就是后手必胜。

我们使用数学归纳法证明。设命题 $P(k)$ 表示：当 $\sum a_i\le k$ 时，结论成立。

显然 $P(0)$ 成立，因为此时 $a_i$ 一定全 $0$，异或和为 $0$，后手胜。

下证： 当 $P(k-1)$ 成立时， $P(k)$ 成立。

设此时 $a_i$ 的异或和为 $x$。分类讨论：

若 $x>0$，设 $x$ 二进制最高位为 $2^p$ 位。那么一定有至少一个 $a_i$，它的 $2^p$ 位为 $1$。我们把 $a_i$ 变成 $a_i\oplus x$，那么 $a_i$ 比 $p$ 高的位不变，$p$ 位上由 $1$ 变成 $0$，不管后面怎么变 $a_i$ 都会变小。这样一来，所有 $a_i$ 的异或和变成了 $0$，并且和一定 $<k$。根据 $P(k-1)$ 成立，此时的 $a_i$ 的后手必胜。也就是说原来的 $a_i$ 先手必胜。

若 $x=0$，无论先手如何操作，和都会变小，并且异或一定会变成一个非 $0$ 的数。（将 $a$ 变成 $a^{\prime }<a$，异或和变化为 $a\oplus a^{\prime }$，当且仅当 $a^{\prime }=a$ 时它可以为 $0$，由于 a ′ < a a'a′<a，因此它一定不为 $0$）根据 $P(k-1)$ 成立，此时的 $a_i$ 先手必胜，也就是原来的 $a_i$ 后手必胜。

综上，$P(k-1)$ 成立时，$P(k)$ 成立。

证明概括

SG：你发现一个SG值和单堆Nim唯一的不同在于它可以变大，但是变大的话你显然可以再变回来，所以和单堆Nim等价

Nim：你发现你找一个最高位重合的异或一下就可以把非0的异或和变成0，并且异或和为0时无论如何都会变成非0