1 定义

1.1 公平组合游戏

• 游戏由两名玩家交替行动
• 可执行的行动与当前局面有关，与轮到哪名玩家无关
• 同一局面不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定在有限步后以非平局结束

1.2 非公平组合游戏

与公平组合游戏的区别在于不符合第二点，也就是说可达到的状态与当前玩家有关。

1.3 反常游戏

其胜者为第一个无法执行操作的人。

2 博弈图

把一个游戏局面看成一个点，把可以执行的行动看作边，于是就得到了博弈图，公平组合游戏的博弈图一定是有向无环图。

定义一个点为先手必胜，就是说当前局面下有先手必胜策略；同理，先手必败表示当前局面下先手不管怎么行动，后手都有策略使得先手必败。

首先没有后继节点的状态一定是先手必败。

先手必胜一定至少存在一个先手必败的后继状态，先手必败的所有后继节点一定是先手必胜。

由此，我们可以判断所有状态是先手必胜还是先手必败。

3 简单博弈问题

3.1 常规套路

简单博弈问题的常规套路是猜一个必胜态和必败态的判断方法，然后证明：

• 不能操作时为必败态；
• 由必胜态一定存在方案到必败态；
• 由必败态不管怎样都只能到必胜态。

3.2 Nim Game

给定 $N$ 堆石子，第 $i$ 堆有 $a_i$ 个石子。

两名玩家轮流行动，每次在一堆石子中取若干个，不能不取，最后不能取的人输。

首先一个方法是枚举所有状态判断，复杂度高达 $O(\prod_{i=1}^n a_i)$，不可行。

设所有状态中满足 $\oplus_{i=1}^n a_i = 0$ 的称为必败态，否则称为必胜态。

不能再取的状态一定是必败态。

在必败状态时，不管怎么走，一定会使得 $\oplus_{i=1}^n a_i \ne 0$，得到必胜态。

在必胜状态时，设 $\oplus_{i=1}^n a_i$ 二进制下最高位为 $j$，找到第 $j$ 位为 $1$ 的一堆石子 $k$，

把这对石子从 $a_k$ 取到 $\oplus_{i=1 \wedge i \ne k}^n a_i$ ，可以证明 $\oplus_{i=1 \wedge i \ne k}^n a_i < a_k$，取完后满足 $\oplus_{i=1}^n a_i = 0$。

于是我们证明了结论：所有状态中满足$\oplus_{i=1}^n a_i = 0$ 的称为必败态，否则称为必胜态

4 SG 函数

4.1 SG 函数的定义

对于博弈图 $G = (V,E)$ 上一点 $u$，有 $SG(u) = mex_{(u,v)\in E}\{SG(v)\}$。

其中 $mex$ 表示一个自然数集合中最小的不出现的自然数。

4.2 SG 函数的性质

性质1: 当一个点的 $SG$ 函数值为 $0$，这个点为先手必败点。

证明：当一个点的后继节点中有必败点时，根据定义这个点为必胜点，$SG$ 函数也因为这个后继节点 $SG$ 值为 $0$ 而不可能为 $0$；

当一个点后继节点中没有必败点时，这个点为必胜点，$SG$ 函数也等于 $0$，故得证。

性质2：当有多个博弈在同时进行且互相之间互不干扰，总的 $SG$ 值等于这些博弈的 $SG$ 值的异或和。
其中同时进行指的是双方每一步选择一个博弈移动一步，不能移动的一方输。

证明：咕。

一般直接求 $SG$ 函数一定会超时，所以需要用一些特殊结论优化这个过程。