前置知识

• \(\operatorname {mex}\)：没有出现过的最小自然数，如 \(\operatorname {mex} \{0,2,3\}=1\)。
• \(\oplus\)：按位异或。

前言

博弈类问题大致分为，公平组合游戏、非公平组合游戏（绝大多数的棋类游戏）、反常游戏。
只需要关注公平组合游戏 \(\texttt{(ICG)}\)，反常游戏是公平组合游戏的变形，经济类博弈也不是博客所讨论的范围

• 两个玩家轮流行动且游戏方式一致。
• 两个玩家对状况完全了解。
• 游戏一定会在有限步数内分出胜负。
• 游戏以玩家无法行动结束。

博弈的双方都被认为是神之个体，因为所有玩家对状况完全了解，且充分为自己打算，绝对理性
当局面确定，结果必然注定，并且没有任何随机的成分
游戏中的每一个状态，最终导致的结果也必然注定，只有必胜态、必败态，两种状态
这一类博弈问题的结果没有任何意外，一方可以通过努力去改变结果是不可能的，这一点是反直觉的。

• 常用对数器打表来找规律。
• 博弈论的题目就是 要干去干，去找规律，不要怕。

巴什博弈 \(\texttt{(Bash)}\)

\(n\) 个的石头，每次操作可以拿走 \([1,m]\) 个石头。拿到最后 \(1\) 个石头的人获胜（也就是不能拿石头的人输）。

这个问题特别简单，就是显然答案是如果 \(n\) 为 \(m+1\) 的倍数那么先手输，否则先手赢。

\(\texttt{sg}\) 函数

接下来引入 \(\texttt{sg}\) 函数。

\(\texttt{sg}\) 表示当前状态的胜负情况。

有如下公式 \(sg(A)=\operatorname {mex} (sg(B)|A\to B)\)。

式子中的 \(A\) 和 \(B\) 表示状态，\(A\to B\) 表示 \(A\) 状态可以达到 \(B\)状态。也就是说我们可以通过 \(A\) 能达到的状态的SG函数值推算出 \(A\) 的 \(SG\) 值。

如果 \(\texttt{sg}\) 值为 \(0\) 则表示先手输，否则先手赢。

数学归纳法证明：

1. 最终状态 \(SG=0\)。
2. 对于任意一个必胜态 \(SG\not=0\)，存在一个后继态 \(SG=0\)
3. 对于任意一个必败态 \(SG=0\)，不存在一个后继态 \(SG=0\)。

\(\texttt{e.g.}\)：在巴什博奕中：当 \(m = 2\) 时，\(\texttt{sg[0]=0,sg[1]=1,sg[2], sg[3]=0,}\cdots\)。

\(\texttt{FAQ}\):

• Q: 不就是判断一个输赢吗？为什么要用一个 \(\texttt {int}\)，我 \(\texttt{bool}\) 也可以啊。
• A: 是的，确实可以只有 \(\texttt{bool}\)，用 \(\texttt{int}\) 另有用途，我们下面会讲。

P2197 【模板】\(\texttt{(Nim)}\) 游戏——\(\texttt{sg}\) 多个独立的子问题的合并

题目描述

甲，乙两个人玩 \(\texttt{nim}\) 取石子游戏。

\(\texttt{nim}\) 游戏的规则是这样的：地上有 \(n\) 堆石子（每堆石子数量小于 \(10^4\)），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 \(n\) 堆石子的数量，他想知道是否存在先手必胜的策略。

公式引入

若局面X由若干个子游戏 \(X1,X2…Xn\) 构成，则
\(SG(x)=SG(X_1)\oplus SG(X_2) \oplus \cdots\oplus SG(X_n)\)

数学归纳法证明：

1. 最终局面成立
2. \(\forall X\)，所有后继局面可以取到 \(G(X_1)\oplus SG(X_2) \oplus \cdots\oplus SG(X_n)-1\)，取不到\(SG(X_1)\oplus SG(X_2) \oplus \cdots \oplus SG(X_n)\)

同样看做 \(\texttt{Nim}\) 游戏

设 \(S \rightarrow S_1\)

\(S \oplus (S \oplus S_1) =S_1\)
设 \((S \oplus S_1)\) 最高位为 \(k\)，存在 \(A\) 使得 \(k\) 位为 \(1\)。

那么\(A \oplus (S \oplus S_1) < A\)，所以让 \(A\) 变成\(A \oplus (S \oplus S_1)\)就行了。

问题解答

显然对于每一个子问题，对于石头个数为 \(n\)， \(\texttt {sg(n)=n}\)。

所以 \(SG=\oplus_{i=1}^{n}a_i\)。判断 \(\oplus_{i=1}^{n}a_i 是否为零即可\)

代码

#include<bits/stdc++.h>
using namespace std;
int t, n, a;
signed main(){
	scanf("%d", &t);
	while (t--) {
		scanf ("%d", &n); int ans = 0;
		while (n--) scanf("%d", &a), ans ^= a;
		if (ans == 0) puts("No"); else puts("Yes");
	}
    return 0;
}

P4279 [SHOI2008] 小约翰的游戏

题目描述

甲，乙两个人玩 取石子游戏。

