经典NIM游戏的变式及NIM型游戏

王姿婷 李建华通讯作者：lijianhua@bnu.edu.cn ② 李友耕.进位制与数学游戏[M].北京：科学出版社，008. pp. -6.

(1.海南省文昌中学 571300；2.北京师范大学数学科学学院 数学与复杂系统教育部重点实验室 100875)

1 前言

经典NIM游戏是一种古老的二人游戏，其规则十分简单，但从3堆开始，其制胜策略就因需用到进位制的转化而变得稍显复杂.事实上，这么多年来，经典NIM游戏仍被人津津乐道，除了它独特的求解思路外，由它衍生出的各种变式游戏也是它在岁月蹉跎中保持熠熠生辉的重要原因.例如，对拿取过程中的规则进行微调就可以得到简单的变式游戏；或者将游戏的形式由取子转为在有限棋盘上行棋，这种变式游戏在与经典NIM游戏进行转化时，有时不十分直接自然，需要对两种游戏的本质特征有一定的了解；另外，还有些已成型的游戏体系，在数学的某些领域内借用某种分析手段进行拆解后，方能看出和经典NIM游戏之间其实是能够互通的，图论中就有这样的游戏模型.相较于第三种类型的变式游戏，从前面两种中找出联系可能更易于接受一些，而前两种变式游戏具体有哪些例子呢？这正是本文将要介绍的内容.

2 经典NIM游戏的变式

2.1 三子冲锋棋

游戏介绍：

此游戏是李友耕所著《进位制与数学游戏》中提到的一种变式棋子游戏——十格三子棋②.在成一横行的若干方格中，随意放上3颗棋子(允许几枚棋子放在同一方格内).游戏双方轮流操作，以从右向左的方向为正方向，任选3颗棋子中的一颗沿着正方向移动到任一方格中(只能前进，不能不动或者后退).走棋子时，可以跳过别的棋子，也可以走在有棋子的方格内.谁把最后一颗棋子走到最左边的方格内，使对方下一步无棋子可走，谁就获胜.

图1

游戏中的数学：

这个游戏存在唯一前进的正方向，而且双方都可以对所有棋子进行操作，前进格数任意，终点是左边的最后一个方格.

实际上，这个游戏可以看成是经典NIM游戏的又一种变形，只不过棋子的堆数变成了棋子的颗数，而每一堆棋子颗数变成了每一颗棋子可走的方格数.如图1所示的三子冲锋棋，以每颗棋子与最左边的方格的距离为考察对象，随着不断前进，与考察对象的距离就越短，刚好对应拿取数目会变少，因此，这里其实就是经典NIM游戏中k=3时的局势(3,7,8)，最终的胜利局势是(0,0,0)，并且，其后手有利的局势就是“NIM和”为0的局势.

若将正方向换至从左向右，则有两种策略，一种是换考察对象为与最右边方格的距离，那么思路无异，还有另一种是照样以每颗棋子与最左边的方格的距离为考察对象，不过此时就变为距离越来越大的游戏了，可以将这样的游戏类型对应原来以拿取为游戏操作的NIM游戏的回溯，若将前者称为“拿取式”，这种规定一个目标终态，由空开始往上加的形式可成为“添加式”，这样的游戏形式可能更适用于教室中的课堂游戏，因为直接往上抢数字即可，抢数字的游戏是纸笔间就可以完成的.另外，可以直观到，“添加式”与“拿取式”的NIM游戏本身就可以很自然的进行切换.

当然，此游戏格子数与棋子数不限于此，同样都可以进行推广，推广后同样还是能够对应回经典NIM游戏.

2.2 靠拢游戏

游戏介绍：

在成一横行的若干个方格里(方格数可以任意划定)，随意挑选某几个方格，在这些方格里各放上一颗棋子，每一个方格所放的棋子都不超过一颗(如图2).随后，规定从右向左为前进的方向，游戏双方轮流操作，任选其中一颗棋子向前走动(只能前进，不能不动或后退).走棋子时，只能走在空格内，不能走到已有棋子的方格内，也不能跳过别的棋子.谁走完棋子后使得对方无法可走，谁就获胜.与三子冲锋棋一样，这也是李友耕提到的一种变式棋子游戏，文中称其为“斗法游戏”.

图2

游戏中的数学：

