Nim游戏等简单博弈模型， $SG$ 函数的计算与应用。

博弈论

博弈论中的基本概念

Nim游戏

给定 $n$ 堆物品，每一堆有 $a_i$ 个，两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可以把一堆全部取完，但是不能不取，取走最后一件物品的人胜利，两个人都采取最优策略。

容易发现，没有物品是一种平衡态，如果先出手的人总可以将不平衡态转化为平衡态，那么先手必胜，后手必败。

在Nim游戏中，这种平衡态指的是所有堆剩余物品的异或和为0 。

公平组合游戏ICG

若一个游戏满足：

由两名玩家交替行动。
在游戏进程的任意时刻，可以执行的合法行动与轮到哪个玩家无关。
不能行动的玩家判负。

则该游戏叫做公平组合游戏（ICG）。

NIM游戏就是公平组合游戏。生活中常见的棋类游戏大多不是公平组合游戏。

有向图游戏

给定一个有向无环图，图中有唯一一个起点，在起点放有一枚棋子，两名玩家交替地沿着有向边移动棋子，每次走一步，无法移动者判负，则该游戏被称为有向图游戏。

容易把任何一个公平组合游戏转化为有向图游戏。

Mex运算

$S$ 是自然数 $N$ 的子集，则

mex(S) = \min_{x\in N, x\notin S}\{x\}

即 $S$ 中没有出现的最小的自然数。

SG函数

在有向图游戏中，对于每个结点 $x$ ，设从 $x$ 出发共有 $k$ 条有向边，分别到达 $y_1, y_2 ... y_k$ ，则

SG(x) = mex(\{SG(y_1), SG(y_2), ... SG(y_k)\})

边界条件：出度为 $0$ 的点的 $SG$ 值显然是 $0$ 。

这个可以通过记忆化搜索去计算。

有向图游戏的和

假设现在有 $m$ 个有向图游戏 $G_1, G_2, ... G_m$ ，其行动规则是每次任选某个游戏，然后移动一步。这些游戏加起来得到的游戏 $G$ 叫做有向图游戏的和。

有向图游戏的和的 $SG$ 函数值等于每个有向图游戏的 $SG$ 函数值的异或和。

SG(G) = SG(G_1) \oplus SG(G_2)...\oplus SG(G_m)

SG定理

有向图游戏的某个局面必胜，当且仅当该局面对应的 $SG$ 函数的值大于 $0$

有向图游戏的某个局面必败，当且仅当该局面对应的 $SG$ 函数的值等于 $0$

例题

博弈论问题中用到的理论知识主要是上面提到的部分。在求解不同的具体问题时，除了有理论基础之外，还要有强大的分类讨论能力。

集合-Nim游戏

不同于普通的Nim游戏，集合Nim游戏规定了一个每次可以取走的石子的数目的集合 $S$ ，每次只能取走 $S$ 中给出的个数的石子，无法取走就算输。

给出每堆石子的初始石子个数，那么我们肯定可以画一个局面转移图，去枚举所有的可能到达的状态及其连接关系，这样对于每一堆石子，其实就是在玩有向图游戏，所以借助 $SG$ 函数，将每堆石子的函数值求出来再异或，利用 $SG$ 定理即可判断是否先手必胜。

代码实现的话，主要是记忆化搜索求 $SG$ 函数的值：

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 10010;

int n, k, s[N], h[N], dp[M];

int sg(int x) {
    if (dp[x] >= 0) return dp[x];

    unordered_set<int> val;
    for (int i = 1; i <= k; i++) {
        if (x >= s[i]) {
            val.insert(sg(x - s[i]));
        }
    }

    for (int i = 0; ; i++) {
        if (!val.count(i)) {
            return dp[x] = i;
        }
    }
}

int main() {
    cin >> k;

    for (int i = 1; i <= k; i++) {
        cin >> s[i];
    }

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    memset(dp, -1, sizeof dp);

    int res = 0;
    for (int i = 1; i <= n; i++) {
        res ^= sg(h[i]);
    }

    if (res) {
        puts("Yes");
    } else {
        puts("No");
    }

    return 0;
}

WanderOvO

博弈论

博弈论