尼姆

尼姆是一个组合游戏，两名玩家轮流从几堆物品中取出物品。唯一的规则是，每个玩家必须在他们的回合中至少拿一个物品，但他们可以在一个回合中拿多个物品，只要它们都来自同一堆。

尼姆是最著名的例子公正的游戏在这款游戏中，两名玩家的行动始终相同，因此唯一的区别在于其中一名玩家先走。从某种意义上说，对于任何初始配置都已经找到了确切的策略，这个问题也完全解决了。

规则

基本的Nim从两个玩家和几个玩家开始堆，每个包含几个物体．有时，堆也会被调用桩，对象被调用石头．

每个玩家必须轮流拿至少一块石头，但只要都来自同一堆石头，他们可以拿不止一块。它可以使一堆空，有效地将这堆从游戏中移除。当玩家无法移动时，游戏结束。当然，只要有石头，任何玩家都可以拿着石头移动。所以结束条件可以被改写，即如果没有石头剩下，游戏就会结束。

在里面正常的尼姆，输家是无法移动的玩家。根据组合博弈论的惯例，这被称为正常条件，正常的博弈论使最后一个参与者走一步棋取得胜利。在里面米塞尔尼姆，无法移动的玩家获胜;这相当于玩家输掉最后一个石头。

例如游戏

以以下游戏为例。一开始有三堆 $3、4、5$ $3., 4., 5.$ 石头分别。爱丽丝和鲍勃在玩，爱丽丝开始了。

桩1	桩2	桩3	移动
$3.$	$4.$	$5.$	起始位置
$1.$	$4.$	$5.$	1.爱丽丝需要 $2.$ $2.$ 1号堆中的石头
$1.$	$4.$	$3.$	2.鲍勃拿着 $2.$ $2.$ 3号堆中的石头
$1.$	$2.$	$3.$	3.爱丽丝需要 $2.$ $2.$ 2号堆中的石头
$0$	$2.$	$3.$	4.鲍勃需要 $1.$ $1.$ 第1堆的石头
$0$	$2.$	$2.$	5.爱丽丝需要 $1.$ $1.$ 3号堆的石头
$0$	$1.$	$2.$	6.鲍勃 $1.$ $1.$ 2号堆的石头
$0$	$1.$	$1.$	7.爱丽丝需要 $1.$ $1.$ 3号堆的石头
$0$	$1.$	$0$	8.鲍勃需要 $1.$ $1.$ 3号堆的石头
$0$	$0$	$0$	9.爱丽丝需要 $1.$ $1.$ 2号堆的石头

在正常的比赛中，爱丽丝赢了，因为爱丽丝拿走了最后一块石头，因此鲍勃没有任何动作。在米塞尔的比赛中，爱丽丝反而会输，但在这种情况下，爱丽丝会拿走最后一块石头 $2.$ $2.$ 移动7时，从桩3中取出石头，留下桩尺寸的Bob $0 1 0$ $0, 1., 0$ 从而迫使鲍勃拿走最后一个物体。

在上面的游戏中，Alice玩了一个完美的游戏，没有让Bob抢到胜利。这可以概括为一般策略。

策略

这个尼姆森 $b \ oplus$ 两个非负整数 $A.$ $A.$ 和 $B$ $B$ 定义如下。表示 $A.$ $A.$ 和 $B$ $B$ 作为两个不同的幂的和．把出现两次的2的幂消掉，然后把剩下的数加起来。nimsum也被计算机科学家称为XOR。

例如, $3\oplus 5$ $3. \oplus 5.$ 可以如下计算。我们有 $3 = 2^1 + 2^0$ $3. = 2.^{1.} + 2.^{0}$ 和 $5 = 2^2 + 2^0$ $5. = 2.^{2.} + 2.^{0}$ ．我们取消 $2 ^ 0$ $2.^{0}$ 出现两次，然后把剩下的加起来 $2 ^ 1 + 2 ^ 2$ $2.^{1.} + 2.^{2.}$ ,给 $3\oplus 5=6$ $3. \oplus 5. = 6.$ ．

