本文不是题解。

这里，先放一个我做的 PPT：link。如果有补充，放在下面。

什么是博弈论

博弈论，是经济学的一个分支，主要研究具有竞争或对抗性质的对象，在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。

通俗地讲，博弈论主要研究的是：在一个游戏中，进行游戏的多位玩家的策略。

游戏是两个及以上的参与者之间的互动行为，且他们的目标不相同。

本文只讨论公平组合游戏。

公平组合游戏

公平组合游戏的定义如下：

游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息；
任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；
游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。

例：报数游戏。从 $0$ 开始，每人在对方所报数基础上，加上范围 $[1,7]$ 的整数。谁先报到 $40$ 谁赢。

策梅洛定理

在二人参与的游戏/博弈中，如果满足：

游戏的步骤数有限；
信息完备（二人都了解游戏规则，了解游戏曾经所发生过的信息）；
不会产生平局；
确定性（游戏中不会加入随机因素）。

则先行一方有必胜策略，或者后行一方有必胜策略。

Nim 游戏

$N$ 堆物品，每堆有 $a_i$ 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。取走最后一个物品的人获胜。

Nim 游戏属于公平组合游戏。

博弈图和状态

在公平组合游戏中，可以对所有有可能出现的状态看作是图的节点，如果从一个状态可以通过一步转移到达另一个状态，则在两点之间连一条有向边，这样就得到了一个状态图。

如果不会出现平局，则为 DAG，所有状态可分为两种，P 态（对于先手必胜）和 N 态（对于后手必胜）。

如果当前状态下游戏不能继续进行，则这个状态被称为终止态。

例如，如果节点 $(i,j,k)$ 表示局面为 $(i,j,k)$ 时的状态，则我们可以画出下面的博弈图（仅显示部分节点和边）。

通过推理，我们可以得出下面三条定理：

定理 1：没有后继状态的状态是 N 态。
定理 2：一个状态是 P 态当且仅当存在至少一个 N 态为它的后继状态。
定理 3：一个状态是 N 态当且仅当它的所有后继状态均为 P 态。

如果博弈图是一个有向无环图，则通过这三个定理，我们可以在绘出博弈图的情况下用 $O(N+M)$ 的时间（其中 $N$ 为状态种数， $M$ 为边数）得出每个状态是 P 态还是 N 态。

Mex 运算

设 $S$ 表示一个非负整数集合。定义 $\operatorname{mex}(S)$ 为求出不属于集合 $S$ 的最小非负整数的运算。

\operatorname{mex}(S)=min \{ x \mid x \in N,x \notin S \}

SG 函数

对于任意状态 $x$ ，它的 SG 函数值为：

\operatorname{sg}(x)=\operatorname{mex} \{ \operatorname{sg}(y) \mid \text{y 是 x 的后续状态} \}

如果知道一个状态的 SG 函数值，则可以快速地判断该状态是 P 态（值为 $0$ ）还是 N 态（值不为 $0$ ）。

Nim 和

让我们再次回顾 Nim 游戏。

如果之间计算状态的 SG 函数的话，由于后继数量太多，算法效率比较低。有没有什么巧妙而快速的方法呢？

定义 $Nim$ 和为所有 $a_i$ 的异或和。当且仅当 Nim 和为 $0$ 时，该状态为必败状态；否则该状态为必胜状态。

证明见题解：P2197 【模板】nim 游戏。

SG 定理

定理：游戏和的 SG 值为所有子游戏 SG 值的 Nim 和。

SG 定理是解决一类组合游戏的有力工具。

结语

限于作者时间和水平上的不足，仅仅介绍了博弈论问题的冰山一角——公平组合游戏。

引用资料

OI Wiki
信息学奥赛一本通-提高篇
zzy 大佬

例题

P3150 pb的游戏（1）
P4136 谁能赢呢？
P1290 欧几里德的游戏
P2197 【模板】nim 游戏
P4576 [CQOI2013]棋盘游戏

本文作者：Yurchiu

本文链接：https://yz-hs.github.io/1b12e9984a40/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

博弈论 OI

最后更新：2023-08-21, 23:18:21

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158