算法趣谈(0)——古老的石子游戏

相信很多人在小学数学题或其他地方都见过这样一个游戏：从1开始，每人依次报1-3个数，先报到20的人胜利。而本文正是介绍组合博弈中的这一类游戏——捡石子，并介绍数学家发展出的一般理论与证明。

阅读本文的可能的收获

相较于可以直接搜索到的各种有关石子博弈的文章，本文更系统的介绍这些经典的石子游戏并给出结论，读者在掌握方法后就可以和别人愉快的玩耍了(doge)。
本文会给出对于这些博弈的未经审视的证明供大家参考。虽然本文的核心思路和概念来自各路证明(我当然想不出来这么巧妙的方法)，但语言和证明细节都由我自己完成，很有可能是存在缺陷的，也希望读者在阅读过程中也能帮忙检查这些证明。

我们先借最简单的巴什博弈来介绍先手、后手必胜和奇异局势等基本概念，而这些概念则会贯穿所有博弈。

巴什博弈 Bash Game

游戏描述：场上有1堆石子，数目为n个，双方依次拿1~ m个石子(\(m\) 为定义好的正整数)，拿到最后一个石子的玩家获胜。

相信大家在许多场合已经见过这个游戏，并且大概已经知道了答案：

若n是(1+m)的倍数，先手必胜。
反之，后手必胜。

等等，我们需要先简单且不严谨的定义一下这些概念：

定义1：必胜

若玩家在当前局势下，无论对手进行任何符合规则的操作，该玩家都能有相应的策略赢得最终的胜利，则称玩家在该局势下是必胜的。若首先行动的玩家是必胜的，则称该游戏是先手必胜的，若后行动的玩家是必胜的，则称后手必胜。

事实上，经典的石子游戏属于两人组合策略博弈，必然存在先手必胜或后手必胜。严谨的关于策略、必胜等的定义其实也并不困难，但本文重点不在于此，感兴趣的读者可以在任何一本正经的博弈论教材中找到相关定义。

当我们知道这个答案后不难猜出答案的来源，一个玩家总是有办法将一轮双方取石子总数控制在1+m，那如果石子的数目不是模为0，先手方只需要拿石子，使得剩下的石子是 1+m 的倍数，然后每次都将剩下的石子数控制在 k(1+m)，直到石子被拿完。

较为严格的证明会在下文给出。

上述过程显然不难理解，而值得思考和推广的核心在于石子是1+m的倍数这种局面，我们有以下发现：

0(1+m)=0，即如果玩家进行操作，将局势转换这该情况，该玩家获胜。
如果当前局面是(1+m)倍数，那么玩家无论选择在规则下拿几个石子(1~m)，剩下的石子总不会是其倍数。
如果当前局面不是(1+m)倍数，那么该玩家总可以拿部分石子，使得剩下的石子总数是(1+m)的倍数。

而将这种局面进行抽象，也就得到了本文的核心概念：

定义2：奇异局势

假设有 \(l\) 堆石子个数分别为 \(n_1,\dots,n_l\) (简称 \((n_i)\))，我们记所有局势的集合为\(U=\{(a_1,\dots,a_l)\},a_i\le n_i,a_i\in \mathbb{N}\)，即所有可能发生的石子数组成的集合。若集合 \(S\subset U\)满足如下性质：

