Nim 游戏的若干变种

今年我为北京世纪坛的数学益智游戏展贡献了不少内容。我打算在这里记录一些自己的创作、发现、收获和心得。这是该系列的第三篇。

今年的数学益智游戏展有一个特色,就是到访者可以购买一个小册子,这可以为自己的参展体验加分。我们内部把它叫作“任务单”。任务单里有很多任务,对应了展会中的各种项目。完成任务可以获得印章,赢取奖励。为了增加任务单的附加价值,任务单上还附赠了很多简单展品的高级玩法说明。这里举一个有趣的例子。

展会现场有很多冰糕棍,可以用来做冰糕棍炸弹。任务单上给出了冰糕棍的另一种玩法——Nim 游戏。将冰糕棍从左到右摆成若干堆。两人轮流从其中一堆冰糕棍中取走任意数量的冰糕棍(可以全部取走,但不能不取)。取走最后一根冰糕棍的玩家获胜。

考虑到任务单的读者可能已经熟悉 Nim 游戏了,因此为了让所有人都能有新的收获,我补充了一些不太常见的 Nim 游戏变种。我一共准备了 10 条补充规则。游戏开始前,双方可以任选其中一条来玩。

  1. 每次只能从最左端或者最右端的那一堆中取冰糕棍。
  2. 每次只能从冰糕棍数最多的那一堆中取冰糕棍(如果冰糕棍数最多的堆出现了并列的情况,任选其中一堆即可)。
  3. 每次只能从冰糕棍数最少的那一堆中取冰糕棍(如果冰糕棍数最少的堆出现了并列的情况,任选其中一堆即可)。
  4. 第一个人可以从任意一堆中取冰糕棍,今后每个人只能从和刚才不同的堆中取冰糕棍。
  5. 第一个人可以从任意一堆中取冰糕棍,今后每个人只能从和刚才相邻的堆中取冰糕棍。
  6. 第一个人可以从任意一堆中取冰糕棍,今后每个人只能从和刚才相同的堆中取冰糕棍(除非刚才那一堆被取完了)。
  7. 每次取完后,还可以再从另一堆中取走同样多的冰糕棍。
  8. 每次取冰糕棍的数目改为最多 3 根。
  9. 取走最后一根冰糕棍的玩家算输。

还差一条,应该写什么呢?我有三个备选方案。大家可以猜一猜,我最后用了哪个方案。

  • 游戏双方各有一次“跳过”的机会。
  • 游戏中有一次“跳过”的机会,任意玩家使用后该机会作废。
  • 每次对方取完后,如果他还有别的取法,你便能要求他该轮换一种取法。


这三条补充规则都挺有意思,它们都在一个更底层的层面修改了游戏规则。我们都来分析一下。Nim 游戏里局面信息透明,不含运气成分,不会有平局产生中,所以一定有一个人拥有必胜策略。对于有的开局,先手拥有必胜策略。对于另外的开局,后手拥有必胜策略。

如果游戏双方各有一次“跳过”的机会,整个游戏跟原版其实没啥区别。对于任意一种开局,在原版中不管是先手必胜还是后手必胜,这个人在新版中仍然能够必胜。他只需要在对方选择跳过时也立即选择跳过(自己绝不主动跳过),就能把对方的跳过机会给抵消掉。一切就变回成传统的 Nim 游戏了。所以,我没有采用第一个方案。

如果整个游戏只有一次“跳过”的机会呢?情况会变得更有意思。如果一个局面在原版的 Nim 游戏中是后手必胜的,那么在新版的 Nim 游戏中,先手上来就选择跳过,从而变成后手,便能赢得胜利。

如果一个局面在原版的 Nim 游戏中是先手必胜的?让我们看看 (1, 2) 这个局面。在原版的 Nim 游戏中,它是先手必胜的。先手可以拿走后一堆中的一根冰糕棍,接下来只能是每人各拿一根,从而先手获胜。在新版的 Nim 游戏中,先手显然不会上来就用“跳过”,把必胜局面拱手让给对方;先手也不会把其中一堆取光,不然直接就输了。所以,他只能像刚才一样,把 (1, 2) 变成 (1, 1)。接下来,两人本该一人拿一根,但后手可以用一次“跳过”,从而取得最后一根。所以胜负关系也交换了。

两版 Nim 游戏的胜负关系总是颠倒的吗?不是。(1, 3) 这个局面在两版游戏中都是先手必胜的。原版中,先手直接把 (1, 3) 变成 (1, 1),就也必胜了。新版中,先手把 (1, 3) 变成 (1, 2),他就成了上一段讨论的开局中的后手,从而获得胜利。

所以,第二个方案看上去很不平凡。但是我也没采用。原因很简单——在普通玩家看来,“跳过”这个行为似乎没啥价值,正面反馈不够大。游戏时,大家可能会想:我明明可以多拿些冰糕棍,为什么想要跳过呢?因而,游戏为啥变得不一样了,这并不显然。

最终我选择了方案三。每轮对方首次取完后,只要对方还有别的取法,你都可以要求他换成新的取法。这种推翻对方取法的权力会给人一种兴奋感,让人跃跃欲试。它给游戏带来的变化也很明显:策略上变得更宏观,更复杂了。我的一步好棋可能会被对方否决掉,而我故意先走一步不好的,对方就直接接受了!

我把这个游戏叫作“带有否决的 Nim 游戏”。游戏灵感来自于 Erich Friedman 提出的 Veto Nim。但是我对否决的理解肯定跟 Erich Friedman 不一样,因为我们算出来必胜必败局面不相符。Erich Friedman 的否决是啥意思,我现在还没弄清楚。

我把带有否决的 Nim 游戏做成了一个小游戏。大家可以在游戏中体验这个规则给游戏带来的变化。详细的分析我就不写了。大家边玩儿边思考吧。

45 条评论

发表评论

  ×  1  =  6