Zth's Blog

记录学习路上的点滴

0%

Nim游戏与SG函数

列举了一些Nim游戏的经典变形和SG函数的应用

经典Nim游戏

定义

给定$n$堆物品, 第$i$堆物品有$a_i$个。 两名玩家轮流行动, 每次可以选一堆, 取走随意多个物品, 可以把一堆取光, 但是不能不取。 取走最后一堆物品的人胜利。 两人都采用最优策略, 问先手是否必胜。

定理

Nim博弈先手必胜, 当且仅当$A_1 \ xor \ A_2 \ xor \ \cdots \ A_n \neq \ 0$

与Nim游戏相关的名词

公平游戏ICG

若一个游戏满足:

  1. 由两名玩家交替行动
  2. 在游戏进程的任意时刻, 可以执行的合法行动与轮到哪名玩家无关
  3. 不能行动的玩家判负

则该游戏为一个公平组合游戏

显然, Nim游戏属于公平组合游戏

有向图游戏

给定一个有向无环图, 图中有唯一一个起点, 在起点上放有一枚棋子。 两名玩家交替的把这枚棋子沿有向边进行移动, 每次可以移动一步, 无法移动者判负。 该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。 具体方法是:

把每个局面看成图中的一个节点, 并且从每个局面向沿着合法行动能达到的下一个局面连有向边

Mex运算

设$S$表示一个非负整数集合。 定义$mex(S)$为求出不属于集合$S$的最小非负整数的运算, 即

SG函数

在有向图游戏中, 对于每个节点$x$, 设从$x$出发共有$k$条有向边, 分别到达节点$y_1, y_2, \cdots , y_k$, 定义$SG(x)$为$x$的后继节点$y_1, y_2, \cdots , y_k$的$SG$函数值构成的集合执行$mex$运算的结果, 即

特别的, 整个有向图游戏$G$的$SG$函数被定义为有向图游戏起点$s$的$SG$函数值, 即$SG(G) = SG(s)$

局面和子游戏

局面和子游戏两个概念比较容易混淆,而局面, 子局面, 子游戏的关系和其$SG$值的计算也有所不同, 这里我们简单介绍一下, 具体例子为《算法竞赛进阶指南》中的Cutting Game

对当前局面进行一次操作可能产生一个或若干个子局面, 而每一个子局面都由一个或若干个子游戏构成

其中任意一个子局面的$SG$值是这个子局面包含的所有子游戏的$SG$值的异或和

当前局面的$SG$值则是对所有子局面的$SG$值取$mex$运算得到的结果

Nim游戏拓展

阶梯Nim游戏

模型

给定$n$个石子 第$i$堆石子有$a_i$个。 两名玩家轮流行动, 每次可以选一堆, 将这一堆里的随意多个石子移到相邻的前一堆, 即每次选择一个$i$, 将$a_i$中的$k$个石子移动到$a_{i - 1}$, 可以把一堆全移走, 但是不能不移动。 最后一次移动的人胜利。 两人都采用最优策略, 问先手是否必胜。

解法

阶梯Nim游戏先手必胜, 当且仅当$A_1 \ xor \ A_3 \ xor \ A_5 \ xor \cdots \ xor \ A_{2k - 1} \neq 0$, 即所有奇数编号的石子数量异或和不为零

证明

将奇数位编号石子堆和偶数位编号石子堆分开考虑

假定先手第一步移动奇数位, 考虑后手的操作

  1. 后手也移动奇数位, 对于奇数位而言, 相当于进行了一次Nim游戏(取走一堆石子, 只不过在这里是移到了偶数位)
  2. 后手移动偶数位, 也就是说后手选择了一个偶数$i$, 从$a_i$移动$k$枚石子到$a_{i - 1}$, 那么此时先手只需要将$k$枚石子从$a_{i - 1}$移动到$a_{i - 2}$, 那么相当于对于奇数堆而言, 这次操作没有任何意义, 又回到了先手原来的状态

那么这样反复操作之后, 如果有$A_1 \ xor \ A_3 \ xor \ A_5 \ xor \cdots \ xor \ A_{2k - 1} \neq 0$, 那么对于奇数堆而言Nim游戏先手必胜, 必定会出现一个先手移动完一堆石子后, 所有奇数上的石子都没有了, 即对于奇数位而言先手获得了胜利

此后后手只能移动偶数位, 后手移动哪些石子, 先手就把后手的石子向前再次移动, 此后先手必胜

$A_1 \ xor \ A_3 \ xor \ A_5 \ xor \cdots \ xor \ A_{2k - 1} = 0$时先手必败的证明和上述步骤类似

变形

树上Nim游戏, 就是阶梯Nim游戏, 只不过这里的奇数位编号石子变成了深度为奇数的节点的石子堆, 其先手必胜的证明方法与阶梯Nim游戏基本相同

还有很多拓展, 以后慢慢补