竞赛博弈论的判断框架 • FXJ Wiki

收录内容#

博弈论原笔记
做题时的判断入口
几种最常见模型的结论和记法

先说我现在的判断顺序#

博弈论题最容易让人慌，是因为题面很花。但大多数竞赛题真正常用的入口其实就几个：

先判断是不是公平组合游戏：双方能做的操作是否完全对称？状态会不会重复？是不是谁不能动谁输？如果这些条件都满足，才值得往 Nim / SG 那条线走。
再看能不能直接归到经典模型：Bash、Nim、反常 Nim、威佐夫、斐波那契博弈这些都有现成结论，能直接识别就不要硬推一遍。
如果是多个独立子游戏，就往 SG 定理靠：把整体拆成若干互不影响的部分，最后常常就是异或。
如果结论不明显，就打表看规律：很多 SG 题最后都不是纯模板，而是先小范围算值，再观察是否有周期或简单表达。

博弈论原始整理#

教程：

资料：

概念#

公平组合游戏#

游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息；

任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；

游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。

非公平组合游戏#

非公平组合游戏（Partizan Game）与公平组合游戏的区别在于：在非公平组合游戏中，游戏者在某一确定状态可以做出的决策集合与游戏者有关。大部分棋类游戏都不是公平组合游戏，如国际象棋、中国象棋、围棋、五子棋等（因为双方都不能使用对方的棋子）。

反常游戏#

反常游戏（Misere Game）按照传统的游戏规则进行游戏，但是其胜者为第一个无法行动的玩家。以 Nim 游戏为例，普通 Nim 是取走最后一颗石子者获胜，而反常 Nim 中取走最后一颗石子者反而失败。

为什么一定要先判断是不是公平组合游戏？

因为后面的 Nim 和 SG 定理，都默认在一个非常标准的环境里成立：

双方可选操作完全对称；
游戏不会无限循环；
局面信息完全公开；
无法行动的一方输。

如果题目本身不满足这些条件，比如双方能做的动作不一样、或者有平局、或者状态会反复来回，那就别直接往 SG 套。

巴什博弈（Bash Game）#

一共 $n$ 颗石子，两个人轮流拿，每次可以拿 $1$ 到 $m$ 颗，没有石子可以拿的一方失败。

练习：P4018 Roy&October 之取石子 ↗

这个模型最核心的结论就是：

若 $n \bmod (m+1)=0$ ，则先手必败；
否则先手必胜。

原因也很直接：

后手总能把两个人这一轮拿走的总数凑成 $m+1$ ；
这样局面会稳定地回到 $m+1$ 的倍数上。

所以这类题通常只是在原始模型外面包一点叙事，真正识别出“每次取 $1\sim m$ 个”的壳就够了。

尼姆博弈（Nim Game）#

$n$ 堆物品，每堆有 $a_i$ 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。

取走最后一个物品的人获胜。

定义 Nim 和：

a_1 \oplus a_2 \oplus a_3 \oplus \dots \oplus a_n

若 Nim 和为 $0$ ，则后手 win；不为 $0$ ，则先手 win。

即 Nim 和 $\ne 0$ 为必胜态，Nim 和 $=0$ 为必败态。

$0 \to \ne 0$ ：一旦拿走了石子，则在二进制某些位上的奇偶性一定会发生变化；

$\ne 0 \to 0$ ：总能找到一种取法，把最高位的那一位抹平，从而把局面变回异或和为 $0$ 。

模板题：P2197 【模板】Nim 游戏 ↗

我对 Nim 的记法#

别把它只背成“异或和不为零先手赢”。更好记的方式是：

异或和为 $0$ 的局面，是一种平衡态；
你一旦动了它，这种平衡一定会被打破；
只要当前不是平衡态，先手总能通过操作把它重新拉回平衡态。

所以做题时，真正要找的是：题目能不能化成若干堆、每步只改变一堆、最后拼成“整体异或”的模型。

反常游戏#

谁先拿走最后的物品，谁输。其他与 Nim 相同。

若所有数都为 $1$ ，则根据奇偶性获胜；否则仍按 Nim 和判断：Nim 和 $\ne 0$ 则先手 win，Nim 和 $=0$ 则后手 win。

这块最容易错的点就在于：

不要把普通 Nim 的结论原封不动搬过来；
真正需要特判的是“所有堆都只剩 1”的那种末态附近。