可以证明 $\奥普拉斯$ $\oplus$ 是联想，从而得到几个数的尼姆和 $A_1 oplus a_2 oplus ldots oplus a_n$ $A._{1.} \oplus A._{2.} \oplus \dots \oplus A._{N}$ 定义的。

现在，给一个正常的Nim位置(桩的尺寸) $a\u 1，a\u 2，\l点，a\u n$ $A._{1.}, A._{2.}, \dots, A._{N}$ ，如果玩家移动获胜 $A_1 \oplus a_2 \oplus \ldots \oplus a_n \neq 0$ $A._{1.} \oplus A._{2.} \oplus \dots \oplus A._{N} \neq = 0$ ；确定一堆牌就能找到获胜的一步棋 $I \in \{1,2， \ldots, n\}$ $我 \in {1., 2., \dots, N}$ 还有一个数字 $B_i \in \{0,1， \ldots, a_i - 1\}$ $B_{我} \in {0, 1., \dots, A._{我} - 1.}$ 这样 $A_1 \oplus a_2 \oplus \ldots \oplus a_{i-1} \oplus bi \oplus a_{i+1} \oplus a_{i+2} \oplus \ldots \oplus a_n = 0$ $A._{1.} \oplus A._{2.} \oplus \dots \oplus A._{我 - 1.} \oplus B_{我} \oplus A._{我 + 1.} \oplus A._{我 + 2.} \oplus \dots \oplus A._{N} = 0$ ，从堆里拿出几块石头 $我$ $我$ 这样 $b_i$ $B_{我}$ 石头离开了。如果 $A_1 \oplus a_2 \oplus \ldots \oplus a_n = 0$ $A._{1.} \oplus A._{2.} \oplus \dots \oplus A._{N} = 0$ ，则要移动的玩家将失败。

例如，在上面的游戏中 $3、4、5$ $3., 4., 5.$ ，我们可以看到 $3\oplus 4\oplus 5=7\oplus 5=2$ $3. \oplus 4. \oplus 5. = 7. \oplus 5. = 2.$ , $1 \oplus 4 \oplus 5 = 5 \oplus 5 = 0$ $1. \oplus 4. \oplus 5. = 5. \oplus 5. = 0$ ，所以移动的玩家(在这个例子中是Alice)通过减少第一堆而获胜 $3.$ $3.$ 石头 $1.$ $1.$ 石头。在那之后, $1 \ + 4 \ + 5 = 0$ $1. \oplus 4. \oplus 5. = 0$ ，所以理论上，只要对手表现完美，移动的玩家(在这里是Bob)就会输。

在里面米塞尔尼姆，策略几乎是一样的。只要在建议搬家后，至少会有一堆大小 $2.$ $2.$ 或者更大的，遵循正常的尼姆策略。不过，如果在建议搬家之后，就不会有堆大小了 $2.$ $2.$ 或更大，使用不同的移动：

如果建议的移动使桩具有 $1.$ $1.$ 石头走了，让它有了 $0$ $0$ 而不是石头，或者
如果建议的移动使桩具有 $0$ $0$ 剩下的石头，让它拥有 $1.$ $1.$ 石头代替。

