巴什（Bash）博弈和尼姆（Nimm）博弈

巴什（Bash）博弈

题目： 只有一堆 n 个物品，两个人轮流从这堆物品中取物， 规定每次至少取一个，最多取 m 个。最后取光者得胜。问是否存在先手必胜的策略。

首先引入 N（先手必胜）状态和 P（先手必败）状态的概念。

什么是 N（先手必胜）状态？如果我能使对方的状态为 P（先手必败）状态，那么我当前的状态不就是 N（先手必胜）状态了吗？

对于本题，可以从简单的状态入手，当石子数为 0 时为一个 P 状态，则石子数为 [1,m] 时是 N 状态，因为总可以一次拿完。而石子数为 m+1 时，先手无论如何操作，后手总可以拿完剩下的石子，故是一个 P 状态。继续向前推发现，当石子数为 m+1 的倍数时，与上述情况是相同的，先手必败；否则，先手总可以让后手处于上述状态，后手必败。

尼姆（Nimm）博弈

题目：两个人玩游戏，有 n 堆物品，每次操作可以选一堆物品去拿，最少拿一个，无物品可取者为负。问是否存在先手必胜的策略。

那我们就来总结一下简单的 P（先手必败）状态：

• 1.每个堆的物品数都为 0 //根本就没有物品取

• 2.有两个堆且两个堆的物品数相同 //如果我取其中的一个堆，对方就对另一个堆进行相同的操作，怎样都是我去面对状态 1 //貌似干掉了威佐夫（Wythoff）博弈

对上面状态 1 进行分析可知，只有一个堆的时候，我就能使对方必败，对状态 2 进行分析，如果有两个堆且物品数目不等，我就能让他们相等，我就必胜。

再对状态 2 分析，将两个堆推广到 2*n 个堆，且每个堆都有与其相同的堆，那么这种状态依旧是 P（先手必败）状态。

再进一步推广，一个结论就是亦或和值为零则后手胜，否则先手胜

对于上面分析的状态，毫无疑问满足这个结论，但一般性地来讲是否符合呢？而又怎样理解呢？

先说思考方向：枪打出头鸟

如果有成对相同的堆那就无需考虑，因为对手的操作，我完全可以复制过来形成状态 2，而这种成对亦或为 0，对结果没影响，可以剔除掉进行一下讨论

此时将思维从十进制转换成二进制，将所有的数目看成二进制，且思维不要停留在单独的堆上（因为是亦或运算啊）

设 k=a[1]^a[2]^a[3]^…^a[n]。

如果 k==0，说明没有特立独行的位数，

（：哎，刚才不是堆吗？怎么开始看位数了？参考系都不一样了啊？

那我们想一下，如果 k!=0，说明存在一个 1 在最高位，那我们就可以对有这个最高位的堆进行操作去让其他的位（不管是什么，最高位都比他们大啊）不再特立独行。

（：不对啊？怎么又跑到特立独行的位数了啊？

我不是先证明如果 k!=0 时，情况反转吗？

（：那你凭什么保证 k==0 时必输这个结论正确啊？

接下来思考一下，如果我随便取了，k 是不是就不等于 0 了？因为相当于亦或了我刚才的操作数，而我不可能不取物品滴

而这种规则下，我如果总是可以保证 k==0 时不是我面对的状态，我就能去抵消对手的操作而使结果变为 k==0，最后，是对手面对的 0，

（：？？？？？

可以看作是打地鼠，只要 k 中有 1 冒出来，我就去消灭，如此，反正我不是最后遇到零的，管他还有多少堆，堆中有多少个呢