好甜 好甜 好甜🥰这个世界需要更多的纯爱🥰

感觉够重量级了于是兑现一下之前的承诺

没看出封面和内容的关联.jpg

概述

博弈论简介

博弈论是经济学的一个分支，主要研究多个个体在特定规则下的最优策略。

出于实用性考虑，本文仅讨论算法竞赛中最常见的博弈类型——组合博弈（Combinatorial Game, CG）。其中，又以公平组合博弈（Impartial Combinatorial Games, ICG）最为常见。

公平组合博弈

满足以下条件的博弈是公平组合博弈：

  1. 有两名玩家，且交替行动。

  2. 在游戏的任意状态中，能够继续执行的行动只取决于当前的局面，与之前的操作、轮到哪名玩家无关。

    绝大多数棋类中，每名玩家只能操作本方棋子，因而不属于ICG。

  3. 游戏以玩家无法行动结束，且一定会在有限步数内分出胜负。

在公平组合博弈中，默认玩家都是绝对理性人，也能够预料到博弈中发生的所有局面，又因为游戏会在有限步内结束，因此游戏中的每一个局面的最终结果是确定的，只有必胜和必败两种情况。

必胜态与必败态

必败态（P-Position）：该局面的后续所有可以经过一次操作到达的局面均处于必胜态。

必胜态（N-Position）：该局面的后续所有可以经过一次操作到达的局面至少有一个处于必败态。

特别的，我们定义最终无法行动的局面为必败态。

这就给了我们一种使处于必胜态的玩家取得胜利的明确策略：必胜态后续必有一个必败态，处于必胜态的玩家A将局面操作至必败态，同时将移动权交给玩家B，玩家B处于必败态，其后续所有状态均为必胜态，无论怎么操作，移动权交还到玩家A时局面必为必胜态，再继续操作，局面循环必胜态与必败态交替的过程。同时因为游戏一定会在有限步数内结束，故必定会到达无法行动的局面，此时移动权必定在玩家B，因此A必然取得胜利。

经典ICG实例

巴什博弈（Bash Game）

一共有n颗石子，两个人轮流拿，每次可以拿1~m颗石子，拿到最后一颗石子的人获胜。

结论：当 $n\equiv 0 \pmod{m+1}$ 时后手必胜，否则先手必胜。

具体策略是，如果 $n\equiv r \ne0 \pmod{m+1}$ ，那么先手取 $r$ 个石子，剩下 $m+1$ 倍数个石子。此时不管后手怎么取，先手都可以将其恢复成 $m+1$ 的倍数，直至变为 $0$ 。如果 $n\equiv 0 \pmod{m+1}$ ，则反过来分析，后手必胜。

按照上面的必胜态和必败态来分析，即石子数为 $m+1$ 的倍数时为必败态，非倍数为必胜态。获胜策略就是使得局面在必胜态和必败态之间来回交替变换直到达到最终局面。

尼姆博弈（Nim Game）

非常重要！是后续SG定理的基础！

一共有n堆石头，两人轮流进行游戏，在每个玩家的回合中，选择任何一个非空的石头堆，并从这堆石头中移除任意正数的石头数量，拿到最后一颗石子的人获胜。

结论：当每堆石头数量的异或和为 $0$ 时后手必胜，否则先手必胜。

具体策略是，如果异或和不为 $0$，那么先手在某一堆中拿掉一些石子使得异或和为 $0$。此时不管后手怎么取，先手都可以将其异或和恢复成 $0$，直至先手取到最后一颗石子。反之后手必胜。

我们需要证明两件事：

第一，异或和不为 $0$ 时，先手必然存在一个方案使得拿掉某堆的一些石子后可将异或和变为 $0$。

第二，异或和为 $0$ 时，怎么取石子都会使得异或和不为 $0$ 。

第二点好证，先进行证明。我们把所有数拆成二进制，按照每一位去考虑。异或和为 $0$ ，说明所有位上的 $1$ 的数量都是偶数。如果从某一堆石子中取若干石子，必然会导致这个数某一位上的 $1$ 消失，从而使得这一位的 $1$ 的数量变成奇数，从而异或和非 $0$ 。