换句话说，正确的做法是留下奇数个大小的堆 $1.$ $1.$ ．(在正常游戏中，大小堆的数量应该是偶数 $1.$ $1.$ 相反，要使nim和为零。）

获胜策略的证明

下面的证明是一般的尼姆的策略，由C. Bouton给出。

当且仅当桩大小的Nim和不为零时，移动玩家在正常Nim中获胜。

我们将从简单的基本情况开始：如果桩大小都为零，那么移动玩家将失败，nim和为零。从现在开始，假设并非所有桩大小都为零。

首先，我们观察到，对于所有非负整数，nim和遵循以下几个属性 $a、 b、c：$ $A., B, C :$

结合性： $（a\oplus b）\oplus c=a\oplus（b\oplus c）$ $(A. \oplus B) \oplus C = A. \oplus (B \oplus C)$

交换性: $A + b = b + A$ $A. \oplus B = B \oplus A.$

身份: $0 \ + a = a$ $0 \oplus A. = A.$

Self-inverse: $a\oplus a=0$ $A. \oplus A. = 0$

一次性计算多个数的nimsum是可能的:将所有数写成不同的2的幂的和，找出所有出现奇数次的2的幂，并对每个2的幂的一次出现求和。例如, $1\oplus 3\oplus 7=\big（2^0\big）\oplus\big（2^0+2^1\big）\oplus\big（2^0+2^1+2^2\big）=2^0+2^2=5$ $1. \oplus 3. \oplus 7. = (2.^{0}) \oplus (2.^{0} + 2.^{1.}) \oplus (2.^{0} + 2.^{1.} + 2.^{2.}) = 2.^{0} + 2.^{2.} = 5.$ ．

假设桩的尺寸为 $a\u 1，a\u 2，\l点，a\u n$ $A._{1.}, A._{2.}, \dots, A._{N}$ 在搬家之前，以及 $B_1 b_2 ldots b_n$ $B_{1.}, B_{2.}, \dots, B_{N}$ 后移动。假设移动是在桩上 $K$ $K$ ；然后对所有 $我\ neq k$ $我 \neq = K$ , $ai = b_i$ $A._{我} = B_{我}$ ．让 $S = a_1 oplus a_2 oplus ldots oplus a_n$ $s = A._{1.} \oplus A._{2.} \oplus \dots \oplus A._{N}$ 和 $T = b_1 \oplus b_2 \oplus ldots \oplus b_n$ $T = B_{1.} \oplus B_{2.} \oplus \dots \oplus B_{N}$ ．我们有

$\begin{aligned}t&=0\oplus t\\\&=（s\oplus s s）\oplus t\\&=s\oplus t\\\&=s\oplus\big（（a\u 1\oplus a\u 2\oplus\oplus\oplus a\n）\oplus（b\oplus 1\oplus b\u 2\oplus\oplus\oplus\oplus\n\oplus\oplus\oplus\b\n）\big）\\\\&=s\oplus\oplus\oplu（0\oplus 0\oplus\ldots\oplus 0\oplus（a\u k\oplus b\u k）\oplus 0\oplus\ldots\oplus 0\big）\\\&=s\oplus（a\u k\oplus b\u k）。\end{aligned}$

现在我们将证明两个结果。

结果1:如果 $s = 0$ $s = 0$ 那么 $t \ neq 0$ $T \neq = 0$ ．如果原始大小的nimsum为零，那么移动中的玩家就输了(他们必须让nimsum非零)。

我们声称 $A_k \oplus b_k \neq 0$ $A._{K} \oplus B_{K} \neq = 0$ . 事实上，如果是这样的话

$\{对齐}开始a_k & = a_k \ oplus 0 \ \ & = a_k \ oplus (a_k \ oplus b_k) \ \ & = (a_k \ oplus a_k) \ oplus b_k \ \ & = b_k。结束\{对齐}$

因此 $a_k = b_k$ $A._{K} = B_{K}$ . 但这与移动玩家在桩上移动的事实相矛盾 $b_k$ $B_{K}$ ，因此必须使规模有所不同。

因此,自 $A_k \oplus b_k \neq 0$ $A._{K} \oplus B_{K} \neq = 0$ ,我们有

$\开始{aligned}t&=s\oplus（a\u k\oplus b\u k）\&=0\oplus（a\u k\oplus b\u k）\\&=a\u k\oplus b\u k\\&\neq 0。\end{aligned}$

结果2:如果 $s \ neq 0$ $s \neq = 0$ ，这是可能的 $t=0$ $T = 0$ ．如果原始大小的尼姆和不为零，那么移动的玩家就赢了(他们可以使尼姆和为零)。

考虑2的最大幂， $2 ^ k$ $2.^{K}$ ，不大于 $s$ $s$ ．至少有一个 $阿尤伊$ $A._{我}$ 这样它也包含 $2 ^ k$ $2.^{K}$ ，否则 $2 ^ k$ $2.^{K}$ 不能出现在 $s$ $s$ ．现在,把 $b_i=s\oplus a_i$ $B_{我} = s \oplus A._{我}$ ．的值 $b_i$ $B_{我}$ 减少 $2 ^ k$ $2.^{K}$ ，最多增加 $2^{k-1} + 2^{k-2} + \cdots + 2^0 = 2^k -1$ $2.^{K - 1.} + 2.^{K - 2.} + \dots + 2.^{0} = 2.^{K} - 1.$ （每项剩余权力由2人组成） $s$ $s$ 增加价值;例如 $S = 2^2 + 2^1 + 2^0$ $s = 2.^{2.} + 2.^{1.} + 2.^{0}$ 和 $A_i = 2^3 + 2^2$ $A._{我} = 2.^{3.} + 2.^{2.}$ 给了 $bi = 2^3 + 2^1 + 2^0$ $B_{我} = 2.^{3.} + 2.^{1.} + 2.^{0}$ )，所以 $b_i < ai$ $B_{我} < A._{我}$ 此外

