【专题】Nim博弈

Nim博弈

基本的尼姆博弈(Nim Game)描述如下:

有若干堆各若干个物品,两个人轮流从某一堆取任意多的物品,每次至少取一个,多者不限,最后取光者得胜。

博弈过程如下:

  • 对于局面 $ a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0 $,无论先手怎么取,必将导致异或和改变为 $ a’_1 \oplus a’_2 \oplus \ldots \oplus a’_n = k \neq 0 $ ,而此时必有 $ a_i $ 使得 $ a_i $ 二进制下第k位为1,后手只要将 $ a_i $ 取成 $ a_i \oplus k $ ,使得局面重新回到异或和为0,直至最后局面变成 $ (0, 0, \ldots, 0) $ ,此时异或和为0。先手必输。
  • 对于局面 $ a_1 \oplus a_2 \oplus \ldots \oplus a_n \neq 0 $ ,反之,先手必胜。

详细证明见下方Bouton定理


Bouton定理

Bouton定理:

假设Nim博弈的石子有 $ n $ 堆,第 $ i $ 堆的石子个数我们用 $ a_i $ 表示,则我们可以使用 $ (a_1, a_2, \ldots, a_n) $ 表示一个Nim博弈的局面。对于 $ (a_1, a_2, \ldots, a_n) $ 的Nim博弈局面,当且仅当 $ a_1 \oplus a_2 \oplus \ldots \oplus a_n \neq 0 $ 时(其中 $ \oplus $ 是按位异或运算),先手必胜。

简单证明如下:

  1. 对于 $ a_1 \oplus a_2 \oplus \ldots \oplus a_n \neq 0 $ 的Nim博弈局面 $ (a_1, a_2, \ldots, a_n) $ ,我们设 $ a_1 \oplus a_2 \oplus \ldots \oplus a_n = k $ 。则必存在 $ a_i $ ,其二进制表示在 $ k $ 的最高位上为1(异或运算的性质),且有 $ a_i \oplus k < a_i $ 。则对于当前局面下的先手可以通过合法的移动将第堆石子取到只剩 $ a_i \oplus k $ 个,那么此时游戏局面变为 $ (a_1, a_2, \ldots, a_{i-1},a_i \oplus k, a_{i+1}, \ldots a_n ) $ 。
    而此时 $ a_1\oplus a_2 \oplus \ldots \oplus a_{i-1} \oplus (a_i \oplus k) \oplus a_{i+1} \oplus \dots \oplus a_n = k \oplus k = 0 $。得出异或和不为0的局面一定存在合法移动可以变为异或和为0的局面
  2. 对于 $ a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0 $ 的Nim博弈局面 $ (a_1, a_2, \ldots, a_n) $ ,假设我们将第 $ i $ 堆石子由 $ a_i $ 个取到 $ a’_i $ 个,则有 $ a_i \neq a’_i $ ,则必有 $ a_1\oplus a_2 \oplus \ldots \oplus a_{i-1} \oplus a’_i \oplus a_{i+1} \oplus \dots \oplus a_n \neq 0 $ (可用反证法证明)。即异或和为0的局面无论怎样合法地进行移动,都将转变为异或和不为0的局面
  3. 对于局面 $ (0, 0, \ldots, 0) $ ,其异或和为0,对于先手而言是必输的局面。
  4. 对于任何异或和不为0的局面,先手只需要按照策略将其转变为异或和为0的局面,就能保证后手永远只能拿到异或和为0的局面。又因为每一次合法的移动都将导致石子个数减少,故总的移动步数是有限的,最终后手将拿到的局面而无石子可拿,故后手必输,先手必胜。反过来即可证,对于任何异或和为0的局面,先手必输。
_/_/_/_/_/ EOF _/_/_/_/_/