斐波那契博弈（Fibonacci Game + Zeckendorf 定理）#

P6487 [COCI2010-2011#4] HRPA ↗

有 $n$ 枚石子。两位玩家定了如下规则进行游戏：保证 $2 \le n \le 10^{15}$ 。

Mirko 先取一次，Slavko 再取一次，然后 Mirko 再取一次，两人轮流取石子，以此类推；
Mirko 在第一次取石子时可以取走任意多个；
接下来，每次至少要取走一个石子，最多取走上一次取的数量的 $2$ 倍；
取走最后一块石子的玩家获胜。

双方都以最优策略取石子。Mirko 想知道，自己第一次至少要取走几颗石子最终才能获胜。

Zeckendorf（齐肯多夫）定理：任意一个非斐波那契数一定能被拆分为若干个不相邻的斐波那契数。

若 $n$ 为斐波那契数，则先手必败，必须直接取走全部。

若 $n$ 不是斐波那契数，则答案是 Zeckendorf 表示法中最小的那一项。

斐波那契博弈

ll fi[85];
void solve() {
    int n;cin >> n;
    fi[1] = 1;fi[2] = 1;
    for (int i = 3;i <= 80;i++)fi[i] = fi[i - 1] + fi[i - 2];
    while (n) {
        auto x = upper_bound(fi, fi + 80, n);
        if (*--x == n) {
            cout << n << '\n';return;
        }
        n -= *x;
    }
}

cpp

这里最该记住的不是证明细节，而是：

这题的必败态恰好落在斐波那契数上；
非斐波那契数则可以借助 Zeckendorf 表示法找到第一次该拿多少。

威佐夫博弈（Wythoff Game）#

P2252 [SHOI2002] 取石子游戏 / 威佐夫博弈 ↗

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。

每次有两种取法：

可以在任意一堆中取走任意多的石子；
可以在两堆中同时取走相同数量的石子。

最后把石子全部取完者为胜者。现在给出初始两堆石子的数目，问先手是胜者还是败者。

结论：设两堆石子为 $(a,b)$ 且 $a \le b$ ，若
$a = \lfloor (b-a)\varphi \rfloor$
其中 $\varphi = \frac{1+\sqrt 5}{2}$ 为黄金分割比，则先手必败；否则先手必胜。

原笔记里记成“小 != (大-小) × 黄金分割比例 则先手赢”，做题时其实就是在判断当前局面是否落在这条冷位序列上。

SG 函数#

SG 函数（Sprague-Grundy 函数），如下是 SG 返回值的求解方式，俗称 mex 过程。

最终必败点是 $A$ ，规定 $SG(A)=0$ ；
假设状态点是 $B$ ，那么 $SG(B)$ 等于“查看 $B$ 所有后继节点的 SG 值，其中没有出现过的最小自然数”；
$SG(B) \ne 0$ ，则状态 $B$ 为必胜态； $SG(B)=0$ ，则状态 $B$ 为必败态。

SG 定理#

如果一个 ICG 游戏（总）由若干个独立的 ICG 子游戏构成（分 1、分 2、分 3…），那么：

SG_{\text{total}} = SG_1 \oplus SG_2 \oplus SG_3 \oplus \cdots

任何 ICG 游戏都是如此，正确性证明和 Nim 博弈的异或思想是同一路子。

什么时候该想到 SG#

题目不是标准 Nim；
但每个局面能走到若干下一局面；
多个子局面彼此独立；
你只需要判断先手 / 后手胜负，而不一定要求具体方案。

这时就很适合：

先定义状态；
枚举每个状态能转移到哪些后继状态；
用 mex 算 SG；
多个子游戏最后异或起来。

做 SG 题时我最常提醒自己的几件事

SG = 0 是必败态，SG != 0 才是必胜态。
先别急着把图画很大，很多题其实可以先打小表看规律。
如果题目里有多个独立部分，别分别判输赢，最后要异或。
一旦题目不满足公平组合游戏条件，就不要机械套 SG。

最后怎么记这篇#

如果只让我留一句话，我会留这个判断链：

能直接识别成经典模型，就优先识别；
不能识别，但状态独立、规则对称，就往 SG 走；
SG 做不出来时，先打表看规律；
整个过程的目标，不是背公式，而是尽快分清这题到底属于哪一类游戏。