由于一直没接触博弈，我已经被博弈题坑了好几把了，所以有了这篇写给自己的学习历程

博弈

博弈：有若干堆物体（可以是火柴棍或是围棋子等等）两个人轮流从堆中取物体若干，规定最后取光物体者取胜。

1.由于博弈双方都能做出最优决策，所以游戏刚开始就意味着结束（好惨，一点游戏体验都没有~），因此博弈能否胜利取决于当前的局面

2..局面是博弈里面最最最重要的东西！！！（所谓SG也是指这一局面的SG），因为双方均采取最优策略，故而局面必然会以双方当前对自己最优的路径走下去，所以结局已经确定了，每个局面也是固定的

3.因此为了得到最优决策，我们可以从最后已得到胜负的局面逆推而来（也就是从一个已知胜负的局面一步步推导其他的局面，有了这样的思想，SG也就相对好理解，即递推思想）

4.必胜点和必败点
P点：必败点，换而言之，就是谁处于此位置，则在双方操作正确的情况下必败。
N点：必胜点，处于此情况下，双方操作均正确的情况下必胜。

5.必胜点和必败点的性质：
1、所有终结点是 必败点 P 。（我们以此为基本前提进行推理，换句话说，我们以此为假设）
2、从任何必胜点N 操作，至少有一种方式可以进入必败点 P。
3、无论如何操作，必败点P 都只能进入 必胜点 N。

Sprague-Grundy定理（SG定理）

1.SG值：一个不等于它的后继点的SG值的且大于等于零的最小整数。
后继点：也就是按照题目要求的走法（比如取石子可以取的数量，方法）能够走一步达到的那个点。

挑程里对SG值的解释：
除任意一步所能转移到的子局面的SG值以外的最小非负整数。

从这可以看出这里对SG的定义是递归定义的。

2.SG的作用
通过递归求出每一个局面为胜态还是败态 若sg[x] = 0,那么x是败态

3.总堆的SG函数值等于各个堆的SG函数值的Nim和（异或和）。Bouton定理就是Sprague-Grundy定理在Nim游戏中的直接应用，因为单堆的Nim游戏 SG函数满足 SG(x) = x。

SG函数

1.mex(minimal excludant)运算：表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。里面存放的是该点后继点的SG值的集合。

对于任意状态 x ， 定义 SG(x) = mex(S),其中 S 是 x 后继状态的SG函数值的集合。如 x 有三个后继状态分别为 SG(a),SG(b),SG(c)，那么SG(x) = mex{SG(a),SG(b),SG(c)}。 这样 集合S 的终态必然是空集，所以SG函数的终态为 SG(x) = 0,当且仅当 x 为必败点P时。

【实例】取石子问题

有1堆n个的石子，每次只能取{ 1, 3, 4 }个石子，先取完石子者胜利，那么各个数的SG值为多少？

SG[0]=0，f[]={1,3,4},

x=1 时，可以取走1 - f{1}个石子，剩余{0}个，所以 SG[1] = mex{ SG[0] }= mex{0} = 1;

x=2 时，可以取走2 - f{1}个石子，剩余{1}个，所以 SG[2] = mex{ SG[1] }= mex{1} = 0;

x=3 时，可以取走3 - f{1,3}个石子，剩余{2,0}个，所以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1;

x=4 时，可以取走4- f{1,3,4}个石子，剩余{3,1,0}个，所以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2;

x=5 时，可以取走5 - f{1,3,4}个石子，剩余{4,2,1}个，所以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3;

以此类推…..

x 0 1 2 3 4 5 6 7 8….

SG[x] 0 1 0 1 2 3 2 0 1….

由上述实例我们就可以得到SG函数值求解步骤，那么计算1~n的SG函数值步骤如下：

1、使用 数组f 将 可改变当前状态 的方式记录下来。

2、然后我们使用 另一个数组 将当前状态x 的后继状态标记。

3、最后模拟mex运算，也就是我们在标记值中 搜索 未被标记值 的最小值，将其赋值给SG(x)。

4、我们不断的重复 2 - 3 的步骤，就完成了 计算1~n 的函数值。

实例选自：https://www.cnblogs.com/ECJTUACM-873284962/p/6921829.html

模板

