这里记录了一些最基本的博弈论问题以及解决方式
定义组合游戏的意义如下：
$1$、两个玩家L,R进行博弈。
$2$、每一回合，双方可选的合法操作有限。
$3$、对于任意一组合法局面，当前决策与之前的操作无关。
$4$、最后总能到达一种状态使得至少有一方的可操作性集合为0，这时游戏结束。
在这基础上加上一些别的条件，就组成了不同种类的组合游戏。
其中主要分为回合制与非回合制两种。
可以证明，回合制组合游戏总是存在最优纯策略：即每一步都有一种确定最优的决策方式。
而非回合制组合游戏不一定存在纯策略，但一定存在最优的混合策略，即以一定的概率随机的选择一种决策。
一般来讲，纯策略是混合策略的特殊情况。因为混合策略涉及到概率，所以通常与纯策略的博弈问题有着不同的处理方式。
回合制有向图游戏
在组合游戏的基础上，增加条件：
$1$、双方交替进行操作，每次操作与当前的玩家无关。
$2$、最先无法进行合法操作的一方判负。
所以有向图游戏是存在纯策略的博弈问题，因此可以使用对抗搜索解决，或者使用SG函数解决。
SG函数
对于游戏的每个子游戏，存在一种衡量局面优劣的函数SG函数，整个游戏的SG函数就是各个子游戏的异或和。
每个局面的SG函数为当前局面的后继状态的SG函数集合中最小的没有出现的非负整数，可以发现对于某一状态而言：
$1$、如果没有后继状态，SG函数为0，表示必败。
$2$、如果后继状态中存在必败状态，那么SG函数为正，表示必胜。
$3$、如果后继状态全是必胜，那么SG函数为0，表示必败。
这和对抗搜索的想法完全一致，只不过SG函数提供了量化的方法，因此允许快速合并多个子局面。
e.g. P2197 Nim游戏
n堆石子，每人每次选择一堆至少取走一颗，问先手是否有必胜策略。
Nim游戏的各个子游戏的SG函数值就是石子个数(想一想，为什么)，然后异或起来看是不是0就行了。
为什么是异或？
非回合制零和博弈
在组合游戏的基础上，增加条件：
$1$、每一步操作会对某一方带来收益，同时让另一方支付代价。任意时刻，双方的收益和为0。
在这里如果双方交替操作的话，就一定存在纯策略，那就可以用对抗搜索解决。但是如果是同时操作，就一般不存在纯策略作为最优决策，问题就变成了混合决策问题。
所谓混合决策，就是一方的最优策略是以不同概率使用不同的决策。
对于每种局面，首先画出对应的收益矩阵$E=[e_{ij}]_{n\times{m}}$，在这里假设玩家1（叫做L）有n种不同的决策，玩家2（叫做R）有m种不同的决策，$e_{ij}$就表示当L选择i决策，R选择j决策时L的收益，这个矩阵就叫L的收益矩阵，R的收益矩阵就是$E[-e_{ji}]_{m\times{n}}$。
设玩家L选取各个决策的概率为$\begin{Bmatrix}l_1,l_2,l_3,…,l_n\end{Bmatrix}$。
玩家R选取各个决策的概率为$\begin{Bmatrix}r_1,r_2,r_3,…,r_n\end{Bmatrix}$。
双方的目标都是最大化己方的收益，最大化对方的支出。
感觉上，一方的最优策略应该满足：无论对方怎么选择决策，己方的收益都不会小于某个值，而对方的收益都不会大于某个值。
当一方采用最优策略时，另一方无论怎么调整都不会是收益更大。
这个概念叫做纳什平衡，有兴趣的话可以去查一下百科。
双方都采用最优策略时的收益叫做收益矩阵的值，双方的决策方式叫做平衡点。
求解收益矩阵
由上述可知，一方的任意策略满足在任意情况下收益都不会低于某个值，而最优策略使得这一值最大化。
设该值为$V(V>0)$。
问题就变成了：
求此时$V$的最大取值。
第一个式子就是各个决策的概率和为1，第二个式子表示在极端情况下（R碰巧采用了针对己方混合策略的最优纯策略）也能保证收益，因为在R使用各个纯策略的情况下都能最大化最小收益，所以j是要从1枚举到m的。
设$L_i=\frac{l_i}{V}$，问题就变成了：
或者变个形式：
这就是一个标标准准的线性规划问题了。
对于非零和博弈的话，就不存在纳什平衡，因为纳什平衡只适用于非合作性博弈问题当中，自然不能用收益矩阵求解。
反过来说，只要是非合作性博弈问题就可以使用这种方法，而不仅仅限于零和博弈问题了。
e.g. P4232 无意识之外的捉迷藏
两个人在一个$n$个点的$DAG$上走，两人走到同一节点时游戏结束，或者游戏到了$T$时刻没有结束，游戏视作在$T+1$时刻结束。每一时刻双方同时走一步，可以走到用有向边相连的相邻节点处。
设游戏结束时刻为$t_0$，一方收益为$t_0$，另一方收益为$-t_0$。
双方都采用最优策略时，求游戏的期望结束时间。$n,T\leq 20$
这个是求收益矩阵的模板了，状态$f[i,j,k]$表示一个人在$i$点，一个人在$j$点，时刻为k的期望还有多久结束，每一个状态的后继状态就是遍历两点的所有出边，然后构造并求解收益矩阵即可。
不平等回合制博弈
不平等博弈就是在组合游戏上追加：
$1$、双方交替进行操作，最先不能操作的一方判负。
$2$、双方的决策不一定完全相同。
在处理不平等博弈的时候，除了利用其纯策略的性质而使用万能的对抗搜索之外，还有一种有力工具就是$Surreal\ Number$(超现实数)。
$Surreal\ Number$
（下面内容大部分来自 方展鹏《浅谈如何解决不平等博弈问题》，这里只是一个简单的概述，即根据自己的理解组成的不完整但是够用的内容）
$1$、一个超现实数由两个集合组成$\begin{Bmatrix}L|R\end{Bmatrix}$，每个集合要么为空，要么是由若干个超现实数组成的集合。
$2$、对于$x=\begin{Bmatrix}X_L|X_R\end{Bmatrix}$，$y=\begin{Bmatrix}Y_L|Y_R\end{Bmatrix}$，当且仅当不存在$x_i\in{X_L}$使得$y\leq x_i$并且不存在$y_i\in{Y_R}$使得$y_i\leq x$。
这些定义都是递归给出的，值得注意的是这里的$\leq$不是指小于等于，而是类似于集合中的偏序概念。不过之后会说到，超现实数集合是一个全序集，所以理解成小于等于也未尝不可。
然后通过下面的达利函数，我们可以构建出有理数与超现实数的对应关系：
解释一下这个第四条，就是左右两个数加在一起取个平均数。
基本定理
$1$、对于$x=\begin{Bmatrix}L|R\end{Bmatrix}$,有$L_{max}\leq x\leq R_{min}$，$x=\begin{Bmatrix}L_{max}|R_{min}\end{Bmatrix}$
$2$、对于$x=\begin{Bmatrix}X_L|X_R\end{Bmatrix},y=\begin{Bmatrix}Y_L|Y_R\end{Bmatrix}$:
$\qquad x+y=\begin{Bmatrix}X_L|X_R\end{Bmatrix}+\begin{Bmatrix}Y_L|Y_R\end{Bmatrix}=\begin{Bmatrix}X_L+y,x+Y_L|X_R+y,x+Y_R\end{Bmatrix}$
$3$、对于$x=\begin{Bmatrix}X_L|X_R\end{Bmatrix}$,有$-x=\begin{Bmatrix}-X_R|-X_L\end{Bmatrix}$
与不平等博弈的关系
如果游戏$G$等价于$x=\begin{Bmatrix}L|R\end{Bmatrix}$，其中两个集合表示两个玩家的决策所产生的的后继状态集合：
$x>0 \ L$必胜，$x<0 \ R$必胜，$x=0$后手必胜。
$x>0$时：$L$先手时总能将$x$转移到一个大于等于0的状态，$R$先手只能将其转移到大于0的状态。轮到$L$时恒有$x>0$，左集合始终不为空，$L$必胜。
$x<0$时同理。
$x=0$时，$L$先手会将局面变成$x<0$，$r$先手会将局面变成$x>0$，然后同上。
将一个游戏的多个子游戏合并就是将其对应的$Surreal\ Number$对应的值相加。
e.g.Procrastination
$n$个有黑白正方体堆成的柱子，先手只能拿白色，后手只能拿黑色。每人每次选择一个柱子拿走一个对应颜色的正方体，然后将该正方体上面的所有正方体（包括这个）全部拿走。一方不能操作时判负，判断先手是否存在必胜策略。
$n,h_i\leq 50$，$h_i$表示第$i$个柱子的高度。
根据定义$O(n)$递推然后相加即可，就是从下向上维护双方决策的最值，或者按照论文中的做法推式子。