公平组合游戏

公平组合游戏是两个人进行的游戏，回合制并且每个人操作的对象是同一个，换言之每一步状态，怎么操作都与操作者无关，两人都是全知全能，进行每一步操作时都了解后面操作的所有状态，去选择对自己最有利的解，这就叫做公平组合游戏，而基础的博弈论就是探讨这种情况的。

博弈论中最基本的知识

在进行公平组合游戏时，每一步的状态可以概括为两种。
p态：后手必胜，即这个回合开始时操作者的对手一定会赢。
n态：先手必胜，即这个回合开始时操作者一定会赢。
知道这两个概念之后不难推出两个结论。

  1. 能变成p态的状态一定是n态。因为每个人都想要最优解，如果前面已经先手必胜，那么等于可以选择下一回合自己变成后手必胜。当然也可以不选，那么就会输。
  2. p态只能变成n态。这个回合我是后手必胜的状态，无法操作，但由于是必胜的状态，下一回合我操作一定是先手必胜。

sg函数

sg函数是决定谁胜谁败的关键。
我们规定sg函数的公式为 g(x)=mex{g(y)} 其中x表示了当前状态，y表示了所有x状态通过一步转换能变成的状态集合。
mex函数表示大括号中所有数的第一个非负整数，比如mex{0，1，2，3}=4。
那么这个公式的作用是什么，p态出现当且仅当g(x)=0，我也不会证明。。
前面的sg函数运用于一个子游戏，当一个大的组合游戏分为多个子组合游戏时，我们该如何计算其中的sg函数呢？
大的g(x)值是所有子游戏起点的SG值的异或（XOR）和，异或就不需要说了吧，两个1变成0，两个0还是0，1^0=1。

hash 博弈

根据Bash博弈的规则，当有 n 个石子时，玩家可以取走 k 个，其中 1≤k≤x。所以，状态 n 可以转移到 n−1,n−2,…,n−x 这 x 个状态（只要这些状态 ≥0）。
所以sg函数是g(n)=mex({g(n−1),g(n−2),…,g(n−x)})
我们慢慢枚举
g(0)=0 g(1)=mex{g(0)}=1 g(2)=mex{g(0),g(1)}=2….. g(x)=mex{g(0),g(1)….g(x-1)}=x
重点来了g(x+1)=mex{g(x)…..g(1)}=0
由此可见sg函数是关于x+1的一个循环，我们知道后手必胜的条件就是g(n)=0
也就是说当且仅当n=k(x+1),k属于正整数时候才成立。

nim 博弈

n 堆石子，第 i 堆有 ai 个。双方轮流选择任意一堆，并从该堆中取走任意数量（但至少一个）的石子。无法操作者输 。
这是多个组合问题，把他先分解，看成一个个子问题来做，以一堆为研究对象。设没堆石子有k个。
sg函数为g(k)=mex{g(0),g(1),g(2)…g(k-1)}=k
k=ai 那么也就是说这个数列必须满足 a1^a2^a3^….an=0 进入后手必胜状态。