（一）巴什博奕（Bash Game）：只有一堆n个物品，两个人轮流从这堆物品中取物，规
定每次至少取一个，最多取m个。最后取光者得胜。

结论: n是否是(m + 1)的倍数,n 是(m + 1)的倍数则先手必败，否则先手必胜

策略：1.如果n是（m + 1） 的倍数，则无论你取什么（x），对手可以取（m + 1 - x） ，那么最后一次一定是对手取完，先手必败
2.如果n不是（m + 1） 的倍数，那么先手可以取余数然后就转化为1了
代码实现 hdu 题目 巴什博弈板子题 传送门

#include <iostream>
using namespace std;
int main(){
    int t ;
    cin >> t ;
    while(t--){
        int n,m ;
        cin >> n >> m ;
        if(n % (m + 1)) cout << "first\n" ; //先手必胜  
        //因为余数不是0，先手一定可以通过一步操作转化为余数是零的状态
        else cout << "second\n" ;
    }
    return 0;
}

（二）威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同
时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

结论 : 两堆值为a,b,其中（a > b） ，如果（a - b） * (sqrt(5) + 1) / 2 == b ，那么先手必败，否则先手必胜

定义先手必输的局势为奇异局势，前几个奇异局势为(0,0),(1,2),(3,5),(4,7),(6,10)…
假设(x,y)为第k个奇异局势
1.x为前1…k个奇异局势中没有出现过的最小正整数，y=x+k
2.任何一个自热数都包含在一个且仅有一个奇异局势中
证明这个结论，我们只需要证明两点:(1)任意自然数都出现过(2)任意自然数仅出现一次
对于(1)：反证法，设v这个数没有出现过，那么v可以做一个新的奇异局势的x
对于(2): 反证法
假设数v出现了两次，那么v一定不是所在奇异局势的x(x必须之前未出现)
那么v只能同时是两个奇异局势的y，又因为任意一个奇异局势的差值不相同，因此v不可能出现两次
3.任何操作都会将奇异局势变为非奇异局势
若取走一堆中的石子，那么两对石子的差值会改变，必将成为非奇异局势
若同时取走，因为同一个差值只会对应一种奇异局势，必将成为非奇异局势
4.可以采取适当的方法将非奇异局势变为奇异局势
引用 ： 威佐夫博弈by自为风月马前卒

代码实现 poj 1023 威佐夫博弈 传送门

#include <iostream>
#include <cmath>  // 因为使用了根号5，所以要使用sqrt函数
using namespace std;

int main(){
    int a,b;
    while(cin >> a >> b){
        if(a > b) swap(a,b) ;
        int ans = abs(a-b) * (sqrt(5.0) + 1.0) / 2.0 ;  //大数减去较小数的差值乘(sqrt(5) + 1) /2 等于较小数
        if( ans == a) puts("0") ;
        else puts("1") ;
    }
    return 0;
}

扩展，还需要输出第一个人拿完石子之后的策略
代码实现 hdu 2177 取(2堆)石子游戏

#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int a,b;
    while(cin >> a >> b, a || b){
        if(a > b) swap(a,b) ;
        int cha = b - a ;  //记录差值
        int ans = abs(a-b) * (sqrt(5.0) + 1.0) / 2.0 ;  //威佐夫博弈处理
        if( ans == a) puts("0") ;
        else{
            puts("1") ;             //如果能赢，那么有两种操作
            int x = cha * (sqrt(5.0) + 1.0) / 2.0 , y = x + cha ;   
            //1.可以将两堆同时减去一个数，使得形成奇异局势 ，那么由于同时减去一个数，差值不变，由判断定理得
            // 奇异局势的较小值应该等于 差值乘 (sqrt(5) + 1) /2 ，得到较小的值x，然后加上差值就是较大数y
            printf("%d %d\n",x,y) ;
            int t = a *(sqrt(5.0) + 1.0) / (sqrt(5.0) + 3.0) ;
            //2.可以在较大的堆中拿去一些石子，使得原先较大的一堆变成较小的一堆，然后原先较小的一堆变成大堆
            //由于已知较大堆，那么可以设较小堆为t（b堆拿完后） ，可以列 (a - t) * (sqrt(5) + 1) /2 = t ;
            //可以解得t = a *(sqrt(5.0) + 1.0) / (sqrt(5.0) + 3.0)
            printf("%d %d\n",t,a) ;

        }
    }
    return 0;
}

（三）尼姆博奕（Nimm Game）：有若干堆各若干个物品，两个人轮流从某一堆取任意多的
物品，规定每次至少取一个，多者不限，最后取光者得胜。

结论： 将所有的值异或，如果异或结果不是0，则必胜，否则必败

策略：记ans为所有物品异或结果
记k为ans的最高位，那么n堆中必定存在至少一个数x的第k为是1（异或的性质，因为异或是不进位加法）；
那么如果将x变为 x^ans ,那么就可以把ans转化为0

第一个类型：就是让其判断胜利的人，对n堆石子求异或和，根据当Nim和！= 0时，先手胜利，否则失败就能判断出来。
第二个类型：先取完者判输，统计一下所有数一下大于1的个数，并将所有数字异或一遍，若大于1的个数为0&&异或和为0||大于1的个数大于0&&异或和不为零，则先手胜，否则后手胜。
第三个类型：限制最多取的个数，例如第i堆石子共有m个，最多取r个，先对m=m%（r+1）;然后在进行异或求和。再根据异或和判断输赢。
第四种类型：先手的人想赢，第一步有多少种选择。当先手必输时，很显然是0。如果先手赢，那么先手必须努力创造奇异局势，即让其剩余的石子量异或和为0，上面已经讲了当面对非奇异局势是如何转化成奇异局势。当nim游戏的某个位置：（x1,x2,x3），当且仅当其各部分的nim - sum = 0(即x1（+）x2（+）x3 = 0（也就是各部分的异或为0）) 当前位置为必败点，这对于多个堆的情况同样适用。我们首先求出所有堆异或后的值sum，再用这个值去对每一个堆进行异或，令res = x1（+）sum(sum为所有堆的异或和)。如果res < x1的话，当前玩家就从x1中取走（x1-res）个，使x1乘下res这样必然导致所有的堆的异或值为0，也就是必败点（达到奇异局势），这就是一种方案。遍历每一个堆，进行上面的断判就可以得到总的方案数。
res = x1（+）sum；其实就是除了x1之外的n-1堆异或和，a（+）b（+）c=sum；sum（+）c=a（+）b（+）c（+）c=a（+）b;
ps:注意一个必败点不可能导致另一个必败点，因为如果这样的话当前这个必败点就不是必败点了，所以这里对于每个堆的操作至多只有一种方法
可以导败必败点，如果res > x1的话就无论从这个堆取走多少都不可能导致必败点！！！
引用： 博弈—尼姆博弈讲解

图片是陈锋老师讲的博弈论里截的
sg函数

待更新
1.极大极小搜索：
2.普通nim博弈：
3.anti-nim游戏：
4.every-SG游戏：
就是多线程博弈。
5.不平等博弈：
参考 ： 博弈总结