//f[N]:可改变当前状态的方式，N为方式的种类，f[N]要在getSG之前先预处理
//SG[]:0~n的SG函数值
//S[]:为x后继状态的集合
int f[N],SG[MAXN],S[MAXN];
void  getSG(int n){
    int i,j;
    memset(SG,0,sizeof(SG));
    //因为SG[0]始终等于0，所以i从1开始
    for(i = 1; i <= n; i++){
        //每一次都要将上一状态 的 后继集合 重置
        memset(S,0,sizeof(S));
        for(j = 0; f[j] <= i && j <= N; j++)
            S[SG[i-f[j]]] = 1;  //将后继状态的SG函数值进行标记
        for(j = 0;; j++) 
            if(!S[j]){   //查询当前后继状态SG值中最小的非零值
                SG[i] = j;
                break;
            }
    }
}
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

eg.HDU 1848 Fibonacci again and again
http://acm.hdu.edu.cn/showproblem.php?pid=1847

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll fi[100], SG[1010], S[1010];

int init(){
    fi[0] = fi[1] = 1;
    for(int i=2; i <= 100; i++){
        fi[i] = fi[i-1] +fi[i-2];
        if(fi[i] > (1LL << 13)){
            return i;
        }
    }
}

void  getSG(int n, int t){
    int i,j;
    memset(SG,0,sizeof(SG));
    //因为SG[0]始终等于0，所以i从1开始
    for(i = 1; i <= n; i++){
        //每一次都要将上一状态 的 后继集合 重置
        memset(S,0,sizeof(S));
        for(j = 0; fi[j] <= i && j <= t; j++)
            S[SG[i-fi[j]]] = 1;  //将后继状态的SG函数值进行标记
        for(j = 0;; j++)
            if(!S[j]){   //查询当前后继状态SG值中最小的非零值
                SG[i] = j;
                break;
            }
    }
}

int main(){
    int n, m, p, t;
    t = init();
    getSG(1000, t);
    while(scanf("%d%d%d", &n, &m, &p), n||m||p){
        if(SG[n] ^ SG[m] ^ SG[p])//注意^和==的优先级 == 优先于 ^ 因为优先级白白wa了n遍
            printf("Fibo\n");
        else
            printf("Nacci\n");
    }
    return 0;
}

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
 

一.巴什博奕（Bash Game）（同余理论）

定义：只有 一堆 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）的倍数，就能最后获胜。
这个游戏还可以有两种变相的玩法：
1.减法博弈
两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。
2.初始状态下有石子n个，除最后一次外其他每次取物品个数必须在[p，q]之间，最后一次取硬币的人输。（HDU 2897 邂逅明下）
这题状态稍微复杂一些，并且胜负条件与之前相反，一般bash博弈里每次取个数可以看作在[1,m]之间，胜负手判断为 n % (1+m)，因此我们可以猜想每次取[p,q]的胜负手判断为 n % (p+q)，通过验证猜想我们可以发现如下策略：

1**.n=k∗(p+q)时，先手第一次取 q 个，随后的回合若后手取 x 个，先手再取 p+q−x个，那么最后就会留给后手 p 个，先手胜**。
2.n=k∗(p+q)+s时，则要分情况考虑：
若 s 在[1,p]之间，先手取 x，后手可以取 p+q−x，最后留给先手 s 个，后手胜；
若 s 在(p,p+q)之间，先手任取 x 个 (1≤s−x

#include<cstdio>
using namespace std;

int main(){
    int t, a, b;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &a, &b);
        if(a%(b+1) == 0)
            printf("second\n");
        else
            printf("first\n");
    }
    return 0;
}

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

#include<cstdio>
using namespace std;

int main(){
    int ans, s;
    while(scanf("%d%d", &ans, &s)!=EOF){
        if(ans % (s+1) == 0)
            printf("-1\n");
        else{
            printf("%d\n", ans%(s+1));
        }
    }
    return 0;
}

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

2.HDU4764 Stone
http://acm.hdu.edu.cn/showproblem.php?pid=4764
题目大意：Tang和Jiang轮流写数字，Tang先写，每次写的数x满足1<=x<=k，Jiang每次写的数y满足1<=y-x<=k，谁先写到不小于n的数算输。
不能写到n 所以先写到n-1的就能赢~

using namespace std;

