之前其实也只会自己能推出来的博弈论题，都是最简单的那种，然后遇到难的就惨败
来总结一下一些常见的简单博弈的特征及其解决算法
巴什博弈
特征
一堆物品有n个，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。
引申的还有其它的表述方法，类似于两人操控一个棋子轮流走一段长度，到最后位置的人输或者赢之类的
算法
考虑第一步是不是必败态，否则必胜。证明也很简单，控制剩余石子的数量，使对方无论如何行动都达不到赢面即可
对于巴什博弈，那么我们规定，如果最后取光者输，那么又会如何呢？
n%（m+1）==0则后手胜利
推广：减法博弈
特征
巴什博弈的变形，轮流取石子，只能取给定的集合中的石子个数，取到最后一个石子的人获胜。
算法
这个就得用到动态规划了qaq
可以发现当前石子数m如果可以通过取集合中的任何一个，让m-ai变成一个P态（先手必胜态），则当前m就是N态（后手必胜态），如果不能，则m为P态。
使用dp[i]表示有i颗石子时的胜负状态，则dp[i-a[j]](a[]为集合)是之前能达到的状态，如果他们中至少有一个是必胜态，那么i是必败态，否则i时必胜态。
斐波那契博弈
特征
有一堆石子，两个顶尖聪明的人玩游戏，先取者可以取走任意多个（很明显大于1），但不能全取完，以后每人取的石子数不能超过上个人的两倍
算法
斐波那契博弈有一个非常重要的性质：
先手必败，当且仅当石子数为斐波那契数
就没有什么其他的好说了（
威佐夫博弈
特征
有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利。
算法
这种情况下是颇为复杂的。我们用（a[k]，b[k]）（a[k] ≤ b[k] ,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）。（注：k表示奇异局势的序号， 第一个奇异局势k=0）
可以看出,a[0]=b[0]=0, a[k]是未在前面出现过的最小自然数,而 b[k]= a[k] + k。
这里的奇异局势有这样三个性质：
任何自然数都包含在一个且仅有一个奇异局势中。
任意操作都可将奇异局势变为非奇异局势。
采用适当的方法，可以将非奇异局势变为奇异局势。
两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。
那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：
ak =[k*（1+√5）/2]，bk= ak + k （k=0，1，2，…n 方括号表示取整函数)
（k=0，1，2，…n 方括号表示取整函数)
奇妙的是其中出现了黄金分割数（1+√5）/2 = 1.618…因此，由ak，bk组成的矩形近似为黄金矩形，由于2/（1+√5）=（√5-1）/2，可以先求出j=[a（√5-1）/2]，若a=[j（1+√5）/2]，那么a = aj，bj = aj + j，若不等于，那么a = aj+1，b = aj + j + 1，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异局势。
尼姆博弈（nim游戏）
特征
有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。
而这里的物品数可以看作是每堆的最大变化次数（
算法
假设只有三堆，我们用(a,b,c)表示某种局势，首先(0,0,0)显然是必败态，无论谁面对(0,0,0) ，都必然失败；第二种必败态是(0,n,n)，自己在某一堆拿走k（k ≤ n）个物品，不论k为多少，对方只要在另一堆拿走k个物品，最后自己都将面临(0,0,0)的局势，必败。仔细分析一下，(1,2,3)也是必败态，无论自己如何拿，接下来对手都可以把局势变为(0,n,n)的情形。
然后之后不知道有哪个天才把这玩意和异或（^）联系了起来，有：
任何奇异局势(a,b,c)都有a XOR b XOR c = 0
面对的是一个非必败态(a,b,c)，要如何变为必败态呢？
假设 a < b < c，我们只要将 c 变为a XOR b，即可。因为有如下的运算结果：
a XOR b XOR (a XOR b)=(a XOR a) XOR (b XOR b) = 0 XOR 0 = 0
要将c 变为a XOR b，只要对 c进行 c-(a XOR b)这样的运算即可。
同样的也可以拓展到 n 堆物品，有下述结论：
Bouton定理：先手能够在非平衡尼姆博弈中取胜，而后手能够在平衡的尼姆博弈中取胜。
而平衡的尼姆博奕则为：
a XOR b XOR c XOR …= 0
推广：阶梯博弈（NimStaircase）
特征
游戏开始时有许多硬币任意分布在楼梯上，共n阶楼梯从地面由下向上编号为0到n。游戏者在每次操作时可以将楼梯j(1<=j<=n)上的任意多但至少一个硬币移动到楼梯j-1上。游戏者轮流操作，将最后一枚硬币移至地上的人获胜。
算法
阶梯博弈等效为奇数号阶梯的尼姆博弈。
假设我们是先手。我们按照尼姆博弈的原则进行第一次移动。如果对方移动奇数号阶梯的石子，我们继续按照尼姆博弈的原则移动。如果对方移动的是偶数号阶梯的石子，及对方将偶数号阶梯的石子移动到了奇数号（对奇数号产生了影响）我们就接着将对方移动到奇数号的石子再向下移动一个台阶，移动到偶数号。这就意味着在偶数号的棋子对我们的博弈是没有影响的。
而为什么等效于奇数号的尼姆博弈而不是偶数号的？
这是因为如果等效于偶数号的，当后手移动奇数号的，移动到0了，就不能保证状态一致了。
所以有：
将奇数层的状态异或，如果不为0，先手必胜，否则先手必败
环形博弈
特征
n个石子围成一个环，每次可取走1个或相邻的两个，注意若两个石子之间的石子被取走，这两个石子仍然是不相邻的
算法
其实这个博弈可以看作对称博弈的特殊情况，下面在对称博弈的时候证明（
若n<=2则先手胜，否则后手胜
推广：对称博弈
特征
n个石子围成环,每次只能取相邻的一个到k个之间
算法
k等于1时，一次最多只能拿1个（每堆只有一个），那就是看奇偶了。
n≤k 这种情况，那肯定先拿的赢。
这条就是对称博弈了， 除了上述两种情况外的情况（n>k && k!=1）这时候，无论你第一个人拿什么，怎么拿，后手的人完全可以在第一个人拿的对称的地方做同样的事情。这样，后手就一定会取得胜利，因为最后一步是后手走的。
如果k<n：对k=1,如果n能被2整除,则后手赢；如果k>1,后手赢（先手取什么位置后手就取对称的位置，这样保证后手永远能取到)；
如果k>=n：先手赢.