博弈论入门 | Yuhang's Blog

程序竞赛中的博弈论入门。Nim游戏，SG函数，常见策略和变形。

我们讨论的是无偏博弈(impartial game)。也就是说，在任意局势内，“所有可行的走法仅仅依赖当前的游戏局势，而和现在正在要行动的是哪一方无关”。详见维基百科。我们接下来要讨论的“状态”，就是指某一时刻的游戏局势。

必胜和必败状态的定义

某状态为必败状态，当且仅当该状态：
1. 没有后继状态，
2. 或其所有后继状态都是必胜状态。
某状态为必胜状态，当且仅当该状态：
1. 存在至少一个后继状态为必败状态。

推论

若某状态只有一个后继状态，那么该状态和此后继状态中必有一个必胜状态、一个必败状态。

SG函数

定义SG函数为 $SG (x) = mex {SG (y_{1}), SG (y_{2}), \dots SG (y_{k})}$ 其中 $y_{i}$ 是 $x$ 的后继状态， $mex$ 函数表示不属于该集合的最小非负整数。可以发现 $SG$ 函数为 $0$ ，当且仅当某状态为必败：

若某状态 $x$ ：
1. 没有后继状态，则 $SG (x) = 0$ ，因为空集的 $mex$ 函数显然为 $0$ ；
2. 只有必胜后继状态，则亦满足 $SG (x) = 0$ ，因为没有后继状态的函数值为 $0$ ，可以取到最小的非负整数。
若某状态 $x$ ：
1. 存在必败后继状态，则必满足 $S G (x) > 0$ ，原因显然。

Nim 游戏

规则是：初始有 $n$ 堆物体，每次玩家从选择一堆物体并取走若干（不能不取，可以取完），取完最后一堆物体的人获胜。由于是公平组合游戏，局面的必胜、必败状态只由每堆物体之中的数量决定。先考虑最简单的情况：我们只有一堆物体。假设这堆物体有 $x$ 个，那么：

当且仅当 $x = 0$ ，局面为必败状态，从而 $SG (0) = 0$ ；
当 $x > 0$ 时，其后继状态是 $0, 1, 2, \dots, x - 1$ ；由数学归纳法及 $SG$ 函数的定义，可得 $SG (x) = x$ 。

因此 $SG (x) = x$ 。当我们有多堆物体的时候，我们可以视为这是多个“一堆Nim游戏”的组合游戏，即每堆是一个独立的游戏，每局每人选择其中一个游戏进行。设 $A$ ， $B$ 为游戏状态，记 $A + B$ 为组合游戏状态。可以证明： $SG (A + B) = SG (A) \oplus SG (B)$ 其中 $\oplus$ 是异或运算。首先可以观察到此处的异或运算满足了必要的交换律、结合律、归零律、恒等律，但这不足以构成有效证明。证明需要从定义入手。由于每局 $A$ 和 $B$ 可以视为相互独立的状态，则有 $SG (A + B) = mex ({SG (C + B) ∣ A \to C} \cup {SG (A + D) ∣ B \to D})$ 根据归纳假设， $SG (A + B) = mex ({SG (C) \oplus SG (B) ∣ A \to C} \cup {SG (A) \oplus SG (D) ∣ B \to D})$ 下面只需证明 $SG (A) \oplus SG (B)$ 等于上式右侧即可。首先 $SG (A) \oplus SG (B)$ 不在两个集合中（因为假如在，就会得到 $A = C$ 或 $B = D$ ）；其次可以证明所有小于 $SG (A) \oplus SG (B)$ 的非负整数均存在于其中至少一个集合中，具体过程此处省略。这一结论的证明可以参考Nimber - Wikipeida。有了这一结论，我们得到：对于一个有 $n$ 堆物体、每堆物体有 $a_{i}$ 个的Nim游戏状态 $A$ ，其 $SG$ 函数值是： $SG (A) = a_{1} \oplus a_{2} \oplus \dots \oplus a_{n}$ 这一结果称为Nim和。当且仅当Nim和为 $0$ 时，一个状态是必败状态。 SG定理指出任何公平组合游戏都等价于一堆Nim游戏，这种等价性正是体现在每个游戏局面的 $SG$ 函数上的。