int main(){
    int n, k;
    while(~scanf("%d%d", &n, &k) && (n+k)!=0){
        if((n - 1) % (k+1) == 0)
            puts("Jiang");
        else
            puts("Tang");
    }
    return 0;
}
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

3.HDU 2897 邂逅明下（变种2）
http://acm.hdu.edu.cn/showproblem.php?pid=2897

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, p, q, s;
    while(~scanf("%d%d%d", &n, &p, &q)){
        if(n%(p+q) == 0){
            puts("WIN");
        }
        else{
            s = n % (p + q);
            if(s <= p)
                puts("LOST");
            else
                puts("WIN");
        }
    }
    return 0;
}

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

二.尼姆博弈（Nimm Game）（异或理论）

定义：有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。
以三堆物品为例：我们用（ak, bk, ck）（ak ≤ bk ≤ ck,k=0，1，2，…,n)表示三堆物品的数量并称其为局势，无论谁面对局势（0，0， 0），都已经输了，这种局势我们称为奇异局势。

奇异局势有如下三条性质：

1。任何自然数都包含在一个且仅有一个奇异局势中。

2。任意操作都可将奇异局势变为非奇异局势。

3。采用适当的方法，可以将非奇异局势变为奇异局势。

本题（0，n，n）也是一个奇异局势，只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情形。
计算机算法里面有一种叫做按位模2加，也叫做异或的运算，我们用符号（+）表示这种运算。这种运算和一般加法不同的一点是1+1=0。先看（1，2，3）的按位模2加的结果：

1 =二进制01
2 =二进制10
3 =二进制11 （+）
———————
0 =二进制00 （注意不进位）

对于奇异局势（0，n，n）也一样，结果也是0。

任何奇异局势（a，b，c）都有a（+）b（+）c =0。

 

  
1
  
2
  
3
  
4
 

如果我们面对的是一个非奇异局势（a，b，c），要如何变为奇异局势呢？假设 a < b < c,我们只要将c变为 a（+）b,即可,因为有如下的运算结果: a（+）b（+）(a（+）b)=(a（+）a)（+）(b（+）b)=0（+）0=0。要将c 变为a（+）b，只要从 c中减去 c-（a（+）b）即可。

例1。（14，21，39），14（+）21=27，39-27=12，所以从39中拿走12个物体即可达到奇异局势（14，21，27）。

例2。（55，81，121），55（+）81=102，121-102=19，所以从121中拿走19个物品就形成了奇异局势（55，81，102）。

例3。（29，45，58），29（+）45=48，58-48=10，从58中拿走10个，变为（29，45，48）。

例4。我们来实际进行一盘比赛看看：
    甲:(7,8,9)->(1,8,9)奇异局势
    乙:(1,8,9)->(1,8,4)
    甲:(1,8,4)->(1,5,4)奇异局势
    乙:(1,5,4)->(1,4,4)
    甲:(1,4,4)->(0,4,4)奇异局势
    乙:(0,4,4)->(0,4,2)
    甲:(0.4,2)->(0,2,2)奇异局势
    乙:(0,2,2)->(0,2,1)
    甲:(0,2,1)->(0,1,1)奇异局势
    乙:(0,1,1)->(0,1,0)
    甲:(0,1,0)->(0,0,0)奇异局势
    甲胜。

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

以上步骤转载自：https://www.cnblogs.com/kuangbin/archive/2011/08/28/2156426.html
1. 令 s = a1^a2^a3….^an(^符号表示异或运算)
2.若 s = 0,则此局面为败态，否则为胜态
3.无论是胜态还是败态，当从一个石堆拿走一些石头（即改变一个ai，改变量大于等于1），一定会发生胜态和败态的转变

当他与sg结合， 我们发现sg异或和为0的状态也是败态，否则胜态。

结论就是：把每堆物品数将其转化为二进制形式并全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜。
代码模板

bool nimu(int x){
    int d, t;
    t = 0;
    for(int i=0; i<n; i++){
        scanf("%d", &d);
        t ^= d;
    }
    if(t == 0)  printf("后手必胜\n");
    else        printf("先手必胜\n")；
}

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

三.威佐夫博弈（Wythoff’s Game）（黄金分割）

有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利。
这里的必输局势：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）
直接说结论了，若两堆物品的初始值为（x，y），且x < y，则令z=y-x；

