博弈论问题大致分为，公平组合游戏、非公平组合游戏（绝大多数的棋类游戏）、反常游戏
只需要关注公平组合游戏，反常游戏是公平组合游戏的变形。
以下为公平组合游戏的特征：
1.两个玩家轮流行动且游戏方式一致。
2.两个玩家对状况完全了解
3.游戏一定会在有限步数内分出胜负
4.游戏以玩家无法行动结束
巴什博弈
一共有n颗石头，两个人轮流拿，每次可以拿1~m颗石子，拿到最后一颗石子的人获胜，根据n，m，返回谁赢。
分析：
显然，如果 n = m + 1那么由于一次最多只能取 m 个物品，所以无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，故后者必然取胜。根据这样的规律，我们发现了如何取胜的法则。
如果 n = ( m + 1 ) r + s（r为任意自然数，0 ≤ s ≤ m，那么先取者首先拿走 s个物品，接下来若后取者拿走 k ( 1 ≤ k ≤ m ) 个，那么先取者再拿走 m + 1 − k个，结果剩下 ( m + 1 ) × ( r − 1 )个，以后都保持这样的取法，那么后取者最终会面临 ( m + 1 ) 的局面，而先取者则必然获胜。总之，要保持给对手留下 ( m + 1 )的倍数，最后就一定能获胜。
质数次方版取石子（巴什博弈拓展）
一共有n颗石子，两个人轮流拿
每一轮当前选手可以拿 p 的 k 次方颗石子
当前选手可以随意决定p和k，但是要保证p是质数，k是自然数
拿到最后一颗石子的人获胜。
根据石子的个数返回谁赢
如果先手赢，返回0
如果后手赢，返回1
分析：
任意6的整数倍，它一定不是某一个整数的自然数次方
因为6的整数倍，一定由2和3两个质数组成，那么必然无法由某个整数的自然数次方得到。
因此我们就可以很快的得出结论
如果n为6的倍数，那么后手赢。
如果n不为6的倍数，那么先手赢。
因为当 n 为 6 的整数倍时，无论先手的人拿多少，后手的人都可以使其重新变为6的整数倍（因为1~5都可以拿），因此后手是必赢的。
如果 n 不为 6 的倍数，那么先手的人就可以先把它变为6的倍数，这样先手的人必赢
尼姆博弈
一共有 n 堆石头，两人轮流进行游戏
在每个玩家的回合中，玩家需要选择任何一个非空的石头堆，并从这堆石头中移除任意正数的石头数量
谁先拿走最后的石头就获胜，返回最终谁会获胜
分析：
如果所有的石堆进行异或和，然后再对石堆进行操作。
最后输的人一定是面对异或和等于0的情况，也就是没有石头了。
因此当异或和不为0时，先手赢。当异或和为0时，后手赢
证明：
反尼姆博弈（反常游戏）
一共有n堆石头，两人轮流进行游戏
在每个玩家的回合中，玩家需要选择任何一个非空的石头堆，并从这堆石头中移除任意正数的石头数量
谁先拿走最后的石头就失败，返回最终谁会获胜。
分析：
因为最后的情况是异或和不为0，所以不能直接用尼姆博弈
进行分类讨论
情况一：
情况二：
情况三：
结论：
当石子的个数都为1时，偶数则先手赢，奇数则后手赢。
当遇到其他情况，如果异或和不为0，则先手赢，如果异或和为0，则后手赢
sg函数
图游戏的概念
任何局面都认为是图种的点，每一个局面都可以通过一种行动，走向图中的下一个点，如果当前行动有若干个，那么后继结点就有若干个。最终，必败局面的点认为不再有后继结点。那么公平组合游戏，就可以对应成一张图。
后继结点：该节点在一次操作内能走向的下一个点
sg函数
如下是sg函数返回值的求解方式，俗称mex过程
最终必败点是A，规定sg（A） = 0
假设状态点是B，那么sg（B） = 查看B所有后继结点的sg值，找出其中没有出现过的最小自然数
sg（B）!= 0，那么状态 B 为必胜态，
sg（B）== 0，那么状态 B 为必败态。
证明：
sg函数的定理
如果一个公平组合游戏（总），由若干个独立的公平组合游戏构成（分1，分2，分3·····）那么：
sg（总）= sg（分1）^sg（分2）^sg（分3）……
当数据规模较大时，可以通过打印sg表观察。
如果sg（总）= 0，那么先手就是必败局面。
如果sg（总）!= 0，那么先手就是必胜局面
证明：
sg打表的代码
void bash(int n, int m)
{int* sg = (int*)malloc(sizeof(int)*(n+1));int* appear = (int*)malloc(sizeof(int)*(1000)); //记录出现过的自然数 sg[0] = 0;for (int i=1; i<=n; ++i){memset(appear, 0, sizeof(appear)); //初始化为0，表示都没出现过。for (int j=1; j<=m && i-j>=0; ++j){appear[sg[i-j]] = 1; // 出现过就为1}for (int j=0; j<=i; ++i){if (appear[j] == 0){sg[i] = j;break;}}}
}通过sg打表，如果能找到规律，那就可以用O(1)的过程就可以得到sg(x)。
如果找不到规律，那就只能暴力求解所有的sg值
考试时要根据题目的数据量来决定是否优化
E&D游戏
桌子上有2n堆石子，编号为1,2,3,……2n
其中1,2为一组；3,4为一组；……2n-1和2n为一组
每组可以进行分割操作：
任取一堆石头，将其移走。
从同一组的另一堆石头中取出若干个石子放在被移走的位置，组成新的一堆
操作完成后，组内每堆的石子数必须保证大于0
显然，被分割的一堆的石子数至少要为2
两个人轮流进行分割操作，如果轮到某人进行操作时，所有堆的石子数都为1，判定此人输掉比赛
返回先手能不能赢
分析：
总游戏是对所有的石头进行操作。
分游戏是对一组里的两个石头进行操作
那么本题的就可以计算分游戏的sg值
然后进行异或和求出先手赢还是后手赢。
计算sg[a][b];
注意：本题的数据量很大，一堆石子的个数在1~2*10^9之间，所以要打表找规律求出sg
代码：
# include <stdio.h>
# include <string.h>
int dp[100][100];
int sg(int a, int b) //求sg[a][b]的值
{if (a == 1 && b == 1)return 0;if (dp[a][b] != -1) //如果之前出现过，动态规划 return dp[a][b];int appear[1000];memset(appear, 0, sizeof(appear));if (a > 1){//假设a = 5时//拆为 1 4//2 3//3 2//4 1 for (int l=1, r=a-1; l<a; ++l, --r){appear[sg(l, r)] = 1;}}if (b > 1){for (int l=1, r=b-1; l<b; ++l, --r){appear[sg(l, r)] = 1;}}int ans = 0;for (int i=0; i<1000; ++i)if (appear[i] == 0){ans = i;break;}dp[a][b] = ans;return ans;}int main()
{memset(dp, -1, sizeof(dp));printf("石子数9以内所有组合的sg值\n");printf(" ");for (int i=1; i<=9; ++i){printf(" %d", i);}printf("\n");printf("\n");for (int a=1; a<=9; ++a){printf("%d ",a);for (int b=1; b<a; ++b)printf("X ");for (int b=a; b<=9; ++b){int g = sg(a, b);printf("%d ", g);}printf("\n");}
}打印结果：
找不出规律，于是我们把行列都减一
于是我们可以发现一个规律
该状态的sg值 = （（行 - 1）| （列 - 1）后的值，最低位0的索引）
例如：
sg[2][5] =
（2 - 1） | （5 - 1）= 0001 | 0100 = 0101，最低位0的索引为1。
因此sg[2][5] = 1;（和最上面那个表格对应）
分裂游戏
本题给的数据规模不大，因此可以直接把sg全部暴力解出
但是本题的sg求法很好
注意：
最后结果一定是所有的糖都在最后一个瓶子里，这样才判断输赢
因为选择的三个编号的 i ，j，k为 i < j <= k
所有这就是一个不断把糖豆放到最左边的过程。
分析：
并且本题以一个瓶子为分游戏是不合理的。
因为我们会从一个瓶子里拿出一个糖豆，分裂成两颗糖豆，再放入别的瓶子，因此瓶子和瓶子之间不是独立的，因此不能以一个瓶子作为分游戏
因此我们要以一个糖豆作为分游戏
以把所有的糖豆放到最后的瓶子作为总游戏
以单独的一块糖，双方进行操作，判断输赢。
假设我们把处在编号最大的瓶子里的糖豆设为编号为0（也就是把所有瓶子的编号反一反，方便理解）
因为这个糖豆无法进行操作了，也就是没有后继结点了，所以sg（0） = 0；
注意：
我们在这里是把一颗糖豆作为分游戏，把它分裂成两个糖豆后，相当于这两个糖豆是作为后继结点的分游戏，因此要进行异或求出后继结点。
后继结点的概念：该节点在一次操作内能走向的下一个点
代码：
# include <stdio.h>//这里我们把编号0的瓶子放在最右边
//糖果还是同样的最终全部会放在编号为0的瓶子里
int sg[21]; //假设有20个瓶子 ，说明有20种可能的糖果
int appear[1000];
sg[0] = 0;
int num[100]; //记录每个瓶子里的糖果
void build() //此函数直接把0~20瓶里糖豆的sg值全部求出来，因为相同瓶里的sg值相同
{for (int i=1; i<=20; ++i){memset(appear, -1, sizeof(appear));// i > j >= k for (int j=0; j<i; ++j)for (int k=0; k<=j; ++k)appear[sg[j] ^ sg[k]] = 1;for (int j=0; j<1000; ++j){if (appear[j] == 0){sg[i] = j;break;}}}
} int main()
{n = 20;for (int i=0; i<n; ++i){scanf("%d", &sum[i]);} build();int eor = 0; //所有糖果，每个糖果都是独立游戏，所以把所有糖果的sg值异或起来 for (int i=0; i<n; ++i)if (num[i] % 2 == 1) //因为是对整体进行异或，并且处于同一个瓶子里的糖果sg值一样// 异或后就会为0，因此我们只计算个数为奇数个的糖果sg值 eor = eor ^ sg[i];if (eor == 0){printf("-1 -1 -1\n");printf("0");//零种方法 }else{int cnt = 0; //记录先手必胜的方法数 int a = -1, b = -1, c = -1; //讨论第一步该怎么行动 //要想先手第一步就获胜，那么就是要让sg（总）变为0，这样就是先手必胜的方法。//然后再记录第一步最小的字典序int pos; //记录总的sg值 for (int i=n-1; i>=1; --i){if (num[i] > 0){for (int j = i-1; j>=0; --j)for (int k = j; k>=0; --k){pos = eor ^ sg[i] ^ sg[j] ^ sg[k];//相当于进行第一步之后的sg（总） if (pos == 0)cnt = cnt + 1;if (a == -1){a = i;b = j;c = k;}}}}}}