Nim游戏【朴素】
背景
Nim游戏
给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。
我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。
所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。
NIM博弈不存在平局，只有先手必胜和先手必败两种情况。
公平组合游戏ICG
若一个游戏满足：
1.由两名玩家交替行动；
2.在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
3.无法移动者判负；
则称该游戏为一个公平组合游戏。
NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。
结论
必败态为 \(a_1 \text{^} a_2 \text{^}... a_n = 0\)
必胜态为 \(a_1 \text{^} a_2 \text{^}... a_n \ne 0\)
※
必胜态：（当前操作者）必胜【可以转化为（对手）必败态，而（对手）必败态不能转化为（当前操作者）必败态】
必败态：（当前操作者）必败【不能转化为（对手）必败态，只能转化为（对手）必胜态】
证明
- 证：\(a_1 \text{^} a_2 \text{^}... a_n \ne 0\)【必胜态】可以转化为 \(a_1 \text{^} a_2 \text{^}... a_n = 0\)【必败态】
首先，
假设 \(a_1 \text{^} a_2 \text{^}... a_n = x \ne 0\)
从 \(a_i\) 中取走 \(a_i - a_i \text{^}x\) 使得 \(a_i = a_i \text{^} x\)
那么 \(a_1 \text{^} a_2 \text{^}... a_n = x \text{^} x = 0\)
然后,
再证明一定存在使得上述操作是合法的 \(a_i\)【合法的前提是 \(a_i \ge a_i \text{^} x\)】
假设 \(x\) 最高位 \(1\) 为第 \(k\) 位，那么 \(a_1 , a_2 ,... a_n\) 中一定存在 \(a_i\) 第 \(k\) 位也为 \(1\)
那么此时 \(a_i \ge a_i \text{^} x\)
因此一定存在使得上述操作是合法的 \(a_i\)
因此 \(a_1 \text{^} a_2 \text{^}... a_n \ne 0\)【必胜态】可以转化为 \(a_1 \text{^} a_2 \text{^}... a_n = 0\)【必败态】
- 证：\(a_1 \text{^} a_2 \text{^}... a_n = 0\)【必败态】 不能转化为 \(a_1 \text{^} a_2 \text{^}... a_n = 0\)【必败态】
反证法
假设 \(a_1 \text{^} a_2 \text{^}...a_i'\text{^}... a_n = 0\)
那么 \(((a_1 \text{^} a_2 \text{^}...a_i... a_n) \text{^} (a_1 \text{^} a_2 \text{^}...a_i'\text{^}... a_n) = 0 \text{^} 0 \text{^} ...(a_i\text{^}a_i')\text{^}...0 = 0\)
然而 \((a_1 \text{^} a_2 \text{^}...a_i... a_n) \text{^} (a_1 \text{^} a_2 \text{^}...a_i'\text{^}... a_n) = 0 \text{^} 0 \text{^} ...(a_i\text{^}a_i')\text{^}...0 = a_i\text{^}a_i'\)
由于 \(a_i < a_i'\)
因此 \(a_i\text{^}a_i' \ne 0\)
因此假设不成立
因此 \(a_1 \text{^} a_2 \text{^}... a_n = 0\)【必败态】 不能转化为 \(a_1 \text{^} a_2 \text{^}... a_n = 0\)【必败态】
台阶-Nim游戏
现在，有一个 \(n\) 级台阶的楼梯，每级台阶上都有若干个石子，其中第 \(i\) 级台阶上有 \(a_i\) 个石子(\(i≥1\))。
两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。
已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
结论
必败态为 \(a_1 \text{^} a_3 \text{^}... a_{2*+1} = 0\)
必胜态为 \(a_1 \text{^} a_3 \text{^}... a_{2*+1} \ne 0\)
分析
可以维持通过操作始终维持奇数级台阶为普通Nim游戏
- 如果先手移动偶数阶的石子到下一台阶【奇数】，那么后手可以将这些石子继续往下一级台阶【偶数】移动，从而使得奇数级台阶的石子数不变，异或和也不变，从而维持奇数级台阶为普通Nim游戏
- 如果先手移动奇数阶的石子到偶数阶即相当于普通Nim游戏
集合-Nim游戏
背景
Mex运算
设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：
mex(S) = min{x}, x属于自然数，且x不属于S
有向图游戏
给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。
SG函数
在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1, y2, …, yk，定义SG(x)为x的后继节点y1, y2, …, yk 的SG函数值构成的集合再执行mex(S)运算的结果，即：
SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})
特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(s)。
定理
有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0。
有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。
有向图游戏的和
设G1, G2, …, Gm 是m个有向图游戏。定义有向图游戏G，它的行动规则是任选某个有向图游戏Gi，并在Gi上行动一步。G被称为有向图游戏G1, G2, …, Gm的和。
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即：
SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)
注意：Nim游戏也是特殊的有向图游戏的和，即求异或和