（一）巴什博奕（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）的倍数，就能最后获胜。 这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十 个，谁能报到100者胜。
（二）威佐夫博奕（Wythoff Game）：
问题描述： 有两堆各若干个物品，两个人轮流从某一堆或同 时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
问题解决思路:
这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，…,n)表示 两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们 称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6， 10）、（8，13）、（9，15）、（11，18）、（12，20）。
可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k，奇异局势有 如下三条性质：
1。任何自然数都包含在一个且仅有一个奇异局势中。
证明： 由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak + k > ak -1 + k-1 = bk-1 > ak-1 。所以性质1。成立。
2。任意操作都可将奇异局势变为非奇异局势。
证明： 事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其 他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由 于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
3。采用适当的方法，可以将非奇异局势变为奇异局势。
转化方式：
假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了 奇异局势（0，0）；如果a = ak ，b > bk，那么，取走b – bk个物体，即变为奇异局 势；如果 a = ak ， b < bk ,则同时从两堆中拿走 ak – ab – ak个物体,变为奇异局 势（ ab – ak , ab – ak+ b – ak）；如果a > ak ，b= ak + k,则从第一堆中拿走多余 的数量a – ak 即可；如果a < ak ，b= ak + k,分两种情况，第一种，a=aj （j < k） ,从第二堆里面拿走 b – bj 即可；第二种，a=bj （j < k）,从第二堆里面拿走 b – a j 即可。
从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜 ；反之，则后拿者取胜。
那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：
ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，…,n 方括号表示取整函数)
奇妙的是其中出现了黄金分割数（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，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异 局势。
公式的推导过程：http://baike.haosou.com/doc/1561844-1650988.html
公式的推导过程中出现了一个叫做 Beatty序列 的东西哦！ 相对于威佐夫博弈本身， 这个东西更值得学习一下。 链接：http://www.java3z.com/cwbwebhome/article/article19/res046.html
（三）尼姆博奕（Nimm Game）：
问题描述： 有三堆各若干个物品，两个人轮流从某一堆取任意多的 物品，规定每次至少取一个，多者不限，最后取光者得胜。
问题解决思路： 这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，首 先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是 （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
1（+）2（+）3 = 0；
对于奇异局势（0，n，n）也一样，结果也是0。
任何奇异局势（a，b，c）都有a（+）b（+）c =0。
如果我们面对的是一个非奇异局势（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，4 5，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：今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根， 可将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
定义：若所有火柴数异或为0，则该状态被称为利他态，用字母T表示；否则， 为利己态，用S表示。 [定理1]：对于任何一个S态，总能从一堆火柴中取出若干个使之成为T态。
证明： 若有n堆火柴，每堆火柴有A(i)根火柴数，那么既然现在处于S态， c = A(1) xor A(2) xor … xor A(n) > 0;
把c表示成二进制，记它的二进制数的最高位为第p位，则必然存在一个A(t),它二进制的第p位也是1。（否则，若所有的A(i)的第p位都是0，这与c的第p位就也为0矛盾）。
那么我们把x = A(t) xor c,则得到x < A(t).这是因为既然A(t)的第p位与c的第p位同为1,那么x的第p位变为0,而高于p的位并没有改变。所以x < A(t).而 A(1) xor A(2) xor … xor x xor … xor A(n) = A(1) xor A(2) xor … xor A(t) xor c xor … xor A(n) = A(1) xor A(2) xor… xor A(n) xor A(1) xor A(2) xor … xor A(n) = 0
这就是说从A(t)堆中取出 A(t) – x 根火柴后状态就会从S态变为T态。 证毕!
[定理2]：T态，取任何一堆的若干根，都将成为S态。
证明：
反证法： 若 c = A(1) xor A(2) xor … xor A(i) xor … xor A(n) = 0； c’ = A(1) xor A(2) xor … xor A(i’) xor c xor … xor A(n) = 0;
则有 c xor c’ = A(1) xor A(2) xor … xor A(i) xor … xor A(n) xor A(1) xor A(2) xor … xor A(i’) xor c xor … xor A(n) = A(i) xor A(i’) =0
进而推出A(i) = A(i’)，这与已知矛盾。所以命题得证。
[定理 3]：S态，只要方法正确，必赢。
证明：
最终胜利即由S态转变为T态，任何一个S态，只要把它变为T态，（由定理1，可以把它变成T态。）对方只能把T态转变为S态(定理2)。这样，所有S态向T态的转变都可以有己方控制，对方只能被动地实现由T态转变为S态。故S态必赢。
[定理4]：T态，只要对方法正确，必败。
证明： 由定理3易得。 接着来解决第二个问题。 定义：若一堆中仅有1根火柴，则被称为孤单堆。若大于1根，则称为充裕堆。 定义：T态中，若充裕堆的堆数大于等于2，则称为完全利他态，用T2表示；若充裕堆的堆数等于0，则称为部分利他态，用T0表示。 孤单堆的根数异或只会影响二进制的最后一位，但充裕堆会影响高位（非最后一位）。一个充裕堆，高位必有一位不为0，则所有根数异或不为0。故不会是T态。
[定理5]：S0态，即仅有奇数个孤单堆，必败。T0态必胜。
证明：
S0态，其实就是每次只能取一根。每次第奇数根都由己取，第偶数根都由对 方取，所以最后一根必己取。败。同理, T0态必胜#
[定理6]：S1态，只要方法正确，必胜。
证明：
若此时孤单堆堆数为奇数，把充裕堆取完；否则，取成一根。这样，就变成奇数个孤单堆，由对方取。由定理5，对方必输。己必胜。
[定理7]：S2态不可转一次变为T0态。
证明：
充裕堆数不可能一次由2变为0。得证。
[定理8]：S2态可一次转变为T2态。
证明：
由定理1，S态可转变为T态，态可一次转变为T态，又由定理6，S2态不可转一次变为T0态，所以转变的T态为T2态。
[定理9]：T2态，只能转变为S2态或S1态。
证明：
由定理2，T态必然变为S态。由于充裕堆数不可能一次由2变为0，所以此时的S态不可能为S0态。命题得证。
[定理10]：S2态，只要方法正确，必胜.
证明：
方法如下：
1） S2态，就把它变为T2态。（由定理8）
2） 对方只能T2转变成S2态或S1态（定理9） 若转变为S2, 转向1） 若转变为S1, 这己必胜。（定理5） [定理11]：T2态必输。 证明：同10。 综上所述，必输态有： T2,S0 必胜态： S2,S1,T0. 两题比较： 第一题的全过程其实如下： S2->T2->S2->T2-> …… ->T2->S1->T0->S0->T0->……->S0->T0(全0) 第二题的全过程其实如下： S2->T2->S2->T2-> …… ->T2->S1->S0->T0->S0->……->S0->T0(全0) 下划线表示胜利一方的取法。 是否发现了他们的惊人相似之处。 我们不难发现(见加黑部分)，S1态可以转变为S0态（第二题做法），也可以转变为 T0（第一题做法）。哪一方控制了S1态，他即可以有办法使自己得到最后一根（转变为 T0）,也可以使对方得到最后一根（转变为S0）。 所以，抢夺S1是制胜的关键！ 为此，始终把T2态抛给对方，将使对方处于被动状态（是对方受控于自己），他不得不把局势转化到S2.
题目练习及代码详解：http://www.cnblogs.com/acm1314/p/4643256.html
-----------------------------------------------------------------------------------------------------
详解SG函数。 所有的公平组合博弈都可以抽象成下列 模型:
有向无环图,某个点上有一枚棋子,双方轮流
将棋子沿某条有向边移动,无法移动者为负
其中,一个点表示一个局面,而一条有向边则
表示一种可行操作。
公平组合博弈问题解法:
往往可以从终局面出发,逆向递推,求出任意局面是P局面还是N局面但如果游戏是一系列子游戏的组合时,局面的数量非常庞大,上述方法就会变得十分低效。
然而SG函数可以解决所有公平双人博弈。
SG函数
定义有向图每个顶点的SG函数值
g(x)=mex{g(y)|y是x的后继}
若g(x)=0,则x为P局面
若g(x)>0,则x为N局面
简略证明:
终局面g(x)=0
若g(x)>0,则至少有一个后继y满足g(y)=0
若g(x)=0,则任何后继y都有g(y)>0
mex函数mex函数： 定义函数mex,表示取最小的不属于该集合的非负整数
例:
mex{}=0
mex{0,1,2,4}=3
mex{2,3}=0
游戏的“和”
设G 1 ,G 2 ,...,G n 是n个公平组合博弈游戏
定义G为G 1 ,G 2 ,...,G n 的和:G的移动规则为
任选一个子游戏G i 操作一次
则G的SG函数值
g(G)=g(G 1 )⊕g(G 2 )⊕...⊕g(G n )
注:⊕为异或符号
若g(G)=0,则游戏G后手必胜
若g(G)>0,则游戏G先手必胜
证明思路:证明下列三条即可
终局面SG函数值为0
若SG函数值不为0,则一定存在一个操作使得新局
面的SG函数值为0
若SG函数值为0,则任何操作都会使新局面的SG值
大于0
SG函数总结：有了SG函数这一工具,我们可以把这一类复杂的游戏分解成若干个简单的子游戏,然后依次求出每个子游戏的SG函数值,最后异或起来,就可以判断原游戏先手胜还是后手胜的问题了！
举例说明SG函数：
现在有N 堆数目各不相同的石子， 两人进行取石子游戏。 游戏规则是， 每次只能在一堆里面取石子， 且每次只能取 1， 2，或 3个石子。 请判断是先手必胜还是先手必败。
解题思路：
先对每堆石子进行巴什博弈处理 （因为取子的顺序并不会影响博弈结果）。 然后每堆石子数目都不会超过三个。例如： 如果每堆石子数目分别为： 1， 2， 3， 4， 5， 6， 7， 8， 9，，，，，，
进行过巴什博弈后， 将成为： 1， 2， 3， 0， 1， 2， 3， 0， ，， ，，， 然后对这些数进行异或求“和” 即可！ 。 （因为经过巴什博弈处理后， 每堆石子数目都不会超过 3 。 即：相当与每次可以取任意个石子。 把这种博弈成功进行转化成了尼姆博弈）
然而如果你求一下SG函数值就会惊奇的发现。 SG的函数值刚好为： 1， 2， 3， 0， 1， 2， 3，，，，。 当然这不仅仅是偶然！ 如： 每次只能取1， 2， 5， 个石子。 该如何进行博弈呢？。 显然第一步已经不能进行巴什博弈啦 ，因为巴什博弈的条件已不符合。但是仔细看一下SG函数的定义就可以发现， 这时仍然符合SG函数， 所以仍然可以通过求SG函数值， 然后进行异或求“和”求出结果。
博弈题目练习及代码详解： http://www.cnblogs.com/acm1314/p/4643256.html