<总结+题解>Nim游戏,ICG

Nim 游戏的规则是这样的:地上有n堆石子,每人每次可从任意一堆石子里取出任意多枚石子扔掉,可以取完,不能不取。每次只能从一堆里取。最后没石子可取的人就输了。

我们从基本的思路开始

以下我们为先手

首先,我们假设面前只有一堆石子,我们必胜,取完面前的就好了
我们把这种局面归纳为n=1,a_1 \neq 0

接下来我们考虑n=2,已知一种情况为先手必败:a_1=1,a_2=1
1. 假设两堆数量都不是1:
1. 把一堆取到1:对方到达情况2,我们必败
2. 取后两堆数量还是都大于1,对方到达情况1
2. 两堆里面有一堆是1:取另一堆到1,对方到达情况3,我们必胜
3. 两堆都是1

我们发现还是不能推出必胜必败,于是我们继续找先手必胜或必败的情况,发现如果a_1=a_2,我们无论取多少,对方都可以在另一堆中和我们取相同多的数量,经过多次后我们一定会到达a_1=1,a_2=1的情况然后必败
然后我们知道,如果我们进行一次决策后对方必败,那我们就必胜,所以如果两堆不一样,我们取出差值,对方就会变成两堆一样然后必败,我们就必胜

好了,经过刚刚的~洗礼~,我们再来看看n为任意正整数的情况:
我们把所有的a_i异或起来为0的时候必败
证明:
1. a_1=a_2=\dots=a_n,由题可得
2. 假设我们取出一堆石子的非零的数量,那么异或和必定不为0,这个异或值的最高位肯定来源于不止一个数,我们找到一个包含异或值最高位的数,一定能通过取这里面的一个数让异或和回到0

综上,a_1\oplus a_2 \oplus \cdots \oplus a_n = 0时必败

int sum = 0;
while (n--)
{
    int v;
    scanf("%d", &v);
    sum ^= v;
}
puts(v ? "Yes" : "No");

接下来我们看另一个~游戏~例子:

给定一个有向无环图和一个起始顶点上的一枚棋子,Alice和Bob交替的将这枚棋子沿有向边进行移动,无法移动者判负。

这个~游戏~例子可以看做所有ICG的抽象模型

ICG(公平组合游戏,Impartial Combinatorial Games):
1. 游戏有两个人参与,二者轮流做出决策,双方均知道游戏的完整信息;
2. 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关
3. 游戏中的同一个状态不可能多次抵达,游戏以玩家无法行动为结束,且游戏一定会在有限步后以非平局结束。

我们把ICG的局面看做点,决策看做点和点之间的有向边,就变成了这个~游戏~例子


接下来我们来看mex(minimal excludant)函数:

mex函数表示最小的不属于这个集合的非负整数

我们定义这个DAG每个点的SG值为mex({SG(y) | y为后继})
我们发现当你在一个SG值为0的点是必败的:
1. 没法移动的点的SG函数一定为0(空集)
2. 如果一个点SG函数为0,说明它的后继(儿子)的SG值都不为0,那这个点的每个后继一定都有一个SG函数为0的点(孙子),说明它的每个后继(儿子)都是必胜的(能有一个方法让对方必败,自己就一定必胜),自己就是必败的(如果对方一定必胜,自己一定必败)

当然,举几个取石子的例子(一堆n个石子两人轮流取取完就输了)
1. 可以取任意个:\operatorname{SG}(x) = x
2. 可以取1\sim m\operatorname{SG}(x) = x \bmod (m + 1)
3. otherwise:按照定义算


最后是把ICG转化成Nim游戏
我们现在有很多个抽象出来的DAG,并且算出了每个点的SG函数值,一个局面的SG函数就是所有子局面的SG函数的异或和,证明和Nim游戏差不多(注意一个DAG的一个点的SG函数为x代表后继的SG函数值包含0\sim x-1的所有情况)


Nim游戏也可以化为ICG的DAG模型
把每堆棋子看成一个DAG,每个节点连到后面每个节点
那么每个DAG的起点的SG函数就是这堆石子的个数,整个游戏开始局面的SG函数就是每个子开始局面的SG函数,异或和为0就代表先手必败


最后口胡一下NimK游戏
我们的Nim游戏都是n堆石子里面取1堆,而NimK游戏允许你一次取k堆的石子
我们之前异或可以看成对每个二进制位求然后模2,所以取k堆对每个二进制位求和模k+1就好了,证明略去,全0先手必败

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注