博弈论练习笔记
一、前置知识
有向图游戏的必胜必败局面的判定引理：
- 终局是必败局面。
- 有向图游戏的某个局面必胜，当且仅当它的后继局面中存在必败局面。
- 有向图游戏的除终局外某个局面必败，当且仅当它的任意后继局面都是必胜局面。
对于有向图游戏的题，满足上述三条判定引理的做法都是正确的。
单个有向图游戏的 SG 函数：
- $SG(x)=\operatorname{mex}{(SG(y_1),SG(y_2),\cdots,SG(y_k))}$，其中 $y_1,y_2,\cdots,y_k$ 为 $x$ 的后继节点。
- $SG(G)=SG(s)$，其中 $G$ 为整个有向图，$s$ 为有向图的起点。
有向图游戏的和的 SG 函数（SG 定理）：
- $SG(G)=SG(G_1)\operatorname{xor}SG(G_2)\operatorname{xor}\cdots\operatorname{xor}SG(G_k)$，其中 $G$ 为有向图游戏的和，$G_1,G_2,\cdots,G_k$ 为 $G$ 的子游戏。
易证 SG 函数是满足判定引理的，因此可以使用 SG 函数来判断必胜必败局面：
- 有向图游戏的某个局面必胜，当且仅当它的 SG 函数值大于 $0$。
- 有向图游戏的某个局面必败，当且仅当它的 SG 函数值等于 $0$。
单个有向图游戏中 $\operatorname{mex}$ 并没有什么作用可以退化为 $01$ 来表示必胜必败局面。
但是有向图游戏的和中 $\operatorname{mex}$ 与 SG 定理密切相关不能退化为 $01$。
没有规律的有向图游戏一般都暴力记忆化搜索求 SG 函数值，时间复杂度为 $O(n+m)$，$n$ 为状态数，$m$ 为转移数（最坏 $n^2$）。
博弈论中先手和后手都采取的是最优策略，因此一定不优甚至是更劣的策略不能加入到有向图中，否则可能导致一些奇葩问题。
二、nim 游戏
- P2197 【模板】nim 游戏
- P1247 取火柴游戏
经典 nim 游戏。
先手必败当且仅当物品数的异或和为 $0$，易证满足判定引理。
注意 nim 游戏既可以看成是单个有向图游戏（一张 $n$ 堆物品的图），也可以看成是有向图游戏的和（$n$ 张一堆物品的图的和）。
三、单个有向图游戏
- P1290 欧几里德的游戏
先得到 $0$ 的获胜，即 $(a,0)$ 必败为终局。
以样例 $(25,7)$ 为例：
$(25,7)$ 可以到达 $(18,7),(11,7),(7,4)$，
$(18,7)$ 可以到达 $(11,7),(7,4)$，
$(11,7)$ 可以到达 $(7,4)$。
若 $(7,4)$ 为必胜局面，则 $(11,7)$ 为必败局面，$(25,7),(18,7)$ 为必胜局面；
若 $(7,4)$ 为必败局面，则 $(25,7),(18,7),(11,7)$ 都为必胜局面。
因此若 $(b, a\bmod b)$ 为必胜局面，则 $\lfloor\dfrac{a}{b}\rfloor>1$ 时为必胜局面，$\lfloor\dfrac{a}{b}\rfloor=1$ 时为必败局面；
若 $(b,a\bmod b)$ 为必败局面，则 $(a,b)$ 为必胜局面。
时间复杂度 $O(T\log{V})$。
-
P1288 取数游戏II
因为至少有一条 $0$ 边不能走相当于把环断成了链，所以先手从起点出发有两个方向可以选择。
手玩样例会遇到一个问题：将非 $0$ 边变成 $0$ 边断掉后路是否会更劣？
若先手不断后路，则后手继续沿先手方向走必败就一定会断掉这个方向，先手不优还可能更劣；
若后手不断后路，因为先手必断后路所以之前全是 $0$ 边，先手直接往回走就能让后手被夹在 $0$ 边之间，后手必败。
因此先手和后手都一定会断后路，所以胜负只与两个方向的可走的边的数量的奇偶性有关，存在奇数先手必胜，都为偶数先手必败。
-
CF917B MADMAX
注意数据范围很小，点数只有 $100$，字符集大小只有 $26$，暴力记搜即可。
定义 $sg[x][y][ch]$ 表示当前先手在点 $x$，后手在点 $y$，字符的 ASCII 至少为 $ch$ 时先手必胜还是必败。
状态数为 $26n^2$，转移数为 $26nm$ 即最坏 $26n^3$，时间复杂度为 $O(26n^3)$。