博弈论入门 | Yuhang's Blog

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

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

必胜和必败状态的定义

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

推论

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

SG函数

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

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

Nim 游戏

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

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

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