$\begin{aligned} t &= s \oplus (a_i \oplus bi)\ \ &= s \oplus大(a_i \oplus (s \oplus a_i))\ \ &= 0结束\{对齐}$

这证明了定理。 $_ \广场$ $_{□}$

上面给出的misère Nim的策略是正确的：遵循正常的Nim策略，除非移动玩家将使所有堆大小小于 $2.$ $2.$ 石头，移动的玩家使成堆的数量 $1.$ $1.$ 石头奇数而不是偶数。

唯一的变化是当移动的玩家需要减少单堆的大小 $2.$ $2.$ 或多到少 $2.$ $2.$ $($ 其他桩的大小不超过 $1).$ $1.) ．$

假设桩是 $a\u 1，a\u 2，\l点，a\u n$ $A._{1.}, A._{2.}, \dots, A._{N}$ ,在那里 $a_1 \通用电气2$ $A._{1.} \geq 2.$ 和 $a_2，a_3，a_1$ $A._{2.}, A._{3.}, \dots, A._{N} \leq 1.$ ．然后 $a_2\oplus a_3\oplus\ldots\oplus a_n=0\vee 1$ $A._{2.} \oplus A._{3.} \oplus \dots \oplus A._{N} = 0 \lor 1.$ ．如果 $A_1 \oplus a_2 \oplus \ldots \oplus a_n = 0$ $A._{1.} \oplus A._{2.} \oplus \dots \oplus A._{N} = 0$ ，这就意味着 $A_1 = 0 \vee 1$ $A._{1.} = 0 \lor 1.$ ,矛盾。所以移动的玩家赢了。显然，移动的玩家在第一堆中可能只有0或1个石头，因为它至少从一开始就有 $2.$ $2.$ 石头。

一旦移动的玩家决定了移动，剩下的游戏便是被迫的;奇数 $1.$ $1.$ 大小的堆和对手开始时，对手也会拿走最后一颗石，从而输掉。

这证明了正确性。 $_ \广场$ $_{□}$

尼姆的其他变奏曲

尼姆有很多变体。最著名的是normal Nim和misère Nim;在一些教科书中，正常的尼姆被认为是标准游戏，misère尼姆是变体，而在另一些教科书中，它是相反的。由于《Nim》是一款非常基础的游戏，所以只要添加一条额外规则便能够获得许多可能的变体;这个列表并不是要涵盖所有的可能性，只是一些众所周知的可能性。

一种变体称为减法游戏．这相当于Nim，但是所取的石头的数量被限制在一些正整数集合内:例如，第一个 $K$ $K$ 数字或平方数。一般来说，这是玩一堆。

通常，尼姆玩的是堆成一堆的石头。另一种变体是将石头排成一排，这样在一排中间拿石头会将一排分成两行。换句话说，玩家的行动是从一堆石头中取出至少一块，然后随意地将这堆石头分成两堆。凯勒是单桩游戏，允许分裂，但玩家可以取最多 $2.$ $2.$ 一次石头。道森的象棋是Kayles的另一个变体，玩家最多可以使用 $3.$ $3.$ 一次石头;然而，只有当一堆石头中只有一块石头时，才允许拿一块石头，而拿两块石头是不允许分裂的。圆形的尼姆使用最初排列成圆形的石头进行游戏，因此第一次玩桩时，不能将其拆分；此外，一个人只能使用不超过 $3.$ $3.$ 石头。

