時間過得真快，大家不是還在盡情享受假期嗎？假期當(dāng)然不能沒有游戲。這最后一個懶惰的休息日，還不如讓小編制帶你玩?zhèn)€小游戲。(威廉莎士比亞，《哈姆雷特》，《度假名言》)在這個小游戲中，點擊一下，圍繞可愛的貓盡情地。呵呵，享受寒冷的勝利吧！

回到正題。

今天要講的游戲叫做圍小貓，2021年底在小編我的朋友圈里著實是火了一把，如果你還沒有玩過，可以在搜索引擎中搜索“圍小貓”。記憶力好的讀者可能會記得，這款游戲并不是第一次火了，沒錯，它就是2014年曾在朋友圈大火過的“圍住神經(jīng)貓”的新皮膚！其原型可以追溯到更早。

上次小編我還未出山放過了你，這次既然被我逮到了，嘿嘿，今天我不把你圍住，我就不是中二所小編！

游 戲 介 紹

首先介紹一下游戲規(guī)則。起始小貓位于棋盤中心，6-8個障礙物會被預(yù)先隨機放置在地圖上。我方每次點擊小圓點就可以在該處放置一個障礙物，而小貓也會向地圖邊緣移動一格，這樣不斷重復(fù)下去，直到貓貓被障礙物圍住游戲勝利，或者到達(dá)地圖邊緣溜走游戲失敗。

初上手的時候你會發(fā)現(xiàn)，這個游戲并不簡單，幾乎很難成功。因為棋盤其實并不大，貓只需要5步就可以跑出棋盤邊界，很難將小貓堵住。

那么一個自然而然的問題是：如果棋盤足夠大，可以保證將小貓堵住嗎？在回答這個問題之前，請讓我先介紹一下“天使問題”（angel problem）。

天 使 問 題

天使問題首次見于1982年出版的《Winning Ways》一書，由書作者數(shù)學(xué)家約翰·H·康威（John H. Conway）提出。這是一個雙方玩家分別扮演天使和惡魔的博弈游戲。游戲在一個無限大方格棋盤上進(jìn)行，起始棋盤是空的。定義正整數(shù)k為天使的階數(shù)，k階天使每步可以跳到k*k范圍內(nèi)的任何一格，無論路上有沒有障礙物。

圖1 藍(lán)色虛線框內(nèi)為3階天使的移動范圍|圖源維基百科

每一輪中，惡魔可以在棋盤上放置一個障礙物，但不可放在當(dāng)前天使所在的位置，而天使可以移動到范圍內(nèi)未被放置障礙物的任何一處。若在一輪中，天使無法移動，則惡魔獲勝。如果天使能無限地繼續(xù)游戲，則天使獲勝。

康威已經(jīng)證明（雖然他說是該書的共同作者伯利坎普展示給他的），只要棋盤大小大于32*33，k=1的情況下惡魔是必勝的。

為方便展示，這里將格點化為方格。如圖2所示是一個33*33的棋盤，天使起始位于紅色方格。無論天使開局怎么走，惡魔前8步只需將棋盤四周的8個黑格填上障礙物，這時天使必然位于中間的藍(lán)色區(qū)域內(nèi)，距離接觸包圍圈還有7步。

圖2 1階情形惡魔必勝|(zhì)圖源自制

而無論天使向哪個方向逃，惡魔都可以隔一格放一個障礙物這樣逐漸縮小缺口，保證在天使接觸棋盤邊緣之前將缺口堵上，因此惡魔是必勝的。

一階的天使問題告訴我們，只要棋盤足夠大，讓我們可以提前布置好包圍圈，就一定能圍住天使。而且天使問題中的棋盤是八連通的，即天使向橫豎斜八個方向都可以移動，所以布置一個包圍圈至少需要八步。而圍小貓中的棋盤是六連通的，因此包圍圈只需要6步。我們定義貓貓從空白棋盤中心逃脫的最少步數(shù)為棋盤的深度n，可以看到，圍小貓游戲的棋盤深度為5。

圖3 游戲棋盤的深度為5

豐富的游戲經(jīng)驗告訴我，n=5顯然是不夠的。如果要保證必勝，像天使問題里一樣布置一個包圍圈至少需要6個障礙物，也就是6步。因為貓n步就會逃出棋盤，而我們必須在貓?zhí)用撝盎ㄖ辽僖徊蕉伦√用摰姆较?，所以棋盤的深度n至少應(yīng)該為6+1+1=8。那么棋盤需要有多大才能保證必勝呢？答案就是n=8。圖中偶數(shù)號格點為我方放的障礙物，奇數(shù)號格點依次為貓貓的行動軌跡，可以看到這種情況下，我方是必定獲勝的。

圖4 n=8時的必勝策略|圖源知乎

所以，只要棋盤的深度不小于8，即使是一個空白的棋盤，我們也是必定可以圍住小貓的。相應(yīng)地，在沒有障礙物的情況下，棋盤深度小于8時我們是不可能圍住小貓的。

那 么，有 障 礙 物 呢？