再证明第一点。还是按照每一位考虑，异或和非 $0$ ，代表至少有一位上是 $1$ ，所有数中这一位上 $1$ 的数量为奇数。我们从异或和的最高有效位上是 $1$ 的某个数中去取，设异或和是 $sum$ ，这个数是 $a$ ，则我们将其变成 $a \oplus sum$ ，即取 $a - a \oplus sum$ 个石子。容易发现 $a \ge a \oplus sum$ ，则可以保证这样操作必定合法，所有数异或和必定可变为 $0$ 。

证明完毕，按照上述策略拿取石子即可。

斐波那契博弈（Fibonacii Game）

有一堆个数为n(n>=2)的石子，游戏双方轮流取石子，规则如下：

  1. 先手不能在第一次把所有的石子取完，至少取1颗；

  2. 之后每次可以取的石子数至少为1，至多为对手刚取的石子数的2倍。

取走最后一个石子的人获胜。

结论：n为斐波那契数时先手必败，反之先手必胜。

证明：

先证明n为斐波那契数时先手必败。通过数学归纳法：n=2，n=3时显然结论成立。假设对于前k项斐波那契数都成立。那么对于第 $k+1$ 项，$f[k+1]=f[k]+f[k-1]$，将石子拆成两堆。由于斐波那契数相邻项的比值接近黄金分割率，从第二项开始，$f[k]\lt 2f[k-1]$ 。如果先手取的石子数大于等于 $f[k-1]$ ，则后手可以全部取完。否则先手取的石子数小于 $f[k-1]$ ，我们再对 $f[k-1]$ 做拆分，递归下去，把每次拆分前的状态当做一个子问题，必然存在一个时刻，先手取的石子数量大于等于某个子问题的对应的值，此时后手简单的把这个子问题取光即可。由于斐波那契隔项的比值大于 $2$ ，则后手取后先手无法取完当前子问题同级的另一个子问题，则又按照同样的逻辑递归下去，每次的结果都是后手把子问题的石子全部取光，从整体上看就是后手一定能取走最后一个石子。

再证明n不为斐波那契数时先手必胜。需要使用齐肯多夫定理（Zeckendorf定理）：任何正整数可以表示为若干个不连续的Fibonacci数之和。 因此将n分解后，先手只需要简单地取走最小的那项数，留给后手的就是和上面类似的取若干斐波那契数的子问题（无法一次取完，至少取一颗），则后手必败，先手必胜。

