NOI 一轮复习：组合博弈论

博弈论主要研究一些有竞争或对抗性质的对象，在一定规则下/产生的各种行为。

接下来讨论的所有问题，若没有写出，均默认为两人轮流行动的、完美信息、无随机因素。

通常来讲，无法行动的人会输掉，称为正常博弈，而无法行动却获胜称为反常博弈。

公平组合博弈

我们从 Nim 游戏开始研究。有 $n$ 堆石子，每人每次可从任意一堆石子里取出正整数枚石子扔掉，谁不能动谁就输了。

我们将每个状态视作一个节点，那么博弈情况就可以刻画成一张有向图。不难发现，异或和为 $0$ 时先手必败。

大部分的公平组合游戏都可以转换为有向图游戏，对于状态 $x$ 和它的 $k$ 个后继状态 $y_1,\cdots,y_k$ ，定义 SG 函数为：

$\operatorname{SG}(x)=\operatorname{mex}\{\operatorname{SG}(y_1), \operatorname{SG}(y_2), \ldots, \operatorname{SG}(y_k)\}$

对于由 $n$ 个有向图游戏组成的组合游戏，当且仅当 $\oplus \operatorname{SG}(s)\ne 0$ 的时候，先手必胜，称之为 P 态（previous player）。也就是说， $\operatorname{SG}(x)=0$ 是必败态，称之为 N 态。

SG 定理：一个游戏的 SG 值是其所有子游戏的 SG 值的异或和，这可以说明 Nim 游戏结论的由来。

针对树形结构的博弈，我们假定一次操作可以删除一条边，然后保留根节点所在的子树。不能操作者输掉。

首先对于一条长度为 $x$ 的链，其 SG 值为 $x-1$ 。一棵树可以分解成若干个子问题，每个子问题都是根节点的一棵子树加上根节点本身。

如果一棵子树的 SG 值为 $x$ ，那么其可以等效为一个长度为 $x+1$ 的链。也就是说，新搞一个点连到树根上，这棵树的 SG 值会加 $1$ 。

因此不难计算。模板，代码。