BZOJ 2463 谁能赢呢？

这篇是当年无知时期写的关于一道博弈题的无知记录。说来惭愧，接触博弈论题目这么多年，居然只知道SG函数的名字和要用到异或（部分因为忘了，部分因为当年没好好学）。是应该好好学习一下。

几个引理

  • 如果对于先手方，后手方总有办法能够走等价步骤，必定先手必败
  • 能一步走到必败态的状态为必胜态
  • 只能走到必胜态的状态为必败态
  • 无状态可走为必败态

抵消

  • 在一个圆形桌面上，甲、乙轮流放一元硬币，不许重叠，甲先放，首先放不下硬币的一方为负。甲如何取胜呢？

    只要桌面比硬币大就是甲必胜。甲首先把硬币放在桌面中央，然后乙放在哪里甲就放在他的中心对称位置，即可取胜。

  • 最近EOJ月赛的一道题

  • 回到BZOJ 2463 谁能赢呢？

    题意：一个n×n的棋盘，一个石头被放在左上角。每回合，选上下左右中的一个移动一格，要求目的地未被访问过。不能移动者输。

    解：

    如果n是奇数，去掉初始格后一定能被1×2的骨牌覆盖。先手走的第一步一定走到其中一个骨牌中的一格，那么对于先手者的每一步，后手者只需要把当前所在的骨牌走完便可以将状态抵消掉。
    如果n是偶数，走了一步就变成奇数情况，分析同理。

  • 事实上下面大部分博弈论的题目考虑的本质就是后手是否必定能找到一个抵消先手的方案

巴什博弈

  • 一堆火柴有N根，A，B两人轮流取出。每次可以取1根或2根，问先取者能否有必胜策略？

    设f[x]为剩x根火柴时轮到某个人取，他的必胜必败状态，必胜为1，必败为0，则首先f[0]=0

    f[x]=(!f[x-1])&&(!f[x-2])，找规律即显然得到答案

  • 若每次可以取1..t根火柴（t<N）呢？

    一样的方法，N=(n+1)*k则必败，剩余情况必胜

NIM

甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。例如下所示的初始局面：共3堆，其中第一堆的石子数$a_1=3$，第二堆石子数$a_2=3$，第三堆石子数$a_3=1$。两人轮流按下列规则取走一些石子，游戏的规则如下：

每一步应取走至少一枚石子

  • 每一步只能从某一堆中取走部分或全部石子

  • 如果谁无法按规则取子，谁就是输家

image-20210322201414149

对于只需要异或起来判是否是0的证明参见OIWIKI

有向图游戏与 SG 函数

  • 在一个有向无环图中，只有一个起点，上面有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负。

显然上面的所有游戏都可以转化为有向图游戏（但有一些转化了反而不容易做）

显然我们可以类似线性递推的方法定义每个点的f[x]，拓扑排序求出答案。

同时，我们也可以引入SG定理：

定义mex(minimal excludant)运算，表示最小的不属于某个集合的非负整数。例如
$$
mex\lbrace0,1,2,4\rbrace=3\\
mex\lbrace2,3,5\rbrace=0\\
mex\lbrace\varnothing\rbrace=0
$$
对于任意状态$x$，定义$SG(x) = mex(S)$,其中$S$是$x$后继状态的$SG$函数值的集合。如$x$有三个后继状态分别为 $SG(a),SG(b),SG(c)$，那么$SG(x) = mex { SG(a),SG(b),SG(c) }$。

游戏的SG函数等于各个子游戏(互相没有边指向的DAG)SG函数的Nim和(异或和)。

证明

令状态x=(x1,x2,…,xn)，b=SG(x1,…xn)=SG(x1)^SG(x2)^…^SG(xn)。我们只需证明一下两点：

  • 对于每一个非负整数a < b，我们一定可以从x到达另一个状态使得新状态的SG函数值为a

  • 由x可以到达的每一个状态的SG函数值都不等于b

第一条：

令d=a^b，设k为d的二进制位数，那么d在二进制的第k位上的数字一定是1，由于a<b，故b的二进制形式第k位上一定是1，而a是0。由于b=SG(x1,…xn)，故至少由一个SG(xi)在二进制的第k位上是1，不妨令i=1，所以d^SG(x1)<SG(x1)。由SG函数的定义得在这个有向图中一定可以由位置x1到达另一个位置x1’，使得SG(x1’)=d^SG(x1)，那么由原来得状态(x1,x2,…,xn)就可以到达(x1’,x2,…,xn)，而且SG(x1’,x2,…,xn)=SG(x1’)^SG(x2)^…^SG(xn)=d^SG(x1)^SG(x2)^…^SG(xn)=d^b=a^b^b=a。

第二条：