終于回到了我們最初的問題：如何在一個n=5的棋盤上利用已有的障礙物圍住貓貓。其實這里的思路還是一樣的，那就是：先用若干步布置一個包圍圈，然后通過圍堵來完善包圍圈。唯一的不同是，由于棋盤不夠大，我們必須利用已有的障礙物來布置包圍圈。和棋盤的深度一樣，我們定義包圍圈的深度為貓貓?zhí)映霭鼑Φ淖钌俨綌?shù)。很顯然，包圍圈越深，留給我們布置防線的步數(shù)就越多。

先來研究一下包圍圈應(yīng)該是什么樣子的：包圍圈應(yīng)當(dāng)是六邊形，與棋盤形狀相同，且每條邊都經(jīng)過每個經(jīng)過格點的圓心，不允許斜著直接連。只有包圍圈的每個頂點（如下面圖6中的1-6號點）或者與該頂點相鄰且在包圍圈上的格點（如下圖6中的7-15號點）有障礙物，才能起到擋住貓貓的效果。如果上述位置沒有障礙物的話，就無法保證在貓貓被追趕到此處時閉合包圍圈。

圖5 紅色連線沒有經(jīng)過所有經(jīng)過格點的圓心，是錯誤的斜連。上面的深藍(lán)色折線是正確的連法

如果一個頂點或與其相鄰且在包圍圈上的格點上有障礙物，我們就稱這個頂點已完成，定義一個包圍圈的完成度為已完成的頂點數(shù)量。下面我們舉一個例子來說明。

圖6 一個包圍圈的例子

圖6是一個包圍圈的雛形，可以看到1，2，11，4，5號點都有障礙物，他們對應(yīng)的頂點都已完成。但它并不是一個完整的包圍圈，因為頂點6是未完成的。如果貓貓從右上往左上逃，我們堵住8號點后貓貓會逃至16號點，此時6，7兩點均空，貓貓?zhí)用?。頂點5雖然有障礙物，但它本身也是一個頂點，不能算作頂點6的相鄰點。所以這個包圍圈的完成度是5。

從棋盤深度為8的情形我們可以知道，在包圍圈完成，即完成度為6時，如果貓貓距離包圍圈至少有2格，我們根據(jù)貓貓的位置放障礙物來圍堵就可以必勝。也就是說，必勝條件是包圍圈深度+包圍圈完成度至少為8。所幸，上圖中的貓貓距離包圍圈有3格，也就是說包圍圈的深度是3，如下圖所示，我們只需補上包圍圈里缺失的點，就可以保證必勝。這就是看過本文的我們，第一步落在看似不需要優(yōu)先圍堵的6號點的原因。下面圖7展示了圖6例子中圍貓的必勝方法。

圖7 圖6的必勝方法

需要注意的是，畫包圍圈也是有技巧的。比如下面這個圖8就有AB兩種畫圈的方式，且包圍圈的完成度均為5。如果按照紅色的A方案規(guī)劃4，5號點之間的包圍圈，則包圍圈的深度為2，5+2<8，無法圍住貓貓。如果按照藍(lán)色的方案B，則包圍圈的深度為3，5+3=8，可以圍住貓貓。所以畫圈的方式也是很重要的哦！

圖8 兩種不同的包圍圈方式

然而，由于游戲條件的限制，初始只有6-8個障礙物，棋盤深度也只有5，所以大多數(shù)情況下都是無法必勝的，如果想圍住小貓，就多多地刷新吧！

不過，實際上游戲里的這只小貓并不太聰明，它的逃脫邏輯只是一個單層的貪心算法：只考慮當(dāng)前看來是最好的逃脫路線。所以我們可以利用這點設(shè)下陷阱，誘導(dǎo)貓貓走出多余的步數(shù)，從而贏下無法必勝的棋盤，有興趣的讀者朋友一定要去試一試哦。

圍 住 貓 貓 的 秘 訣！

最后，讓我們總結(jié)一下圍住貓貓的秘訣吧！只需要簡單的三步哦。

第一步：根據(jù)已有的初始障礙物劃定包圍圈，在保證有盡可能多頂點被完成的前提下，讓包圍圈的深度盡可能地大。

第二步：判斷包圍圈完成度+包圍圈的深度是否≥8？如果小于則無法保證圍住貓貓，直接重置。

第三步：先將包圍圈完成，然后對應(yīng)貓貓所在位置進(jìn)行圍堵即可獲勝。

寫 在 最 后

還記得開頭說的天使問題嗎？這個問題其實并沒有被完全解決。目前在天使的階數(shù)k比較小，比如k=2的時候，數(shù)學(xué)家已經(jīng)證明天使在無限大棋盤上是必勝的，但是對于任意有限階的天使，哪方能必勝這個問題尚無答案。也許，能夠解決這個問題的就是聰明的你。解決不了也沒關(guān)系，至少，你學(xué)會如何抓住貓貓了，對吧？

參考文獻(xiàn)：

[1]維基百科 天使問題

[2]John H. Conway, The angel problem, in: Richard Nowakowski (editor) Games of No Chance, volume 29 of MSRI Publications, pages 3–12, 1996.

[3]曾加的回答 - 知乎

封面來源搜狐網(wǎng)，表情包來源網(wǎng)絡(luò)

編輯：fiufa

---