例题 P6487 [COCI 2010/2011 #4] HRPA

斐波那契博弈模板题。黑题重拳出击。

当然没学过这个从零推这个确实扯淡。所以才需要后面的SG定理。

威佐夫博弈（Wythoff Game）

有两堆石子，两个人轮流取，每次可以从任意一堆中取任意数量的石子，也可以从两堆中取走相同数量的石子，拿到最后一颗石子的人获胜。

结论：设两堆石子数量为 $a$ 和 $b$ （$a\le b$），当 $a = \left\lfloor \frac{(\sqrt{5}+1)}{2}(b-a) \right\rfloor$后手必胜，否则先手必胜。

不会证，用SG定理打表观察可知。（

例题 P2252 [SHOI2002] 取石子游戏 |【模板】威佐夫博弈

SG函数与SG定理

有向图游戏与SG函数

我们可以把任意的ICG都抽象成一个有向图，ICG中每一个状态一一对应有向图的一个节点，每个节点向操作一步可到达的所有节点连边，最终无法行动的点没有后续节点。

ICG必定会在有限步内结束，显然这个有向图是无环的。

我们引出SG函数（Sprague-Grundy函数）：

定义最终无法行动的点的 $SG$ 值为 $0$ 。

一般地，对于一个状态点N，其 $SG$ 值定义为其所有后续节点的 $SG$ 值的最小排除数（$MEX$）。

如果 $SG(N)=0$ ，则该点处于必败态；如果 $SG(N)\ne 0$ ，则该点处于必胜态。

我们结合必胜态必败态的定义和 $MEX$ 的运算规则来分析这个结论：

必胜态后续必然存在一个必败态，所以其后续节点的 $SG$ 值集合中必然包含 $0$ ，那么这个节点的 $MEX$ 必然不为 $0$ ；

必败态后续均为必胜态，其后续节点的 $SG$ 值集合中必然不包含 $0$ ，那么这个节点的 $MEX$ 必然为 $0$ 。

这不是循环论证，我们从无法行动的点的 $SG$ 值反推即可得到这个结论。

必胜态必败态恰好和 $MEX$ 运算结合了起来，实在是妙！

SG定理

上面的结论只需要判断 $SG$ 值是否为 $0$ 即可，而具体的值用于 $SG$ 定理。

SG定理（Bouton定理）：如果一个ICG可以拆分成若干独立的子ICG，那么 $SG(总)=SG(分1)\oplus SG(分2)\oplus \cdots \oplus SG(分n)$ 。

$SG$ 定理适用于任何ICG，我们可以使用类似尼姆博弈的方式来证明这个定理。

如果先手状态下 $SG(总) \ne 0$ ，那么必然可以操作其中一个子ICG，使得所有子ICG的异或和变成 $0$ 。反证法可以证明，如果一个节点的 $SG$ 值为 $x$ ，那么其后续节点的 $SG$ 值必然包含 $0$ 到 $x-1$ 的所有值，即可以通过一步操作把这个子ICG的 $SG$ 值变为 $0$ 到 $x-1$ 中任意一个数，可以发现这和尼姆博弈非常类似。那么只需要按照尼姆博弈的方式控制所有子ICG的 $SG$ 值即可。

有向图游戏和尼姆游戏的区别在于有向图游戏的每个节点的后续节点的 $SG$ 值有可能大于该节点的 $SG$ 值。但我们不向这些节点操作，即可把有向图游戏规约到尼姆游戏。

也就是说，我们有了 $SG$ 定理，对于任意的ICG，我们都可以通过暴力打表的方式来观察规律，视情况寻找 $O(1)$ 做法或直接暴力解决。

例题

P2148 [SDOI2009] E&D

本关考验你打表功夫。模型很好提取，把SG表打出来找规律。

P2148

很美的分形使我原地旋转。其实到这一步可以递归 $O(\log{V})$ 来算答案了。

$O(1)$ 公式直接给出：$SG(x,y)=f((x-1)|(y-1))$ ，其中 $f(x)$ 是 $x$ 二进制表示下低位连续 $1$ 的个数。

怎么观察？多练吧。

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e2 + 10;
constexpr int MOD = 998244353;

int sg[N][N];
int c[N * N];

int SG(int a, int b) {
    if (a == 1 && b == 1) return 0;
    if (sg[a][b] != -1) return sg[a][b];
    vector<int> c(N * N);
    if (a > 1) {
        for (int i = 1; i < a; ++i) c[SG(i, a - i)] = 1;
    }
    if (b > 1) {
        for (int i = 1; i < b; ++i) c[SG(i, b - i)] = 1;
    }
    for (int i = 0; i < N * N; ++i) {
        if (!c[i]) {
            return sg[a][b] = sg[b][a] = i;
        }
    }
}

int calc(int x, int y) {
    int sg = 0;
    // while (x % 2 != 1 || y % 2 != 1) {
    //     sg++; 
    //     if (x % 2 == 1) x++;
    //     if (y % 2 == 1) y++;
    //     x /= 2;
    //     y /= 2;
    // }
    sg = __builtin_ctz(~((x - 1) | (y - 1)));
    return sg;
}

void bf() {
    memset(sg, -1, sizeof(sg));
    sg[1][1] = 0;
    int step = 1;
    for (int i = step; i <= 64; i += step) {
        for (int j = step; j <= 64; j += step) {
            cout << (SG(i, j)) << " \n"[j == 64];
        }
    }
    cout << "==========================\n";
    for (int i = step; i <= 64; i += step) {
        for (int j = step; j <= 64; j += step) {
            cout << calc(i, j) << " \n"[j == 64];
        }
    }
}

void solve() {
    int m, n;
    cin >> m;
    n = m / 2;
    int xorsum = 0;
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        xorsum ^= __builtin_ctz(~((x - 1) | (y - 1)));
    }
    cout << (xorsum ? "YES" : "NO") << "\n";
}

