在 2002 年张一飞写过一篇论文 《由感性认识到理性认识-透析一类博弈游戏的解答过程》 从此开启了这类博弈问题的大门,留下学习笔记。

取石子游戏

$A,B$ 两人面对若干堆石子,按照如下规则取石子

  1. 每步至少取一枚石子
  2. 每步只能在某一堆取走部分或者全部石子
  3. 谁无法按照规则取石子,谁就是输家

首先抛开问题,我们先从一般的入手。

我们可以用一个 $n$ 元组 $(a_1,a_2,\cdots,a_n)$ 表示一个局面 $S$。显然 改变 $n$ 元组的顺序仍然是一个局面。

一个局面 $n$ 元局面 $(a_1,a_2,\cdots,a_n)$ 和一个 $m$ 元局面 $(b_1,b_2,\cdots,b_m)$ 之和显然就是一个 $m + n$ 元局面 $(a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_m)$。类似的一个局面也可以有多种分解。

对于局面 $S$,若先行者有必胜策略,则称 “$S$ 胜”;
对于局面 $S$,若后行者有必胜策略,则称 “$S$ 负”。

如果局面 $S$ 胜,则必然存在取子方式 $S \to T$,且 $T$ 负;
如果局面 $S$ 负,则对任意取子方式 $S \to T$,有 $T$ 胜。

局面分解理论,若 $S = A + B$ 则下面结论显然

  1. 若 $A,B$ 一胜一负,则 $S$ 胜
  2. 若 $A,B$ 全为负,则 $S$ 负
  3. 若 $A,B$ 全为胜,则 $S$ 无法判断(还需要进一步信息才能确定)
  4. 若 $A=B$,则 $S$ 负
  5. 空局面是负局面

因此根据上面的分解理论,可以将一个局面进行化简。例如 $(2,2,2,7,9,9)$ 可以化简成 $(2,7)$

而局面分解的关系,很容易让人联想到整数的位运算-异或。

对于上面取石子问题,每一个局面都可以分解成只有一堆石子的局面。
对一个局面,定义一个函数 $f$,然后把它们异或是不是,然后判断是非为 0,作为是否胜的充要条件.这样做是否可行呢?先对原始例子进行实验。

函数 $f$:若局面 $S$ 只有一堆石子,设 $S={a}$,则定义 $f(a) = a$。
设局面 $S = (a_1,a_2,\cdots,a_n)=(a_1)+(a_2)+\cdots (a_n)$,则 $f(S) = f(a_1) \oplus f(a_2) \oplus \cdots \oplus f(a_n)$
我们断言:对于一个局面 $S$,若 $f(S) = 0$,则 $S$ 负,否则,$S$ 胜。

下面证明上面的结论。
引理:$a_1 \oplus a_2 \oplus \cdots \oplus a_n = p \neq 0$,则必存在 $1 \leq k \leq n$,使得 $a_k \oplus p < a_k$。这是因为我们看 $p$ 的最高位,有奇数个$a_k$在此位置非零, 那么与 $p$ 异或后,这一位就从 $1$ 变为 $0$,证毕。

若 $f(S) = 0$,则无论先行者如何取子 $S \to T$,都有 $f(T) \neq 0$。
若 $f(S) \neq 0$,则先行者存在一种取法 $S \to T$, 使得 $f(T) = 0$。这是因为由引理 $a_1 \oplus a_2 \oplus a_n = p \neq 0$,存在 $1 \leq k \leq n$,使得 $x = a_k \oplus p < a_k$。那么我们在第 $k$ 堆取走 $a_k - x$ 个石子,那么 $a_1 \oplus \cdots a_{k - 1} \oplus x \oplus a_{k + 1} \cdots \oplus a_n = p \oplus p = 0$,证毕。

必胜策略代码

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
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << "请输入一个正数组,以 0 结尾,输出下一步的必胜策略:" << std::endl;
std::vector<int> a;
int n;
while (std::cin >> n && n) a.emplace_back(n);
int s = 0;
for (auto x : a) s ^= x;
if (s == 0) std::cout << "必败,随便选择一个合理策略吧,等待对手失误吧" << std::endl;
else {
for (auto &x : a) if (x ^ s <= x) {
x ^= s;
break;
}
std::cout << "以下是下一步的一个必胜策略:\n";
for (auto x : a) std::cout << x << " ";
std::cout << std::endl;
}
return 0;
}

这说明了上述想法的可行性。下面把这种思想推广成一般的 SG(Sprague-Grundy)函数的情形

SG 函数

当对石子的取法进行限制时,例如每次最多能去 $m$ 个,或每次最少取 $l$ 个等,此时再令 $f(x) = x$ 就不合适了。那么应该选择怎样的 $f$ 呢。显然 $f$ 必须满足:

  1. 若 $f(S) = 0$, 则无论先行者如何取子 $S \to T$,都有 $f(T) \neq 0$
  2. 若 $f(S) \neq 0$, 则先行者存在一种取子 $S \to T$,使得 $f(T) = 0$。

