博弈论基础知识

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 stdin

def 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 i

N = 10010
cn, cs = read()[0], read()
n, nums = read()[0], read()
f = [-1] * N

res = 0
for v in nums:
    res ^= sg(v)
if res: print("Yes")
else: print("No")

• 拆分

拆分-Nim游戏

代码如下：

from sys import stdin

def 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] * N

def 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] = i
    
    return i
    
res = 0
for v in nums:
    res ^= sg(v)

if not res:
    print("No")
else:
    print("Yes")