浅谈算法——博弈论（从零开始的博弈论）

网上的博弈博客和论文有很多，但是有些没有详细的证明，仅仅是给出了结论。今天作者将一些常见的博弈论模板集中起来，给大家介绍一下博弈论中一些单一游戏的决策和常见的Nim模板与证明。 注：下列游戏都建立在双方都有最优策略的情况下，若未加以说明，则每人每次至少取一个石子。 ## 例1：取石子游戏之一 有两个游戏者：$A$和$B$，有$n$颗石子。 约定：两人轮流取走石子，每次可取$1,2$或$3$颗。$A$先取，取走最后一颗石子的人获胜。 问题：$A$有没有必胜的策略？ 分析：这是小学必备奥数题之一，我们可以很容易的知道，当$n$为$0,4,8,12……$时，$A$必定会输，因为不论$A$取多少，$B$只要和$A$共同取走$4$即可；当$n$不为$0,4,8,12……$时，$A$只需要将$n$取成$4$的倍数，这样就变成了$B$先取，$B$一定会输，所以$A$一定会赢。 经过我们的分析发现，对这个游戏而言，$0,4,8,12……$这些状态是对于先手的**必败状态**，而其他状态是对于先手的**必胜状态**。 如果我们推广一下，每次不一定取$1,2,3$颗，而是取$1\sim m$颗，那么我们就可以得到，如果$n\%(m+1)=0$，即为先手**必败状态**，否则为先手**必胜状态**。而这个游戏就是著名的**巴什博弈（Bash Game）** 下面，我们现在介绍一下有关博弈的一些名词和概念 **1、平等组合游戏** - 两人游戏。 - 两人轮流走步。 - 有一个状态集，而且通常是有限的。 - 有一个终止状态，到达终止状态后游戏结束。 - 游戏可以在有限的步数内结束。 - 规定好了哪些状态转移是合法的。 - 所有规定对于两人是一样的。 因此我们的例1提到的游戏即为一个平等组合游戏，但是我们生活中常见的棋类游戏，如象棋、围棋等，均不属于平等组合游戏，因为双方可以移动的棋子不同，不满足最后一个条件；而我们后续提到的游戏，以及博弈中的其他游戏，基本属于平等组合游戏 **2、N状态（必胜状态），P状态（必败状态）** 像例1的分析一样，$0,4,8,12……$等状态就是对于先手的P状态（必败状态），其他的则是对于先手的N状态（必胜状态）。 那么我们定义两个状态之间的转换： - 所有的终止状态都为P状态 - 对于任意的N状态，存在至少一条路径可以转移到P状态 - 对于任意的P状态，只能转移到N状态 证明过于简单，这里不再赘述，我们只需要明白一点，每个人都会选择最策略即可。 当然这里所说的都是最后走步的人获胜的游戏，至于那些走到最后失败的游戏，我们在最后做了一个简单的讲解（**Anti Nim**）。 ## 例2：取石子游戏之二 将例1的游戏扩展一下，我们定义一个集合$S=\{{p_{1},p_{2},...,p_{k}}\}(k \in Z^*)$，$A,B$在游戏的时候取走的石子数必须是集合里的数，其他条件不变。 那么，$A$还有必胜策略吗？ 有没有必胜策略，我们关键是要找到哪些状态是P状态，哪些状态是N状态，不过，本题没有例1那么容易判断，因此我们需要引入一个新东西——SG函数，它的定义如下： $$f(v)=mex\{f(u)|u\in child[v]\}$$ 其中，mex(minimal excludant)是定义在整数集合上的操作。它的自变量是任意整数集合，函数值是不属于该集合的最小自然数。 $$mex(A)=min\{k|k \in \complement_{N}A\}$$ 那么，终止状态的SG值显然为$0$，并且SG值为$0$的状态就是P状态，SG值不为$0$的状态就是N状态。 证明则非常显然，SG值为$0$的状态，说明它的所有后继状态都不为$0$，也就是它只能转移到非$0$状态，而SG值不为$0$的状态则不一样。那么SG值为$0$的状态就是必败状态的定义，SG值不为$0$的状态就是必胜状态的定义，所以我们只需要用集合S求出每个状态的SG值即可。 ## 例3：取石子游戏之三 有$n$个石子，$A,B$两人轮流取石子，规定他们每次至多只能取当前石子总数$\lceil \dfrac{s}{2}\rceil$个石子，问$A$先手是否有必胜策略 这题主要是为了加强大家对SG函数的理解，我们考虑从$0$开始 $SG(0)=0,SG(1)=1,SG(2)=0,SG(3)=mex\{SG(3-1),SG(3-2)\}=2$ $SG(4)=mex\{SG(4-1),SG(4-2)\}=1...$ 我们把他们列出来找下规律： ``` 0,1 0,2,1,3 0,4,2,5,1,6,3,7 0,8,4,9,2,10... ``` 好像有个很奇怪的规律：数列在间隔递增，上一行的数间隔着插在下一行的数中间。没错，这就是本题SG函数的规律，先手必败当且仅当SG值为$0$。 ## 例4：取石子游戏之四（Nim游戏） 有$n$堆石子，石子数目分别为$x_{1},x_{2},...,x_{n}$，$A,B$两人每次可以选一堆石子取走任意多个，问$A$先手是否有必胜策略。 这题相当于例2的扩展版本，由于这里有多堆石子，因此我们可以得到多个SG值，而且这些SG值必定为$x_{1},x_{2},...,x_{n}$，那么我们怎么由这一些SG值得到整局游戏的SG值呢？ Nim游戏的神奇之处在于它的SG值和异或扯上了关系，Nim游戏中先手必败当且仅当$x_{1}\oplus x_{2}\oplus...\oplus x_{n}=0$,$(\oplus$为异或)，那么，这个为什么是成立的？ 首先，$\oplus$满足如下定律和性质 - 交换律：$x\oplus y=y\oplus x$ - 结合律：$x\oplus(y\oplus z)=(x\oplus y)\oplus z$ - 拥有单位元：$0\oplus x=x$ - 相同两数运算为0：$x\oplus x=0$ - 消除律：$x\oplus y=x\oplus z\Rightarrow y=z$ 当Nim游戏的SG值为$0$时，我们假定取$x_{k}$中的某些石子，使得其变成$x_{k}'$，我们假设$x_{1}\oplus x_{2}\oplus...\oplus x_{k}\oplus...\oplus x_{n}=0=x_{1}\oplus x_{2}\oplus...\oplus x_{k}'\oplus...\oplus x_{n}$，根据消除律可得，$x_{k}=x_{k}'$，这与我们的条件相矛盾，因此说明在取了石子之后，SG必然发生了改变； 那么对于一个SG值不为$0$的状态，我们必然可以通过一个操作，使得SG值变$0$。我们只需要找到当前SG最左端为$1$的一列（二进制），任意找到一堆石子使得那一列同样为$1$，从这堆中取走若干个石子，使得SG'值为$0$。这是显然可以的，因为将那一列变成$0$，这个数就必然变小了，对于其他列只需要把$0$变成$1$，$1$变成$0$即可。 因此，我们得到，对于Nim游戏而言，必败状态当且仅当$x_{1}\oplus x_{2}\oplus...\oplus x_{n}=0$，对于其他情况，先手必能使当前局面变成必败状态。 ## 例5：取石子游戏之五（Nimk） 有$n$堆石子，石子数目分别为$x_i$，$A,B$两人每次可以选取最多$k$堆石子，并从选中的每堆石子堆中取走任意多的石子，问$A$是否有必胜策略 首先这题又称Nimk，那么肯定和Nim游戏有关联，其实Nimk就是Nim游戏的一个简单扩展 Nimk存在必胜策略，当且仅当，将所有石子数转成二进制后，存在某位上，所有二进制数中1的个数之和$\%(k+1)$不为$0$，用数学语言表述，则存在一个数$t$，使得$(\sum\limits_{i=1}^n x_i\land2^{t-1})\%(k+1)\ne 0$ 如何证明？首先终止局面全为$0$，满足必败条件 对于任意一种必胜状态，必然存在一种取石子方式，使得其可以转移到必败状态。我们设必胜状态下，$1$的个数$\%(k+1)$不为$0$的最高二进制位上有$m$个$1$，则将这些$1$都改成$0$需要更改$m$堆；若遇到下一个二进制位上，$1$的个数$\%(k+1)$不为$0$，记该位上有$r$个$1$，并且记之前改变的$m$堆在该位上有$a$个$1$和$b$个$-1$（所有变量都是在$\%(k+1)$之后的值） 然后我们分情况讨论： - $a\geqslant r$，则将$r$个$1\rightarrow0$ - $b\geqslant k+1-r$，则将$k+1-r$个$0\rightarrow 1$ - $a<r$且$b<k+1-r$，则我们改变之前$m$堆以外的$r-a$堆，那么此时我们改变的堆数为$m+r-a\Rightarrow a+b+r-a\Rightarrow b+r$，又因为$b+r<k+1-r+r\Rightarrow k+1$，所以我们改变的堆数$m-r+a<k+1$，那么这样的改法是合法的 重复上述操作，我们必然能使每一位上的$1$的个数$\%(k+1)$为$0$，即转移到先手必败态 那么对于任意一个先手必败态而言，由于我们每次最多只能选取$k$堆，所以我们不能在同一二进制位上改变$k+1$个值；而且每次改变会导致一系列的连锁反应，因此我们无法从一个先手必败态转移到先手必败态，证毕 其实Nim游戏相当于Nimk中$k=1$的情况…… ## 例6：取石子游戏之六（Wythoff's Game） 有两堆石子，个数为$x_{1},x_{2}$；$A,B$轮流取石子，规定要么只取一堆的任意多个，要么在两堆里取同样任意多个，问$A$先手是否有必胜策略。 这种情况下是颇为复杂的，普通SG函数已经无法解决这个问题。我们用$(a_{k},b_{k}),(a_{k} \leqslant b_{k},k \in [0,n])$表示两堆物品的数量并称其为局势，如果甲面对$(0,0)$，那么甲已经输了，这种局势我们称为奇异局势。 那么，我们该如何去找到这些奇异局势呢？ 首先我们知道，局势$(x,y)$和局势$(y,x)$是等价的。考虑递推的思想，我们已经知道$(0,0)$是个奇异局势，也就是个先手必败态，那么根据定义，能够到达$(0,0)$状态都为先手必胜态，也就不是奇异局势。 我们从直角坐标系来考虑，$(0,0)$为奇异局势后，那么$(0,k),(k,0),(k,k)$都是非奇异状态，我们把它们划去，然后找到第一个没有被划的点，也就是$(1,2)$和$(2,1)$（因为他俩对称），然后按同样的方法处理，之后找到$(3,5)$和$(5,3)$...  这样我们可以得到前几个奇异局势是：$(0,0)$、$(1,2)$、$(3,5)$、$(4,7)$、$(6,10)$、$(8,13)$、$(9,15)$、$(11,18)$、$(12,20)$... 通过找规律，我们大胆猜测一下$(a_{k},b_{k})$满足： - $a_{k}$是未在之前出现过的最小自然数 - $b_{k}=a_{k}+k$。 下面我们给出其证明： - 根据我们寻找奇异局势的方法，可以得知$a_{k}$为之前未出现的最小自然数 - 我们使用数学归纳法，假定之前的$k\in[1,n],(a_{k},a_{k}+k)$都为奇异局势，我们只需要证明$(a_{n+1},a_{n+1}+n+1)$为奇异局势即可 从局势$(a_{n+1},a_{n+1}+n+1)$出发，只可能走向三种状态，从左边拿一点，从右边拿一点，或者两边一起拿一点： 情况一：因为比$a_{n+1}$小的数在之前都出现过，所以一旦左边少了，我们只要把右边拿到相同的情况即可 情况二（右边取的较少）：这样使得两堆之间差值变小了，变成了$(a_{n+1},a_{n+1}+m)$，这样我们拿成$(a_{m},a_{m}+m)$即可 情况二（右边取的较多）：这样使得右边比左边少了，这样就变成了和情况一类似，可以直接取到奇异拘束 情况三：若拿成$(a_{m},a_{m}+n+1)$，我们直接取成$(a_{m},a_{m}+m)$即可 奇异局势还有如下三条性质： - 任何自然数都包含在一个且仅有一个奇异局势中。 - 任意操作都可将奇异局势变为非奇异局势。 - 采用适当的方法,可以将非奇异局势变为奇异局势。 我们同样给出其证明： - 由于$a_{k}$是未在前面出现过的最小自然数，所以有$a_{k}>a_{k-1}$ ,而$b_{k}=a_{k}+k>a_{k-1}+k-1=b_{k-1}>a_{k-1}$ 。所以性质1，成立。 - 若只改变奇异局势$(a_{k},b_{k})$的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使$(a_{k},b_{k})$的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。 - 假设面对的局势是$(a,b)$： 如果 $a=b$，则同时从两堆中取走$a$ 个物体，就变为了奇异局势$(0,0)$； 如果$a=a_{k},b>b_{k}$，那么，取走$b-b_{k}$个物体，即变为奇异局势； 如果$a=a_{k},b<b_{k}$,则同时从两堆中拿走$a_{k}-a_{b-a_{k}}$个物体，变为奇异局势$(a_{b-a_{k}},a_{b-a_{k}}+b-a_{k})$； 如果$a>a_{k},b=a_{k}+k$，则从第一堆中拿走多余的数量$a-a_{k}$即可； 如果$a<a_{k},b=a_{k}+k$，分两种情况: - 第一种，$a=a_{j},(j<k)$,从第二堆里面拿走$b-b_{j}$即可； - 第二种，$a=b_{j},(j<k)$,从第二堆里面拿走$b-a_{j}$即可。 从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。 而且，通过如上性质，我们可以发现，$a_{n},b_{n}$很像**Beatty数列**。其实，$a_{n},b_{n}$就是**Beatty数列**。 下面介绍下**Beatty数列**和**Beatty定理**： 取正无理数$\alpha,\beta$，使得$\frac{1}{\alpha}+\frac{1}{\beta}=1$ 构造两个数列$a_{n},b_{n}$，它们的通项为$a_{n}=\lfloor{\alpha n}\rfloor,b_{n}=\lfloor{\beta n}\rfloor$ 那么这个数列显然是正整数序列，**Beatty定理**指出，两个数列都是严格递增的，并且每个正整数在两个数列中只出现一次 我们给出其证明： - 单调性：因为$\frac{1}{\alpha}<1,\alpha>1$，所以$\alpha n-1>\alpha (n-1)$，所以$a_{n}-1>a_{n-1}$，$b_{n}$也亦然如此。 - 完备性：我们要证明这个命题，只需要证明对于任意一个$k,(k \in Z^*)$，小于等于$k$的数在序列中出现了$k-1$次即可。 设数列$a_{n}$的前$p$项小于等于$k$（不包括$p+1$项），又因为每项取整前为无理数，不可能取到整数值，那么就有 $\begin{cases}\alpha p<k+1\\\alpha (p+1)>k+1\end{cases}$ 合并两式，得到$p=\lfloor\frac{k+1}{\alpha}\rfloor$，这就是小于等于$k$的数在$a_{n}$中的出现次数，同理，我们可以得到其在$b_{n}$中的出现次数，那么我们有小于等于$k$的数在**Beatty数列**中的总出现数$S=\lfloor\frac{k+1}{\alpha}\rfloor+\lfloor\frac{k+1}{\beta}\rfloor$ 注意到两个取整函数中的数都是无理数，于是我们就有严格的不等式 $(\frac{k+1}{\alpha}-1)+(\frac{k+1}{\beta}-1)<S<\frac{k+1}{\alpha}+\frac{k+1}{\beta}$ 于是有$k-1<S<k+1$，那么$S=k$，证毕。 我们回到之前的奇异局势，由于奇异局势中的$a_{n},b_{n}$序列满足**Beatty数列**，那么同样满足其构造方法，即$a_{n}=\lfloor\alpha n\rfloor,b_{n}=\lfloor\beta n\rfloor$且$\frac{1}{\alpha}+\frac{1}{\beta}=1$。 因为$a_{n}+n=(\alpha +1)n=b_{n}$，所以$\frac{1}{\alpha}+\frac{1}{\alpha +1}=1$，解得$\alpha=\frac{\sqrt{5}+1}{2}$ 那么，我们就得到了通项式:$a_{k}=\lfloor{k×\frac{\sqrt{5}+1}{2}}\rfloor,b_{k}=a_{k}+k$ 所以对于任意局势，先手必败当且仅当局势为奇异局势，我们只需要用通项式判断其是否为奇异局势即可。 ## 例7：取石子游戏之七（Fibonacci Nim） 有一堆个数为$n$的石子，$A,B$轮流取石子，满足： - 先手不能在第一次把所有的石子取完； - 之后每次可以取的石子数介于$1$到对手刚取的石子数的$2$倍之间（包含$1$和对手刚取的石子数的$2$倍）。 约定取走最后一个石子的人为赢家，问$A$先手是否有必胜策略。 这个和之前的**Wythoff's Game**和取石子游戏有一个很大的不同点，就是游戏规则的动态化。之前的规则中，每次可以取的石子的策略集合是基本固定的，但是这次有规则：一方每次可以取的石子数依赖于对手刚才取的石子数。 这个游戏叫做**Fibonacci Nim**，肯定和**Fibonacci数列**：$1,2,3,5,8,13,21,34,55,89,…$ 有密切的关系。如果试验一番之后，可以猜测：先手胜当且仅当n不是**Fibonacci数**。换句话说，必败态构成**Fibonacci数列**。 就像**Wythoff博弈**需要**Beatty定理**来帮忙一样，这里需要借助**Zeckendorf定理（齐肯多夫定理）**：任何正整数可以表示为若干个不连续的**Fibonacci数**之和。 首先我们证明下**Zeckendorf定理（齐肯多夫定理）**： 我们以$Fib_{n}$代表**Fibnacci数列**的第$n$项，$m,(m \in Z^*)$，易知当$m=1,2,3$时，该定理都成立，那么我们运用数学归纳法：假定该定理对所有小于$m$的数都成立，我们只要证明该定理对$m$成立即可。 - 当$m$为$Fib$数时，该定理成立 - 当$m$不为$Fib$数时，设$Fib_{p_{1}}<m<Fib_{p_{1}+1}$。 设$m'=m-Fib_{p_{1}}<Fib_{p_{1}+1}-Fib_{p_{1}}=Fib_{p_{1}-1}$，即$m'<Fib_{p_{1}-1}$ 因为$m'<m$，又因为归纳法假设$m'$可以表示成不连续的**Fibnacci数列**之和，即$m'=Fib_{p_{2}}+Fib_{p_{3}}+...+Fib_{p_{t}},(p_{2}>p_{3}>...>p_{t})$且不是连续的整数，又因为$m'<Fib_{p_{1}-1}$，所以$p_{2}<p_{1}-1$，即$p_{1},p_{2}$也不是连续的整数。 故$m=m'+Fib_{p_{1}}=Fib_{p_{1}}+Fib_{p_{2}}+...+Fib_{p_{t}},(p_{1}>p_{2}>...p_{t})$且不是连续的整数，所以该定理成立 所以**Zeckendorf定理（齐肯多夫定理）**对所有的$m,(m \in Z^*)$都成立 那我们再看看**Fibnacci数列**的**必败证明**： 首先给出三个定理，之后证明需要用到: - $Fib_{n+1}<2*Fib_{n}<Fib_{n+2}$ - $Fib_{n+2}<3*Fib_{n}$ - $4*Fib_{n}<3*Fib_{n+1},(4*Fib_{n}<3*(Fib_{n}+Fib_{n-1})\Rightarrow Fib_{n}<Fib_{n+1}<3*Fib_{n-1})$ 同样运用数学归纳法： - 当$i=2$时，先手只能取1颗，显然必败，结论成立。 - 假设当$i \leqslant k$时，结论成立。 则当$i=k+1$时，$Fib_{i}=Fib_{k}+Fib_{k-1}$。 则我们可以把这一堆石子看成两堆，简称$k$堆和$k-1$堆。 (一定可以看成两堆，因为假如先手第一次取的石子数大于或等于$Fib_{k-1}$，则后手可以直接取完$Fib_{k}$，因为$Fib_{k}<2*Fib_{k-1}$) 对于$k-1$堆，由假设可知，不论先手怎样取，后手总能取到最后一颗。下面我们分析一下后手最后取的石子数$x$的情况。 如果先手第一次取的石子数$y \geqslant \dfrac{Fib_{k-1}}{3}$，则这小堆所剩的石子数小于等于$2y$，即后手可以直接取完，此时$x=Fib_{k-1}-y$，则$x \leqslant \dfrac{2*Fib_{k-1}}{3}$。 我们来比较一下$\dfrac{2*Fib_{k-1}}{3}$与$\dfrac{Fib_{k}}{2}$的大小。即$4*Fib_{k-1}$与$3*Fib_{k}$的大小，我们已经得出后者大。 所以我们得到，$x<\dfrac{Fib_{k}}{2}$。 即后手取完$k-1$堆后，先手在能取最多石子的情况下不能一次性取完$k$堆，所以游戏规则没有改变，则由假设可知，对于$k$堆，后手仍能取到最后一颗，所以后手必胜。 即$i=k+1$时，结论依然成立。 对于不是**Fibonacci数列**，首先进行分解。 分解的时候，要取**尽量大**的**Fibonacci数**。 比如分解$85$： $85$在$55$和$89$之间，于是可以写成$85=55+30$，然后继续分解$30$，$30$在$21$和$34$之间，所以可以写成$30=21+9$，依此类推，最后分解成$85=55+21+8+1$。 则我们可以把$n$写成$n=Fib_{p_{1}}+Fib_{p_{2}}+……+Fib_{p_{k}},(p_{1}>p_{2}>……>p_{k})$ 我们令先手先取完$Fib_{p_{k}}$，即最小的这一堆。由于各个$Fib$之间不连续，则$p_{k-1}>p_{k}+1$，则有$Fib_{p_{k-1}}>2*Fib_{p_{k}}$。即后手只能取$Fib_{p_{k-1}}$这一堆，且不能一次取完。 此时后手相当于面临这个子游戏(只有$Fib_{p_{k-1}}$这一堆石子，且后手先取)的必败态，即先手一定可以取到这一堆的最后一颗石子。 同理可知，对于以后的每一堆，先手都可以取到这一堆的最后一颗石子，从而获得游戏的胜利。 ## 例8：取石子游戏之八（Staircase Nim） 有$n$堆石子，每堆石子的数量为$x_{1},x_{2},...,x_{n}$，$A,B$轮流操作，每次可以选第$k$堆中的任意多个石子放到第$k-1$堆中，第$1$堆中的石子可以放到第$0$堆中，最后无法操作的人为输。问$A$先手是否有必胜策略。 **Staircase Nim**又名**阶梯Nim**，它其实可以通过一些转化变成我们所熟知的Nim游戏，先手必败当且仅当奇数阶梯上的石子数异或和为$0$，那么为什么是这样呢？ 假如我们是先手，我们就按照这个方法将多余的石子从奇数堆移动到偶数堆里面。 此后如果对手移动的是奇数堆，我们就继续移动奇数堆使得SG值重新变为$0$；如果对手移动的是偶数堆，我们就将他移动到奇数堆中的石子继续往下移。 这样经过多次操作我们总能使奇数堆保持必胜状态，最后我们总可以在对手之后将石子从奇数堆移动到偶数堆，最后移动到第$0$堆，这样对手就不能移动了。 所以通过整个过程我们可以发现，偶数堆中的石子不会影响整个游戏的结果，只有奇数堆中的石子会影响游戏结果。 因此对这个游戏而言，先手必败当且仅当奇数堆中的石子数异或和为$0$。 ## 例9：取石子游戏之九（Anti Nim） 本题为例4（Nim 游戏）的变相版本，其他条件均不变，唯独定义：取到最后一个石子的人为输。那么$A$先手是否有必胜策略？ 这题和Nim游戏非常类似，就是输赢的条件不同，但是这个游戏的胜利状态却和Nim有一些区别，这个游戏的的胜利当且仅当： - 所有堆石子数都为$1$且SG值为$0$ - 至少有一堆石子数大于$1$且SG值不为$0$ 我们对这个游戏进行分析，将其分为两种情况： - 所有堆的石子数均为$1$ - 至少有一堆石子数大于$1$ 对于第一种情况而言，我们可以很容易得到当堆数为奇数时，先手必败，否则先手必胜。 对于第二种情况而言，我们分两种情况进行讨论： - 当SG值不为$0$时： 若还有两堆石子数目大于$1$时，我们将SG值变为$0$即可；若只有一堆石子数目大于$1$时，我们总可以让状态变成有奇数个$1$。所以当SG不为0时，先手必胜。 - 当SG值为$0$时： 这样的话至少会有两堆石子的数目大于$1$，那么先手决策完之后，必定会使局面的SG值不为$0$，这样便到了先手必胜局。所以当SG为$0$时，先手必败。 但是上述有关的推导只对于Anti Nim成立，对与**Anti SG-组合游戏**这个推论是不成立的，因此Anti SG-组合游戏的推论我们是需要重新证明的。不过这篇博客主要讨论单一游戏的决策问题，因此对于SG-组合游戏不予以讨论，有兴趣的读者可以参考[贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》](https://wenku.baidu.com/view/25540742a8956bec0975e3a8.html)