假设存在状态(x1’,x2,…,xn)使得SG(x1’,x2,…,xn) = b，即SG(x1’)^SG(x2)^…^SG(xn)=SG(x1)^SG(x2)^…SG(xn)，所以我们得到SG(x1’)=SG(x1)，而由SG函数得定义这是不可能出现的。

证毕

这样按照定义，状态x的函数值就一定是b了。

这样，我们只要依次求出每个有向图的SG函数值，然后再将它们进行异或操作，就得到了整个状态的SG函数值，便也可以判断出这个位置是必胜还是必败。

  • 有1堆n个的石子，每次只能取1或3或4个石子，先取完石子者胜利，那么胜负状态？

    SG[0]=0

    SG[1]=mex(SG[0])=1

    SG[2]=mex(SG[1])=0

    SG[3]=mex(SG[2],SG[0])=1

    SG[4]=mex(SG[0],SG[1],SG[3])=2

    依此类推

  • 有k堆n个的石子，每次只能取1或3或4个石子，先取完石子者胜利，那么胜负状态？

    显然对每一堆求出上面题目中的SG函数，异或即可

模型的转化

  • 一个100x100的棋盘，坐标范围是[0,100]的，上面有n个棋子。Alice 和 Bob轮流操作，每次操作可以把一枚棋子向左或者向下或者向斜下方移动任意步，也就是(x,y)有这三种移动(x−l,y),(x,y−l),(x−l,y−l)。多个棋子可以同时在同一位置。第一个把棋子移动到(0,0)点的人获胜。问是否先手必胜。

因为这道题是第一个到原点的获胜，所以没法直接按照常规SG来设置。但是可以发现，不能把棋子移到三条直线上，否则下一步对方就能胜利。因此应该把末态放在(1,2)和(2,1)两个点，对每个棋子分开算SG值再异或得到答案。

  • 在一个阶梯上,每层有若干个石子,每次可以将某一层中若干个石子移动到他下一层阶梯中去.问胜负情况

胜负情况仅由奇数层石子决定。若对方将偶数堆石子移动到奇数堆，则我方只要将这些石子从该层移到下一层的偶数堆，则该回合没有对奇数层的石子造成影响。而将奇数层石子移动到偶数层则可以看做是nim游戏中将这些石子拿走。因此以该种方法，若奇数层nim游戏计算结果为必胜，则我方必胜。

为何奇数层结果必败则我方必败？没有别的方式取胜吗？确实，因为一旦奇数层nim必败，则对方可以用相同方法使我方必败，且没有其它情况。

  • 定义有如下操作的游戏:
    1. 从一堆中取走任意个数的石子.
    2. 将一堆石子分成两堆不为空的石子.

只需要改变SG函数的计算方式，利用上面提到的有向图游戏进行建模，就能想清楚。

  • 有几个有根树，每次可以删除一个子树（也可以是树本身），不能操作的人算输，求先手是否必胜

对于某几棵独立的树，总SG值显然为它们的异或和。若这几棵树同时是某个点的亲儿子，则可达状态相比于子树互相独立时的情况多了一种：把父亲删掉。因此总的SG值为各子树SG值的异或和+1。

  • 有几个有根树，每次可以删除一个有父亲的子树（不能是整棵树），不能操作的人算输，求先手是否必胜

结论：某棵树的SG值是其各子树SG值+1后的异或和

证明：

数学归纳法，假设对于点数<n的情况结论均成立。分两类，第一类为在某个点数<n的情况的根B上安一个新的根A，第二类为其它情况。

对于第一类情况，删除AB间的边可以到达SG=0的状态；删除其它边后的SG值为以B为根时的SG值+1(由于这时点数已经<n)。故当前状态可以经过一步到达0到B子树的SG之间的任意SG值，因此答案为B子树SG值+1

对于第二类情况，由于这就是一个nim游戏，显然异或即可

Nim-k

  • 有若干博弈游戏，每次可以一下子进行最多k个游戏，谁无法进行谁输。

结论：整个游戏的SG = 每个游戏的SG用二进制表示的每一位用（k+1）进制异或 （即相加后模，判断是否为0）

同时进行k个游戏的话，先手至少改变1个、至多改变k个游戏的SG值，若二进制每一位的和都被(k+1)除尽，则后手必然可以找出反制措施，使游戏SG值的每一位仍然保持除尽的状态。

也就是说，这个问题相当于同时在二进制每一位做巴什博弈，但是感受起来并不是很直观。

3人Nim

  • 有n堆石头，三个人轮流取石子。拿走最后一个的是第一，倒数第二步是第二，倒数第三步是第三。每个人想让自己的名次最高。

结论：将所有数字写成二进制表示，每位做模 3 加法，如果等于 0 就是最后一个玩家获胜。第一个玩家获胜当且仅当可以移动到必胜态，其他情况第二个玩家获胜

Anti-Nim

拿走最后一个石子的人算赢，其余与nim游戏相同。

