【算法】【博弈论】一看就懂的 Nim 游戏、SG函数、SG定理 全网最佳解读！

一看就懂的 Nim 游戏、SG函数、SG定理 全网最佳解读！

本文为原创文章，转载请注明本文链接！

By.ShizuriYuki

1 Nim 游戏

1.1 简介

Nim游戏规则：有 \(n\) 堆石子，数量分别是 \(\{a_1, a_2, a_3,\dots, a_n\}\) ，两个玩家轮流拿石子，每次从任意一堆中拿走任意数量的石子，拿走最后一个石子的人获胜（即最后没有石子拿的人输）。

1.2 分析

首先明确一个事实：

异或和可以看作是统计每位上 1 的总个数的奇偶性。如果这一位有偶数个 1，则这一位计算结果为 0；如果这一位有奇数个 1，则这一位计算结果为 1。

---

从简单情况开始分析：

（A先手，B后手）注意转移后先后手需要互换后再判断更不容易出错。

• 有 2 堆石子：

  总共 4 种情况：

  1. \(\{0,0\}\) ：A Lose，先手A必输。

  2. \(\{0, n\}\) ：A Win，先手A必赢。

  3. \(\{n,n\}\) ：A Lose，先手A必输 。

     分析：

     • 若先手A取 \(\{ ( a_1, n ) \}\)，则剩下 \(\{0,n\}\)，转移至情况2，后手B赢。
     • 若先手A取 \(\{(a_1, k)|1 \leq k < n\}\)，则剩下 \(\{n-k,n\}\)，后手B可以也取，使\(\{(a_2, k)|1 \leq k < n\}\)得剩下为 \(\{n-k,n-k \}\)。如此循环，知道先手A遇到 \(\{1,1\}\) ，只能取1，剩下 \(\{0,1\}\)，转移至情况2，后手B赢。

  4. \(\{n,m\}\) ：A Win，先手A必赢。

     分析：先手A取\(\{(max(a_1,a_2),abs(a_1-a_2)\}\)，则剩下 \(\{k,k\}\)，转移至情况3，先手A必赢。

---

• 有 3 堆石子：

  总共 7 种情况：

  1. \(\{0,0,0\}\) ：A Lose，先手A必输。

  2. \(\{a,0,0\}\) ：A Win，先手A必赢。

  3. \(\{a,a,0\}\) ：A Lose，先手A必输。分析：转移至只有 2 堆石子的情况3，先手A必输。

  4. \(\{a,b,0\}\) ：A Win，先手A必赢。分析：转移至只有 2 堆石子的情况4，先手A必赢。

  5. \(\{a,a,a\}\) ：A Win，先手A必赢。分析：先手A取出一个 a ，转移至情况3，先手A必赢。

  6. \(\{a,a,b\}\) ：A Win，先手A必赢。分析：先手A取出一个 b ，转移至情况3，先手A必赢。

  7. \(\{a,b,c\}\) ：若 \(a \oplus b \oplus c \neq 0\) ，先手A必赢；若 \(a \oplus b \oplus c = 0\) ，先手A必输。

     分析：

     • \(H_n = a \oplus b \oplus c = 0\) ：

       先手A任意取其中一堆的任意数量石子，将导致这一堆的石子数的二进制数至少有 1 位发生变化。

       由于异或和可以看作是统计这一位上 1 的总个数的奇偶性，则全部位为偶数个 1 的产生的原结果 0 将至少有一位变为奇数个 1。

       这将导致 \(a_1 \oplus a_2 \oplus a_3 \neq 0\) ，转移至该情况。

     • \(H_n = a \oplus b \oplus c \neq 0\) ：

       先手A一定能从 \(\{a,b,c\}\) 找出一个数 \(x\)，使得剩下的数的异或和 \(H_{n-1} < x\) （正确性在后面证明）。然后从 \(x\) 取走 \(x - H_{n-1}\) 个石子，使得 \(x = H_{n-1}\) 。

       这将导致 \(a_1 \oplus a_2 \oplus a_3 = 0\)，转移至该情况。

     • 如此以上两种情况交替循环，直到全部石子被全部取完，同时取完的时候必然有 \(a_1 \oplus a_2 \oplus a_3 = 0\) 。

       故从 \(a \oplus b \oplus c = 0\) 先手的必然会输，从 \(a \oplus b \oplus c \neq 0\) 先手的必然会赢。

---

1.3 定理

若 \(a_1 \oplus a_2 \oplus a_3 \oplus \dots \oplus a_n \neq 0\) ，先手必赢； 若 \(a_1 \oplus a_2 \oplus a_3 \oplus \dots \oplus a_n = 0\) ，先手必输。

1.4 思路

与有 3 堆石子的情况7 \(\{a,b,c\}\) ，是同样的思路。

但其中我们需要证明这一点：

• 先手A一定能从 \(\{a_1, a_2, a_3,\dots, a_n\}\) 找出一个数 \(x\)，使得剩下的数的异或和 \(H_{n-1} < x\)

证明如下：

• 设 \(H_n=a_1 \oplus a_2 \oplus a_3 \oplus \dots \oplus a_n\) 。

  设 \(x \in \{a_1, a_2, a_3,\dots, a_n\}\) ，同时 \(x\) 在 \(H_n\) 的二进制最高位处为 1 （通过异或和的奇偶统计得知必然存在这样的数）。

  则剩下的数的异或和为 \(H_{n-1}=H_n \oplus x\)。

• 以 \(H_n\) 的二进制数的最高位的 1 为轴，将 \(H_n\) 、 \(H_{n-1}\) 、\(x\) 分割为 3 部分的二进制数：\(\{front, highbit, end\}\) 。

  其中：（请原谅我在指数位标注）

  • \(H_n^{front}=0, \space \space H_{n-1}^{front} = x^{front}\);（两数异或和为 0 则两数相等）
  • \(H_n^{highbit}=1, \space \space H_{n-1}^{highbit} = 0,\space \space x^{highbit}=1\);
  • \(end\) 不用管，比较前面的高位即可确定大小.

  通过 \(H_{n-1}^{front} = x^{front}, \space \space H_{n-1}^{highbit} = 0 < x^{highbit} = 1\)，可得 \(H_{n-1} < x\) .

• 证毕。

实例：
		     front | highbit | end
	x:     0 1 1 0 |    1    | 1 1 0 0 0 1
	Hn-1:  0 1 1 0 |    0    | 0 1 1 0 1 0
	Hn:    0 0 0 0 |   *1*   | 1 0 1 0 1 1

这里的必胜情况称为 N-position 点，必败情况称为 P-position 点。遇到 N 点的人，可以将情况转化为 P 点，使得下一个人一直遇到必败情况 P。而遇到 P 点的人游戏又只能转换为 N 点，如此 N、P 交替，游戏终止于 P 点。

1.5 例题

hdu1850

2 Sprague-Grundy 函数

2.1 图游戏