笔记汇总

公平组合游戏是在中水平竞赛中最常考的模型，

其特点是任意一种状态都不能重复到达。

所以，我们可以因此建立一个 $DAG$，

其中点为局面，边为决策，且每个点要么必胜要么必败。

从而得到三条定理：

• 没有后继状态的状态是必败状态。
• 一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。
• 一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。

我们可以枚举所有状态求得答案。

但这样求出答案的效率较为低下，

如果能像分治那样将它拆分成很多小的游戏并组合就好了。

这样可以省掉状态图上面的关联部分。

而组合的方法就叫 $SG$ 定理：

当且仅当 Nim 和为 $0$ 时，该状态为必败状态；否则该状态为必胜状态。

注意，这是因为状态为 $0$ 时是必败（基础），

Nim 和为 $0$ 是所有状态为 $0$ 的必要不充分条件，因为答案最终有解，则充分性证明如下，

如果 Nim 和不为 $0$，

由于 Nim 和实质是异或，不存在状态外的更高位，

我们是用小游戏的 $SG$ 函数建立的异或，所以必定可以找到决策令后手 Nim 和为 $0$（$SG$ 函数定义）

如果 Nim 和为 $0$，

由于状态必然改变，则其决策另后手的 Nim 和必然不为 $0$，

充分性证毕。

注意，上面我们引入了 $SG$ 函数，

这是一个可以充分表示上面决策图关系的函数。

虽然状态彼此不同，但 $SG$ 函数仅需要表示胜负关系就够了（所以并不一定不同），

不过，同一个 $SG$ 函数（相同值的函数直接等价化简），绝不能通过转移重复到达。

所以不能向 $SG$ 函数比它大的点转移。（不然不满足状态彼此不同的定义）

如果没法转移，则其值为 $0$。

对于多信息的关系我们可以建立多元$SG$函数。