【笔记】博弈论
0 基本概念 & 性质
0.1 博弈论
1 SG 函数
ps. 通过 SG 函数来理解三个基本模型，也是不错的选择。
1.2 定义
\(\text{SG}(x)=\text{mex}\{\text{SG}(y_i)\}\)（其中 \(y_i\) 为 \(x\) 的后继状态）
1.3 SG 定理
由 \(n\) 个博弈图组成的游戏，设起点（即每个连通分量内入读为 0 的点）分别为 \(s_{1}, s_{2}, \dots, s_{n}\)。
当 \(\text{SG}(s_{1})\oplus\text{SG}(s_{2})\oplus\cdots\oplus\text{SG}(s_{n})\neq 0\) 时，先手必胜；反之，先手必败。
1.3.1 证明
2 三个基本模型
2.2 布什博弈
2.2.1 概述
2.2.2 结论
若 \(m+1\nmid n\)，先手必胜；反之，先手必败。
2.2.3 证明
构建决策树
3 例题
3.0 Links
3. 取石子
Key：
本质上是求 SG 值，但是由于最终不许要用 SG 定理，于是 SG 值可以就为 0/1 表示是否先手必胜
令 \(sum=\sum a_i\)
先单独考虑操作 1：若 sum 为奇，必胜；为偶，必败。
可以发现操作 2 其实相当于某人跳过了一次操作，而不改变。
性质 1： 操作 2 就是用来浪费时间的，所以如果可以做就尽量做 。
后继状态：（当前为 \((x,y)\) 表示：全是 1 的堆数 | 其余最多操作次数 = 大于 1 的堆的总和 + 堆数 - 1，特别地，空集 = 0）
-
取走 1 个
-
取 x：\((x-1,y)\)
-
取 y：\((x,y-1)\)
ps. y 中不到最后只剩一堆的时候，不会出现堆的个数变为 1 的（性质 1），所以可以直接减。
-
-
合并
-
合两个 x：\((x-2,y+2+[y\neq 0])\)
ps. 特判 y 原先为空集。
-
合两个 y：\((x,y-1)\)
-
合一个 x 和 一个 y：\((x-1,y+1)\)
-
注意判断，从 y 转为 x 的情况。
3. 小约翰的游戏
反 Nim 问题。
讨论：
-
全为 1：n 为偶，必胜；为奇，必败。
-
有一个不为 1：必胜。（本质上可以归类为 3）
先手一定可以通过一次操作，将状态转化为偶数个 1。
-
有多个不为 1：转化为了普通 Nim 问题
先手想要把情况变为 2，即要把不为 1 的堆拿成只剩一堆，然后让自己处理，于是就转化为了普通 Nim 问题。
4 Trick
- 有种奇怪的感觉：最后只剩 1 的时候都比较关键。