signed main() {
    
    FIO;
    // bf();
    TESTS {
        solve();
    }

    return 0;
}

P3185 [HNOI2007] 分裂游戏

重点在于怎么提取模型。需要把豆子看成独立游戏，而不是瓶子。豆子的一个后继状态对于两个豆子的子问题，对于这两个子问题，其 $SG$ 值异或起来才是完整的后继状态的 $SG$ 值。数据范围很小，打表即可。

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
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 21;
constexpr int MOD = 998244353;

int sg[N], p[N];
bool c[N * N];

void init() {
    for (int i = 1; i < N; ++i) {
        memset(c, 0, sizeof(c));
        for (int j = i - 1; j >= 0; --j) {
            for (int k = j; k >= 0; --k) {        
                c[sg[j] ^ sg[k]] = 1;
            }
        }
        for (int j = 0; j < N * N; ++j) {
            if (!c[j]) {
                sg[i] = j;
                break;
            }
        }
    }
}

void solve() {
    int n;
    cin >> n;
    int xorsum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        if (p[i] & 1) xorsum ^= sg[n - 1 - i];
    }
    if (!xorsum) {
        cout << "-1 -1 -1\n0\n";
        return;
    }
    int cnt = 0, a = -1, b, c;
    for (int i = 0; i < n; ++i) {
        if (!p[i]) continue;
        for (int j = i + 1; j < n; ++j) {
            for (int k = j; k < n; ++k) {
                if (!(xorsum ^ sg[n - 1 - i] ^ sg[n - 1 - j] ^ sg[n - 1 - k])) {
                    cnt++;
                    if (a == -1) {
                        a = i;
                        b = j;
                        c = k;
                    }
                }
            }
        }
    }
    cout << a << " " << b << " " << c << "\n" << cnt << "\n";
}

signed main() {
    
    FIO;
    init();
    TESTS {
        solve();
    }

    return 0;
}

Anti-SG游戏与SJ定理

以上，我们研究的都是正常游戏，即游戏胜利者是博弈结束前最后一次参与行动的玩家。与之相对的是反常游戏，即游戏结束前最后一次参与的玩家是失败者。

下面介绍反尼姆博弈（Anti-Nim Game）：

一共有n堆石头，两人轮流进行游戏，玩家每个回合选择一个非空的石头堆，并从中移除任意正数的石头，拿到最后一颗石子的人失败。

结论：若每堆石头数量均为 $1$ ，则总石头数为偶数时先手必胜，为奇数时后手必胜；否则必然存在一堆石头数量大于 $1$ ，此时先手必胜。

证明：每堆石头数量均为 $1$ 的情况显然。我们考虑只有一堆石头数量大于 $1$ ，其余均为 $1$ 的情况。设这堆石头数量为 $x$ ，可以发现先手可以视情况而定拿取 $x$ 或 $x-1$ 颗石头，来控制数量为 $1$ 的石头堆数量的奇偶，所以该情况下先手必胜。容易证明此时每堆石头数量的异或和不为 $0$ 。那么如果存在多个数量大于 $1$ 的石头堆，先手可以控制石头数量，从某堆石头中拿取一些石头使得石头数量的异或和变为 $0$ 。后续证明和正常尼姆博弈类似，后手永远面临石头异或和为 $0$ 的情况，永远不可能面临存在一堆石头数量大于 $1$ 情况下的基础必胜局面，而随着游戏不断进行，先手必然可以遇到只有一堆石头数量大于 $1$ ，其余均为 $1$ 的情况，所以先手必胜。

Anti-SG游戏

推广得到Anti-SG游戏的定义：

规定决策集合为空的游戏者获胜。

其余规则与SG游戏相同。

SJ定理

和SG定理类似，将Anti-SG游戏拆分成若干独立的子游戏，规定当所有子游戏的 $SG$ 值为 $0$ 时游戏结束。

先手必胜当且仅当：

  • 总游戏的 $SG$ 值为 $0$ 且所有子游戏的 $SG$ 值小于等于 $1$
  • 总游戏的 $SG$ 值不为 $0$ 且存在某个子游戏的 $SG$ 值大于 $1$

可以看到这恰好对应了反尼姆博弈的两种情况，对比记忆即可。