浅谈博弈论——Nim 游戏

· · 个人记录

简介

博弈论，是经济学的一个分支，主要研究具有竞争或对抗性质的对象，在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。

通俗地讲，博弈论主要研究的是：在一个游戏中，进行游戏的多位玩家的策略。

公平组合游戏

博弈论中，一般主要研究公平组合游戏。公平组合游戏（Impartial Combinatorial Games，简称 ICG）的定义如下：

根据定义，取数游戏、21点、Nim 游戏等为公平组合游戏；而常见的如象棋、围棋等不是公平组合游戏，因为每个游戏者只能动自己的棋子，也就是与游戏者有关，不符合第二条定义。

Nim 游戏

背景

还记得这个游戏吗？ 给出n列珍珠，两人轮流取珍珠，每次在某一列中取至少1颗珍珠，但不能在两列中取。最后拿光珍珠的人输。 后来，在一份资料上看到，这种游戏称为“拈（Nim）”。据说，它源自中国，经由被贩卖到美洲的奴工们外传。辛苦的工人们，在工作闲暇之余，用石头玩游戏以排遣寂寞。后来流传到高级人士，则用便士（Pennies），在酒吧柜台上玩。 最有名的玩法，是把十二枚便士放成3、4、5三列，拿光铜板的人赢。后来，大家发现，先取的人只要在3那列里取走2枚，变成了1、4、5，就能稳操胜券了，游戏也就变得无趣了。于是大家就增加列数，增加铜板的数量，这样就让人们有了毫无规律的感觉，不易于把握。 直到本世纪初，哈佛大学数学系副教授查理士•理昂纳德•包顿（Chales Leonard Bouton）提出一篇极详尽的分析和证明，利用数的二进制表示法，解答了这个游戏的一般法则。 有很多人把这个方法写成计算机程序，来和人对抗，不知就理的人被骗得团团转，无不惊叹计算机的神奇伟大。其实说穿了，只因为它计算比人快，数的转化为二进制其速度快得非人能比，如此罢了。

概述

Nim游戏是博弈论中最经典的模型，它又有着十分简单的规则和无比优美的结论。

规则：有 n 堆石子，每堆石子的数量为 a_i。每人每次只能选堆石 1 堆石子，并从这堆石子中取出任意多枚石子扔掉，可以取完，不能不取。最后没石子可取的人就输了。

请问是否存在先手必胜的策略。

结论

当 a_1\oplus a_2 \oplus \cdots \oplus a_{n-1} \oplus a_n=0 时，先手必败；否则，先手必胜。其中 \oplus 是按位异或，点我查看详细定义。

证明

显然一个局面 A 如果是先手必胜的当且仅当它可以通过一次操作变为先手必败的局面 A'，因为 A 中的先手到了 A' 中就成了后手。而 A' 是先手必败的，也就是后手必胜的，那么 A 就是先手必胜的。同理，如果一个局面 A 是先手必败的当且仅当无论此时先手怎么操作都会变成必胜局面。

采用数学归纳法。

当 a_1=a_2=\cdots =a_{n-1}=a_n=0 时，a_1\oplus a_2 \oplus \cdots \oplus a_{n-1} \oplus a_n=0。显然此时先手必败，因为没石头可取了。

如果此时 a_1\oplus a_2 \oplus \cdots \oplus a_{n-1} \oplus a_n>0，不妨设 a_1\oplus a_2 \oplus \cdots \oplus a_{n-1} \oplus a_n=k。证明此时先手必胜，只需证明一定能通过一次操作使得先手必败，也就是 a_1\oplus a_2 \oplus \cdots \oplus a_{n-1} \oplus a_n=0。而为了将其变成先手必败的局面，必须得找到一个 a_i 将它变成 a_i' 满足 a_i'=a_i\oplus k 且 a_i' < a_i。

