ICG 游戏博弈问题与 SG 定理

ICG 游戏

定义

ICG 游戏是博弈游戏的一种，其定义如下：

  1. 游戏由两人参加，两人轮流做出决策
  2. 当有一人无法决策即无论如何都必败时对手胜出，且 ICG 游戏一定会在有限步内完成，游戏没有平局
  3. 游戏的状态转移是单向的，同一个状态只能达到一次

必胜点和必败点

必胜点 N ( Next ) 和必败点 P ( Previous ) 描述的是某个游戏状态当前的胜负。

若当前状态为必胜点 N ，则先手必胜，反之，若当前状态为必败点 P ，则先手必败。

可能到这里为止大家还是会觉得比较抽象，所以我们给出一个实际例子：

假设有一堆石头，两人轮流从这堆石头中取走 1 ~ 5 块石头，初始状态下有 n 块石头，问 n 为何值时先手必胜？

先说结论：n % 6 != 0 时先手必胜。

原因十分简单，若 n 不是 6 的倍数，则先手一定可以取走 1 ～ 5 块内的石头使得取走石头后这堆石头的数量能被 6 整除，此后，对手只要取走 m 块石头，我们就取走 6 - m 块石头，可以保证我们每次取完后石头的数量都是 6 的倍数。如此一来，最后的石头一定是被我们取走。

于是，我们可以得到石头数量 n 对应的 NP 状态：

n 0 1 2 3 4 5 6 7 8 9 ...
state P N N N N N P N N N ...

在这里，我们不难得出结论：

  • 所有必胜点必然可以在一步操作内转移到必败点
  • 所有必败点无论如何操作只能转移到必胜点

SG 定理

SG 是 Sprague-Grundy 的缩写，SG 定理是处理 ICG 博弈问题的重要方法，在讲解其使用之前，我们先简要介绍一下 SG 函数的定义。

SG 函数

首先我们定义 \(mex\) ( minimal excludant ) 运算，\(mex(F)\) 即表示不属于非负整数集 \(F\) 中最小的元素：

例如： \[ \begin{array}{} mex(\{1, 2, 3\}) = 0 \\ mex(\{0, 1, 3, 4\}) = 2 \\ mex(\emptyset) = 0 \end{array} \] 什么是 SG 值？

SG 值是一种通过递归定义的值，它一般情况下是一个非负整数，可以用来描述游戏状态是必胜点还是必败点，假设游戏状态 \(V_i\) 的 SG 值为 \(SG(V_i)\) ，那么其状态转移方程如下： \[ SG(V_i) = mex(\{SG(V_j) \ | \ V_i \rightarrow V_j \}) \] 其数值上等于与 \(V_i\) 所有后继状态的 SG 值不相等的最小非负整数。

基于此，我们得到一条重要结论：SG 值不为 0 的状态为必胜点，SG 值为 0 的状态为必败点。

这个结论很好证明：若 SG 值不为 0，说明该状态一定能一步转移到 SG 值为 0 的状态，即可以一步转移到必败点，所以该状态一定为必胜点；反之，若 SG 值为 0，则该状态无法一步转移到必败点，只能转移到必胜点或者无法决策，故该点一定为必败点。

我们还是用上述的取石头问题来举例说明，则不同石头数量 n 对应的 SG 值如下：

n 0 1 2 3 4 5 6 7 8 9 10
SG(n) 0 1 2 3 4 5 0 1 2 3 4

\[ \begin{array}{} SG(0) = mex(\emptyset) = 0 \\ SG(1) = mex(\{0\}) = 1 \\ SG(2) = mex(\{0, 1\}) = 2 \\ SG(3) = mex(\{0, 1, 2\}) = 3 \\ SG(4) = mex(\{0, 1, 2, 3\}) = 4 \\ SG(5) = mex(\{0, 1, 2, 3, 4\}) = 5 \\ SG(6) = mex(\{1, 2, 3, 4, 5\}) = 0 \\ ... \newline SG(10) = mex(\{5, 0, 1, 2, 3\}) = 4 \\ ... \end{array} \]

SG 定理详解

现在我们已经知道了 SG 函数的定义，那 SG 定理又是什么呢？

什么是 SG 定理 ?

SG 定理指的是若一个 ICG 博弈游戏的游戏状态可以分为多个子状态，且子状态互相独立，则该游戏状态下的 SG 值等于所有子状态的 SG 值的异或值。

这又是什么意思呢？别急，我们还是用取石头的例子来说明：

假设现在有 \(k\) 堆石头，每堆石头有 \(n_i(i = 1, 2, ...,k)\) 块石头 ，两个人轮流从每一堆石头中取走 \([1, m]\) 块石头，先取完所有石头的一方获胜。我们设此刻游戏状态的 SG 值为 \(SG((n_1, n_2, ..., n_k))\) ，由 SG 定理可得： \[ SG((n_1, n_2, ..., n_k)) = SG(n_1) \oplus SG(n_2) \oplus ... \oplus SG(n_k) \]

  • \(SG((n_1, n_2, ..., n_k)) \neq 0\) ：先手胜
  • \(SG((n_1, n_2, ..., n_k)) = 0\) ：先手败

以上就是完整的 SG 定理了。

SG 定理的合理性

为什么 SG 定理会与位运算的异或有关呢？它们是如何联系上的？为什么这种计算是合理的呢？

