25
Jul
小游戏“围住神经猫”背后的数学问题
一夜之间，微信朋友圈便被这个有趣的小游戏“围住神经猫”刷屏了。如果没有见过的可以点开这个链接玩玩看：围住神经猫。一开始看到刷屏的小游戏，我不以为意，以为又是一个无聊的游戏罢了，但是当进去玩了一次之后，便恍然大悟为什么它会火了：这不就是数学游戏界神人John Conway设计的“天使与魔鬼”游戏么！John Comway最有名的数学游戏作品大概是“生命游戏”了，其规则之简单和产生的变化之丰富多彩实在是让人叹为观止；另外著名的“自由意志定理”也出自他的手中。这次的“天使与魔鬼”游戏，于1982年发表，也是他的作品中极其有趣的一个。
最原始的“天使与魔鬼”游戏规则是这样的：在无限大的2维正方形格点上，两个玩家，分别称为天使和魔鬼，轮流行动。初始时，格点是空的，只有天使站在棋盘的原点处。魔鬼每轮的行动是可以在天使站立的格点之外的任意一个格点处挖一个陷阱，挖好的陷阱会始终存在在棋盘上；天使每轮的行动是可以每次移动至多k步，其中每一步可以是横向、竖向或者斜向走一格，k为正整数。下图为示意图，红色是魔鬼挖好的陷阱，而蓝色虚线框表示k=3时天使一次行动可以到达的范围。天使行动时可以跨过陷阱，但是不可以踩在陷阱上。最终，如果天使被围困得无论如何也不得不踩在陷阱上，魔鬼就赢了；如果天使可以无限地逃跑，天使就赢了。问题是：k等于几的时候魔鬼有必胜策略，等于几的时候天使就有必胜策略了？…