记w=（int）[（（sqrt（5）+1）/2）*z ]；

若w=x，则先手必败，否则先手必胜。

其中出现了黄金分割数（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，bj+1 = aj+1+ j + 1，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异局势。

代码模板

int Wgame（int a,int b)
{
    a=min(a,b);
    b=max(a,b);//先交换大小位置
    int k=b-a;
    double path=(sqrt(5.0)+1.0)/2;
    if(a==int(path*k) return 1;
    return 0;
}
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

以下转自：https://blog.csdn.net/qq_15714857/article/details/49691585

Ferguson游戏

Description

Initial

有两个盒子，一个装有 m 颗糖，一个装有 n 颗糖，表示为 (m, n) .

Step

每次清空一个盒子，将另一个盒子里的糖转移一些过来，并保证两个盒子至少各有一颗糖。

Win

最后进行转移糖者胜，无法转移糖者败。
Solve

m, n 都为奇数，先手败；m, n 至少一个为偶数，先手胜。
Proof

显然，初始状态为(1, 1)，先手必败；

设 max(m, n) = 2，即初始状态为 (1, 2)，(2, 1) 或 (2, 2)，对于 (1, 2)，(2, 1) 先手可以把 1 清空，然后将 2 分为 (1, 1) ，先手胜；对于 (2, 2) ，先手可以把其中一个 2 清空，然后将另一个 2 分为 (1, 1) ，先手胜。符合结论。

设 max(m, n) < k 均符合结论，当 max(m, n) = k ：

设 m 与 n 至少一个为偶数（假设m是偶数），则将 n 清空，把 m 分为两个奇数 (a, b) ，由于max(a, b) < k ，因此(a, b) 必败，(m, n) 必胜（利用规则2）；

设 m 与 n 均为奇数，则只能把其中一个数分为一个奇数 a ，一个偶数 b ，由于max(a, b) < k ,因此对于任何的方式分解出的(a, b) 均必胜，(m, n) 必败（利用规则1）；

故 max(m, n) = k 符合结论。

故对于任意 (m, n) 结论成立。

chomp!游戏
–0
Description

Initial

 

  
1
  
2
 

有一个 m * n 的棋盘，棋盘的每一个格子用(x, y)表示，最左下角是(1, 1)，最右上角是(m, n) ；

Step

 

  
1
  
2
 

每次可以拿走一个方格，并拿走该方格右边与上边的所有方格。

Win

 

  
1
  
2
 

谁拿到(1, 1)谁败。
Solve

当 m = n = 1，先手败；除此之外，先手均有必胜策略（先手胜）。
Proof

反证法：

假设后手能取得胜利，那么先手可以第一步拿走(m, n)，若后续回合内后手通过拿走(x, y)达到了必胜状态，先手均可以第一步就拿走(x, y)来达到必胜状态。
故不存在后手必胜状态。

由于无法给出构造性证明，所以只能证明先手必胜，而不能给出广义的必胜策略。

约数游戏

Description

Initial

桌上有 n 个数字：1~n。

Step

两人轮流在选择一个桌上的数 x ，然后将 x 与 x 的约数都拿走。

Win

拿去最后一个数的人胜出（无法选择数字的人失败）。
Solve

先手有必胜策略。（先手胜）
Proof

这个游戏是 chomp! 的思想的应用。

假设后手能取得胜利，那么先手可以第一步拿走 1，若后续回合内后手通过拿走 x 达到了必胜状态，先手均可以第一步就拿走 x 来达到必胜状态。

练习题：
POJ 2234 Matches Game
HOJ 4388 Stone Game II
POJ 2975 Nim
HOJ 1367 A Stone Game
POJ 2505 A multiplication game
ZJU 3057 beans game
POJ 1067 取石子游戏
POJ 2484 A Funny Game
POJ 2425 A Chess Game
POJ 2960 S-Nim
POJ 1704 Georgia and Bob
POJ 1740 A New Stone Game
POJ 2068 Nim
POJ 3480 John
POJ 2348 Euclid’s Game
HOJ 2645 WNim
POJ 3710 Christmas Game
POJ 3533 Light Switching Game
kuangbin的博弈专项
http://www.cnblogs.com/kuangbin/category/319084.html

可能两者有重复~喵 都是我从网上找的相关练习题~