時間過得真快，一轉眼已經是大年初六啦，大家是不是還在盡情享受假期呢？假期當然少不了遊戲，在這最後的慵懶假日，不如讓小編來帶你玩個小遊戲吧！在這個小遊戲中，輕輕點選就可以圍住可愛的貓貓，然後盡情…咳咳，享受冰冷的勝利吧！
回歸正題。今天要講的遊戲叫做圍小貓，2021年底在小編我的朋友圈裡着實是火了一把，如果你還沒有玩過，可以在搜尋引擎中搜尋“圍小貓”。記憶力好的讀者可能會記得，這款遊戲并不是第一次火了，沒錯，它就是2014年曾在朋友圈大火過的“圍住神經貓”的新皮膚！其原型可以追溯到更早。
上次小編我還未出山放過了你，這次既然被我逮到了，嘿嘿，今天我不把你圍住，我就不是中二所小編！
遊 戲 介 紹
首先介紹一下遊戲規則。起始小貓位于棋盤中心，6-8個障礙物會被預先随機放置在地圖上。我方每次點選小圓點就可以在該處放置一個障礙物，而小貓也會向地圖邊緣移動一格，這樣不斷重複下去，直到貓貓被障礙物圍住遊戲勝利，或者到達地圖邊緣溜走遊戲失敗。
初上手的時候你會發現，這個遊戲并不簡單，幾乎很難成功。因為棋盤其實并不大，貓隻需要5步就可以跑出棋盤邊界，很難将小貓堵住。
那麼一個自然而然的問題是：如果棋盤足夠大，可以保證将小貓堵住嗎？在回答這個問題之前，請讓我先介紹一下“天使問題”（angel problem）。
天 使 問 題
天使問題[1]首次見于1982年出版的《Winning Ways》一書，由書作者數學家約翰·H·康威（John H. Conway）提出。這是一個雙方玩家分别扮演天使和惡魔的博弈遊戲。遊戲在一個無限大方格棋盤上進行，起始棋盤是空的。定義正整數k為天使的階數，k階天使每步可以跳到k*k範圍内的任何一格，無論路上有沒有障礙物。
圖1 藍色虛線框内為3階天使的移動範圍|圖源維基百科[1]
每一輪中，惡魔可以在棋盤上放置一個障礙物，但不可放在目前天使所在的位置，而天使可以移動到範圍内未被放置障礙物的任何一處。若在一輪中，天使無法移動，則惡魔獲勝。如果天使能無限地繼續遊戲，則天使獲勝。
康威已經證明[2]（雖然他說是該書的共同作者伯利坎普展示給他的），隻要棋盤大小大于32*33，k=1的情況下惡魔是必勝的。
為友善展示，這裡将格點化為方格。如圖2所示是一個33*33的棋盤，天使起始位于紅色方格。無論天使開局怎麼走，惡魔前8步隻需将棋盤四周的8個黑格填上障礙物，這時天使必然位于中間的藍色區域内，距離接觸包圍圈還有7步。
圖2 1階情形惡魔必勝|圖源自制
而無論天使向哪個方向逃，惡魔都可以隔一格放一個障礙物這樣逐漸縮小缺口，保證在天使接觸棋盤邊緣之前将缺口堵上，是以惡魔是必勝的。
一階的天使問題告訴我們，隻要棋盤足夠大，讓我們可以提前布置好包圍圈，就一定能圍住天使。而且天使問題中的棋盤是八連通的，即天使向橫豎斜八個方向都可以移動，是以布置一個包圍圈至少需要八步。而圍小貓中的棋盤是六連通的，是以包圍圈隻需要6步。我們定義貓貓從空白棋盤中心逃脫的最少步數為棋盤的深度n，可以看到，圍小貓遊戲的棋盤深度為5。
圖3 遊戲棋盤的深度為5
豐富的遊戲經驗告訴我，n=5顯然是不夠的。如果要保證必勝，像天使問題裡一樣布置一個包圍圈至少需要6個障礙物，也就是6步。因為貓n步就會逃出棋盤，而我們必須在貓逃脫之前花至少一步堵住逃脫的方向，是以棋盤的深度n至少應該為6+1+1=8。那麼棋盤需要有多大才能保證必勝呢？答案就是n=8[3]。圖中偶數号格點為我方放的障礙物，奇數号格點依次為貓貓的行動軌迹，可以看到這種情況下，我方是必定獲勝的。
圖4 n=8時的必勝政策|圖源知乎[3]
是以，隻要棋盤的深度不小于8，即使是一個空白的棋盤，我們也是必定可以圍住小貓的。相應地，在沒有障礙物的情況下，棋盤深度小于8時我們是不可能圍住小貓的。
那 麼，有 障 礙 物 呢？
終于回到了我們最初的問題：如何在一個n=5的棋盤上利用已有的障礙物圍住貓貓。其實這裡的思路還是一樣的，那就是：先用若幹步布置一個包圍圈，然後通過圍堵來完善包圍圈。唯一的不同是，由于棋盤不夠大，我們必須利用已有的障礙物來布置包圍圈。和棋盤的深度一樣，我們定義包圍圈的深度為貓貓逃出包圍圈的最少步數。很顯然，包圍圈越深，留給我們布置防線的步數就越多。
先來研究一下包圍圈應該是什麼樣子的：包圍圈應當是六邊形，與棋盤形狀相同，且每條邊都經過每個經過格點的圓心，不允許斜着直接連。隻有包圍圈的每個頂點（如下面圖6中的1-6号點）或者與該頂點相鄰且在包圍圈上的格點（如下圖6中的7-15号點）有障礙物，才能起到擋住貓貓的效果。如果上述位置沒有障礙物的話，就無法保證在貓貓被追趕到此處時閉合包圍圈。
圖5 紅色連線沒有經過所有經過格點的圓心，是錯誤的斜連。上面的深藍色折線是正确的連法
如果一個頂點或與其相鄰且在包圍圈上的格點上有障礙物，我們就稱這個頂點已完成，定義一個包圍圈的完成度為已完成的頂點數量。下面我們舉一個例子來說明。
圖6 一個包圍圈的例子
圖6是一個包圍圈的雛形，可以看到1，2，11，4，5号點都有障礙物，他們對應的頂點都已完成。但它并不是一個完整的包圍圈，因為頂點6是未完成的。如果貓貓從右上往左上逃，我們堵住8号點後貓貓會逃至16号點，此時6，7兩點均空，貓貓逃脫。頂點5雖然有障礙物，但它本身也是一個頂點，不能算作頂點6的相鄰點。是以這個包圍圈的完成度是5。
從棋盤深度為8的情形我們可以知道，在包圍圈完成，即完成度為6時，如果貓貓距離包圍圈至少有2格，我們根據貓貓的位置放障礙物來圍堵就可以必勝。也就是說，必勝條件是包圍圈深度+包圍圈完成度至少為8。所幸，上圖中的貓貓距離包圍圈有3格，也就是說包圍圈的深度是3，如下圖所示，我們隻需補上包圍圈裡缺失的點，就可以保證必勝。這就是看過本文的我們，第一步落在看似不需要優先圍堵的6号點的原因。下面圖7展示了圖6例子中圍貓的必勝方法。
圖7 圖6的必勝方法
需要注意的是，畫包圍圈也是有技巧的。比如下面這個圖8就有AB兩種畫圈的方式，且包圍圈的完成度均為5。如果按照紅色的A方案規劃4，5号點之間的包圍圈，則包圍圈的深度為2，5+2包圍圈的深度為3，5+3=8，可以圍住貓貓。是以畫圈的方式也是很重要的哦！
圖8 兩種不同的包圍圈方式
然而，由于遊戲條件的限制，初始隻有6-8個障礙物，棋盤深度也隻有5，是以大多數情況下都是無法必勝的，如果想圍住小貓，就多多地重新整理吧！
不過，實際上遊戲裡的這隻小貓并不太聰明，它的逃脫邏輯隻是一個單層的貪心算法：隻考慮目前看來是最好的逃脫路線。是以我們可以利用這點設下陷阱，誘導貓貓走出多餘的步數，進而赢下無法必勝的棋盤，有興趣的讀者朋友一定要去試一試哦。
圍 住 貓 貓 的 秘 訣！
最後，讓我們總結一下圍住貓貓的秘訣吧！隻需要簡單的三步哦。
第一步：根據已有的初始障礙物劃定包圍圈，在保證有盡可能多頂點被完成的前提下，讓包圍圈的深度盡可能地大。
第二步：判斷包圍圈完成度+包圍圈的深度是否≥8？如果小于則無法保證圍住貓貓，直接重置。
第三步：先将包圍圈完成，然後對應貓貓所在位置進行圍堵即可獲勝。
寫 在 最 後
還記得開頭說的天使問題嗎？這個問題其實并沒有被完全解決。目前在天使的階數k比較小，比如k=2的時候，數學家已經證明天使在無限大棋盤上是必勝的，但是對于任意有限階的天使，哪方能必勝這個問題尚無答案。也許，能夠解決這個問題的就是聰明的你。解決不了也沒關系，至少，你學會如何抓住貓貓了，對吧？
參考文獻：
[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]曾加的回答 - 知乎
封面來源搜狐網，表情包來源網絡
編輯：fiufa
轉載内容僅代表作者觀點
不代表中科院高能所立場
編輯：lili
精彩視訊 不要錯過