这款游戏相较于三子冲锋棋又稍微多了些限制，每一格只允许放一颗棋子，而且不允许有超越的操作，这样一来，若仍将每颗棋子与最左端空格的距离为考察对象以期实现将其与经典NIM游戏直接关联的想法就必须好好斟酌一下了，因为并不是任意一颗棋子的距离减少都是任意且连续的了，这与经典NIM游戏是有区别的，那么，其制胜策略该怎么找呢？

由于每一颗棋子都被前面的一颗挡住，故每一颗棋子的活动空间实则为它与它前面相邻的那颗棋子的空格数(最左端的棋子为其前面的空格数)，所以这才是这款游戏应该被考虑的对象.

但我们发现，动一颗棋子以后，它与它前面那颗棋子间的空格数减少了，同时它与它后面那颗棋子间的空格数就增加了，这一增一减的似乎没办法兼顾到，那该怎么办呢？经典NIM游戏中的拿取只会带来棋子数减少的效果，减少只能是所动棋子与其前一颗棋子之间移动后产生的效应，此游戏中，中部的棋子都有两颗棋子与之相邻，那么，可否只考虑它与相邻两颗中的一颗棋子之间的影响呢？若我们只以两两作为一组来考虑，只考虑每组中两颗棋子间空格数的变化，而暂时搁置它的移动对组外另一颗棋子的影响，似乎就能够使得由减所带来的增这一变化得到“缓冲”.

下面，我们两两分组，考虑从左边开始，第1颗棋子与第2颗棋子之间，第3颗棋子与第4颗棋子之间，以及第5与第6颗棋子之间的空格数，而不考虑两两分组之外的相邻棋子间的空格数，拿第1第2颗棋子构成的小组作为例子分析，如果对方动了第1颗，也即往前移动了一格，那么该小组内空格数增大了，我们可以将第2颗也往前移动一格，这样一来该组内空格数没有发生改变，又轮到对方拿棋，也就是说这样的操作下来，我们关注的空格数其实没有发生变化，那么，如果对方动了第2颗呢？那会减少了该组内的空格数，这是能够对应上经典NIM游戏中操作的！也就是说我们确实可以找到这一游戏与经典NIM游戏之间的对应，从左到右依次两两分组后将组内两棋子间的空格数作为关注点，而不考虑其他空格数，如第2颗与第3颗棋子之间的空格数，因为对于这类棋子，对方把后一颗棋子向前移动几步，我方只要移动跟那颗棋子配对的相应棋子，“亦步亦趋”即可，这样一来，我们所关注的两两分好的组内的空格数就不会发生什么变化.如图2的靠拢游戏，就可视为经典NIM游戏中k=3时的局势(4,1,2).并且，对其进行的这种转化后，便可以知道其后手有利的局势就是相应的那些“NIM和”为0的局势.

2.3 闷宫游戏

游戏介绍：

图3所示的是一盘象棋残局，是原载于清代《竹香斋象戏谱》一书中的“双炮禁双炮”闷宫棋局.象棋的具体走法估计读者都不陌生，此处不做过多叙述.

按照中国象棋的规则，把对方憋死(无法动弹)，也算胜利.下面我们看看这一残局中有哪些可动弹的位置：由于炮5的横向移动会导致对方的炮吃掉本方的将(帅)，炮3的横向移动后，对方的炮3直接越过楚河汉界进行将军，故这盘棋双方的炮都不能离开原纵向路径，逼近将(帅)旁边的兵(卒)也不该移动，否则本来能够挟制的将(帅)就逃脱了，必输无疑.因此双方只有两个炮和边上的兵(卒)可动，且只能按沿着纵向移动.

图3

游戏中的数学：

观察上图所示的棋局，由之前的简要分析我们知道，现在也就只有两个炮及边上的兵能移动，而且还是纵向移动，于是我们可以数出：中路两炮相隔4个空位，边上两炮相隔6个空位，边上的兵(卒)相隔2个空位，但实际上只能走一步(否则会被对方吃掉).

随着棋子的移动空位个数会变少，每次只能动一个棋子，这是可以观察到的特点.因此，如果把可移动的空位当成棋子的颗数的话，那么这种棋局，其实就相当于初始状态为(1,4,6)的经典NIM游戏，从我们一直的策略里面可知，这不是一个平衡数组，故若黑方先走，只要第一步走“炮七进一”，就可以稳操胜券，因为此时的局势变为了(1,4,5)的平衡状态.接下来对方要走的就只可能是炮3进4(1,4,1)(那我们就走炮五进四(1,0,1))，兵9进1(0,0,1)(那我们就走炮七进一(0,0,0))，炮3退2(0,0,2)(我们就走炮七进二(0,0,0))，炮三退二(0,0,2)(我们走炮七进二(0,0,0)).因此我们一定能获胜.

