博弈论(sg函数）

巴什博弈

只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。
最后取光者得胜。

显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，

后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：

如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走
k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的
取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。

##威佐夫博弈

有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

我们再用逆推归纳法分析。我们用（ak，bk）（ak
≤ bk ,k=0，1，2，…,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输

了，这种局势我们称为奇异局势。

前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。

可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k。

若两堆物品的初始值为（a , b），且x < y，定义k=b-a；定义x = [ ( ( sqrt(5) + 1 ) / 2 ) * k ]
若x=a，则先手必败，否则先手必胜。

##Nim博弈

有n堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

这里奇异局势变成了多堆(x1,x2,x3…)，所以有一个结论就是把每堆Xi异或起来，结果为0则先手必败

##sg函数
在网上看过了很多介绍sg函数的文章，但是感觉还是不太明白，就像当初第一次知道dp的时候。。。。。所以，还是自己再进行以下，浅显的个人理解。
sg函数：SG(x)=mex{ SG(y) | x->y }，mex(x)表示非x集合中最小的自然数
以下就是个人的浅显理解：
在解释之前，首先要知道sg值只需要关注0和非0两种状态就行了

在看了mex函数之后，是不是感觉字面理解了，但是，啥意思呢？
首先，一个点的下一个状态，也就是子状态会有很多个，然后每个子状态又会有自己的子状态。当一个状态的子状态可以直接判断为必胜态或者必败态的时候，子状态返回自己的sg值，然后，用一个vis数组存下来，这里vis数组就相当于mex函数，然后当当前状态的所有子状态都返回了自己的sg值，并用vis记录了下来，那么，vis从0开始，没有被标记过的第一个自然数则是当前状态的sg值。
当一个值被vis数组记录过，那么说明当前状态可以转换成对应sg值的状态，那么，如果0被标记了，那么说明当前状态可以转换成必败态，呢么当前状态的sg值一定是非0的，也就是必胜态。到这里，mex函数的意义是不是有点明白了，就是寻找第一个不能转换到的状态，那么，在看之前说的只需要关注0和非0两种状态就行了，意思就是，当你通过mex函数也就是vis数组找到的当前点的sg值为0则说明，当前点没办法转换到必败态，那么，当前点就是必败态，所以sg值为0；反之，非0则说明可以转换到必败态，那么当前则是必胜态。