列举了一些Nim游戏的经典变形和SG函数的应用
经典Nim游戏
定义
给定$n$堆物品， 第$i$堆物品有$a_i$个。 两名玩家轮流行动， 每次可以选一堆， 取走随意多个物品， 可以把一堆取光， 但是不能不取。 取走最后一堆物品的人胜利。 两人都采用最优策略， 问先手是否必胜。
定理
Nim博弈先手必胜， 当且仅当$A_1 \ xor \ A_2 \ xor \ \cdots \ A_n \neq \ 0$
与Nim游戏相关的名词
公平游戏ICG
若一个游戏满足：
- 由两名玩家交替行动
- 在游戏进程的任意时刻， 可以执行的合法行动与轮到哪名玩家无关
- 不能行动的玩家判负
则该游戏为一个公平组合游戏
显然， 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$， 即所有奇数编号的石子数量异或和不为零
证明
将奇数位编号石子堆和偶数位编号石子堆分开考虑
假定先手第一步移动奇数位， 考虑后手的操作
- 后手也移动奇数位， 对于奇数位而言， 相当于进行了一次Nim游戏(取走一堆石子， 只不过在这里是移到了偶数位)
- 后手移动偶数位， 也就是说后手选择了一个偶数$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游戏基本相同