教程 博弈论之反向Nim取石子游戏
ωαηg
·
·
个人记录
不要觉得这是我自己写的教程，我可是参考了别人的。
参考自某奆佬的博客
1 定义
反向Nim取石子游戏，是指一般规则与Nim取石子游戏相同，但最后一个取完的人是失败而不是获胜的取石子游戏。
2 我们从一道例题开始
有一堆石子，每次我们可以从某一堆石子中取出任意个（至少一个），两人轮流取，不能取的人获胜（相当于最后一个取完的人失败）。问先手是否存在必胜策略。
那么这就是一道经典的反向Nim游戏。
你的第一眼反应一定是这样的：
我们把每一堆石子的数量全部异或起来，如果为0先手必胜，不为0先手必败。
不好意思，这样是错的。
我们随便来一组数据，比如说：
2\ 2
$$0\ 2$$
而你的对手却走出了这样的一步：
$$0\ 1$$
你会惊讶地发现你死了。
为什么你会死？因为你的对手从一个先手必败的局面转化到了另一个先手必败的局面，本来应该继续进行的胜利计划在某个必败态停了一回合，这个必败被留给了你。
因此你的胜负判定方法显然是不合理的。这违反了博弈论的基本原则：**所有的N态的后继状态全部都是P态**。但如果按照你的方法，只有部分是P态。
好了，现在你没辙了，你可能会去思考修改SG函数。但是这样也并不是很可行。毕竟我们的$sg(0)$是等于1还是2，还是19260817呢？
那怎么办？其实我们只要修改一下取数策略就行。
----
## 3 反向Nim的取数策略
### 3.1 我们先来一波定义
1. 我们用**T态**表示所有石子的数量全部异或起来等于0的局面；用**S态**表示所有石子的数量全部异或起来大于0的局面。（因为此时我们已经无法确定是否必胜了，所以不用P和N）；
2. 我们把石子数只有1的那些堆称为**孤单堆**，大于等于2的堆称为**充裕堆**；
3. S态里面还有三个小态：
**S0态**表示没有充裕堆的S态；
**S1态**表示只有一个充裕堆的S态；
**S2态**表示有两个及以上充裕堆的S态；
4. T态里面也有三个小态**T0,T1,T2**，定义与S0,S1,S2类似。
----
### 3.2 神 · 分类讨论
现在我们正式开始博弈了。
> 定理一：T1态不存在
一个大于1的数和一堆1异或起来能等于0？我打死也不信。
> 定理二：S0态必败，T0态必胜
非常显然。只有1的情况下自己手玩几个就能知道。如果1的个数是奇数（也就是异或起来大于0），必败；否则必胜。
> 定理三：S1态，先手必胜。
如果当前孤单堆的数量是奇数，那么就把多出来的那个充裕堆一次性取完，恭喜对手死了；否则就把它取成一个，恭喜对手又死了。
> 定理四：S2态不可能一次性转化为T0态
显然，你不可能一次性把两个充裕堆变成孤立堆。
> 定理五：S2态一定可以一步转变为T2态
根据取石子游戏基本原理，S态一定可以一步转移到T态。但因为S2不可能一步转移到T0态，而T1态又不存在，显然就一定是转移到T2态了。
> 定理六：T2态只能一步转移到S1态和S2态
继续根据取石子游戏基本原理，T态不可能继续停留在T态（只有S态能继续停留在S态），所以T2不可能一步转移至T0或T1；而又因为充裕堆不可能一次性由两个变成0个，所以T2只可能一步转移至S1或S2
> 定理七：S2态必胜，T2态必败
根据定理五，我们把S2态一步转变为T2态。根据定理六，对手只可能把T2态转移到S1态或S2态。如果是S1态，那么已经必胜；如果是S2态，我们递归处理。
同样的，我们也可以得到T2态必败的结论
综上所述，我们得到如下结论：
**必胜态：T0,S1,S2**
**必败态：S0,T2**
**缺席：T1**
事实上，反向Nim游戏与一般Nim游戏的胜败态并无多大区别，只有S0和T0调换了位置。
----
## 4 代码
很清爽。
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int sum=0;
char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)){
sum=sum*10+(c^48);
c=getchar();
}
return sum;
}
int n;
int main(){
while(~scanf("%d",&n)){
int ans=0,cnt=0;
for(int i=1;i<=n;i++){
int a=read();
ans^=a,cnt+=(a>1);
}
if(ans==0){
if(cnt==0) puts("Yes");
else puts("No");
}
else{
if(cnt==0) puts("No");
else puts("Yes");
}
}
return 0;
}
```
----
## 5 再来一道例题：hdu2509
### 5.1 Problem
不想放题面。自己看[链接](http://acm.hdu.edu.cn/showproblem.php?pid=2509)
### 5.2 Solution
第一眼看，是不是觉得特别珂怕？这道题目可以一堆变成两堆！
但其实，一堆变成两堆没有任何作用。此题的SG函数仍然是$sg(i)=i
理性理解
我们可以用递归（其实那个叫归纳法）证明：
首先，sg(0)=0，这是肯定的
现在，我们假设已经证明了sg(i-1)=i-1,我们要证sg(i)=i
根据博弈论基本原理，再根据题目的“一堆变成两堆”的规则，我们可以列出公式：
sg(i)=mex\{sg(j) \oplus sg(k) | j+k<i\}
显然，sg(j) \oplus sg(k)会囊括0\sim i-1，因为我们让j=0\sim i-1,k=0就可以了。
所以就有sg(i)=i
感性理解
我们可以使用类似于阶梯Nim的感性理解方式。
-
假设我在无视拆分的情况下，我们必胜方。那么显然，我的胜利计划中肯定不包括拆分，只要不是shabby，就不会作死去拆分；
-
假设我们是必败方，我只能通过拆分来转败为胜。那么转败为胜的途径是什么呢？就是通过某种操作使得局面停留在必败态，把必败态留给对手。
首先，我们显然不可能停留在S0，因为孤单堆不可能拆分；
然后，我们也不可能停留在T2，因为如果我想保持异或和继续为0，我就得保证拆出来的两堆的异或和和被拆分的那一堆的大小相同。（分句：我/就得/保证/拆出来的两堆/的异或和/和/被拆分的那一堆/的大小/相同）这显然不可能。因为两个数的异或和不可能比两者加起来要大。拆出来的两堆的大小和一定小于原先的一堆，因而异或和也一定不会与其相等。
所以必败方不可能通过拆分来转败为胜。
所以证明完毕：一堆拆成两堆没有任何意义。
5.3 Code
与刚刚的模板一模一样，一个字也不差。
刚刚的模板就是抄这道题的。
6 咕咕咕
本教程将持续更新。如果我做着做着有了一些新的体会，会随时添加。