巴什博弈
一般对于这类博弈类的题目，都有一个条件：“两人足够聪明”或者”两人没有失误”
硬币游戏
想必大家小时候都有玩过这么一个游戏
两个人博弈，每个人每次可以拿1-3枚硬币，轮流拿，总共n枚硬币，最后取光者胜，这就是一个很典型的巴什博弈
对于上面的取硬币问题，我们举三个例子
不妨设甲是先手，乙是后手
- 总共4枚硬币，甲无论怎么取都是输
- 总共5枚硬币，甲只要第一次取1枚硬币，乙无论怎么取，甲都是赢
- 总共4n枚硬币，甲无论怎么取都是输，甲每次取x枚，乙接着取4-x枚，乙就一定能赢
巴什博弈
巴什博弈(Bash Game):只有一堆n个物品，两个人轮流从这堆物品中取物，规
定每次至少取一个，最多取m个。最后取光者得胜。
显然，如果\(n=m+1\)，那么由于一次最多只能取\(m\)个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果\(n=(m+1)*r+s\),(\(r\)为任意自然数，\(s\le m\)),那么先取者要拿走\(s\)个物品，如果后取者拿走\(k（k\le m )\)个，那么先取者再拿走\(m+1-k\)个，结果剩下\((m-1)\times (r-1)\)个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下\(1. （m+1）\)的倍数，就能最后获胜。
巴什博弈博弈论里面最简单的一种形式。以下题目利用巴什博弈可以轻松解决：
-
http://acm.hdu.edu.cn/showproblem.php?pid=1846 （brave game）
-
http://acm.hdu.edu.cn/showproblem.php?pid=2147 （kiki’s game）
-
http://acm.hdu.edu.cn/showproblem.php?pid=2149 （public sale）
下面介绍分析此类题目的通用方法：P/N分析：
P点： 即必败点，某玩家位于此点，只要对方无失误，则必败；
N点： 即必胜点，某玩家位于此点，只要自己无失误，则必胜。
以上题目均可以通过P/N分析法来解决。
例如上面的硬币问题，4的倍数点都是P点，其他点都是N点
三个定理
一、所有终结点都是必败点P（上游戏中，轮到谁拿牌，还剩0张牌的时候，此人就输了，因为无牌可取
二、所有一步能走到必败点P的就是N点
三、通过一步操作只能到N点的就是P点
代码实现
bool Bash_Game (int n,int m){//判断先手是否必赢
if(n%(m+1)==0)return false;
else return true;
}
本文参照：https://www.cnblogs.com/java20130726/archive/2013/05/24/3218207.html