nim游戏原理
参考nim游戏
尼姆博弈 是一个两人博弈。两名玩家轮流从若干堆物品中拿取一定数量的物品，每次操作需：
- 选择某一堆。
- 从该堆中至少拿 1 个，至多拿完全部物品（不能不拿）。
游戏可以设置“拿到最后一个物品获胜”或“拿到最后一个物品失败”。
视频规则 中，游戏的等价关系不变量是nim 和是否为 0，详细解释。
定义 1：nim 和
所有堆的异或和定义为nim 和。
例子：
对状态(3, 5, 7)，nim 和计算为：
nim(3,5,7) = 3 ⊕ 5 ⊕ 7 = 1
注：可用浏览器的 JS 计算。
约定 1：状态分类
为了简化证明，将硬币状态分成 5 类：P、Q、R 明显可判定，平衡态 S 与非平衡态 F 是主要讨论对象。
5 类状态的“标准型”指该类形式最简单的状态。
| 状态类 | 定义 | 标准型 |
|---|---|---|
| 平衡态 S | nim 和为 0，且不是 P、Q、R | k₀=(x,x), x>1；k₁=(1,2x,2x+1) x⊕x=0；1⊕2x⊕(2x+1)=0 |
| 非平衡态 F | nim 和不为 0，且不是 P、Q、R | (1,2) |
| 奇堆纯 1 态 P | 仅有奇数堆 1 | (1) |
| 偶堆纯 1 态 Q | 仅有偶数堆 1 | (1,1) |
| 仅 1 堆态 R | 仅有一堆数量 >1 | (2) |
约定 2：必胜态与必败态
- P1：P、Q、R 的结果显然，无需讨论。
- P2（必胜态）：若参与者 A 构造状态 U 后存在必胜走法，则 U 为 A 的必胜态。
- P3（必败态）：若参与者 A 构造状态 U 后无必胜走法，则 U 为 A 的必败态。
- P4：状态 K₀ = (x,x) | x>1 是平衡态，也是必胜态，作为 S 类标准型。
- P5：参与者 A 为平衡态构造者。
- P6：最高位、s 位等均指二进制位。
- P7：
- 状态 (s) 表示只有一个 s 个硬币堆，其他堆为 0。
- 状态 (s,t) 表示只有两堆，分别有 s 和 t 个硬币，其他堆为 0。
- P8（并堆）：状态间的一种运算，用 ⊕ 表示，nim((s) ⊕ (t)) = s ⊕ t。
结论：
- 平衡态 ⊕ 平衡态 = 平衡态
- 非平衡态 ⊕ 平衡态 = 非平衡态
定理 1：平衡态是必胜态，非平衡态是必败态
不论规则是“拿到最后一个赢”还是“拿到最后一个输”，都成立。
记住：拿成平衡态者获胜。
T1：K₀ 是平衡态
- K₀ = (0,0,…,x,x)
- 因为 nim(K₀) = x ⊕ x = 0，所以 K₀ 是平衡态。
T2：K₀ 是必胜态
下一步 B 拿后的状态为 (m,X)，分类讨论：
| m | 规则 | A 拿法 | 结果 |
|---|---|---|---|
| 0 | 拿最后一个赢 | A 把 X 堆全拿走 | A 赢 |
| 0 | 拿最后一个输 | A 把 X 堆剩 1 个 | A 赢 |
| 1 | 拿最后一个赢 | A 把 X 堆剩 1 个 | A 赢 |
| 1 | 拿最后一个输 | A 把 X 堆全拿走 | A 赢 |
| >1 | 拿最后一个赢 | A 把 X 堆剩 m 个 | 回到 P2 步骤 |
| >1 | 拿最后一个输 | A 把 X 堆剩 m 个 | 回到 P2 步骤 |
因硬币数严格递减，总会结束于上表绿色情况。
T3：平衡态的下一个状态一定不平衡
设平衡态 nim 和为 0，从第 j 堆拿后剩 m 个：
t ⊕x j x_jxj= m, t>0
则下一状态 nim 和 = t > 0，不平衡。
T4：不平衡态的下一状态可平衡也可不平衡
设不平衡态 t>0，其最高位为 s，存在某堆 x_j 的第 s 位为 1，则可以通过调整 x_j 堆的数量：
- 拿成平衡：A 拿剩 t ⊕x j x_jxj个，使 nim 和变 0
- 拿成不平衡：A 拿走该堆小于 s 位的部分，使 nim 和 s 位保持不平衡
T5：存在拿法使构造 S 的 A 最终获胜
必胜表：
| 规则 | 必胜态 | 必败态 |
|---|---|---|
| 拿最后一个赢 | K₀, S, Q | P, F, R |
| 拿最后一个输 | K₀, S, P | Q, F, R |
A 可通过拿到 K₀、P 或 Q 获胜，B 最终走向必败态 F1 或 F2。
T6：只要 A 尽可能保持平衡，B 必经 F1 或 F2
- F1 = (1,1,…,1,m), m>1, nim>0
- F2 = (0,0,…,x,m), x,m>1, nim>0, x≠m
硬币有限，最终状态必终结于 K₀ 或 F2。
推论 1
- K₀、K₁ 是必胜态
- 平衡态的并堆也是必胜态
因异或运算难口算，推论可快速判定大多数状态是否必胜。
平衡态构造技巧
口诀：
从x j x_jxj堆拿剩x j x_jxj⊕ t 个，直到 P、Q、R 状态
其中 t 为 nim 和，x j x_jxj为与 t 最高位相同的堆。
技巧总结：
| 技巧 | 说明 |
|---|---|
| 技巧1 | K₀ = (x,x) |
| 技巧2 | K₁ = (1,2x,2x+1) |
| 技巧3 | 奇数个奇堆不平衡，只看个位 |
| 技巧4 | 从x j x_jxj堆拿剩x j x_jxj⊕ t 个，直到 P,Q,R 状态，需要大量异或计算 |
| 技巧5 | 平衡状态下，随便只拿一个 |
| 技巧6 | 并堆定理 |
| 技巧7 | a 是最大堆，将 a 堆剩下 b^c |
| 技巧8 | (a^b^c).toString(2).toString(2) |
可以通过如下脚本确定如何拿硬币
/** * 状态s下,如何拿硬币 * @param s {Array[number]} - 输入的数字数组 * @return {[number,number,number]} - 返回一个包含三个数字的数组： * 状态s的nim和 * xj堆的数量 * xj堆剩下的数量 */functionnim(s){//计算状态s的nim和constt=s.reduce((acc,cur)=>acc^cur,0);letxj=Math.max(...s);//必败态,就从最大堆拿一个if(t===0){return[t,xj,xj-1];}//找出xj堆for(letitofs){if((it>>(t.toString(2).length-1))&1===1){xj=it;break;}}//xj堆剩下的数量return[t,xj,xj^t];}/** * 状态s的下一个最佳状态 * @param s {Array[number]} 当前状态 * @return {Array[number]} 下一状态 */functionm(s){s=Array.isArray(s)?s:[...arguments];const[t,xj,nextXj]=nim(s);letflag=0;letnextS=s.map((it)=>{if(flag===0&&it===xj){flag=1;returnnextXj;}else{returnit;}});if(t===0){thrownewError("可能会输:"+nextS.toString());}returnnextS;}m(3,5,7)