故这一游戏的后手有利的局势也是“NIM和”为0的棋局.

这几种NIM型游戏都是基于经典NIM游戏变形而得到的，与前面介绍的几个游戏相比，这一游戏变形较大，颇有点改头换面的意思，但稍加分析会知道，这样的变形仍尚属明显且易辨识的，下面介绍几种直观上将其与NIM游戏建立起联系并不十分简单的游戏.

2.4 翻硬币游戏

游戏介绍：

这款游戏[注]王晓珂.解析一类游戏[J]国家集训队2007论文的规则是：在若干空格中各放置一枚硬币(也可是扑克牌等有可区别两面的道具)，但有些正面朝上，有些反面朝上，游戏的双方轮流选择在正面朝上的硬币中选择一枚翻至反面，若愿意，可同时选择该枚硬币左边的任意一枚硬币进行翻面(可正变反亦可反变正)，最后无法操作者为败.不妨令黑色代表正面，白色反面，如图4，即为八个硬币的某一布局.

一排硬币摆在桌面上，只能对其进行翻面处理，估计游戏一开始，你能做的就只是盘算着自己应该翻哪一枚硬币而且该不该将其左面的某一枚棋子进行翻面，并猜测对手会有什么样的心思，你不知道这里面能有什么技巧，正如你不知道这竟能与经典NIM游戏沾上关系一般.

图4

游戏中的数学：

在正式进入分析之前，我们不妨先给桌上的硬币从小到大编个号，如图5所示，若将正面的硬币视为一堆棋子，对应的编号视作这堆棋子的颗数，那么我们就可以将这一游戏的操作放在我们熟悉的NIM游戏中进行考虑了.下面我们分类讨论一下所有可行的操作：1. 将某一正面硬币翻至反面.刚刚将正面联系为有棋子，故此举可视为将这堆棋子全数取走；2. 若在第1中操作的同时又翻动了左边一枚反面硬币.反面变正面，相当于又有一堆出现，结合第1步的操作，其实这意味着将原来那堆棋子的数目切换至现反面硬币翻正的这一堆棋子所代表的编号颗数，故先前我们编号时左小右大其实是有用意的，因为这样的操作正好可以视为将某堆棋子取少达到的效果；3. 当然，若同时翻动的是左边的一枚正面硬币，则意味着同时将两这堆棋子取尽.

由于在于棋子游戏建立联系的分析过程中发现，第3种操作是会动到2堆棋子的，而且这种情况下只能将这两堆都取尽，故与穆尔游戏k=2中取棋子数目任意这一特点又不相同.不过需注意到的是，同时取尽的两堆从编号上可以知道，它们数目一定是不等的，所以不妨再回到经典NIM游戏的角度找一下其平衡局势.

若某一硬币局面为一个平衡局势，由之前对三种操作手法的分析知道，由于之后对手最多在转变为棋子游戏的意义上操作两堆硬币，若此时又出现了一个平衡状态，那么意味着之前那个平衡局势实为原两个堆数为2的有利局势的组合，而堆数为2的有利局势是(p,p)形式的局势，故这是(p,p,q,q,k)的一个平衡局势，由于任意一个编号格子内只能有一个正面朝上的硬币，因此这种状态在此游戏中颗本不存在，换句话说，后手只能造出非平衡的局势；而由前面对经典NIM游戏的分析，我们知道任意给出一个非平衡的数组，总能适当减小某一个数从而达到恢复平衡数组的目的，而这刚好对应第二种操作手法.

图5

2.5 楼梯移物

游戏介绍：

首先，在地面上放置有一个n阶的楼梯，其中每一阶楼梯上都放着若干形状大小相同的物块，游戏者每次可以选择任意一阶并将其上任意数量(大于等于一)的物块移至下一阶楼梯上，游戏双方轮流进行决策，最终谁先将物块全部移至地面即可获胜.如图6即为分别放置有3、6、4、8、5的五阶楼梯.

图6

游戏中的数学：

