什么是博弈论#

博弈论，即组合博弈，指一种游戏，这种游戏一般有以下性质：

1. 两人游戏，且轮流行动
2. 对等、完全 双方得知信息对等，双方可以进行的行动完全相同．
3. 确定性 游戏没有随机性的变量（如骰子、随机数等）
4. 无平局
5. 有限性 游戏无法无限继续，最终在一定时间内一定有一名玩家胜利，一名玩家失败．

相关定义#

• 博弈论：研究绝对理性决策者之间战略互动的数学模型．
• $\color{green}{\mathcal{N}}$ 必胜态（Next player wins）：至少存在一种可能使得对方处于 $\color{red}{\mathcal{P}}$ 的一种游戏状态被称为必胜态．
• $\color{red}{\mathcal{P}}$ 必败态（Previous player wins）：存在任意一种方法让对方处于 $\color{green}{\mathcal{N}}$ 的一种游戏状态被称为必败态．
• 终局：处于终局时，有且仅有一名玩家获得立即胜利． 如 FPS 游戏中，仅剩 1 名玩家存活就是一个终局．

解决博弈论的一般步骤#

1. 明确终局
2. 进行倒推
3. 寻找规律
4. 进行数学证明（可以省略）

典例：#

巴什博弈#

考虑总共有 $n$ 个物品，两名玩家，每次玩家必须至少取 $1$ 个，最多取 $m$ 个．最后一个物品十分值钱，取到最后一个物品的玩家获胜．

首先，检查这是不是博弈论：

所以下定结论，这是博弈论．

明确终局

很显然，终局是场上只剩下一个物品时，此时先手玩家 $\color{green}{\mathcal{N}}$．

进行倒推

我们尝试推演当 $m=2$ 时的情景，其中，红色节点表示先手玩家 $\color{red}{\mathcal{P}}$，绿色节点代表先手玩家 $\color{green}{\mathcal{N}}$．

先选定一个起始节点，起始节点不宜太大，太大则会难于分析，需要选取适中的起始节点．在这里，选择起始节点 $n=7$．

尝试分析起始节点的胜负性．

首先，列举其所有可能的游戏发展子状态．例：$n=7$ 的子状态是 $n=6$（拿一个） 和 $n=5$（拿两个）

flowchart LR
7(n=7)--"-1"-->6(n=6)
7--"-2"-->5(n=5)

classDef N fill:#67C23A
classDef P fill:#F56C6C

再列举起始节点所有可能的 游戏发展子状态（这里指 $n\in \{5,6\}$）的游戏发展子状态，一直下去，知道抵达终局（这里指 $n=1$）．

列举完之后如下图：

flowchart LR
7(n=7)--"-1"-->6(n=6)
6--"-1"-->5(n=5)
7--"-2"-->5
6--"-2"-->4(n=4)
5--"-1"-->4
4--"-1"-->3(n=3)
5--"-2"-->3
4--"-2"-->2(n=2)
3--"-1"-->2
2--"-1"-->1(n=1)
3--"-2"-->1

classDef N fill:#67C23A
classDef P fill:#F56C6C

最后，给每一个节点染色．若处于当前状态时先手玩家 $\color{red}{\mathcal{P}}$ 则将其染成红色，先手玩家 $\color{green}{\mathcal{N}}$ 则将其染成绿色．

染色规则如下：

• 终局节点根据游戏规则染色（此题中为 $\color{green}{\mathcal{N}}$）
• 若一个节点其所有子节点全为 $\color{green}{\mathcal{N}}$，则该节点为 $\color{red}{\mathcal{P}}$，否则该节点为 $\color{green}{\mathcal{N}}$．

染色完如下：

flowchart LR
7(n=7):::N--"-1"-->6(n=6):::P
6--"-1"-->5(n=5):::N
7--"-2"-->5
6--"-2"-->4(n=4):::N
5--"-1"-->4
4--"-1"-->3(n=3):::P
5--"-2"-->3
4--"-2"-->2(n=2):::N
3--"-1"-->2
2--"-1"-->1(n=1):::N
3--"-2"-->1

