目录：
PN分析
巴什博弈
威佐夫博弈
尼姆博弈
斐波那契博弈
一、PN分析
设：
必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。
必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。
关于博弈，最常见的是构建PN图进行分析
性质：
1 、每个图的末状态均为必败点P
2、所有能够一步到达必败点的都是必胜点N
3、 所有能够一步到达必胜点的都是必败点 P
步骤：
步骤1:将所有终结位置标记为必败点（P点）；
步骤2: 将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点）
步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点） ，则将该点标记为必败点（P点） ；
步骤4: 如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。
例题引入：HDU2147http://acm.hdu.edu.cn/showproblem.php?pid=2147
题意：在一个n*m的棋盘内，从(1,m)点出发，每次可以进行的移动是：左移一，下移一，左下移一。然后kiki每次先手，最后走投无路的一方输。
解法：由题意已知当走到点(n,1)时已经无路可走了，因此点(n,1)为终结点，也就是必输点（P点），由这点便可根据前面所述的步骤推断出其他点。
例如当n=7,m=7时，画出PN图如下：
可以发现规律该PN总是以一行"PNPNPN..."，一行"NNNNN..."的规律排列，故仅当n,m为奇数时，点(1,m)才为必输点(P点)，其他情况均为必胜点(N点）。
代码：
int main(){ int n,m; while(cin>>n>>m){ if(n==0&&m==0) break; if(n%2==1&&m%2==1) cout<<"What a pity!"<<endl; else cout<<"Wonderful!"<<endl; } return 0; }
二、巴什博弈
两个顶尖聪明的人在玩游戏，有一堆n个石子，每次每个人只能取[1,m]个石子，拿到最后一个石子的人获胜。
讨论：
情况1：当 n<=m 时，先手肯定能一次取完所有石子，过先手必胜(N点)；
情况2：当 n=m+1 时，因为每次只能取[1,m]个石子，故不管先手取多少个石子，取后都必定使剩下石子数<=m，即情况1的情形，故此状 态下先手为必输点(P点);
情况3：当 m+2<= n <=2*m+1时，每次都可以取[1,m]内的对应石子数，使剩下石子数变成m+1，即情况2，故此状态下先手为必胜点(N点）;
情况4：当 n=2*m+2时，与情况2类似，无论怎么取都会使剩下石子数变成情况3,故此状态下先手为必败点(P点);
......
由此我们大概已经看出规律了，当n=k*(m+1）时，先手必败，其他情况下先手必胜。
例题：HDU1846 http://acm.hdu.edu.cn/showproblem.php?pid=1846
代码：
int main(){ int t; cin>>t; int n,m; while(t--){ cin>>n>>m; if(n%(m+1)==0) cout<<"second"<<endl; else cout<<"first"<<endl; } return 0; }
三、威佐夫博弈
有两堆各若干个石子，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的石子，规定每次至少取一个，至多不限，最后取光者胜利。
讨论：
设两个堆石子数量为(a, b)
首先由题目给的信息，可以先排除一些特殊的情况：
1、a,b有一个为0时，可以一次取完，所以先手必胜;
2、a=b，且a,b不为0时，也可以一次取完，所以先手必胜;
排除以上情况后再进行下一步的讨论
情况1：a=0,b=0时，已经被取完了，所以先手必败;
情况2：接下来的状态便是 (1,2) ，你会发现这种情况下，无论你怎么取，都会使剩下的石子变成最开始排除的那两种情况，故在此状态下先手是必败的，我们称这种情况为奇异点；
情况3：接下来的点(a, b)只要存在其中一个为1或2时，先手都可以将其转变成情况2，即把对手变成必败的情况，因此此状态下先手必胜；
情况4：排除情况3的点后，最基本的点为（3，4），但是我们发现（3,4）两堆同时取2时可以变成情况2, 所以此时先手也是必胜的，归结到情况3，接下来讨论（3, 5），我们发现无论先手怎么取，后手都是必胜的情况，因此此状态下为先手必败，也为奇异点;
.......
继续讨论我们可以找出奇异点：
第一种（0，0）
第二种（1，2）
第三种（3，5）
第四种 (4 ，7）
第五种（6，10）
第六种 (8，13）
第七种 (9 ， 15）
第八种 (11 ，18）
...
分析可以得到规律
1、两堆石子的差值是递增的，分别是0,1,2,3,4,5,6,7......n
2、我们用数学方法分析发现这些局势的第一个值是未在前面出现过的最小的自然数。
继续分析我们会发现，每种奇异点的第一个值(这里假设第一堆数目小于第二堆的数目)总是等于当前局势的差值乘上1.618
因此要判断先手的输赢，只要判断 a=(int)1.618*(b-a)（b>=a）即可，精度要求高的时候1.618用 (sqrt(5)+1)/2 代替；
例题：P2252 https://www.luogu.com.cn/problem/P2252
int main() { int a,b; scanf("%lld%lld",&a,&b); if(a>b) swap(a,b); int temp=abs(a-b); int ans=temp*(1.0+sqrt(5.0))/2.0; if(ans==a) printf("0"); else printf("1"); return 0; }
四、尼姆博弈
有若干堆石子，每堆石子的数量是有限的，二个人依次从这些石子堆中拿取任意的石子，至少一个（不能不取），最后一个拿光石子的人胜利。
讨论：
情况1： 只有一堆石子时，先手可以直接取完所有石子，故先手必胜；
情况2：有两堆石子时，假设现在有两堆石子且数量不相同，那么你的最佳选择是取走多的那堆石子中多出来的那几个，使得两堆石子数量相同，这样，不管另一个怎么取，你都可以在另一堆中和他取相同的个数，这样的局面你就是必胜。比如有两堆石子，第一堆有3个，第二堆有5个，这时候你要拿走第二堆的三个，然后两堆就都变成了3个，这时你的对手无论怎么操作，你都可以“学”他，比如他在第一堆拿走两个，你就在第二堆拿走两个，这样你就是稳赢的；
情况3：如果是三堆 ，我们用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情型。
引入L . Bouton在1902年给出的定理：状态（a, b, c）为必败状态当且仅当 a 异或 b 异或 c=0
也就是当Nim和为0时，先手必败，否则必胜（Nim和即所有石子数的异或）
例题：https://vjudge.net/problem/POJ-2234
int main() { ll n,t; while(cin>>n) { ll sum=0; cin>>sum; for(int i=1; i<n; i++) { cin>>t; sum=sum^t; } if(sum==0) cout<<"No"<<endl; else cout<<"Yes"<<endl; } return 0; }
五、斐波那契博弈
有一堆个数为n的石子，游戏双方轮流取石子，满足先手不能在第一次把所有的石子取完之后，每次可以取的石子数介于1到对手刚取的石子数的2倍之间，约定取走最后一个石子的人为赢家。
直接上结论：当石子数为斐波那契数时先手必败（即为1, 2, 3, 5, 8,13, 21...）
具体证明请看这里
例题：HDU2516 http://acm.hdu.edu.cn/showproblem.php?pid=2516
代码：
int main() { fib[1]=1;fib[2]=1; for(int i=3;i<=50;i++) fib[i]=fib[i-1]+fib[i-2],mp[fib[i]]=1; while(scanf("%d",&x)&&x!=0) puts(mp[x]==1?"Second win":"First win"); return 0; }