Bash 博弈
一堆石子, 总共 n 个, 两个人轮流取, 每次取 [1,m] 个, 不能操作的人输.
剩余石子为 [1,m] 时, 显然是先手必胜, 必胜策略是全取.
剩余石子为 m+1 时, 是先手必败, 无论第一步如何操作第二步都可以全取.
那么从 [m+1+1,m+1+m] 都是先手必胜, 因为可以一步取到先手必败态.
故剩余石子为 k(m+1)时, 先手都是必败的, 因为无论第一步先手取什么, 后手都可以保持石子数为 m+1 的倍数.
总结: 先手必胜当且仅当 n 不是 m+1 的倍数.
Nim 博弈
有 n 堆石子, 分别是 a1,a2,...an 个, 每次从一堆石子取任意正数个, 不能操作的人输.
异或和为 0 时, 先手必败, 其余情况先手必胜.
若异或和为 x, 且 x 不为 0, 设 x 的二进制最高位为第 k 位, 那么至少存在 1 堆石子 ai 其数量的第 k 位为 1, 易知 ai xor x < ai, 故可以从这堆石子中转移到异或为 0 的状态.
反之, 假如当前异或和为 0, 那么无论怎么取, 下一步异或和必定是非 0 值.
所以当异或和为 0 时, 无论先手做什么, 后手都能维持异或和为 0 的状态转移回来, 直到胜利. 反之先手可以把局面变成异或和为 0 的状态转移给后手.
公平组合游戏:
双方均直到场上的所有信息, 双方每一步能做的事情和当前轮是谁无关, 同一局面不可多次到达, 有限步内会结束, 没有平局, 无法行动的人输. 多个公平组合游戏合起来也是一个公平组合游戏.
把公平组合游戏的每个状态看作节点, 合法的决策是转移边, 那么一个公平组合游戏就是一个 DAG, 出边为 0 的点 (无法移动的点) 是必败点, 由于这是一个 DAG 所以可以通过 DP 求出所有的状态的胜负性. 然后可以规定出 SG 函数: 一个点的 SG 函数值为其后继点的 SG 值的集合的 mex.
显然的结论: 必败点的 SG 值为 0, 经过一次转移之后 SG 值必定改变, SG 值不为 0 的点都是必胜点, 因为其后继状态一定有一个是 SG 值为 0 的点.
不知道怎么证明的 SG 定理: 若干个公平组合游戏的 SG 值, 是他们一个一个的 SG 值的异或和.
使用 SG 定理解决的思路: 观察哪个是一个单独的最小的公平组合游戏, 对这个游戏进行打表, 然后强行看出 SG 函数的规律.
Nim-k 博弈
有 n 堆石子, 分别是 a1,a2,...an 个, 每次从 [1,k] 堆石子取任意正数个, 不能操作的人输.(Nim 游戏是 k=1 的特殊形式)
当且仅当任意的 k 都有 \(k+1|\frac{\sum_{i=1}^n (2^k&a_i)}{2^k}\) 时先手必败, 其余情况先手必胜.
Wythoff 博弈
二分图博弈
起点有一颗棋子, 转移图是一个二分图, 当起点在所有二分图的最大匹配中时, 先手必胜. 否则先手必败.
来源: http://www.bubuko.com/infodetail-3717161.html