博弈论
博弈论主要研究的是：在一个游戏中，进行游戏的多位玩家的策略。
公平组合游戏
公平组合游戏的定义如下：
- 游戏有两人参与，二者轮流做出决策，双方均知道游戏的完整信息。
- 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关。
- 游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。
博弈图（有向图游戏）和状态
博弈中可能出现的某一局面称为一个状态。
将每个状态视为一个节点，再从每个状态向它的后继状态连边，我们就可以得到一个博弈状态图。
定义必胜状态为先手必胜状态，必败状态为先手必败状态，则有：
- 没有后继状态的状态是必败状态
- 一个状态是必胜状态当且仅当存在一个后继状态为必败状态
- 一个状态时必败状态当且仅当它的所有后继状态都是必胜状态
显然，当博弈图是一个DAG的时候我们可以直接逆拓扑出所有状态是必胜还是必败。
博弈图也被称为有向图游戏，其实质为在一个DAG上有唯一的起点，起点上有一个棋子，两位玩家分别将棋子沿有向边移动，无法移动者输。
任何一个公平组合游戏都可以转化为有向图游戏。
SG函数
定义$mex$函数为集合中最小的非负整数，即
对于状态$x$和它的所有$k$个后继状态$y_1,y_2,…,y_k$，定义SG函数
对于由$n$个有向图游戏组成的组合游戏，设它们的起点分别为$s_1,s_2,…,s_n$，则有SG定理：
Nim博弈
给定n堆物品，第i堆物品有a[i]个，两名玩家轮流行动，每次可以取走任一堆的任意个物品，可以取完但不能不取，取走最后一件物品者胜，问先手是否有必胜策略。
首先给出结论：当且仅当$a[1]\oplus a[2]\oplus…\oplus a[n]\not=0$时先手必胜。
显然可以证明下面三个结论：
- 没有后继的状态是必败状态，此时$a[1]\oplus a[2]\oplus…\oplus a[n]=0$
- 对于$a[1]\oplus a[2]\oplus…\oplus a[n]\not=0$的局面一定存在某种取法使得取后$a[1]\oplus a[2]\oplus…\oplus a[n]=0$
- 对于$a[1]\oplus a[2]\oplus…\oplus a[n]=0$的局面一定不存在某种取法使得取后$a[1]\oplus a[2]\oplus…\oplus a[n]=0$
阶梯博弈
甚么是阶梯博弈？阶梯博弈指的是我们可以将状态进行分层（1~k），上层状态每次能且只能向下一层转移的博弈。
给出结论：阶梯博弈等效于奇数层阶梯的Nim博弈。
其实非常好理解，偶数层的状态移动到奇数层时，只要将这个状态再向下移一层，这个状态就与胜负无关了。
巴什博弈
有一堆n个石子，两名玩家轮流从其中取石子，每次至少取1个最多取m个，取走最后一个石子的玩家获胜，问先手是否存在必胜策略。
这个或者说这类问题的解法都很直接，从0开始枚举状态找规律，发现如果每次取的石子数在[p,q]，那么从1开始就是q个必胜3态、p个必败态…这样重复的。
斐波那契博弈
有一堆n个石子，两名玩家轮流从其中取石子，先手不能一次将石子取完且最少取一颗，之后每次取的石子数不能超过上次去的个数的2倍且至少为1，取走最后一个石子的玩家获胜，问先手是否有必胜策略。
结论：先手必败，当且仅当n为斐波那契数。
根据齐肯多夫定理：任何一个正整数都可以表示成不连续的若干个斐波那契数之和，