我们所研究的博弈，实际上是一种组合游戏。这是一种双人之间进行的公平的完全信息博弈,并且一定可以在有限步数内结束。
所以在双方都采取最优策略的前提下,一个状态要么是必胜态要么是必败态,没有第三种情况.
而判定必胜态和必败态最原始的方法就是:

• 必胜态可以转移到必败态.
• 必败态只能转移到必胜态.
• 终止状态的胜负需由规则而定,多数是无法操作者败.

假如把每一个状态都当作无向图中的一个点，状态和状态之间的转移为点之间的边，
呢么可以将这个组合游戏看作是一个有向图游戏(状态转移图)
在此我们引入SG函数，SG[i]=mex(i的子状态)。理解上可以把SG当作一个状态(i)的总结。
mex(ai)运算返回不存在于a数组中最小的非负数。(例:max(0,1,2,4,6)=3)

我在最开始学习的时候认为SG函数以及mex运算只是为了区别0(通常设为必败态)与非0。但实际上理解后发现，
SG的非零取值所代表的不同状态不同。
并且假如一个状态的SG为i，呢么从0~i-1的状态都能同过该状态一步达到。
因此假如有多个游戏(也就是多个的有向图)，我们通过异或可以得到总局面的SG值。

为什么呢，首先我们知道，对手将一个游戏转到了某种状态，你可以在其他的游戏中转到相同的状态，
假如你每一次都能做到相同的操作。呢么就是必胜的。
异或操作可以判别多种状态之间的联系，假如一个游戏和另一个游戏拥有部分相同的可以转到状态，异或操作可以将其抵消。
好了，我们已经学到了博弈游戏可以通过SG函数来进行推演，也了解到了SG函数的递推方式。
已经可以做一些凭依于SG函数的暴力DP题目了。
但是博弈更多的，是复杂的情况，复杂的通过SG递推方式可以完成任务但是复杂度过高(所以可以将SG递推理解成博弈里的暴力(雾))
（当然也有可能是需要将原问题进行转化转化成便于进行SG递推的形式(比较难。不对，是非常难)
所以更多的情况下我们需要找规律(打表)， 或者总结一些泛用的博弈游戏模型：

巴什博奕：

有n个石子，每人可以随便拿1−m个石子，不能拿的人为败者，问谁会胜利

设当前的石子数为n=k∗(m+1)+r：先手会首先拿走r个，接下来假设后手拿走x个，先手会拿走m+1−x个，这样博弈下去后手最终一定失败
设当前的石子数为n=k∗(m+1)：假设先手拿x个，后手一定会拿m+1−x个，这样下去先手一定失败

nim游戏

有n堆石子，两个人可以从任意一堆石子中拿任意多个石子(不能不拿)，没法拿的人失败。问谁会胜利

当n堆石子的数量异或和等于0时，先手必胜，否则先手必败

阶梯博弈

N个阶梯，每个阶梯上都有一定量的石子，石子只能每次从上一个阶梯移到下一个阶梯

阶梯Nim只考虑奇数位置进行Nim游戏，因为假如上一次操作是偶数移到奇数位置，呢我们下一次操作就可以将上一次操作移动的再次移动到下一个偶数位置。因此偶数位置上的石子数并不影响总体。

平衡博弈

最开始有一堆石子，每人每次可以对于一堆石子拿走k(k不大于石子个数的一半)个并将这一堆剩下的石子分为一堆或是石子数任意的两堆。当某一堆石子个数为1时可以直接拿完，问谁会胜利

当n=2或3时后手必胜，其他情况都是先手必胜。
显然，当n为偶数时先手可取出两个并将这堆石子分成相同的两堆。当n为奇数时先手可取出三个并将这堆石子分成相同的两堆。重点是达到的两堆相等的状态。

Anti-Nim游戏

有n堆石子，两个人可以从任意一堆石子中拿任意多个石子(不能不拿)，拿走最后一个石子的人失败。问谁会胜利

当每堆石子都只有一个，且游戏的SG值为0，或者至少一堆石子多于一个，且游戏的SG值不为0，先手必胜。否则先手必败。

Multi-Nim游戏

1.有n堆石子，两个人每次从任意一堆石子中拿任意多个石子(不能不拿)或把一堆石子分为两堆都不为0的石子，没法拿的人失败。问谁会胜利

通过SG函数操作可以模拟，但是观察后可发现性质：

SG(x)=x−1 (x%4 == 0)
SG(x)=x (x%4 == 1||2)
SG(x)=x+1 (x%4 == 3)

2.有n堆石子，两个人从任意一堆石子中拿任意多个石子(不能不拿)后，可以将取的那一堆的石子 分为多堆，也可以不分，没法拿的人失败。问谁会胜利

同Nim取石子游戏结论，即若n堆石子的异或和为0，则先手必败；否则，先手必胜。

Multi-SG游戏规定，在符合拓扑原则的前提下，一个单一游戏的后继可以为多个单一游戏。仍然可以使用SG函数，后继为多个单一游戏的，这个后继的SG值为多个单一游戏SG的异或和

斐波那契博弈

有一堆石子，先取者可以取走任意多个，但不能全取完，以后每人取的石子数不能超过上个人的两倍

先手必败，当且仅当石子数为斐波那契数（神奇

威佐夫博弈

有两堆石子，每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子，不能取的人输，分析谁会获得胜利

假设两堆石子为(x,y)（其中x<y）,那么先手必败，当且仅当(y−x)∗((√5+1)/2)=x ((√5+1)/2) 其实就是1.618，比较神奇
证明需要Betty定理，当时看的不太懂

Every-SG游戏

给定一张无向图，上面有一些棋子，每人每次必须将可以移动的棋子进行移动，不能移动的人输

题目中的要求实际是“不论前面输与否，只要最后一个棋子胜利，那么就算胜利”。这样的话，能赢得游戏必须赢
对于Every-SG游戏先手必胜当且仅当单一游戏中最大的step为奇数。
定理显然：最大的单一游戏步数如果是奇数的话那么肯定是先手取得进行最后一步，否则一定是对手取走最后一个棋子。

树的删边游戏

给出一个有 N个点的树，有一个点作为树的根节点。游戏者轮流从树中删去边，删去一条边后，不与根节点相连的部分将被移走。谁无法移动谁输。

结论：叶子节点的SG值为0；中间节点的SG值为它的所有子节点的SG值加1后的异或和。

无向图的删边游戏

一个无相联通图，有一个点作为图的根。游戏者轮流从图中删去边，删去一条边后，不与根节点相连的部分将被移走。谁无路可走谁输。

Fusion Principle定理：

我们可以对无向图做如下改动：将图中的任意一个偶环缩成一个新点，任意一个奇环缩成一个新点加一个新边；
所有连到原先环上的边全部改为与新点相连。这样的改动不会影响图的SG值。
定理显然。将图变换后就变为树的删边游戏了