假设 k 的二进制形式中最高位是 d，显然有 2^d \le k \lt 2^{d+1}。根据异或的定义，一定存在一个 x 满足 a_x 的二进制形式中的第 d 位是 1。我们只需要将这个 a_x 改为 a_x \oplus k 是一定会变小的（因为它的第 d 位会由 1 变 0，相当于减去了 2^d，那比 d 位低的每一位就算全部由 0 变 1 也只会使它加上 2^0+2^1+\cdots +2^{d-1}，又因为 2^d>2^0+2^1+\cdots +2^{d-1}，所以它一定会变小）。综上，我们证明了当一个局面 a_1\oplus a_2 \oplus \cdots \oplus a_{n-1} \oplus a_n>0，先手必胜。

如果此时 a_1\oplus a_2 \oplus \cdots \oplus a_{n-1} \oplus a_n=0 且 \exists i \in [1,n] 满足 a_i > 0，则只需证明它不能通过一次操作使得 a_1\oplus a_2 \oplus \cdots \oplus a_{n-1} \oplus a_n 仍然为 0。而显然，如果将一个 a_i 变为 a_i' 后有 a_1\oplus a_2 \oplus a_{i-1} \oplus a_i'\oplus a_{i+1} \oplus \cdots \oplus a_{n-1} \oplus a_n=a_1\oplus a_2 \oplus a_{i-1} \oplus a_i' \oplus a_{i+1} \oplus \cdots \oplus a_{n-1} \oplus a_n。根据异或的性质，有 x \oplus x=0。则有两边异或上 a_1\oplus a_2 \oplus a_{i-1} \oplus a_{i+1} \oplus \cdots \oplus a_{n-1} \oplus a_n 有 a_i=a_i'。而一次操作不能不拿，所以这种操作是不合法的，所以不存在一种操作使得操作完后满足 a_1\oplus a_2 \oplus \cdots \oplus a_{n-1} \oplus a_n 仍然是 0。也就是说，此时局面通过一次操作后只能变成一个先手必胜的局面，则此局面先手必败。

结论得证。

K-Nim 游戏

现在我们有了一个 O(n) 判断一个 Nim 游戏是否先手必胜的方法。那我们将游戏升级：将只能选 1 堆石子改为至多选 k 堆石子，还能够快速判断是否先手必胜吗？答案是：依然能！

结论

首先将各堆石子数用二进制表示。

令 sum_i 表示每堆石子二进制表示的第 i 位上数字之和 \bmod (k+1) 的值。

如果存在一个 i 使得 \exists j \in [1,n] 满足 a_j \ge 2^i 且 sum_i>0，则先手必胜；否则先手必败。

证明

仍然采用数学归纳法证明。

当 a_1=a_2=\cdots =a_{n-1}=a_n=0 时，所有 sum_i=0。显然此时先手必败，因为没石头可取了。

如果所有的 sum_i 都为 0，则一次操作肯定会使得某些数位上的值改变。又因为一堆石子每位上都是 0 或 1，所以变动的绝对值不会超过 k。因此操作结束后该位置上的 sum_i 必不为 0。

如果有一些 sum_i 不为 0。则肯定有 sum_i 堆石子的数量二进制表示该位上为11。此时我们只要从高到低扫每一个二进制位，选择 sum_i 堆该位上为 1 的石子，将这些堆每个都取出来 2^i 个石子。这样就可以将 sum_i 变成 0 了。

但是有一个问题：如果这样选出来的石子堆数超过了 k 怎么办？

我们知道，如果一个数的高位从 1 变成 0，则其低位无论怎么变化，这个数还是变小。

于是我们每次只要尽量优先选择有高位变为 0 的数，再选择该位上为 1 的数，这样由于每个位置要选的数不超过k 个，所以总共要选的堆数不会超过 k 堆。

综上，结论得证。

小结

Nim 游戏作为最经典的公平组合游戏，还有许多有趣的变种，这里就不一一列举了。

博弈论已经成为经济学的标准分析工具之一。在金融学、证券学、生物学、经济学、国际关系、计算机科学、政治学、军事战略和其他很多学科都有广泛的应用。