我们用 $(S) = \lbrace S_1, S_2, \cdots S_k \rbrace$ 表示 $S$ 的下一个可能的局面,定义 $g(S) = \lbrace f(S_1),f(S_2), \cdots f(S_k) \rbrace$,则它必然满足 $f(S) \doteq \text{ MEX } g(S)$

注意上述 $f$ 的值域是整数,$g(S)$ 是整数集的子集。其中 $MEX(A \subseteq \mathbb{N})$ 为不在 $A$ 中最小正整数。

若最多取 $m$ 个没有其它的限制条件,可以取 $f(x) = x \mod m + 1, S = (a_1, \cdots, a_n), f(S) = f(a_1) \oplus \cdots \oplus f(a_n)$

对 SG 感性的理解为,连续最长从赢到输的步数。这样所有的例子都通了!

可以参考 300iq Contest 3E Easy Win 测试。

两人轮流取,第 $k$ 次最少取 $1$ 最多取 $k$,我在 Codeforces 上写了解答,这个可以变形。

假设有 $n$ 堆,每堆有 $x_i$, 并且限制,每次至少取 $l_i$,最多取 $r_i$. 问先手还是后手有必胜策略

经过一番思考,比较 $l_i = 1$ 的 case 可知,若 $l_i \leq x_i \mod (l_i + r_i)$,则此回合有必胜策略。否则必败,此时我们定义 $sg_i(x_i) = 0$,否则我们定义 $sg_i(x_i) = \lfloor \frac{x_i \mod (l_i + r_i)}{l_i} \rfloor$。然后最后答案就是 $s = sg_1(x_1) \oplus \cdots \oplus sg_n(x_n) \neq 0$。若 $s \neq 0$, 先手有必胜策略:先手可以让 s 变成 0,然后后手无论如何操作,先手让它们的和为 $l_i + r_i$, 然后所有的堆个数都小于超过 $l_i + r_i$ 然后再类似之前的讨论即可。因为如果第 i 堆必败,那么剔除这个堆不会影响最后胜负情况,反之必然满足 $l_i \leq x_i \mod (l_i + r_i) \leq r_i$

因为每次取至少取 $l_i$,因此本质上第 i 堆现在的个数就是 $sg_i(x_i)$,根据之前的讨论,得知最后的结论。类似地,我们也可以给出代码(这个问题可以做交互题)。

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
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << "欢迎来到石子游戏,请输入石子的堆数" << std::endl;
int n;
std::cin >> n;
std::vector<int> a(n), l(n), r(n);
std::cout << "请输入石子个数,最少取石子个数,最大取石子个数" << std::endl;
int sg = 0;
for (int i = 0; i < n; ++i) {
std::cin >> a[i] >> l[i] >> r[i];
sg ^= a[i] % (l[i] + r[i]) / l[i];
}
if (sg != 0) {
for (int i = 0; i < n; ++i) {
int t = a[i] % (l[i] + r[i]) / l[i];
if (sg ^ t <= t) {
a[i] -= t * l[i];
std::cout << "第 " << i + 1 << " 堆中取 " << l[i] * t << " 个" << std::endl;
break;
}
}
std::cout << "当前石子情况为:" << std::endl;
for (auto &x : a) std::cout << x << " ";
std::cout << std::endl;
} else {
std::cout << "当前无必胜策略,随便取一个合理的取法,等待对手失误吧" << std::endl;
}
return 0;
}

l[i]r[i] 可变时,也可以考虑,暂时不在此说了。

有向无环图上 SG 问题

在一个有向无环图中,只有一个起点,上面有一个棋子,两个玩家轮流沿着有向边推动棋子,不能走的玩家判负。

来自 OI-wiki

对于状态 $x$ 和 它的 $k$ 个后继状态 $y_1, y_2, \cdots, y_k$,定义 SG 函数:

而对于由 $n$ 个有向图游戏组成的组合游戏,设它们的起点分别为 $s_1, \cdots, s_n$,先手必胜当且仅当 $SG(s_1) \oplus \cdots \oplus SG(s_n) \neq 0$。

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
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

int SG() {
// n 个节点,0 为起点,m 条有向边,确保无环。
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int>> e(n);
for (int i = 0; i < m; ++i) {
int x, y;
std::cin >> x >> y;
e[x].emplace_back(y);
}
std::vector<int> sg(n, -1);
std::function<int(int)> dfs = [&](int u) -> int {
if (sg[u] != -1) return sg[u];
std::set<int> S;
for (auto v : e[u]) S.insert(dfs(v));
sg[u] = 0;
while (S.find(sg[u]) != S.end()) ++sg[u];
return sg[u];
};
return dfs(0);
}

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int nroot;
std::cin >> nroot;
int ans = 0;
while (nroot--) {
ans ^= SG();
}
std::cout << (ans ? "先手赢" : "后手赢") << std::endl;
return 0;
}

