Nim 游戏是博弈论中最经典的模型之一，它又有着十分简单的规则和无比优美的结论 Nim游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Games”（以下简称ICG）。
满足以下条件的游戏是ICG（可能不太严谨）：1、有两名选手；2、两名选手交替对游戏进行移动(move)，每次一步，选手可以在（一般而言）有限的合法移动集合中任选一种进行移动；3、对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素； 4、如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动），则这名选手负。根据这个定义，很多日常的游戏并非ICG。例如象棋就不满足条件3，因为红方只能移动红子，黑方只能移动黑子，合法的移动集合取决于轮到哪名选手操作。
经典的 nim 游戏
问题定义
一共有N堆石子，编号1..n，第i堆中有个a[i]个石子。
每一次操作Alice和Bob可以从任意一堆石子中取出任意数量的石子，至少取一颗，至多取出这一堆剩下的所有石子。
两个人轮流行动，取走最后一个的人胜利。Alice为先手。
我们定义Position：
- P：表示当前局面下先手必败
- N：表示当前局面下先手必胜
N，P状态的转移满足如下性质：
- 合法操作集合为空的局面为P；
- 可以转到P的局面为N，因为只要能转换到P局面，那么先手只需要使操作后的局面变为P，那么后手面临一个必败的局面；
- 不能转到局面P的局面为P，因为所有转换都只能转换到N，无论如何后手都必胜，此时先手必败；
问题求解
其实知道这个之后应该是可以记忆化搜索或者用sg函数求解的，但是如果范围非常大，就没法做了。就引进了nim游戏一个很神奇的结论：对于一个局面，当且仅当a[1] xor a[2] xor …xor a[n]=0时，该局面为P局面，即先手必败局面；反之为先手必胜局面。
证明如下：如果初始局面为P局面，则先手会面临的一直都是P局面，直至全0，输掉比赛；如果初始局面为N局面，则先手可以将局面转化为P局面，也就是后手一定输，先手一定赢。
- 全0的局面一定是P局面；
- 如果某个局面异或值不为0，则必能转化为异或等于0的局面；设a[1] ^ a[2] ^ a[i] ^ …^ a[n]=k，那么一定存在一个a[i]与k的最高位均为1，即a[i] ^ k <= a[i]，那么令a[i]=a[i] ^ k(相当于从第i堆拿掉一部分)，则a[1] ^ a[2] ^ a[i] ^ …^ a[n] = k ^ k = 0；
- 如果某个局面异或值为0，则不存在任何一个移动能使局面转化为异或值为0；如果一位的异或值为0，那么这一位上一定有偶数个1，那么只改变一个数，一定无法使其保持0；
Moore’sNimk
问题定义
n堆石子，每次从不超过k堆中取任意多个石子，最后不能取的人失败
结论为：把n堆石子的石子数用二进制表示，统计每个二进制位上1的个数，若每一位上1的个数mod(k+1)全部为0，则必败，否则必胜
证明如下：
- 全为0的局面一定是必败态。
- 任何一个P状态，经过一次操作以后必然会到达N状态：在某一次移动中，至少有一堆被改变，也就是说至少有一个二进制位被改变。由于最多只能改变k堆石子，所以对于任何一个二进制位，1的个数至多改变k。而由于原先的总数为k+1的整数倍，所以改变之后必然不可能是k+1的整数倍。故在P状态下一次操作的结果必然是N状态。
- 任何N状态，总有一种操作使其变化成P状态。从高位到低位考虑所有的二进制位。假设用了某种方法，改变了m堆，使i为之前的所有位都回归到k+1的整数倍。现在要证明总有一种方法让第i位也恢复到k+1的整数倍。
有一个比较显然的性质，对于那些已经改变的m堆，当前位可以自由选择1或0.
设除去已经更改的m堆，剩下堆i位上1的总和为sum
分类讨论：
(1)sum<=k-m,此时可以将这些堆上的1全部拿掉，然后让那m堆得i位全部置成0.
(2)sum>k-m 此时我们在之前改变的m堆中选择k+1-sum堆，将他们的第i位设置成1。剩下的设置成0.由于k+1-sum<k+1-(k-m)<m+1,也就是说k+1-sum<=m，故这是可以达到的。
anti-nim
反nim游戏。正常的nim游戏是取走最后一颗的人获胜，而反nim游戏是取走最后一颗的人输。
一个状态为必胜态，当且仅当：
- 所有堆的石子个数为1，且NIM_sum=0
- 至少有一堆的石子个数大于1，且 NIM_sum≠0
威佐夫博弈：两堆石子，每次可以取一堆或两堆，从两堆中取得时候个数必须相同，先取完的获胜。
这种情况下是颇为复杂的。我们用（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，奇异局势有如下三条性质：
- 任何自然数都包含在一个且仅有一个奇异局势中。由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 。所以性质1。成立。
- 任意操作都可将奇异局势变为非奇异局势。事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
采用适当的方法，可以将非奇异局势变为奇异局势。假设面对的局势是（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），怎样判断它是不是奇异局势呢？我们有如下公式：
巴什博奕:只有一堆石子共n个。每次从最少取1个，最多取m个，最后取光的人取胜。问先手是否有必胜策略，第一步该怎么取。
如果n=(m+1)*k+s (s!=0) 那么先手一定必胜，因为第一次取走s个，接下来无论对手怎么取，我们都能保证取到所有(m+1)倍数的点，那么循环下去一定能取到最后一个。
