这里默认两方均采取最优策略

1. 尼姆博弈

n堆石子，每堆的数量a1，a2，a3...an，一方取完后石子个数为0则该方获胜，问先手是否必胜

if ans = a1^a2^a3^...^an ≠ 0 先手必胜

else 先手必输

 

延伸1：在此问基础上添加一个集合，集合内的数字是每次操作可取的石子个数，每次从一堆中取，最后无法取者判输

对每堆石子算得其sg函数，sg函数异或后不为0，则先手必胜

否则先手必输

 

延伸2：在此问基础上添加一个条件：每次从不超过k堆中取任意多个石子，最后无法取者判输（Moore' s Nimk）

将每堆石子数换算为二进制，计算出二进制中每位的个数x mod (k + 1)是否存在 不等于0，如果存在不等于0，则必胜，否则必输

 

延伸3：在此问基础上添加一个条件：每次取一堆石子的k个（1 ≤ k ≤ max(该堆石子))，放入两堆新的石子，两堆石子各自的数量必须小于拿走的石子数，但两对石子数之和可以大于等于拿走的石子数，先拿完者获胜

对每堆石子求sg函数，if sg函数异或和不为0 先手必胜，else 先手必输

2. 巴什博弈

一堆石子共n个，每次至少取1个，至多取m个，先取完者获胜，问先手是否必胜

if n % (m + 1) != 0 则先手获胜

else 先手必输

 

3. 阶梯博弈

n层阶梯上放n堆石子，每次选择一层的若干石子放入下一层，（选择第一层的石子即这些石子进入地面，不可再被选择）

最后不能选择石子的人判输，问先手是否必胜

奇数层上的石子数异或，if结果不为0，先手必胜，else必输。

 

以下待学习证明

4. 威佐夫博弈

有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利

结论：，若两堆物品的初始值为x和y，且x<y，则另z=y-x

记w=[（（sqrt（5）+1）/2）*z ]

若w=x，则先手必败，否则先手必胜

 

5. 斐波拉契博弈

有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜

结论是：先手胜当且仅当n不是斐波那契数（n为物品总数）

 

6. 反NIM游戏，取完石子的人判输

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

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

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

 

 

附上参考大佬的

原文链接1：https://blog.csdn.net/clover_hxy/article/details/53818624

原文链接2：https://www.cnblogs.com/xiaojuA/p/9841859.html

原文链接3：https://www.cnblogs.com/wujiechao/p/5365039.html