题解
Nim游戏本质上是一个ICG公平组合游戏
若一个游戏满足:
1. 由两名玩家交替行动
2. 在游戏进行的任意时刻,可以执行的合法行动与轮到哪位玩家无关
3. 不能行动的玩家判负
则称该游戏为一个公平组合游戏。尼姆游戏(NIM)属于公平组合游戏,但常见的棋类游戏,比如围棋就不是公平组合游戏,因为围棋交战双方分别只能落黑子和白子,胜负判定也比较复杂,不满足条件2和3。
而ICG都可以转化为有向图游戏
有向图游戏
将公平组合游戏看作一个有向无环图,图中有一个唯一的起点,在起点放有一枚棋子。两名玩家交替把这枚棋子沿着有向边进行移动,每次可以移动一步,无法移动判负。任何一个公平组合游戏都可以转化为有向图游戏。具体方法是,把每个局面看成图中的一个节点,并且从每个局面向沿着合法行动能够到达的下一个局面连接有向边。
小例子
若目前有2堆石子,石子数量为2 3,问先手方甲从第二堆拿一个,是否必胜?
第一步:2 2
第二步:1 2 |2 1| 0 2| 2 0 乙有四种可能
我们发现 从第二步开始,无论乙从哪一堆里哪多少个,甲只要镜像地做出选择,就会必胜
比如:
第二步:1 2
第三步:1 1
第四步:0 1
第五步:0 0
第六步:乙输
比如:
第二步:2 0
第三步:0 0
第四步:乙输
特点
这个游戏没有平局,两方必一胜一输
在这个有向图中,每个dot只有两种状态:
- 先手必胜状态
- 先手必败状态
每个状态对应着一种局面
(实际上就是石子堆数和每堆石子的数量的情况)
这种局面就会决定到底是必胜还是必败
先手必胜状态必然能够经过调整石子的个数,通向至少一个先手必败状态
题目说“两人都采用最优策略”,所以先手者往往会通过调整石子数量让局面倒向此
先手必败状态
而先手必败状态的定义就决定了其通向的所有结点(状态)都是先手必胜状态(因为必败就决定了对手必胜,他就不能够通过调整石子来让对手必败)
结论
那么如何判断当前局面属于哪种状态?这里先给一个结论:
设当前局面有n堆石子,Ai表示第i堆石子剩余的石子个数
当$$\begin{aligned}x=A_{1}\oplus A_{2}\oplus \ldots \oplus A_{n}\\ \end{aligned}$$
结论证明
已知条件:
- 游戏肯定能通过有限步得出输赢 输的判定标准就是最后一步时所有Ai==0
- $\begin{aligned}x=A_{1}\oplus A_{2}\oplus \ldots \oplus A_{n}\\ \end{aligned}$
第一阶段证明:当x≠0时,一定能够通过减少某Ai的值来使下一步的x==0
证:设x的最高位1在第k位,则A1、A2…An中肯定存在一个Ai的第k位为1
那么 Ai^x<Ai
若甲从Ai中拿走Ai-Ai^x
个石子,即:
Ai=Ai-(Ai-Ai^x)=Ai^x
Ai变为了Ai^x
那么
$$x=A_{1}\oplus A_{2}\oplus \ldots \oplus A_{i}\oplus x\oplus \ldots \oplus A_{n}=x\oplus x=0$$
证明完毕。
第二阶段证明:当x==0时,无论经过任何合法操作过后,都不可能保持x==0的状态。也就是要证明,当x==0时,必然通向x≠0的状态。
证:(反证法)设将Ai
变为Ai*
后,可以维持x==0的状态。
$$X=A_{1}\oplus A_{2}\oplus \ldots \oplus A^{*}_{i}\oplus \ldots \oplus A_{n}=0$$
又因为已知条件:
$$X=A_{1}\oplus A_{2}\oplus \ldots \oplus A_{i}\oplus \ldots \oplus A_{n}=0$$
所以$x \oplus x=0$
所以$A_{i} \oplus A^{*}_{i}=0$
所以$A_{i}=A^{*}_{i}$
Ai没有变,非法操作,矛盾
证明完毕。
第三阶段证明:若x≠0,那么此时为先手必胜状态。若x=0,那么此时为先手必败状态。
证:根据已知条件1,游戏必然在有限步内决出胜负,而负者的判定为
$$A_{1}=A_{2}=\ldots =A_{n}=0$$
此时x==0,也就是说负者失败时的状态一定属于x=0状态
而第一阶段已经证明,当x≠0的时候,一定能通过改变石子数量通向x=0,第二阶段证明,x=0时,下一步只能是x≠0。
所以当x≠0时,可以选取最优策略,使得对手处于x=0的状态,对手无论如何操作,先手者还是会面临x≠0的状态。已知条件告诉我们,游戏终将结束,而负者的判定为
$A_{1}=A_{2}=\ldots =A_{n}=0$,这是个x=0的状态。所以有限步过后,随着Ai石子数量减少为0,x≠0的先手者必赢,x=0的后手者终将迎来x=0,
$A_{1}=A_{2}=\ldots =A_{n}=0$的失败。根据先手必胜状态的定义可知,x≠0即为先手必胜状态。同理可推出,x=0即为先手必败状态。
所以Nim游戏先手获胜的判定即为:
代码
#include<iostream>
using namespace std;
#include<algorithm>
int main(void){
int n,x=0;//0与任何数相异或都是它本身
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) x^=a[i];
if(x) cout<<"Yes";
else cout<<"No";
}
拓展——SG函数
mex()函数
mex()就是求序列中未出现的最小的非负整数。
设存在一个集合Set1={1,5,7,8},Set2={0,1,2,6}
如Set1.mex()=0,Set2.mex()=3
SG函数
两种情况:
当SG()==0时,那么说明它下一步一定是非零,因为若下一步能够到达0,SG()>0了
而当SG()!=0时,它下一步一定可以到达0,因为若下一步到不了0,SG()就=0了
而终点定义为0,终点即失败,所以得上图结论。
多个图
SG()函数可以在多张图供做决策的时候发挥作用
如上图,每一步选手可以任意选一张图进行操作,直到两张图都不能操作时判定为输。
每一张图其实就对应一组石子堆,或者一片石子堆
设当前G1所在状态为x1,G2所在状态为x2
$$
S G(x)=S G\left(x_1\right) \oplus S G\left(x_2\right)
$$
考虑一种有n张图的情况,那起点的个数可能有很多个,那么排列组合的状态将是指数级别的,而使用SG函数就可以大大减少计算量。
若有n张图,在图G1,G2…Gn中的当前状态为x1,x2,…,xn,有
$$
S G(x)=S G\left(x_1\right) \oplus S G\left(x_2\right) \oplus \cdots \oplus S G\left(x_n\right)
$$
当SG(x)=0的时候,必胜,反之必败。证明和最初的Nim游戏的证明如出一辙。如果失败那么肯定所有图的SG(xi)==0,那么失败只可能发生在SG(x)=0的时候…
看完之后我想到一些之前做的笔记
1:没有后继状态的状态是必败态
2:一个状态是必胜态当且仅当存在至少一个必败态为它的后继状态
3:一个状态是必败状态当且仅当它的所有后继状态均为必胜状态
如果博弈图是一个有向无环图,则通过这三个定理,我们可以在绘出博弈图的情况下用 $O(N+M) $的时间(其中 $N$ 为状态种数,$M$ 为边数)得出每个状态是必胜态还是必败态
👍
太久了,博弈论、组合数学都有些不记得
写的很棒
谢谢您~