有了先前若干游戏的经验以后，你可能会猜想这次是不是可以将每一阶楼梯上的物块数视为各堆棋子的颗数呢？但如果你对经典NIM游戏最初概念的认识是正确的话，你会知道这一猜想是不可行的，因为移动不代表取走，NIM游戏中只有往外减少的操作，没有往内增加一说，而下移就意味着下一级阶梯上的棋子变多了呀，故这种想法是不理想的.

有了上一种游戏的分析做铺垫，我们也可以类似地想一下，能否也只考虑某些位置而暂时搁置其他位置呢？不能往里加的话，那如果能把某些阶梯看做是寄存箱一样的存在，往里添加不影响外围环境，需要取走时再取，这样一来，那不就可以摆脱先前想法遇到的尴尬境地了吗？

于是问题又来了，哪些阶梯适合扮演这样的角色呢？若把地面看做是第0阶的楼梯，那么这一阶楼梯显然可以作为我们的寄存箱，除此以外还有吗？借着0阶的想法，若把偶数阶的楼梯通通看做是寄存箱的话会怎样呢？奇数阶的物块移至偶数阶上即为寄存，偶数阶如有物块移至到了奇数阶，我们可以将这些物块再次往下移至另一偶数阶，从而保证奇数阶两次操作后相当于没变化，这样一来，至少可以保证奇数阶上的物块数就能够和经典NIM游戏发生对应的了！而且制胜策略也呼之欲出！最终奇数阶上的物块都会被移动至偶数阶上，那么之后要做的就只是亦步亦趋的跟随对手移动了，他移动一次只能将若干物块移至某一奇数阶，那我们也移动的数目到紧邻的偶数阶上.不用多说读者就能够发现，这样一来，最后总将是我们能够获胜.

不得不说，要迅速看出这一变式与NIM游戏之间的联系并非易事，尤其是这里需要将某些位置等同地面，暂且搁置这一想法并不十分自然.稍微细心一点的读者或许会发现此游戏与“靠拢游戏”思维上相近之处，都是只考虑当中的某些位置而将剩余位置搁置一旁.事实上，若将“靠拢游戏”中的任意空格与此空格右边最近的空格之间的整个空间视作是一阶楼梯，最后一个空格的右边可以看做是地面，而每段空间中所包含的棋子数视为物块数，那么两个游戏就能够完全等价了！这可以让我们用一个新的视角去审视“靠拢游戏”，从而获得不一样的心理体验.

3 NIM型游戏

3.1 穆尔游戏

“穆尔”(E.H.Moore)游戏[注]E.H.Moore, A generalization of the game called nim, Annals of Mathematics,1910,series 2,Vol.X1,pp.90-94.的规则与经典NIM游戏的规则基本相同，唯一有区别的地方是：玩家的每一步，可以从任意不超过k堆中取棋子，也即：在桌面上若干堆放置任意数目的棋子中，游戏的双方依次轮流拿取，并要求每人每次可以从任意不超过k堆中取棋子，每堆中取棋子的数目任意，但不能不取，最终谁先把棋子取完就算获胜.事实上，经典NIM游戏只能在一堆中拿取，就可以看成是k=1时的“穆尔”游戏.

游戏中的数学:

我们从最简单的情况2堆开始讨论，当k=1时已在经典NIM游戏中讨论清楚，而我们又容易看到k=2时先手直接可以将所有棋子都取走，显然无意义，另外我们还会知道，当在桌上有T堆棋子且k=T时也一样无讨论的必要，故我们下面讨论1

3堆中k=2时，那么(1,1,1)就是先手必败，我们要竭力给对方留出这样的局势，很快会发现(2,2，2)也是，因为无论对方如何拿取，我们都可以取至(1,1,1)或者(0,0,0).于是我们可以考虑(n,n,n)是否都是先手必败的局面.这就可以尝试用归纳假设进行证明了.

假设当0≤n≤m时(n,n,n)都是先手必败的局面.则当n=m+1时，我们知道，面对(m+1,m+1,m+1)，对方只能在一堆或两堆中取，即取至(p,m+1,m+1)或(p,q,m+1)其中p和q都是小于m+1的自然数，不妨设p≤q

显然(n,n,n)这种先手必败的局面能够满足我们在经典NIM游戏中的给出过的平衡数组的定义，接下来我们考虑，是否还存在其他的平衡数组能与其构成连贯的策略体.

答案是否定的，正如前面归纳假设的证明中所示，当三堆棋子数不全相等时，也即为(p,n,n)或(p,q,n)，那么先手都可以一步将其取至(p,p,p)，故在3堆的情况中，只有(n,n,n)是先手必败的，其余都是先手必赢，而它们是这种游戏情形下平衡数组的形式.