游戏的规则是这样的：地上有 \(n\) 堆石子（每堆石子数量小于 \(5000\)），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就赢了。假如甲是先手，且告诉你这 \(n\) 堆石子的数量，他想知道是否存在先手必胜的策略。

这一题唯一的区别是 最后没石子可取的人就赢了。

题目解析

首先，如果 \(\forall i\) 有 \(a_i=1\)，那么就是看 \(n\) 的奇偶性了。
其次，如果只有一个 \(a_i\not=1\)，那么先手必赢 为什么
最后，因为要的是“只有一个 \(a_i\not=1\)”，异或和不为 \(0\), 所以只要抓住异或和不为 \(0\) 即可获胜，那么就转化为 \(\texttt{(Nim)}\) 游戏了。

示例代码

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t, n, x, ans, sum;
    scanf("%d", &t);
    while (t--) {
        cin >> n, ans = sum = 0;
        for(int i = 1; i <= n; ++ i) scanf("%d", &x), ans ^= x, sum += x;
        if(sum == n) puts(n & 1 ? "Brother" : "John");
        else puts(ans ? "John" : "Brother");
    }
	return 0;
}

P6487 [COCI2010-2011#4] HRPA ——斐波那契博弈

前置知识

1. 斐波拉契数列：

\[F = \{1,1,2,3,5,8,13,21,34,…..\}\\ F(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ F(n-1) + F(n-2) & \text{if } n > 1 \end{cases} \]

1. 齐肯多夫（Zeckendorf）定理：任何正整数都可以表示成若干个不连续的斐波那契数之和。如 \(4=1+3(1\) 和 \(3)\) 不相邻。

证明：

• 若正整数 \(n\) 为斐波那契数，得证。
• 否则，先取 $ F_{t_1} $，其中 $ t_1 $ 满足 $ F_{t_1} < n < F_{t_1 + 1} $。
  • 令 $ n’ = n – F_{t_1} $，同上一步取出一个 $ F_{t_2} $ 满足 $ F_{t_2} < n’ < F_{t_2 + 1} $。
  • 只要证明 $ t_1 \neq t_2 + 1 $。考虑反证法：
    • 假设 $ t_1 = t_2 + 1 $，则第一步取出的应当是 $ t_1 + 1 $ 而不是 $ t_1 $。原因是 $ F_{t_1 + 1} = F_{t_1} + F_{t_1 – 1} $。

题目分析

如果 \(t\) 为斐波拉契数，那么必须全部取完。

设 $ n = F_{i b_t} $，我们把 $ n $ 看成 $ F_{i b_{t-1}} $ 和 $ F_{i b_{t-2}} $ 两堆。

• 若第一步取的个数超过 $ F_{i b_{t-2}} $，则后手可以直接取完剩余石子。
• 否则，该问题变成了一个规模更小的同样的问题。

考虑 $ n = 2 $ 的情况（即规模最小的情况），先手只能取 1，于是后手取 1获胜。

可以结合下面理解一下

比如 \(43=34+8+1\) 那么答案为 \(1\)。
首先取走 \(1\)，然后如果对方选择的数只能选择 \([1,2]\)
假如对方取的是 \(2\)，那么 \(8=3+5\)，我选择把 \(3\) 消掉，我就选择 \(1\)。
这时数字变成了 \(34+5\)
对方又只能选择 \([1,2]\), 假如他选择 \(1\),那么 \(5=2+3\),我就把 \(2\)消掉，选择 \(1\)
这时数字变成 \(34+3\)
对方又只能选择 \([1,2]\), 假如他选择 \(2\),那么我就把 \(3\)消掉，选择 \(1\)
这时数字变成 \(34\)
对方又只能选择 \([1,2]\), 假如他选择 \(2\),那么\(34=21+8+5\)消掉，我就把 \(5\) 消掉，选择 \(3\)
这时数字变成 \(21+8\)
对方又只能选择 \([1,6]\), 假如他选择 \(6\),那么\(29=21+8\)消掉，我就把 \(8\) 消掉，选择 \(2\)
这时数字变成 \(21\)
对方又只能选择 \([1,6]\), 假如他选择 \(6\),那么\(29=21+8\)消掉，我就把 \(8\) 消掉，选择 \(2\)
这时数字变成 \(21\)
对方又只能选择 \([1,4]\), 假如他选择 \(4\),那么\(21=13+8\)消掉，我就把 \(8\) 消掉，选择 \(4\)
这时数字变成 \(13\)
对方又只能选择 \([1,8]\), 假如他选择 \(8\),那么\(13=8+5\)消掉，我就把 \(5\) 直接消掉，获得胜利。

参考资料

• 博弈类问题必备内容详解-上
• 博弈类问题必备内容详解-下
• SG 函数 & 博弈论
• OI-WiKi
• 博弈论 | 详解搞定组合博弈问题的SG函数
• [组合游戏与博弈论]【学习笔记】
• [COCI2010-2011#4] HRPA

施工进度

• 前置知识
• 前言
• \(\texttt{SG}\) 函数
• 巴什博弈\(\texttt{(Bash)}\)
• 尼姆博弈\(\texttt{(Nim)}\)
• 反尼姆博弈
• 斐波那契博弈\(\texttt{(Fibonacci)}\)
• 威佐夫博弈 \(\texttt{(Wythoff)}\)