classDef N fill:#67C23A
classDef P fill:#F56C6C

列下表：

不难发现，当 $m=2$ 时，对于所有的 $n$，当且仅当 $3 \mid n$（$n$ 被 3 整除）时先手是 $\color{red}{\mathcal{P}}$ 的，此外，先手都是 $\color{green}{\mathcal{N}}$ 的．

数学证明

设整数 $k$ 满足 $k= n \bmod 3$，当 $k \in \{1,2\}$ 时，只需要拿取 $k$ 个，就可以转换为 $k=0$ 的情况，从而先手玩家 $\color{red}{\mathcal{P}}$．当 $k=0$ 时，无论拿 1 个还是 2 个，都会转化为 $k \in \{1,2\}$ 的形式，从而先手玩家必败．

推广到 $m \neq 2$ 的情况：当 $(m+1) \mid n$ 时，先手是 $\color{red}{\mathcal{P}}$ 的，此外的所有情况，先手都是 $\color{green}{\mathcal{N}}$ 的．

Nim 游戏#

显然，这是博弈论．

终局条件是场上没有物品时，此时先手玩家 $\color{red}{\mathcal{P}}$．

进行倒推

当 $n=1$ 时，先手玩家只要把这一堆石子取走就可以．故此时，先手玩家 $\color{green}{\mathcal{N}}$．

当 $n=2$ 时，为了方便表示，将 x_y 表示为第一堆剩下 x 个，第二堆剩下 y 个的情况．$x\geq y$

显然，当有一堆时 0 时，先手玩家可以直接拿走那一堆，故此时，先手玩家 $\color{green}{\mathcal{N}}$．

选取 3,2 为初始节点，列表：

flowchart TD
    classDef N fill:#67C23A
    classDef P fill:#F56C6C

    %% 节点声明（顺序也会影响布局）
    0_0:::P
    1_0:::N
    1_1:::P
    2_0:::N
    2_1:::N
    2_2:::P
    3_0:::N
    3_1:::N
    3_2:::N

    %% 从小局势开始连接，逐步到大局势
    %% (1,1) 出发
    1_1--"-1"-->1_0

    %% (2,1) 出发
    2_1--"-1"-->1_1
    2_1--"-2"-->1_0
    2_1--"-1"-->2_0

    %% (2,2) 出发
    2_2--"-1"-->2_1
    2_2--"-2"-->2_0

    %% (3,1) 出发
    3_1--"-1"-->2_1
    3_1--"-1"-->3_0
    3_1--"-2"-->1_1
    3_1--"-3"-->1_0

    %% (3,2) 出发
    3_2--"-1"-->2_2
    3_2--"-1"-->3_1
    3_2--"-2"-->2_1
    3_2--"-2"-->3_0
    3_2--"-3"-->2_0

好像当且仅当 $x=y$ 时为 $\color{red}{\mathcal{P}}$，其他时候都是 $\color{green}{\mathcal{N}}$．

证明也很简单，所有非 $x=y$ 的状态都可以一步转化为 $x=y$ 这个 $\color{red}{\mathcal{P}}$ 的状态．

那么，如何推广呢？

Nim 和#

定义一组数 $a_1,a_2,a_3,\cdots, a_n$ 的 Nim 和为 $a_1\oplus a_2\oplus\cdots\oplus a_n$

那么，当一个状态满足其 Nim 和为 0 是，当前状态为 $\color{red}{\mathcal{P}}$．

由以上证明可以推导出博弈论证明的基本方法：

1. 明确一个必输终局有的性质，记之为 $R$.
2. 对于 $R$，如果所有操作都能破环性质 $R$，且所有不符合性质 $R$ 的局面都至少有 1 种操作能使局面具有 $R$ 性质．那么 $R$ 就是所有必输局面的共同性质．

