Nim博弈是ACM入门的博弈之一，其基本描述为：

有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

这游戏看上去有点复杂，先从简单情况开始研究吧。如果轮到你的时候，只剩下一堆石子，那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩，然后对手就输了。如果剩下两堆不相等的石子，必胜策略是通过取多的一堆的石子将两堆石子变得相等，以后如果对手在某一堆里拿若干颗，你就可以在另一堆中拿同样多的颗数，直至胜利。如果你面对的是两堆相等的石子，那么此时你是没有任何必胜策略的，反而对手可以遵循上面的策略保证必胜。如果是三堆石子……好像已经很难分析了，看来我们必须要借助一些其它好用的（最好是程式化的）分析方法了，或者说，我们最好能够设计出一种在有必胜策略时就能找到必胜策略的算法。（源自百度百科）

如果有点基础的同学就会知道Nim博弈的判断胜负的办法：

将每堆石子个数异或，如果异或结果非零，则先手必胜，否则先手必败。

我们先对必败局面，即最终异或结果为 0

（假设异或结果为 A）进行分析：

如果现在第一个人拿任意一堆石子中的 B个，那么现在剩余石子的异或结果 A′必定不为 0 ，而且可以看出A′=B。接下来是第二个人的操作。在二进制的情况下，A′

的位数和 B 的位数相同（假定为 n+1位），即剩余的所有石子中必定有一堆石子的数量（假定为 C ）不少于 2n 个，且二进制下第 n 位必定为 1 。假如我们拿出这一堆石子中的 2n 个，现在剩下的所有石子异或结果 A′′ 一定小于 2n (A′′ 第 n 位此时变成了 0 ) ，所以我们可以从这 C 个石子中拿走 2n−A′′ 个，剩余 A′′ 个，这样，剩余的石子异或的结果一定为 A′′ ^ A′′ =0 。这样，第二个人就能在一次操作后将异或的结果变为 0。

第二个人持续上述操作，就能够使第一个人当前的异或结果永远为 0，第二个人当前的异或结果永远不为 0 ，而最终当取完所有石子时，结果也为 0。

假如初始 A不为零，那么第一个人也可通过上述操作使得异或结果为 0。

这样就证明了异或结果可以判断最终胜负的正确性。