以下我们给出简要的证明：

根据 SG 值的定义，必败点的 SG 值一定为 0，对于此题而言，游戏的终点就是所有的石头被取完，此时 SG 值是 k 个 0 的异或值，显然为 0。

若当前的 SG 值不为 0，我们假设： \[ SG((n_1, n_2, ..., n_k)) = {001010..}_2 \] 我们找到该 SG 值数值为 1 的最高位，由异或运算符的性质，必然存在奇数个子状态的 SG 值该位为 1，我们不妨假设其中一个子状态对应的 SG 值为 \(SG_0\) ，由 SG 值的定义，该状态一定可以一步之内转变为任何 SG 值小于 \(SG_0\) 的状态，\(SG_0\) 对应母状态下数值为 1 的最高位的值也为 1，我们让其变为 0，然后从这一位开始之后全部位取反，则一定可以将母状态的 SG 值变为 0。

0 1 0 1 1 1
0 1 1 0 0 0
0 1 0 1 0 1
0 1 1 0 1 0
如上，我们将第二个子状态 的 SG 值转移到 0 0 0 1 1 1，就将母状态的 SG 值转化为 0 了
0 1 0 1 1 1
0 0 0 1 1 1
0 1 0 1 0 1
0 0 0 0 0 0

反之，如果母状态的 SG 值为 0，则改变任何一个子状态，由于异或运算的性质，母状态的 SG 值一定无法维持为 0。

而根据 ICG 博弈游戏的定义，游戏一定会在有限步内完成，故所有子状态 SG 值的异或运算不为 0 的母状态一定是必胜点。

实际应用

Fibonacci again and again

Problem Description 任何一个大学生对菲波那契数列(Fibonacci numbers)应该都不会陌生，它是这样定义的： F(1) = 1； F(2) = 2； F(n) = F(n - 1) + F(n - 2) ( n >= 3 )； 所以，1, 2, 3, 5, 8, 13, ... 就是菲波那契数列。 今天，又一个关于 Fibonacci 的题目出现了，它是一个小游戏，定义如下：

  1. 这是一个二人游戏；
  2. 一共有 3 堆石子，数量分别是 m, n, p 个；
  3. 两人轮流走；
  4. 每走一步可以选择任意一堆石子，然后取走f个；
  5. f 只能是菲波那契数列中的元素 ( 即每次只能取1，2，3，5，8 … 等数量 )；
  6. 最先取光所有石子的人为胜者；

假设双方都使用最优策略，请判断先手的人会赢还是后手的人会赢。

Input 输入数据包含多个测试用例，每个测试用例占一行，包含 3 个整数 m, n, p ( 1 <= m, n, p <= 1000 )。 m = n = p = 0 则表示输入结束。

Output 如果先手的人能赢，请输出“Fibo”，否则请输出“Nacci”，每个实例的输出占一行。

输入样例

1
2
3
1 1 1
1 4 1
0 0 0

输出样例

1
2
Fibo
Nacci

分析：

本题所描述的游戏就是一种 ICG 博弈，且三堆石头互不影响，所以我们可以直接使用 SG 定理求解，再加上记忆化 DFS 优化，很容易就能求解此问题。废话不多说，直接上代码😎。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstring>

using namespace std;

#define MAX_FIB_NUM 50
#define MAX_AMOUNT 1005

int Fibonacci[MAX_FIB_NUM]; // 储存 Fibonacci 数列的值
int SG[MAX_AMOUNT]; // 记录 SG 值，初始化为 -1

// 记忆化搜索
int fib(int n) {
    if (Fibonacci[n]) {
        return Fibonacci[n];
    }

    if (n == 0) {
        Fibonacci[n] = 1;
        return 1;
    }
    else if (n == 1) {
        Fibonacci[n] = 2;
        return 2;
    }

    Fibonacci[n] = fib(n - 1) + fib(n - 2); // 记忆

    return Fibonacci[n];
}

int sg(int n) {
    // 返回 SG 值
    if (SG[n] >= 0) {
        return SG[n];
    }
    if (n == 0) {
        SG[n] = 0;
        return 0;
    }
    bool vis[MAX_AMOUNT] = {0}; // 记录当前状态可达状态的 SG 值是否出现过
    for (int i = 0; n - fib(i) >= 0; i++) {
        vis[sg(n - fib(i))] = true;
        // 记录已出现的 SG 值
    }
    for (int i = 0; i < MAX_AMOUNT; i++) {
        if (!vis[i]) {
            SG[n] = i;
            break;
        }
    }

    return SG[n];
}


int main() {

    ios::sync_with_stdio(false);

    memset(SG, 0xff, sizeof(SG)); // 初始化
    int m, n, p;
    while (cin >> m >> n >> p, m != 0 || n != 0 || p != 0) {
        if (sg(m) ^ sg(n) ^ sg(p)) {
            // SG 定理
            cout << "Fibo" << endl;
        }
        else {
            cout << "Nacci" << endl;
        }
    }

    return 0;
}
数据结构与算法
#SG 定理 #SG 函数 #组合博弈 #组合数学 #记忆化搜索 #位运算
ICG 游戏博弈问题与 SG 定理
https://goer17.github.io/2023/03/02/ICG 游戏博弈问题与 SG 定理/
作者
Captain_Lee
发布于
2023年3月2日
许可协议