结论：

一个状态为必胜态，当且仅当：

　　1）所有堆的石子个数为1，且NIM_sum=0

　　2）至少有一堆的石子个数大于1，且 NIM_sum≠0

img

这个讲得很清楚，但是不知道是谁写的就没加reference。感觉碰到之后按类似想法推导即可。

Every-SG

  • 有n个博弈游戏同时进行，轮到他时必须玩所有还没结束的游戏。最后结束的游戏的输赢就是整个游戏的输赢。

博弈中，由于每个游戏互不影响，若某个游戏A必胜，则A会尽量将其获胜时间推迟；若必败，则尽量将失败时间提前。定义每个游戏将会进行的步数step，则最大的step的奇偶性即为答案。奇数则先手败

step计算显然是分类讨论，要么是所能到达的情况的step的max+1，要么是min

威佐夫博弈

  • 两堆石子，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的石子，无法操作者输，求先手是否必胜

把两堆石子的情况看成一个平面上的格点图(右边为x正方向，上面为y正方向)。则若某一个点必败，其右边、上面所有点必胜，其右上对角线必胜。即：若(x,y)必败，(x,>y),(x+k,y+k),(>x,y)均必胜。且x和y对称。

类似质数筛法，x不断向右扫的过程中，只要碰到某一列有未确定为必胜的，即为必败点。若将必败点排列出，则

  1. 横纵坐标这两个整数均不曾在之前的点的坐标中出现
  2. 当前的横坐标为未出现的整数中最小的
  3. 所有整数必定都会出现（如果不致密的话，稍微想一想 感觉就和上面的不太符合
  4. 横纵坐标之差未曾在之前的点的差中出现（则y=x+n,n表示这是第n个点）

贝亚蒂定理：若 a,b 为正无理数，且 $\frac{1}{a}+\frac{1}{b}=1$ 则 $\lfloor a\cdot n \rfloor ,\lfloor b\cdot n \rfloor$可以不重复地表示所有正整数

在这里，$\lfloor a\cdot n \rfloor+n=\lfloor b\cdot n \rfloor\Rightarrow \lfloor a \rfloor +1=\lfloor b \rfloor$

找规律+感受可以发现，取b=a+1时，$(\lfloor a\cdot n \rfloor ,\lfloor b\cdot n \rfloor)$是所有必败态的集合

推导出ab的值即可

(归纳法应该可以证明)

扩展

取出的两堆石子的差的绝对值小于等于k（上面的题目即为k=0的情况）

取b=a+k+1即可

二分图博弈

双方在一张二分图上博弈，首先有一个初始点，每一步可以选择走到与当前点有边相连的别的点上（显然其中一方只会到达在二分图同一边的节点），不得走重复的点，无处走判负。

首先说结论：

若初始点一定被最大匹配包含，则先手必胜；反之，则后手必胜

下面证明：

若初始点一定被最大匹配包含，则先手走到相应匹配点，后手方只能走到别的匹配而不可能走到非匹配点，否则从初始点到结束时的整条路径符合增广路的定义，可以通过将路径上所有边取反（连着的断掉，没连着的连起来）形成一个更大的最大匹配。因此等能走的匹配走完，轮到后手，先手胜。

若初始点不一定被最大匹配包含，则先手第一步一定会走到某个匹配点，否则在该匹配方案中就可以添加先手走的这一对点。于是后手每次走到相应匹配点即可。先手不可能走到非匹配点，否则也会形成一条增广路。

模型

JSOI2009 游戏

题意：

在$n\times m$的迷宫中有一个棋子，AA 首先任意选择棋子放置的位置。然后，YY 和 AA 轮流将棋子移动到相邻的格子里。

游戏的规则规定，在一次游戏中，同一个格子不能进入两次，且不能将棋子移动到某些格子中去。当玩家无法继续移动棋子时，游戏结束，最后一个移动棋子的玩家赢得了游戏。

求 AA 初始将棋子放在哪些格子会有必胜策略。

解：

网格图一人一步，则显然会形成奇偶两种点。利用上述二分图博弈的思想建图即可。

CCPC2020长春 H Combination Lock

题意：

有一个密码锁，两个人博弈，给出初始的密码，规定：

  1. 每一次都可以转动一个位置的数字一个单位
  2. 不可以转动到已经出现过的数字
  3. 不可以转动到被 ban 掉的数字

解：

每操作一次都会改变当前所有数字之和的奇偶性，因此整个图是一个二分图。

其他

回到

Reference

https://blog.csdn.net/luomingjun12315/article/details/45555495

https://oi-wiki.org/math/game-theory/

博弈论在信息学竞赛中的应用 杭州第二中学 李建 NOI教师培训·长沙 2016 – 09

https://blog.csdn.net/weixin_37517391/article/details/82944606

https://blog.csdn.net/white945/article/details/104182216