\(0\in S\)，这里的0实际上指的是 \((0,\dots,0)\)
若当前局势 \((s_i)\in S\) 且 \((s_i)\ne0\)，那么进行任一符合规则的操作，新的局势不是奇异局势， \((s_i')\in U\setminus S\)
若当前局势不是奇异局势，即 \((s_i)\in U\setminus S\)，那么存在一符合规则的操作，新的局势 \((s'_i)\in S\)

我们称集合 \(S\) 是代表奇异局势的集合，集合中的元素是奇异的。

奇异局势将巴什博弈的特殊的局面抽象出来，我们再将其结论也抽象出来：

定理1

若该博弈存在上述定义的奇异局势，那么：

若初始局势 \((n_i)\) 不是奇异局势，则先手必胜。
若初始局势 \((n_i)\) 是奇异局势，则后手必胜。

证明：首先我们有如下观察：

因为每位玩家必须取石子，所以石子的数目一定严格小于上一步的数目，游戏一定在有限步内终止。
由奇异局势定义，(1) 和 (2) 是等价的，所以我们只证明(2).

我们对场上石子数目采用数学归纳法证明。若初始局势 \((n_i)=0\)，是奇异局势，则先手方无子可拿，后手胜。若 \((n_i)>0\)，将双方一轮博弈后的局势看作一个新游戏的初始局势，此时的石子数严格小于原博弈石子数。由归纳假设我们知道，若这个局势 \((n''_i)\) 是奇异局势，则后手必胜。那么后手方如何确保这个局势是奇异局势呢？这就用到了奇异局势的定义和初始条件。由定义2(2)我们知道，先手者进行任何操作进入的局势 \((n'_i)\) 必然不属于奇异局势。而由于0是奇异局势，场面上一定还有石子，由定义2(3)后手者一定可以在取石子后使得新的局势 \((n_i')\) 是奇异局势，这就是我们希望的。

这个定理直觉是是显然的，利用数学归纳法我认为能比较清楚的证明它。

奇异局势可以看作某种意义上的不变量。上述定义和定理给了我们一套解决这类问题的范式：找到并证明该游戏的奇异局势，本文介绍的石子游戏证明都会通过这种方法来描述。

本节最后我们用奇异局势的语言证明巴什博弈的结论，感受一下抽象的力量(bushi)：

定理2：巴什博弈

\(S = \{s\mid s\equiv 0\mod (1+m)\}\)只需证明：

\[0\equiv 0\implies 0\in S\]
由于是 \(s\) 是奇异局势且 \(s\ne 0\)，我们令 \(s=k(1+m),k\ge1\)，若拿 \(1\le t\le m\) 个石子，则 \(s'=(k-1)(1+m)+(1+m-t)\) ， \(s'\equiv (1+m-t),1\le(1+m-t)\le m\implies s'\notin S\)
由于 \(s\) 不是奇异局势，由带余除法我们知道 \(s=k(1+m)+r,1\le r\le m\)，所以只需取 \(r\) 个石子即可。(我们也证明了取法是唯一的)

可能有读者还是觉得本节的内容太平凡了，不过是在奇异局势的语言下叙述了这件事，其证明本质大概是我们小学就会的带余除法，下一节我们会介绍一个有难度的游戏：

尼姆博弈 (Nim Game)

游戏描述： 场上有 \(l\) 堆石子，双方依次选择某一堆石子，取至少一个石子，拿到最后一个石子的玩家获胜。

这个游戏最经典的版本是[3, 4, 5]的情形，先手必胜。感兴趣的读者可以自己先玩玩看。

由上面的讨论，我们知道，我们的最终目的是找到一个局势的集合，使得它满足奇异局势的要求，即找到函数 \(f(n_1,\dots,n_l)\to\{0,1\}\)，来判定一个局势是否是先手必胜(1)还是后手必胜(0)。虽然任意多堆和拿任意多石子让问题难以入手，但我们还是可以有以下观察：

\(f\) 是对称的，多元函数交换变量顺序结果是不变的。
只剩一堆石子时，先手必胜，因为玩家可以直接拿完所有石子。
只剩两堆石子时，也不难想到答案。如果两堆石子数目相同，那后手方总可以在另一堆石子上重复先手方的操作，从而使得两堆石子同时为0，此时先手放无子可拿。
还剩三堆石子时就麻烦了，如果存在两堆石子数目相同，这时我们直接把另一堆拿完，就回到了 \(l=2\)的情形，但如果没有的话我们似乎没有什么办法了…

两堆石子的情况给了我们很大的启发，相同则函数输出为0，后手必胜；不同则函数输出为1，先手必胜。那么什么运算满足这个性质呢？

异或！ 相同为0，不同为1，异或运算可以完成这件事。而两个数的异或运算实质上是在二进制表示上进行的逐位异或。而令人惊奇的是，尼姆博弈中奇异局势等价判断一列数异或是否为0：

例1：[3,4,5]

回到本节开头，一个经典的先手必胜场景：

            3 = 011   -2   1 = 001          
            4 = 100        4 = 100          
            5 = 101        5 = 101   ...    
         XOR ______     XOR ______          
              = 010          = 000          

这个结论由数学家Charles L. Bouton在1901-1902年 Annals of Mathematics上给出

而接下来我们需要证明这一点：

定理3：尼姆博弈

由上一节的定理1我们只要证明 \(S=\{(s_i)\mid \bigoplus_{i=1}^{l}(s_i)=0\}\)是奇异局势，即：

\(0\in S\)，这是显然的
若 \((s_i)\in S\)，我们要证明任取 \(0\le s_k'< s_k ， (s_1,\dots,s_{k-1},s'_,s_{k+1},\dots,s_l)\notin S\) ，这并不困难。我们假设存在一种取法使得异或为0，即\((\bigoplus_{i\ne k}s_i)\oplus s_k'=0\)，那么我们添加上两个异或，可以得到

\[s_k\oplus(\bigoplus_{i\ne k}s_i)\oplus s_k' \oplus s_k= s_k\oplus s_k\\ 0 \oplus s_k' \oplus s_k = 0\\ s_k' = s_k\]

这与 \(s_k'\le s_k\) 矛盾，故假设不成立，不存在这种取法。

若 \((s_i)\notin S\)，我们要证明必存在 \(0\le s_k'< s_k\) 使得 \((s_1,\dots,s_{k-1},s'_k,s_{k+1},\dots,s_l)\in S\). 因为 \(\bigoplus_{i=1}^{l}(s_i)\ne0\)，则我们可以找到二进制最左边的1(例子中010的1)，那么此时石子堆中必然有 \(s_k\) 其该位值为1（如果全0异或之后也还是0），我们就令 \(s_k' = s_k \oplus \bigoplus_{i=1}^{l}(s_i)\)，由 \(s_k\) 的选取我们知道最前面的1被异或成0了，所以 \(s'_k\lt s_k\)，这是一个合法的操作。另一方面， \((\bigoplus_{i\ne k}s_i)\oplus s_k' = (\bigoplus_{i\ne k}s_i)\oplus s_k \oplus \bigoplus_{i=1}^{l}(s_i) = 0\) 这就是所要证明的。

大家可能已经发现了，虽然我们想不出来答案，但如果告诉我们结论，证明还是相对容易的。

最后，我们会介绍一个证明本身也不太容易的博弈——威佐夫博弈。

威佐夫博弈 Wythoff Game

游戏描述： 有两堆石子，双方依次进行选择：从两堆里面拿相同多的石子，或者从一堆里面拿任意多的石子。拿到最后一个石子的玩家胜利。

这个问题没啥好观察的，因为我也观察不出来，我们直接给出结论：

\[\alpha=(1+\sqrt{5}) / 2, \beta=(3+\sqrt{5}) / 2 \\ S=\{(\lfloor n \alpha\rfloor,\lfloor n \beta\rfloor)\mid n \in \mathbb{Z}\}\cup\{(\lfloor n \beta\rfloor,\lfloor n \alpha\rfloor)\mid n \in \mathbb{Z}\},\]

即奇异局势是由这些奇怪的无理数的倍数取下整得到的。为了证明这确实是奇异局势，我们需要先证明一个引理：

引理: Beatty定理

若正无理数满足 \(\frac1p+\frac1q=1\)，那么

\[P=\left\{\lfloor n p\rfloor\mid n \in \mathbb{Z}^{+}\right\}, Q=\left\{\lfloor m y\rfloor\mid m \in \mathbb{Z}^{+}\right\}\]

是一个正整数集的划分。

我们要证明两点：

\(\forall z\in \mathbb Z^+ \implies z\in P \lor z\in Q\) 反证法。若 \(z\notin P \land z\notin Q\)，即 \(np<z<z+1<(n+1)p,mq<z<z+1<(m+1)q\\ \frac{n+m}z <\frac1p+\frac1q=1< \frac{n+1}{z+1}+\frac{m+1}{z+1}\\ n+m<z<n+m+1\) 这与 \(n,m,z\) 都是整数矛盾。
\(\forall z\in \mathbb Z^+ \implies \neg( z\in P \land z\in Q)\) 反证法。若 \(z\in P \land z\in Q\)，即 \(z<np<z+1,z<mq<z+1\\ \frac n{z+1}+\frac m{z+1} <\frac1p+\frac1q=1< \frac nz+\frac mz \\ z<n+m<z+1\) 这与 \(n,m,z\) 都是整数矛盾。

我们发现\(\frac1\alpha+\frac1\beta=1\)，所以可以使用该引理得到一组划分，另外还注意到 \(\beta=\alpha+1\)，所以我们只需证明：

这个结论由数学家Willem A. Wythoff在1907年给出

定理4：威佐夫博弈

\(S=\{(\lfloor n\alpha\rfloor,\lfloor n\alpha\rfloor+n),n\in\mathbb Z\}\) 是奇异局势，具体来说，我们要证明：

\((0,0)\in S\)，\(n=0\) 即可。
\(s=(\lfloor n\alpha\rfloor,\lfloor n\alpha\rfloor+n)\in S\)，如果选择某堆拿石子的话只能拿多的那堆，由引理的分划性 \(s'\notin S\)，而如果两堆同时拿 \(k\) 个石子且还是奇异局势的话， \(s'=(\lfloor n\alpha\rfloor-k,\lfloor n\alpha\rfloor+n-k)\in S\\ \implies \begin{matrix}\lfloor n\alpha\rfloor-k=\lfloor n_1\alpha\rfloor \\ \lfloor n\alpha\rfloor+n-k= \lfloor n_1\alpha\rfloor+n_1 \end{matrix}\implies n=n_1\) 矛盾，故 \(s'\notin S\)
\(s=(s_1,s_2)\notin S，s_1\le s_2\)（对称性假设），由引理中的分划性有以下情况：
- \(s_1=\lfloor n\alpha\rfloor,s_2>=s_1,\)，若 \(s_2-s_1>=n+1\) ，把 \(s_2\) 取到 \(s_1+n\)即可。若 \(s_2-s_1\lt n\)，那么我们知道将两堆各取某些石子，结果必然是 \((\lfloor (s_2-s_1)\alpha\rfloor,\lfloor (s_2-s_1)\alpha\rfloor+(s_2-s_1))\)，为奇异局势。
- \(s_1=\lfloor n\alpha\rfloor+n,s_2\ge s_1\)，将 \(s_2\) 取到 \(\lfloor n\alpha\rfloor\) 即可。

Wythoff 博弈及其扩展 - 知乎 (zhihu.com) 有些对于 \(\alpha,\beta\) 的有趣探讨和扩展。

综上所述，我们就在奇异局势的框架下完成了三个最经典的石子游戏的证明。