可以做到二维平面上有障碍点集,又可以做一个题目了。

注意到上述问题,堆与堆之间是相互独立的,如果不独立,那就很难考虑了。

不公平取石子的游戏

NewCoder 上有个不公平的游戏:A 每次能取 [1, p] 个石子,B 能取 [1, q] 个石子,A 先。

显然 $p = q$ 时,就是之前的经典问题。只需考虑 n % (p + q) 即可。若 $p > q$,那么 A 必胜,因为此时 $p >= q + 1$,所以有必胜策略,若 $p < q$,只有 A 取完则赢,否则必输。

m 堆,

  • $p > q$,若存在 $a_i$ 使得 $a_i > q$ 或 $a_1 \oplus \cdots \oplus a_m \neq 0$,则 A 必赢。
  • $p < q$,若存在大于一个 $a_i$ 使得 $a_i > p$,$A$ 必输。若所有 $a_i \leq p$ 那么就等于无限制。所以我们只需考虑,有唯一的一个 $a_i > p$ 的情形,$x = \oplus \cdots a_{i-1} \oplus a_{i + 1} \cdots \oplus a_m$,若 $x \leq p$ 且 $x + 1 \leq a_i \leq x + p$,则 $A$ 必赢。
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
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, p, q;
std::cin >> n >> p >> q;
std::vector<int> a(n);
int sg = 0;
for (auto &x : a) std::cin >> x;
if (p > q) {
for (int i = 0; i < n; ++i) if (a[i] > q) {
std::cout << "first player win" << std::endl;
return 0;
}
for (auto x : a) sg ^= x;
} else if (p == q) {
for (auto x : a) sg ^= x % (1 + p);
} else {
int cnt = 0, ai = 0;
for (auto x : a) if (x > p) {
++cnt;
ai = x;
}
if (cnt == 0) {
for (auto x : a) sg ^= x;
} else if (cnt == 1) {
for (auto x : a) sg ^= x;
sg ^= ai;
sg = (sg <= p && ai >= sg + 1 && ai <= sg + p);
} else sg = 0;
}
std::cout << (sg ? "first player win" : "second player win") << std::endl;
return 0;
}

无限制取石子问题的反问题

一堆石子谁先取到最后一个谁输!,该问题在 已经介绍了。做法:

首先剔除所有的 0,以及偶数个 1,并不会影响局面的胜负。空局面认为是胜。若此时堆的个数为 1,那么 $a_1 = 1$ 为输局面,其它为赢局面。如果堆数 $n > 1$。那么 $a_1 \oplus \cdots \oplus a_n = 0$ 为输局面,否则为赢局面。(首先对 $n = 2$ 数学归纳证明,然后对一般的 n 数学归纳证明。

有顺序堆的取石子问题

例题:1382B。即看那一步有必赢且必输的策略。

如果此题加限制条件,每次最多取 $m$ 个,那么答案就是第一个 $\mod (m + 1)$ 大于 1 的数。但是要注意 取模后为 0 的情形。

每次可取多堆

例题:1451F

更多博弈问题可见:Codeforces-game

sg 函数是因子个数 + 1

例题:codeforce gym 102911C,从 $n$ 中取 $k$ 个满足 $k > 0$ 且 $n - k$ 是 $n$ 的因子。设 $n = p_1 ^{s_1} \cdots p_r^{s_r}$, 则 $sg(n) = s_1 + \cdots s_r + 1$。

一堆,相邻之间有限制

$n$ 个元素,每次最少取 $1$,最多取 $m$ ($m \geq 2$),且相邻两个的和不能为 $m + 1$。谁无法取谁输。

结论 n % (m + 2) == 0 则先手必输,反之先手必赢。

证明:
首先不难看出若 $n \leq m + 1$ 时,先手必赢,$n = m + 2$ 时,先手必输。

  • 若第一步先手取 1,那么后手取 m - 1,此时先手不能取 2(所以先手无法取完),若第二步先手取 1,那么后手取 1回到最初的情况(那么剩下的数为 $n - m - 2$ 又满足 n % (m + 2) == 0)。若第二步先手取 3,那么后手取 $m - 1$ (此时又回到了第一步的情况,再继续考虑第二步即可)。若 第二步先手取 $x$($x \geq 4$), 后手取 $m + 4 - x$ 就回到了最初的情况。
  • 若第一步先手取了 x ($x \geq 2$) 那么后手取 $m + 2 - x$ 即可。

反之 k = n % (m + 2), $k \neq 0$,若 $k \leq m$,那么先手取 $k$ 即可。否则 $k = m + 1$, 那先手取 $m$,此时后手不能取 $1$,因此后手取完之后,剩下的数依然满足 $n \mod (m + 2) \neq 0$。