【宅系】围住神经猫攻略来啦，整个人都精神多了（多图）

*发表于 2014-7-27 13:31:50* | 查看: 558| 回复: 2 · 发表于 2014-7-27 13:31:50

在微信游戏“围住神经猫”中，有什么有效的策略来围住神经猫？

知乎用户，INTJ / 完美主义者 / 趣题爱好者

（【长文，多图预警】，2014 年 7 月 26 日已更新完毕）

“围住神经猫”虽然是一个小游戏，但细细想来，其实也是一个很有意思、值得探讨的数学问题。

先抛出结论：

在原游戏的条件下，由于初始占有点的随机性，在考虑最坏情况下（如一个点都没占有），无法确保围住神经猫。但是，当棋盘扩展到一定程度时（M 不小于 8，M 的定义会在下面说明），无论初始状态如何，存在策略，必能围住神经猫。

下面给出本人对这个问题较为详尽的分析，个人观点，仅供参考。

如觉得证明过于复杂，可跳过证明，直接看文末总结的本游戏技巧。
————————————————
从表面上看，神经猫能走到的格子数是 9×9=81 格，但这个“棋盘”并不是对称的，神经猫只需要走 4 步就能到棋盘的边缘，而一旦被神经猫逃到棋盘边缘，游戏就结束了。
神经猫的逃跑策略是贪心算法，也就是说，它总是考虑当下离边缘最近的路线。
实际上，如下图所示，神经猫 4 步可以走到的格子被深红色标出，其中带五角星的是棋盘的边缘。

神经猫显然会尽可能地往带五角星的格子逃跑，而我们要做的便是在猫到达五角星格子以前，把它拦住。
为了便于讨论，我们考虑更具有代表性的问题，如下图所示：

问题描述：在一个边长为 M（上图中 M=5）正六边形的棋盘上，要在最坏情况下，依然确保能抓住神经猫，令最小能满足条件的 M 为 N，求 N 的值。
本文证明，N=8。接下来，让我们在数学的海洋中遨游吧！
————————————————
————证明开始的分界线————
————————————————
第一部分：M=8 时，在任意初始状态下，均存在策略，可以确保围住神经猫。
引理 1：
在下图中，神经猫先行，它无法逃出。

经过穷举，这个结论是容易证明的，下图给出一种神经猫企图逃出却失败的例子：数字代表次序，蓝色的数字是神经猫的逃跑路线，橙色数字是我封堵的路线，请注意观察橙 2、4、6、12 的封堵技巧。显而易见，神经猫无法逃出。

引理 1 证毕。
下面证明 N=8 时，无论神经猫用什么办法，总存在策略将其围住。
只需证明，初始状态什么都没有的时候，依然可以围住神经猫即可（如下图所示）。

由于第一步之前，我们并不知道神经猫往哪个方向逃走，因此如果神经猫足够聪明，它显然会根据你的堵截方向，向反方向逃跑，因此第一步的阻拦的作用是微乎其微的。故作较坏打算：假设神经猫先行。
由对称性，不妨设神经猫第一步试图左上方逃走，于是如下图所示。

蓝 1 向左上行，橙 2 拦在了一个很远的地方，围棋十诀有云：慎勿轻速。虽然敌人看起来很遥远，但是还应该小心翼翼地渐渐靠近它，万万不可一开始就近身肉搏。

1）神经猫 A 是个楞头青，认为只要努力就能冲出重围，于是始终往左上跑

到橙 6，由引理可知，神经猫已经无法从左上方逃走。
于是 A 企图转向，可是，如果它扭头就走——

至橙 12，我方已经占据了包围蓝方的有利地形，显然神经猫已经无法从坐下方跑出了，如果它想从其它位置出去，则显然更加不可能了。
如果 A 选择慢慢转向——

看起来似乎要逃出去了，但终究差一口气啊……
神经猫 A，扑街。

2）神经猫 B 似乎聪明了很多，它会视情况，选择性地躲着敌人跑
看到橙 2 的堵截，B 选择了躲避，往又上走，可惜，我方技高一筹，放在了橙 4 的位置，如下图所示——

至橙 14，殊途同归，神经猫 B 依然无法逃脱。
神经猫 B，扑街。

