参考目录：

zhuanlan.zhihu.com/p/422562139

一、公平组合游戏

ICG(Impartial Combinatorial Games)游戏。

1、定义

同时满足以下条件的游戏，叫ICG
 由两名玩家交替行动；
 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
 不能行动的玩家判负；
 两个玩家必须有有限数量的操作和状态。
 游戏中的任何动作都不能依赖于随机因素。
易知，象棋、五子棋、tiktok都不属于ICG，而是Partisan game，五子棋（一方只能下黑子、另一方只能下白子）。骰子、桥牌也不是ICG，因为引入了随机因素。

2、有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
任何一个ICG都可以抽象成一个有向图游戏。具体方法是，把每个状态看成图中的一个节点，合法动作代表图中的有向边。

3、SG(Sprague-Grundy)定理

Sprague-Grundy定理指出，所有的ICG都等价于nim游戏的单堆博弈，或nim游戏的无限泛化。

4、Zermelo’s定理

策梅洛定理表示在二人的有限游戏中，如果双方皆拥有完全信息，并且游戏不含随机因素，那先行或后行者当一必有一方有必胜/必不败的策略。
定理具体表述如下：
 没有平局，每个游戏局面要么是必胜态N-position，要么是必败态P-position；
 一个状态是必败态，当且仅当它的所有后继状态都是必胜态；
 一个状态是必胜态，当且仅当它的后继状态存在一个必败态。
策梅洛定理适用于ICG和Partisan game。

5、必胜态和必败态

通过定义可知，必败态和必胜态。
[1] 所有的状态空间构成全集，必胜态不一定是必败态的补集，由必败态能够转移到的状态空间，构成必胜态。
[2] 每一轮包括两次出手机会，先手和后手。
[3]
引理1：
必败态的前驱一定是必胜态。
引理2：
必败态的后继一定是必胜态。
引理3：
某个(属性)状态，通过两次操作（不论先手如何操作），总是可以 进入必败态 或者 恢复原状态。
那么该状态是必败态，一次操作后的状态是必胜态。（等价于同时证明了必败态必然转化为必胜态，必胜态总是可以转化为必败态）
引理4：
如果某个(属性)状态经过偶数次操作后（不论先手如何操作），总是可以转入必败态，则该状态是必败态。
引理5：
如果某个(属性)状态经过奇数次操作后（不论先手如何操作），总是可以转入必胜态，则该状态是必败态。
[4]
对于这五个引理的应用，参考bzoj1413/acwing1322

6、MEX运算

MEX函数，代表不在集合中的最小自然数。

设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即mex(S) = min({x | x属于自然数，x不属于S})

7、SG函数

在有向图游戏中，对于每个节点x，从x出发共有k条有向边，分别到达y1、y2、…、yk，定义SG(x)为x的后继节点y1、y2、…、yk的SG函数值构成的集合，再执行mex函数运算后的结果，即

SG(x) = MEX({SG(y1), SG(y2),…,SG(yk)})

特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G)=SG(s)。

8、状态组合与SG函数

[1]二维状态组合
两个必败态游戏组合成的游戏是必败态。因为先手必然会把游戏变成必胜态和必败态的组合给后手，后手可以通过聪明的操作把其中的必胜态变成必败态给先手，这样先手拿到的一直是两个必败态，先手输。（必败态，必败态） -> 必败态
必败态和必胜态的组合成的游戏是必胜态。先手可以通过聪明的操作把必胜态变成必败态给对手，这样对手就会作为两个必败态组合的游戏的先手，根据上一条结论，我们知道对手必败，也就是先手必胜。（必败态，必胜态） -> 必胜态
两个必胜态组合生成的游戏可能是必胜态，也可能是必败态。首先先手肯定不能把其中一个必胜态变成必败态，因为这样会给后手一个（必败态，必胜态）的局势，这样后手拿到必胜态，后手必胜，所以只能把其中一个必胜态再变成另外一种必胜态。

[2] n维状态组合
设G1、G2、…、Gm是m个有向图游戏。定义有向图游戏G，它的行动规则是任选某个有向图游戏Gi，并在Gi上行动一步。G被称为有向图游戏G1、G2、…、Gm的组合游戏。

有向图游戏的和的SG函数值等于它所包含的各个子游戏SG函数值的异或和，即

SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)
[3]
有向图游戏的某个局面是必胜态，当且仅当该局面对应节点的SG函数值大于0。

有向图游戏的某个局面是必败态，当且仅当该局面对应节点的SG函数值等于0。

二、做法

1、常规做法
枚举几个状态，找规律。发现必胜态和必败态。
证明必败态必然转化为必胜态、必胜态总是可以转化为必败态。
通过规则或sg函数进行判断。

有时需要分类讨论，因为不同条件下，必败态可能是不同的。
还需要注意临界状态。
2、dfs
由策梅洛定理或SG定理可知ICG必然存在必败态、必胜态。
所以可以通过记忆化搜索+dfs进行有向图游戏的遍历。比如bzoj3895/acwing1321
3、DP
有向图游戏的遍历，也可以通过DP来进行。比如bzoj1413/acwing1322

三、nim-like

1、nim游戏
一堆石子，每人可从任意一堆拿任意多个（至少一个）石子。
2、数量受限
[1]
一堆石子，每人可从任意一堆拿至少1个、最多n个的石子。
[2] 集合nim
操作集合N = {2, 3, 8}
一堆石子，每人可从任意一堆拿n∈N个石子
3、顺序受限
[1] cf1832B sequence nim
一堆石子，只能从最左边的堆拿，至少拿一个
规律：谁先遇到非1的堆，谁必赢。
[2] bzoj1413/acwing1322
一堆石子，只能从两边的堆拿，至少拿一个
4、威佐夫博弈
一堆石子，每人可从任意一堆拿任意多个（至少一个）石子 或者 从任意两堆拿相同数量（任意数量但至少一个）的石子。
5、巴什博弈
6、拆分nim
7、bzoj3895 合并nim
8、anti SG
9、multi SG
10、every SG