博弈论基础知识博弈论基础知识

0X00 一个关于「异或」的前置知识假设有：

那么一定存在一个使减去一个大于 0 的数字得到

证明过程如下（构造法）：
假设 s 的最高位是 m，那么中一定有一个使得的第 m 位一定是 1（反证法，如果所有都不是 1 那么 s 的 m 位一定是 0）。且。
如果这里不好理解，我再举个例子
假设, 也就是 m 位变成了 0 更高位不变所以一定变小
因此，只要我们让变成（减少一部分）等式左边变为

证毕
0X01 切一些简单题掌握了这么一个前置知识以后，我们用这个前置知识来切题。
博弈论的题目，我们一般都得分析出来，如何才能够获胜。先看这一道题 Nim游戏
首先分析出「必胜态」和「必败态」游戏的最后一定是有一个人拿走一个石子后，就没有石子了。此时 n 堆石子异或为

我们现在有就一定能够让对方处于这一前置知识，所以只要当前先手必胜！
接着我们来看一道变化的题目：
台阶-Nim游戏
题目描述如下：
现在，有一个级台阶的楼梯，每级台阶上都有若干个石子，其中第i个石子(i≥1)两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。
这个题有一个小的变形

胜负与偶数台阶无关，因为如果先手移动偶数阶的石子到奇数阶，那么后手一定能够移动相同的石子到偶数阶。所以先手必败

将所有奇数阶的石子异或起来，如果不为 0。那么先手必胜，原因是先手一定能够使石子，使异或为 0。
0X02 sg 函数首先我们来描述这样一个基础问题：
有 n 个石子，假设 A、B 可以轮流拿 1 或 2 颗石子，谁最后没有石子拿谁就输。问如果 A 先拿，A 是不是能够必胜。
这里我取 n = 5 并画出 n = 5 时的所有可能行

文章图片
我们求出每个点的 sg 函数，一个节点的 sg 值是它所有子节点的 sg 值所不能到达的最小自然数。可能很抽象，我们举个例子（按照上这张图写出每个节点的 sg 值）：

0 谁也不能到达。所以 sg(0) = 0
1 能到达 0。sg(0) = 1 所以 sg(1) = 1
2 能到达 1 和 0。sg(0) = 0 sg(1) = 1所以 sg(2) = 2
3 能到达 2 和 1。sg(1) = 1 sg(2) = 2 所以 sg(3) = 0
4 能到达 2 和 3。sg(2) = 2 sg(3) = 0 所以 sg(4) = 1
5 能到达 4 和 3。sg(3) = 0 sg(4) = 1 所以 sg(5) = 2

下面给出这道题的结论，只要是那么此节点一定是必败态。
这里可以用反证法证明：
如果那么 i 这个节点一定能转移到 sg 等于 0 上的节点。而 sg 等于 0 的点要么可以转移到不为 0 的点（后手还是可以转移到另外一个 sg 不等于 0 的点上去），要么就是最后输了的状态。
sg 函数的一些简单拓展问题

n 堆石子和 s 种拿法

集合-Nim游戏
代码如下：

from sys import stdindef read(): return list(map(int, stdin.readline().split()))def sg(n): if f[n] != -1: return f[n] t = set() for c in cs: if c <= n: t.add(sg(n-c))i = 0 while i in t: i += 1 f[n] = i return iN = 10010 cn, cs = read()[0], read() n, nums = read()[0], read() f = [-1] * Nres = 0 for v in nums: res ^= sg(v) if res: print("Yes") else: print("No")

拆分

拆分-Nim游戏
【博弈论基础知识】代码如下：

from sys import stdindef read(n = 2): if n == 1: return int(stdin.readline()) return map(int, stdin.readline().split())N = 110 n = read(1) nums = read() f = [-1] * Ndef sg(x): if f[x] != -1: return f[x]t = set() for i in range(x): for j in range(i+1): t.add(sg(i) ^ sg(j))i = 0 while i in t: i += 1 f[x] = ireturn ires = 0 for v in nums: res ^= sg(v)if not res: print("No") else: print("Yes")