常见解题策略

非组合游戏

如果游戏不存在组合游戏，可以直接使用必胜和必败状态的定义配合（记忆化）搜索打表局面的必胜、必败01状态。伪代码如下。

int mem[N]; // 初始化为-1
int solve(int n) {
    if (n == n0) return 0; // 初始状态
    if (mem[n] > -1) return mem[n];
    for(int i : nxt[n]) { // 后继状态
        if (!solve(i)) return mem[n]=1;
    }

    return mem[n]=0;
}

HDU-1079

对于每个可能的日期，考虑其后继日期：

第二天，
下个月的同一日期（可能不存在）。

若一个日期没有必败后继状态，则其为必败；否则其为必胜。本题数据范围无需打表。注意需要把大于目标日期的状态设为必胜状态，把目标日期设为必败状态。

HDU-1847

打表后发现规律是判断模3是否为0即可。

组合游戏

如果是组合游戏，则需要用SG函数配合异或运算来解题。模板如下：

int mem[N]; //初始化为-1
int sg(int n) {
    if (n == n0) return 0;
    if (mem[n] > -1) return mem[n];

    set<int> st; // 放在全局变量可能递归时出现冲突
    for(int i : nxt[n]) { // 后继状态
        st.insert(sg(i)); // 可能需要异或运算表示组合状态
    }

    for(int i=0; ; i++) {
        if (!st.count(i)) return mem[n]=i;
    }
}

运气好的话就能看出来规律了。

输出必胜策略

有时候题目不是判断是否必胜，而是输出必胜策略。思路简单：对于SG函数非零的必胜状态，思考如何将它转移到SG函数为0的状态。

常见游戏变形

Staircase Nim

参考：https://codeforces.com/blog/entry/44651。石子的堆是编号的，而有些堆的石子在策略上是无用的；对那些有用的堆来说，游戏就变成了一个多堆Nim游戏。 HDU-3389

Fibonacci博弈

参考：https://blog.csdn.net/da\_kao\_la/article/details/82945862。 HDU-2516：1堆石子有 $n$ 个，两人轮流取。先取者第1次可以取任意多个，但不能全部取完。以后每次取的石子数不能超过上次取子数的2倍。取完者胜。打表策略：

int mem[1000][1000];
int solve(int n, int limit) {
    if (n == 0) return 0;
    if (mem[n][limit] > -1) return mem[n][limit];
    rep(i,1,limit) {
        if (!solve(n-i, i*2)) return mem[n][limit]=1;
    }
    return mem[n][limit]=0;
}

int main() {
    mmst(mem, -1);
    rep(i,1,100) {
        cout << i << " " << solve(i, i-1) << endl;
    }
}

可以观察到规律是判断 $n$ 是否为Fibonacci数。

Bash博弈

HDU-2897：一堆硬币一共有 $n$ 枚，从这个硬币堆里取硬币，一次最少取 $p$ 枚，最多 $q$ 枚，如果剩下少于 $p$ 枚就要一次取完。两人轮流取，直到堆里的硬币取完，最后一次取硬币的算输。打表解决容易，结论是模 $p + q$ 循环。

Wythoff博弈

HDU-1527：有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。打表依然可做，但规律不甚明显。结论是：设两堆石子数量为 $(a, b)$ ，其中 $a \leq b$ 。记常数 $ϕ = \frac{1 + \sqrt{5}}{2}$ ，则当且仅当 $a = [ϕ * (b - a)]$ 时，该状态为必败。参考：https://www.cnblogs.com/zjl192628928/p/10485562.html。