博弈论（取石子）
取石子：
取石子游戏是一个古老的博弈游戏，据说是发源于中国，它是组合数学领域的一个经典问题。它有许多不同的玩法，基本上是两个玩家，玩的形式是轮流抓石子，胜利的标准是抓走了最后的石子。
玩家设定： 先取石子的是玩家A，后取石子的是玩家B。
经典的三种玩法：
一、Bash Game，有1堆含n个石子，两个人轮流从这堆物品中取物，规定每次至少取1个，最多取m个。取走最后石子的人获胜。
二、Nimm Game，有k堆各n个石子，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限。取走最后石子的人获胜。
三、Wythoff Game，有2堆各n个石子，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取1个，多者不限。取走最后石子的人获胜。
平衡状态的概念： 引入一个概念，平衡状态，又称作奇异局势。当面对这个局势时则会失败。任意非平衡态经过一次操作可以变为平衡态。每个玩家都会努力使自己抓完石子之后的局势为平衡，将这个平衡局势留给对方。因此，玩家A能够在初始为非平衡的游戏中取胜，玩家B能够在初始为平衡的游戏中取胜。
玩法一（1堆n个石子每次最多取m个）： 最后一个奇异局势是n=(0)。一种奇异局势是，n=(m+1)，那么无论我取走多少个，对方都能够一次取走剩余所有的物品取胜。
奇异局势的判定：
一般的奇异局势是n=(m+1)*i，其中i为自然数，即n%(m+1)=0，面对这种情况无论我怎么取，对方总可以将其恢复为n%(m+1)=0，一直到n=(m+1)局势。
玩家的策略：
就是把当前面对的非奇异局势变为奇异局势留给对方。如果当前的石子个数为(m+1)*i+s，那么就将s个石子取走，使其达到奇异局势。
玩法二（k堆石子每次只从1堆取）： 最后一个奇异局势是(0,0...,0)。另一个奇异局势是(n,n,0...0)，只要对手总是和我拿走一样多的物品，最后会面对(0,0...,0)。
奇异局势的判定：
对于一个普通的局势，如何判断其是不是奇异局势？对于一个局势(s1,s2,...sk)，对所有石子个数做位的异或运算，s1^s2^s3^...^sk，如果结果为0，那么局势(s1,s2,...sk)就是奇异局势（平衡），否则就不是（非平衡）。
从二进制位的角度上说，奇异局势时，每一个bit位上1的个数都是偶数。
玩家的策略：
就是把面对的非奇异局势变为奇异局势留给对方。也就是从某一堆取出若干石子之后，使得每一个bit位上1的个数都变为偶数，这样的取法一般不只有一种。可以将其中一堆的石子数变为其他堆石子数的位异或运算的值（如果这个值比原来的石子数小的话）。
玩法三（2堆石子每次从一或两堆取一样数目的石子）： 最后一个奇异局势是(0,0)。紧接着的奇异局势有(1,2),(3,5),(4,7),(6,10)......
现在把它们看成一个奇异局势组成的序列(0,0),(1,2),(3,5),(4,7),(6,10)......
奇异局势的判定：
我们会发现这个序列的规律，设序列第k个奇异局势元素为(Ak,Bk)，k为自然数。那么，初始条件k=0时是，A0=B0=0，递推关系为下一个奇异局势的Ak是未在前面出现过的最小自然数，且Ak = Bk + k。
上面发现了奇异局势的递推公式，那么给出一个局势，如何判断其是否是奇异局势呢？
这个奇异局势的序列的通项公式可以表示为：
Ak = [k*(1+sqrt(5.0)/2]
Bk = Ak + k
其中k=0，1，2，...,n ，方括号表示int取整函数。
有了这个通项式子，逆向的，对于某一个局势，只需要判断其A是否是黄金分割数的某个k的倍数，然后再确认B是否等于A+k即可。
玩家的策略：
就是把面对的非奇异局势变为奇异局势留给对方。也就是说，玩家必须知道临近的奇异局势是什么，然后把当前局势变成奇异局势。
来源：https://blog.csdn.net/ojshilu/article/details/16812173