尼姆的概括是八进制游戏．玩家们轮流从一堆石头中取出几块石头，就像往常的尼姆一样;但是，控制何时以及如何获取和/或分割堆的规则被简洁地记录为一个八进制数。八进制游戏 $\眉题{0。D_1 d_2 d_3 d_4 \ldots}$ $\overline{0 ． D_{1.} D_{2.} D_{3.} D_{4.} \dots}$ ,数字 $d_n$ $D_{N}$ 指定移除后允许留下多少堆 $N$ $N$ 一堆石头。 $d_n$ $D_{N}$ 是

$1 = 2 ^ 0$ 如果离开 $0$ $0$ 堆是允许的(堆有 $N$ $N$ 石头）， $0$ $0$ 否则;
$2 = 2 ^ 1$ 如果离开 $1.$ $1.$ 允许使用堆（堆具有多个 $N$ $N$ 石头）， $0$ $0$ 否则;
$4 = 2^2$ 如果离开 $2.$ $2.$ 堆是允许的(采取 $N$ $N$ 从堆中取出石头，并将其余的分成两个非空堆)， $0$ $0$ 否则。

例如，道森的象棋有八进制游戏符号 $0.137$ $0 ． 1. 3. 7.$ :

移除 $1.$ $1.$ 只有当它是堆里唯一的石头时，石头才有可能，所以 $d_1 = 1 + 0 + 0$ $D_{1.} = 1. + 0 + 0$ ．
移除 $2.$ $2.$ 石头在任何时候都是可能的，但它不允许分裂桩，所以 $d_2=1+2+0$ $D_{2.} = 1. + 2. + 0$ ．
移除 $3.$ $3.$ 石头在任何时候都是可能的，包括劈开桩，所以 $d_3=1+2+4$ $D_{3.} = 1. + 2. + 4.$ ．

常规Nim具有八进制游戏符号 $0.3333\ldots$ $0 ． 3. 3. 3. 3. \dots$ ．Kayles有八进制的游戏符号 $0.77$ $0 ． 7. 7.$ ．

八进制游戏还有更多的变体。第一个数字，对应于去除 $0$ $0$ 石头，可以镶嵌进去 $4.$ $4.$ 表示将堆一分为二(不拿任何石头)是一种允许的移动。通过使用更高的基数，我们可以表达允许将堆分成3个或更多堆的游戏。

指数 $K$ $K$ 尼姆是尼姆的一种变体，玩家可以在一个回合内从多堆石头中取出石头。这可以结合减法游戏，限制移除的石头总数或从一堆石头中移除的石头数量。

怀托夫游戏是Index- $K$ $K$ 尼姆，从所有受影响的堆中移走的石头的数量必须相同。通常，Wythoff的游戏只有两堆。策略非常不同;两堆游戏解决了，包括Beatty的序列使用 $\ varphi$ $φ$ 和 $\瓦菲^2$ $φ^{2.}$ ．

心胸狭窄的人的游戏更不同的是石头不能被拿走。唯一允许的动作是将一堆东西分成两堆大小不同的东西。这仍然会结束游戏，因为堆的数量将受到石头数量的限制，并不断增加。

不平衡的尼姆有一个额外的规则，即任意两个堆的大小可能不相等。没有对象的堆可能被计算为堆，也可能不被计算为堆;在前一个选项中，这使得结束位置不同，如 $0 1 2 ldots n-1，$ $0, 1., 2., \dots, N - 1.,$ 在哪里 $N$ $N$ 是堆的数目。

甚至还有更古怪的变体贪婪的尼姆，玩家只能从当前最大的一堆石头中取出石头，如果有很多和建筑尼姆在这里，选手们从排位开始 $N$ $N$ 石头成 $P$ $P$ 在玩一场尼姆的游戏之前，堆的结果，使开始的位置是不知道的，直到结束的建设阶段。

宁伯斯和斯普拉格- grundy定理

Sprague-Grundy定理得到了更充分的发展在这一页上．

Sprague-Grundy定理

公平博弈的任何位置都相当于一定大小的Nim堆。

有关……

目录

这是第十二道制胜策略题。