1.NIM初步
通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。
这游戏看上去有点复杂，先从简单情况开始研究吧。如果轮到你的时候，只剩下一堆石子，那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩，然后对手就输了。如果剩下两堆不相等的石子，必胜策略是通过取多的一堆的石子将两堆石子变得相等，以后如果对手在某一堆里拿若干颗，你就可以在另一堆中拿同样多的颗数，直至胜利。如果你面对的是两堆相等的石子，那么此时你是没有任何必胜策略的，反而对手可以遵循上面的策略保证必胜。如果是三堆石子……好像已经很难分析了，看来我们必须要借助一些其它好用的（最好是程式化的）分析方法了，或者说，我们最好能够设计出一种在有必胜策略时就能找到必胜策略的算法。
定义P-position和N-position两种局面，其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P- position，也就是“后手可保证必胜”或者“先手必败”，现在轮到move的人有必胜策略的局面是N-position，也就是“先手可保证必胜”。
更严谨的定义是：
1.【无法进行任何移动的局面（也就是terminal position）是P-position】；
2.【可以移动到P-position的局面是N-position】；
3.【所有移动都导致N-position】的局面是P-position。(面对局面分为，P屁局面，或N牛逼局面)
按照这个定义，如果局面不可能重现，或者说positions的集合可以进行拓扑排序，那么每个position或者是P-position或者是N-position，而且可以通过定义计算出来。
以Nim游戏为例来进行一下计算。比如说我刚才说当只有两堆石子且两堆石子数量相等时后手有必胜策略，也就是这是一个P-position，下面我们依靠定义证明一下(3,3)是一个P-position。首先(3,3)的子局面（也就是通过合法移动可以导致的局面）有(0,3)(1,3)(2,3)（显然交换石子堆的位置不影响其性质，所以把(x,y)和(y,x)看成同一种局面），只需要计算出这三种局面的性质就可以了。 (0,3)的子局面有(0,0)、(0,1)、(0,2)，其中(0,0)显然是P-position，所以(0,3)是N-position（只要找到一个是P-position的子局面就能说明是N-position）。(1,3)的后继中(1,1)是P-position（因为(1,1)的唯一子局面(0,1)是N-position），所以(1,3)也是N-position。同样可以证明(2,3)是N-position。所以(3,3)的所有子局面都是N-position，它就是P-position。通过一点简单的数学归纳，可以严格的证明“有两堆石子时的局面是P-position当且仅当这两堆石子的数目相等”。
根据上面这个过程，可以得到一个递归的算法——对于当前的局面，递归计算它的所有子局面的性质，如果存在某个子局面是P-position，那么向这个子局面的移动就是必胜策略。当然，可能你已经敏锐地看出有大量的重叠子问题，所以可以用DP或者记忆化搜索的方法以提高效率。但问题是，利用这个算法，对于某个Nim游戏的局面(a1,a2,...,an)来说，要想判断它的性质以及找出必胜策略，需要计算O(a1*a2*...*an)个局面的性质，不管怎样记忆化都无法降低这个时间复杂度。所以我们需要更高效的判断Nim游戏的局面的性质的方法。
结论。对于一个Nim游戏的局面(a1,a2,...,an)，它是P-position当且仅当a1^a2^...^an=0，其中^表示异或(xor)运算。
根据定义，证明一种判断position的性质的方法的正确性，只需证明三个命题：
1、这个判断将所有terminal position判为P-position；
2、根据这个判断被判为N-position的局面一定可以移动到某个P-position；
3、根据这个判断被判为P-position的局面只能移动到N-position。
证明：
第一个命题显然，terminal position只有一个，就是全0，异或仍然是0。
第二个命题，对于某个局面(a1,a2,...,an)，若a1^a2^...^an!=0，一定存在某个合法的移动，将ai改变成ai'后满足 a1^a2^...^ai'^...^an=0。
不妨设a1^a2^...^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1，这时ai^k<ai一定成立。则我们可以将ai改变成ai'=ai^k，此时 a1^a2^...^ai'^...^an=a1^a2^...^an^k=0。
第三个命题，对于某个局面(a1,a2,...,an)，若a1^a2^...^an=0，一定不存在某个合法的移动，将ai改变成ai'后满足 a1^a2^...^ai'^...^an=0。
因为异或运算满足消去率，由a1^a2^...^an=a1^a2^...^ai'^...^an可以得到ai=ai'。所以将ai改变成ai'不是一个合法的移动。
根据这个定理，我们可以在O(n)的时间内判断一个Nim的局面的性质，且如果它是N-position，也可以在O(n)的时间内找到所有的必胜策略。Nim问题就这样基本上完美的解决了。
2.NIM深入理解
在“Sprague-Grundy函数”中，我们将面对更多与Nim游戏有关的变种，还会看到Nim游戏的a1^a2^...^an这个值更广泛的意义。
如果把Nim的规则略加改变，你还能很快找出必胜策略吗？比如说：有n堆石子，每次可以从第1堆石子里取1颗、2颗或3颗，可以从第2堆石子里取奇数颗，可以从第3堆及以后石子里取任意颗……这时看上去问题复杂了很多，但相信你如果掌握了本节的内容，类似的千变万化的问题都是不成问题的。
现在我们来研究一个看上去似乎更为一般的游戏：给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。
任何一个ICG都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下面我们就在有向无环图的顶点上定义Sprague-Garundy函数。
首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Garundy函数g如下：g(x)=mex{ g(y) | y是x的后继 }。
来看一下SG函数的性质。
首先，所有的terminal position所对应的顶点，也就是没有出边的顶点，其SG值为0。
对于一个g(x)=0的顶点x，它的所有后继y都满足 g(y)!=0。对于一个g(x)!=0的顶点，必定存在一个后继y满足g(y)=0。
以上这三句话表明，【顶点x所代表的是P-position当且仅当g(x)=0】。我们通过计算有向无环图的每个顶点的SG值，就可以对每种局面找到必胜策略了。
如果将有向图游戏变复杂一点，比如说，有向图上并不是只有一枚棋子，而是有【n枚棋子】每次可以任选一颗进行移动，这时，怎样找到必胜策略呢？
让我们再来考虑一下顶点的SG值的意义。当g(x)=k时，表明对于任意一个0<=i<k，都存在x的一个后继y满足g(y)=i。也就是说，当某枚棋子的SG值是k时，之后局面SG值能变成0、变成1、……、变成k-1，但绝对不能保持k不变。根据这个联想到Nim游戏的规则：每次选择一堆数量为k的石子，可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。这表明，如果将n枚棋子所在的顶点的 SG值看作n堆相应数量的石子，那么这个Nim游戏的每个必胜策略都对应于原来这n枚棋子的必胜策略！
对于n个棋子，设它们对应的顶点的SG值分别为(a1,a2,...,an)，再设局面(a1,a2,...,an)时的Nim游戏的一种必胜策略是把 ai变成k，那么原游戏的一种必胜策略就是把第i枚棋子移动到一个SG值为k的顶点。
其实我们还是只要证明这种多棋子的有向图游戏的局面是P-position当且仅当所有棋子所在的位置的SG函数的异或为0。
刚才，为了使问题看上去更容易一些，认为n枚棋子是在一个有向图上移动。但如果不是在一个有向图上，而是每个棋子都在一个有向图上，每次可以任选一个棋子（也就是任选一个有向图）进行移动，这样也不会给结论带来任何变化。
所以我们可以定义有向图游戏的和：设G1、G2、……、Gn是n个有向图游戏，定义游戏G是G1、G2、……、Gn的和，游戏G的移动规则是：任选一个子游戏Gi 并移动上面的棋子。g(G)=g(G1)^g(G2)^...^g(Gn)。也就是说，游戏的和的SG函数值是它的所有子游戏的SG函数值的异或。
我们给每个position定义SG值，当我们面对由n个游戏组合成的一个游戏时，只需对于每个游戏找出求它的每个局面的SG值的方法，就可以把这些SG值全部看成Nim的石子堆，然后依照找Nim的必胜策略的方法来找这个游戏的必胜策略了！
回到之前的问题。有n堆石子，每次可以从第1堆石子里取1颗、2颗或3颗，可以从第2堆石子里取奇数颗，可以从第3堆及以后石子里取任意颗……我们可以把它看作3个子游戏，第1个子游戏只有一堆石子，每次可以取1、2、3颗，很容易看出x颗石子的局面的SG值是x%4。第2个子游戏也是只有一堆石子，每次可以取奇数颗，经过简单的画图可以知道这个游戏有x颗石子时的SG值是x%2。第3个游戏有n-2堆石子，就是一个Nim游戏。对于原游戏的每个局面，把三个子游戏的SG值异或一下就得到了整个游戏的SG值，然后就可以根据这个SG值判断是否有必胜策略以及做出决策了。看作n个子游戏，其中第1、2个子游戏如上所述，第3个及以后的子游戏都是“1堆石子，每次取几颗都可以”，称为“任取石子游戏”，这个超简单的游戏有x颗石子的SG值显然就是x。
所以，对于我们来说，SG函数是把遇到的看上去有些复杂的游戏试图分成若干个子游戏，对于每个比原游戏简化很多的子游戏找出它的SG函数，然后全部异或起来就得到了原游戏的SG函数，就可以解决原游戏了。
三.斐波那契博弈
一堆石子有n个，两人轮流取，先取者第1次可以取任意多个，但不能全部取完，以后每次取的石子数不能超过上次取子数的
2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win"。
分析：这个跟威佐夫博弈和取石子游戏有一个很大的不同点，就是游戏规则的动态化。后两者的规则中，每次可以取的石子
的策略集合是基本固定的，但是这次有规则2：一方每次可以取的石子数依赖于对手刚才取的石子数。
这个游戏叫做Fibonacci Nim，肯定和Fibonacci数列f[n]：1,2,3,5,8,13,21,34,55,89,… 有密切的关系。如果试
验一番之后，可以猜测：先手胜当且仅当n不是Fibonacci数，换句话说，必败态构成Fibonacci数列。
下面简单谈谈“先手败当且仅当n为Fibonacci数列”这一结论是怎么得来的。
这里要用到一个很有用的定理：任何正整数可以表示为若干个不连续的 Fibonacci 数之和。
这里定理涉及到数论，这里不做证明。下面只谈如何把一个正整数表示为若干个不连续的 Fibonacci 数之和。
比如，我们要分解83，注意到83被夹在55和89之间，于是把83可以写成83=55+28；然后再想办法分解28，28被夹在21和
34之间，于是28=21+7；依此类推 7=5+2，故83=55+21+5+2。
如果 n 是 Fibonacci 数，比如 n = 89。89前面的两个Fibonacci 数是34和55。如果先手第一次取的石子不小于34
颗，那么一定后手赢，因为 89 - 34 = 55 = 34 + 21 < 2*34，注意55是Fibonacci数。此时后手只要将剩下的全部
取光即可，此时先手必败。故只需要考虑先手第一次取得石子数 < 34 即可，于是剩下的石子数 x 介于 55 到 89 之
间，它一定不是一个 Fibonacci 数。于是我们把 x 分解成 Fibonacci 数：x = 55 + f[i] + … + f[j]，其中
55 > f[i] > … > f[j]，如果 f[j] ≤ 先手一开始所取石子数 y 的两倍，那么对后手就是面临 x 局面的先手，所以
根据之前的分析，后手只要先取 f[j] 个即可，以后再按之前的分析就可保证必胜。
下证：f[j] ≤ 2y
反证法：假设f[j]>2y，则 y < f[j]/2 = (f[j-1] + f[j-2])/2 < f[j-1]。而最初的石子数是个斐波那契数，即
n = f[k] = x + y < f[k-1] + f[i] + … + f[j] + f[j-1] ≤ f[k-1]+f[i]+f[i-1] ≤ f[k-1]+f[k-2] ≤
f[k] （注意第一个不等号是严格的），矛盾！f[j] ≤ 2y得证。
如果 n 不是 Fibonacci 数，比如n=83，我们看看这个分解有什么指导意义：假如先手取2颗，那么后手无法取5颗或更
多，而5是一个Fibonacci数，如果猜测正确的话，（面临这5颗的先手实际上是整个游戏的后手）那么一定是整个游戏的
先手取走这5颗石子中的最后一颗，而这个我们可以通过第二类归纳法来绕过，同样的道理，根据“先手败当且仅当n为
Fibonacci数列”，接下去先手取走接下来的后21颗中的最后一颗，再取走后55颗中的最后一颗，那么先手赢。
一共有3堆石子，数量分别是m, n, p个，两人轮流走; 每走一步可以选择任意一堆石子，然后取走f个；
f只能是菲波那契数列中的元素（即每次只能取1，2，3，5，8…等数量）最先取光所有石子的人为胜者；
#include<iostream> using namespace std; #define N 20 #define M 1005 int op[N]; int sg[M]; int n, m, k, cnt; void init() { int i, tmp; op[1] = 1; op[2] = 2; for (i = 3;; ++i) { tmp = op[i - 1] + op[i - 2]; if (tmp > 1000) break; op[i] = tmp; } cnt = i; } int mex(int n) { int i, res, vis[N] = { 0 }; for (i = 1; i < cnt; ++i) { res = n - op[i]; if (res < 0) break; if (sg[res] == -1) sg[res] = mex(res); vis[sg[res]] = 1; } for (i = 0;; ++i) if (vis[i] == 0) return i; } void bx() { int i; for (i = 1; i <= 1000; ++i) sg[i] = mex(i); } int main() { //freopen("data.txt","r",stdin); init(); memset(sg, -1, sizeof(sg)); bx(); while (scanf("%d %d %d", &n, &m, &k) != EOF) { if (n == 0 && m == 0 && k == 0) break; int ans = 0; ans ^= sg[n]; ans ^= sg[m]; ans ^= sg[k]; puts(ans ? "Fibo" : "Nacci"); } return 0; }
http://hi.baidu.com/king___haha/item/542a071140107f9598ce337c
四.一道例题 BJFU1207
有 N 个盒子，每个盒子最多可以放 m 个石子，每个盒子开始有 c 个石子。两个人轮流玩，轮到某一方时，选择其中一个盒子放一些石子进去，要求放进去的石子数不能大于原来盒子里石子数的平方，例如原来盒子有2颗石子，则可以放入1,2,3,4颗石子。当然放完后，盒子里的石子数不能大于m。假设有足够多的石子，轮到谁不能放石子算谁输。
#include <cstdio> #include <cmath> #include <iostream> using namespace std; int sg(int m, int c) { int t = sqrt(m); while (t * t + t >= m) { t--; } if (c == t) return 0; else if (c > t) return m - c; else return sg(t, c); } int main() { int n, m, c; while (scanf("%d", &n) && n) { int ans = 0; for (int i = 0; i < n; i++) { scanf("%d%d", &m, &c); ans ^= sg(m, c); } ans ? puts("Yes") : puts("No"); } return 0; }
五.博弈搜索树-极大极小搜索与Alpha beta剪枝
极小极大搜索是深度优先搜索，当搜索到第二层的第二个绿色的节点其第一个子节点返回值为2（之后无论几都只能小于2），因为这一层是找到对手最大的估计值，而第二层的第一个绿色节点的值为7，因此这个节点估计值为2的子节点可以忽略，此即为Alpha剪枝，因被剪掉的节点是极大节点。相应的也有Beta剪枝，即被剪掉的节点是极小节点。