3）神经猫 C 是一个谨慎的猫咪，它见到敌人，尽量躲避
如下图所示，蓝 5 很及时的转向，可是道高一尺，魔高一丈，橙 6 看似不着边际，其实上是张开了一张大网，至橙 8，C 已经无法逃出了。

神经猫 C，扑街。

4）神经猫 D 是一个胆小的猫咪，它见到敌人，扭头就走
如下图所示，蓝 3、5、7、9、11 皆是躲着防线在跑，可是，至橙 12，我方已经张开一个六边形的大网，等着 D 的到来，D 终究要面对被擒的现实。

神经猫 D，扑街。

于是，神经猫终究逃不出我的手掌心。
其实细心的你应该已经发现，我只要想办法尽快占据下图的紫色圈就可以确保擒住神经猫了。

由于我们只在乎神经猫的位置而不在意它的运动路径，故可以总结一个简化的证明：

① 神经猫在绿色位置（需要 3 步）时，我至少占据了三个红色点；

② 神经猫在天蓝色位置（同样需要 3 步）时，我至少占据了三个褐色点；

在①和②的情况下，前文中的 1）和 2）已经说明，它是逃不走的。
而实际上，由对称性，神经猫要逃走，必须要经过绿色点或者天蓝色点，既然这两种情况它无法逃出，那么所有情况它都无法逃出。

综上所述，M=8 时，总能抓住神经猫，得证。#
第二部分：当 M=7 时，在最坏的初始状态下，神经猫存在策略，可以确保逃走。

看起来只是差了 1 路而已，能有多大差别呢？

引理 2：
当神经猫在绿色格子时，如果我在橙色线后的防御不超过 3 点，则神经猫可以逃出。

证明方法是穷举。
（1）假设所有部署都在红线后
①

②

③

P.S. 如果在最外一圈部署防御，效果并不比在倒数第二圈布置防御更好，这里就不一一列举了。

（2）有防御在橙线和红线之间

引理 2 证毕。
那么，我们能阻止神经猫来到绿色点吗？
我们发现，当神经猫迈出坚实的第一步时，即使我们想方设法不让神经猫在 3 步之内来到绿色点，但我们已经无法阻止它来到 4 个天蓝色点之一的点了。

如下图所示，当神经猫来到天蓝色点时，我们需要三点的防御才能防止它从绿线上方逃走，仅仅两个点显然是防不住的。

但是，我要防止你 3 步内到绿色点，必定要在橙线前布置防御啊，显然无法在橙线后面占据 3 个点。
我既不能让你到绿色点，又不能让你在到达天蓝色点时，派 3 员小兵来盯防你，这两个条件，显然是矛盾的。
综上所述，M=7 时，在最坏情况下，神经猫必能逃走，得证。#
由第一部分和第二部分的结论，即证：N=8。
————————————————
————证明结束的分界线————
————————————————
回到原游戏。从上面的分析可以感受到“围住神经猫”的技巧精髓有如下几点：

1、慎勿轻速。除非有援兵，否则应该要远远地张开一张大网，在己方很弱的情况下，切勿轻敌。因为你的速度不比神经猫快，所以直接近身堵截，你总是慢一步啦。

2、“二间跳”是一个很实用的防御手段，如下图所示：

当然，“二间跳”后的“双飞燕”也是很重要的，这样就彻底守住了。如下图所示：

3、由于游戏中神经猫比较笨，它在左上方有通道的情况下会一味地往左上方逃跑，而不会拐弯，所以，在左上防御充分的前提下，还是尽可能在其它位置做好防御，防患于未然嘛。

（网上有初始 4 个点围住神经猫的例子，参见果壳关于“围住神经猫”的最小步数和最优策略）

如图，正因为神经猫一开始总是往左上角跑，所以这种状态才能围住它，如果神经猫往左下或右上跑，是万万围不住的。

4、上面已经说了，当 N=8 的时候，我才能确保捉住神经猫，对于本题来说，相当比 N=5 略好一些，确实有些情况，因为自己子力太弱，自己根本无法捉住神经猫——这个时候，就放小猫咪一个生路好了，它很可怜的啦。