4堆时，先考虑k=3的情况，因为这种比较简单.显然(1,1,1,1)先手必败，且(2,2,2,2)也是先手必败，这与3堆中k=2时的情况非常类似，故我们会直接想，这样的拿取限制中，平衡数组是不是(n,n,n,n)，答案显然也是成立的，也可以通过归纳假设来证明.

所以在面对4堆中k=2的情况时，我们可以想一下，是否有可能将棋子数进行一定的转化，使之能够体现出，先手只能使2个以内的位置发生变化而我们就能够动到第3个位置这样的形态.于是我们又能联想到经典NIM游戏中的处理办法，这其实很自然，因为这两种游戏的规则类似，解法或许也有相通之处.在经典NIM游戏中的处理办法是将棋子数用二进制表示出来，这里我们就可以考虑也换一个进位制，沿用二进制还是换一个三进制比较好呢？先考虑，三进制的话，数字全由0、1、2构成，那平衡数组是写成三进制时每列保证有3个1或3个2或都是0吗？但是当这样的状态被破坏时，能一步回去吗？似乎不行，例如这样一个例子：

那用三进制给出平衡数组难不成是一列中和能被3整除就行？但是像1+2变为0+0这样的情况，就只需动两堆，也就是一步可以达到的，用不到3堆就意味着对方的操作并不是一定所想状态破坏掉的，所以这也不是我们想要的.更何况，我们还要知道，我们现在仅仅是讨论4堆的情况而已，若以后要考虑十几堆的情况，难道也要用十几进制吗？这显然有点不太实际，所以我们还是只考虑二进制吧.二进制的话，将数字排列后，前面那种想法通过确保每一列上有3个1或3个0好像就可以了，因为对方最多动两堆，所以这种局势一定是会被破坏的，而我们也一定能够一步还原回去！也就是k=2时将棋子数转化为二进制后做列和保证每列都能被k+1=3整除就行，回过头来看，在堆数为3，k=2时先手必败局势(n,n,n)以及堆数为4，k=3时的先手必败局势(n,n,n,n)，确实都能满足这一条件，故我们之前认为的突破口可能是k+1这一设想得到印证.

其实回过头来看，先前在经典NIM游戏中定义“NIM和”概念来进行规律解释的过程，其实也是有学问的.若耐心思考，会发现用二进制数作不进位的“列和”之后模2的用意.由于保证局势的“NIM和”为0后，先手只能在一堆中取棋子，故在拿取完后不可能存在某一列发生了改变却依然能够在作“列和”时模2余0，故先手必打破这种局势，而后手紧接着又能恢复.

放到这里看，其实很容易迁移过来，若规则只许在任意不超过k堆中取棋子，若能够保证之前的状态在化为二进制数后作不进位的“列和”模k+1余0，则先手无论怎么拿取都不可能紧接着造出这样的“列和”模k+1余0的状态！

于是再定义一个“NIM K和”*张远南，栾少波.游戏：拍案称奇[M]上海：上海教育出版社，2011.4. pp. 121;116-136：把每一堆棋子的数目用二进制数表示出来以后，将这几个数作不进位的“列和”后求其模的k+1余数，其结果即为这几个数的“NIM K和”.

又由上面的分析，我们知道，对于“穆尔”游戏，局势的“NIM K和”为0时，为平衡数组.

例如，在可以任意在k=3的“穆尔”游戏中，(1,3,5,7,9,11,13,15)是平衡数组，这是因为

但是在k=2的“穆尔”游戏中该局势便为不利局势了，因为4448(mod3)=1112(mod3)≠0(mod3).(未完待续)

敬告：本刊2016年精装合订本已装订完成，每套100元(含挂号费)，欢迎邮购.汇款地址：北京师范大学数学通报编辑部，邮编：100875，收款人：数学通报编辑部.

说明：本刊的2344问题，在编辑校阅过程中，发现原题的表述不甚严谨，故改为2017年第一期中题目的形式；但在第二期刊出解答时，由于疏忽，又把原题刊载出来，给读者造成了困扰，特为致歉！再有，2017年第二期问题栏的两个小标题，也是由于工作不细致，导致与第一期的一样，此二处应分别是“2017年1月号问题解答”、“2017年2月号问题”.真诚地向广大读者致歉！