阶梯 Nim#

在问题中，处于偶数堆的石子可以视为不存在，因为当先手将偶数堆的石子向下移移到奇数堆，后手可以再将这些石子再向下又移到偶数堆．直到从第 1 堆拿走．

因此，影响战局的只会是奇数堆．再次观察，每一次移动奇数堆的石子，都会使其移动到偶数堆上，又因为偶数堆上的石子可以视为没有，所以，每一次移动奇数堆上棋子到偶数堆，等同于将这些石子移出游戏．这样，阶梯 Nim 游戏就相当于以每一个奇数堆为一个有效堆的 Nim 游戏．

SG 函数#

定义一个局面 $x$ 的 SG 值 为 $sg(x)$，则有

，其中，$a_i\rightarrow x$ 的意思是能从局面 $a_i$ 通过一次合法的操作转换为 $x$．

因此，不难得出，当 $sg(x) = 0$，则局面 $x$ 先手必败，否则先手必胜．

举个例子，就拿巴氏博弈（$m=2$）来说，可列下表：

对于多个相对独立的游戏同时进行（例如：考虑总共 $n$ 堆物品，每堆有 $a_i$ 个物品，两名玩家，每次玩家必须至少取 $1$ 个，最多取 $m$ 个，且不能跨堆取．最终，无法操作的玩家落败．这是多个巴士博弈的游戏同时进行．），则总游戏的 SG 值与其分游戏的 SG 值有如下关系：

Nim 游戏就是一个典型的多个相对独立的游戏同时进行的游戏，以下是每个独立游戏，即为单堆石子可列表格：

因此，对于一个具有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个的 Nim 游戏，整体游戏的 SG 值如下：

不难发现，Nim 游戏的 SG 值就等于其 Nim 和，则从侧面证明了 Nim 游戏策略的正确性．

解决博弈论问题的一般策略#

了解了 SG 函数，接下来就可以总结博弈论问题的一般策略．

1. 理解题意，提炼出博弈论模型．
2. 根据规则，手推或者计算机打表求出一些小数据的 SG 值．
3. 寻找规律．
4. 根据规律编程解决问题．

博弈论模型不难提炼．根据规则，可以写出如下的打表程序：

#include <bits/stdc++.h>
using namespace std;

int n, sg[10000];
vector<int> prime;

int cal_sg(int n) {
	if (n == 0) return 0;
	if (sg[n] != -1) return sg[n];
	set<int> s;
	s.insert(cal_sg(n - 1));
	for (auto pr : prime) {
		int now = pr;
		while (now <= n) {
			s.insert(cal_sg(n - now));
			now *= pr;
		}
	}
	for (int i = 0; ; i++) {
		if (s.find(i) == s.end()) {
			sg[n] = i;
			return i;
		}
	}
}

int main() {
	memset(sg, -1, sizeof(sg));
	// 预处理质数
	for (int i = 2; i <= 100000; i++) {
		bool is_prime = true;
		for (int j = 2; j <= sqrt(i); j++) {
			if (i % j == 0)
				is_prime = false;
		}
		if (is_prime) {
			prime.push_back(i);
		}
	}

	for (int i = 1; i <= 100; i++) {
		if (cal_sg(i) == 0)
			cout << i << " " << cal_sg(i) << " ";
	}
	return 0;
}

在这里，由于只有 1 个独立游戏，因此，我们只关心 SG 值是否为 0．在这里，我打印出了所有 SG 值为 0 的情况．

输出如下：

6 12 18 24 30 36 42 48 54 60 66 72 78 84 90 96

不难发现，某一局面的 SG 值为 0 当且仅当 $n$ 是 6 的倍数．

因此，可以编写程序：

#include <bits/stdc++.h>
using namespace std;

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		if (n % 6 == 0)
			cout << "Roy wins!" << endl;
		else
			cout << "October wins!" << endl;
	}
	return 0;
}