本文共 1196 字，大约阅读时间需要 3 分钟。
Nim游戏是最经典的取石子游戏之一，规则简单却具有深刻的策略性。游戏规则是：每玩家在回合中可以从任意一堆石子中取走至少一颗石子，不能不取。如果轮到某玩家时所有石子堆都为空，此玩家输掉游戏。
在Nim游戏中，P-position（ Previous player wins，先手必输）和N-position（ Next player wins，后手必输）是两个重要的概念。根据定义：
通过这些规则，我们可以判断一个局面是P-position还是N-position。
对于一个Nim游戏的局面(a₁, a₂, ..., aₖ)，它是P-position当且仅当所有堆石子数量的异或（XOR）结果等于0。XOR运算的特性决定了这一定理的成立。
要验证Bouton定理，我们需要证明以下三个命题：
全堆为空的局面（0,0,...,0）显然无法进行任何移动，因此是P-position。
假设一个局面是N-position，意味着它不是P-position。根据Bouton定理，XOR结果不等于0。我们可以找到一个堆，其当前石子数在XOR结果的最高位上有1。将该堆的石子数减少到该数XOR后的结果即可使整个局面的XOR为0，从而变为P-position。
假设一个局面是P-position，XOR结果为0。如果尝试进行任何合法移动，必然会改变某一堆的石子数。根据XOR运算的性质，这样的改变会使得局面的XOR结果不再为0，从而变为N-position。因此，无法通过合法移动将P-position变为另一个P-position。
在Nim取子游戏中，每堆石子可看作二进制数，各位相加为偶数的位称为平衡位。游戏平衡当且仅当所有位的平衡性都满足。
当所有位均为平衡位时，游戏为平衡状态。玩家I可在非平衡取子游戏中获胜，而玩家II则在平衡游戏中占优。
通过Bouton定理，我们可以快速判断Nim游戏局面的胜负。平衡状态决定了后手占优，而非平衡状态则赋予先手主动权。理解这些规律是掌握Nim游戏的关键。
转载地址：http://ndjfk.baihongyu.com/