
(2014年7月27日更新完毕,修正之前错误。转载请注明作者及出处。)
【长文,多图预警】
“围住神经猫”虽然是一个小游戏,但细细想来,其实也是一个很有意思、值得探讨的数学问题。
先抛出结论:在原游戏的条件下,由于初始占有点的随机性,在考虑最坏情况下(如一个点都没占有),无法确保围住神经猫。但是,当棋盘扩展到一定程度时(M不小于9,M的定义会在下面说明),无论初始状态如何,存在策略,必能围住神经猫。下面给出本人对这个问题较为详尽的分析,个人观点,仅供参考。从表面上看,神经猫能走到的格子数是9×9=81格,但这个“棋盘”并不是对称的,神经猫只需要走4步就能到棋盘的边缘,而一旦被神经猫逃到棋盘边缘,游戏就结束了。神经猫的逃跑策略是贪心算法,也就是说,它总是考虑当下离边缘最近的路线。实际上,如下图所示,神经猫4步可以走到的格子被深红色标出,其中带五角星的是棋盘的边缘。
神经猫显然会尽可能地往带五角星的格子逃跑,而我们要做的便是在猫到达五角星格子以前,把它拦住。为了便于讨论,我们考虑更具有代表性的问题,如下图所示:问题描述:在一个边长为M(上图中M=5)正六边形的棋盘上,要在最坏情况下,依然确保能抓住神经猫,令最小能满足条件的M为N,求N的值。
下面证明,N=9。
(特别感谢 @shepherd 指出原证明(N=8)的谬误之处,实际上当M=8时,并不能确保捉住神经猫。为此我不得不将前面的证明完全推倒重来。所幸的是,我又及时找到了一个截然不同的证明,目前看来是正确的)
如觉得证明过于数学化,可跳过该证明,直接看文末总结的本游戏技巧。
——————————————————————————————————
—————————————证明开始的分界线—————————————
——————————————————————————————————
引理部分:
定义1:
如下图所示,橙色点组成的橙环将绿色点组成的绿环完全包住,且满足以下条件:
(1)将所有绿点依次连接,恰能组成一个封闭环而没有多余的线;
(2)对于每一个橙色点,都有绿色点与之相邻(小菱形的长对角线两点不相邻);
(3)对于每一个绿色点,都有橙色点与之相邻。
满足以上条件,称橙环是绿环的一个紧包。
引理1:若A环是B环的一个紧包,那么A环包含的点数比B环包含的点数多6。
证明:
用数学归纳法。
如上图所示,3个绿点恰好被9个橙点包住,结论成立。
如上图所示,第一张图是正常情况,黄色点比浅绿色点多1个,第二张和第三张图为凸出和凹下去的情况,无论哪种情况,虽然黄色点和浅绿色的点的数目增长了(每处凸出或凹进都能增加1个点),但是它们的差依然不变。
(亦可手动验证一下,结论是成立的,如下图所示,橙:绿:天蓝=40:34:28).
引理2:游戏时,防守方若要把进攻方包住,必须要在进攻方的运动路线生成封闭环1步之前形成该环的一个紧包。
此处仅稍作说明。
如下图所示,冷色为进攻方,暖色为防守方(双方均未采取最佳策略),当橙50形成紧包时,进攻方至少还有1步才能生成封闭环。
反之,如果在进攻方路线形成环前1步时防守方尚未形成紧包,进攻方不必形成环,而可从那个缺口冲出。(从表面上看,似乎防守方可以留下一个角,如不占领下图的26,进攻方好像不经过41就出不去,不过实际上,这不是防守方所能控制的,路线是进攻方决定的,他完全可以不往包围圈的角落钻。)
引理3:如防守方先落子,且在进攻方冲出之前,形成一个封闭环,则进攻方的路线中,与封闭环不相邻的点至少为6个。
证明:因为双方是轮流行动,防守方的行动次数至多比进攻方多1,由引理1和引理2易得该结论。(如在上图中,防守方先行(红0),则天蓝色的6个点为与防守方封闭环不相邻的点。)
定义2:称某个位置为第n路,若神经猫至少要n-1步才能到达棋盘边缘。
棋盘的最外1圈为第1路,它紧包的里面一圈为第2路,以此类推。边长为M的六边形,中心点为第M路。
引理4:当进攻方来到第3路时,防守方必须在第1路的相应位置进行防御才能让其不从上方逃出。
证明:
如上图所示,绿1后,橙2必须在最上方封堵,才能避免其从上方逃出;特别地,在角上,蓝1后,防守方必须将两个五角星的点都必须占据才行。
引理部分结束。
回到原题。
第一部分:M=8时,在最坏情况下,无论怎么防守,神经猫存在策略,必能逃脱证明:
见下图
这是原来N=8的拦截方案,但可惜的是,这个方案是错误的。红2、4、6在第2路的防守方案,实际上并不能拦住神经猫。至绿37,神经猫安然逃出。
那如果拦在第1路呢?见下图。
殊途同归,至绿41,神经猫又跑出去了。
实际上,对于M=8,如果没有直接的拦截,神经猫只要6步就能跑到第2路,此时必然会和防守方短兵相接。如果防守方强行不让神经猫来到第2路,则会更快地短兵相接,如下图所示,在第5步时,神经猫就和防守子力短兵相接了。
当神经猫和防守子力短兵相接时,它只需要做一件事:贴着你的防守子走。于是,无论哪种情况,神经猫至多只有前5步是和防守方的子力不相接的。由引理3可知,我无法在神经猫逃出之前形成封闭环,所以必然会被神经猫逃出。
第一部分证毕!
第二部分:当M=9时,即使在最坏情况下,我总有策略,必能围住神经猫。
证明:
如上图所示,我不用管神经猫如何行动,只要依次占据0、2、4、6、8、10六个点即可。至橙10,神经猫最快只能来到第4路。
好了,绿11终于来到了第3路,由引理4可知,我只要拦在12位即可。
下图为变化图,至橙94,神经猫终于被我围住了!
第二部分证毕!
由第一部分和第二部分的结论,即证:N=9。
——————————————————————————————————
—————————————证明结束的分界线—————————————
——————————————————————————————————
回到原游戏。从上面的分析可以感受到“围住神经猫”的技巧精髓有如下几点:
0、游戏的精髓,不是用最少的步数围住神经猫,因为就步数而言,受开局影响太大,主要靠运气;游戏的精髓,是在特定开局情况下(我无法改变):
(1)尽最大可能,确保围住神经猫;
(2)在确保1的情况下,尽可能使包围圈小,从而减少围住它的步数。
1、慎勿轻速。除非有援兵,否则应该要远远地张开一张大网,在己方很弱的情况下,切勿轻敌。因为你的速度不比神经猫快,所以直接近身堵截,你总是会慢一步。当你在部署完防御之前,和神经猫短兵相接,你就跪了。2、包围圈的设计。
由引理3,有推论:当神经猫和我的包围圈短兵相接之前,如果神经猫足够聪明,我必须保证,在我的包围圈,已经布置至少7个子。且尽可能在6个方向上都有子力分布。
如下图所示,如何围住神经猫?
易见,神经猫至多3步就可以与我的防守子力短兵相接。而我设计的包围圈已经有了4个子,所以我接下来的3个子,都必须用于包围圈的设计。
如下的包围圈是可行的:
然后就开始撒下大网:
至红5,大网所需的7点已经占领完毕,神经猫已经无法逃出。
如果它负隅顽抗,参见下图,至40,它终于进入了包围圈。
但是如果包围圈设计得不好呢?如下图所示,左下角的包围圈,神经猫只要2步就可以短兵相接了。
如下图,到白4,实际上你已经围不住神经猫了。
接下来的攻防如几乎是必然的,至白26,神经猫安然逃出。
所以,设计包围圈是很重要的!能不能围住就在可能就在1路之间!
(注:本例证明了,如果神经猫足够聪明,起始的时候,你至少要有4个子,且位置合理,才有机会捉住它。)
3、由于实际游戏中,神经猫没那么聪明,它在左上方有通道的情况下会一味地往左上方逃跑,而不会拐弯,所以,在左上防御充分的前提下,还是尽可能在其它位置做好防御,防患于未然嘛。
(一个具体的例子:参见果壳关于“围住神经猫”的最小步数和最优策略)
如图,正因为神经猫一开始总是往左上角跑,所以这种状态才能围住它,如果神经猫往左下或右上跑,其实是围不住的。
4、上面已经证明,当M=9时,我才能确保捉住神经猫。而实际游戏的情况,只比M=5略好一些。
故,必然存在某些情况,因为自己子力太弱,自己根本无法捉住神经猫
——这个时候,就放小猫咪一个生路好了。
