下載客戶端

登錄

從小玩到大的超級瑪麗，計算復雜性是怎樣的？

2020-08-13 14:34

來源：澎湃新聞·澎湃號·湃客

機器之心轉(zhuǎn)載

作者：張諸俊

吃蘑菇長大的「超級瑪麗」比你想象的更復雜。

「超級瑪麗」（Super Mario Bros.）應該算是紅白機上最著名的游戲了，大部分 80 后、 90 后應該都玩過吧。對于這樣經(jīng)典的游戲，「無聊」的游戲計算復雜性研究人員當然不會放過啦。2015 年，Aloupis, Demaine, Guo 和 Viglietta [1] 證明了「超級瑪麗」屬于 NP-hard。2016 年，Demaine , Viglietta 和 Williams [2] 證明了「超級瑪麗」屬于 PSPACE-complete。

今天我們就來詳細介紹一下關(guān)于這個游戲的計算復雜性的研究。在文中我們將看到如何設置地圖使得超級瑪麗能夠模擬一些計算困難的問題，從而說明該游戲在計算理論的角度下是難解的。

本篇的第 1 節(jié)介紹一個 NP-hard 框架；第 2 節(jié)介紹應用框架證明「超級瑪麗」屬于 NP-hard；第 3 節(jié)介紹一個 PSPACE-hard 框架；第 4 節(jié)介紹「超級瑪麗」屬于 PSPACE-hard 的歸約；第 5 節(jié)說明如何使歸約更完善；第 6 節(jié)進行總結(jié)。

1. NP-hard 框架

我們先來介紹一個用于證明一類 2D 游戲困難性的框架，這個框架來自文獻 [1] 。我們假設在這類 2D 游戲中，玩家操控一個角色在地圖上移動，玩家的目的是使該角色到達地圖上的某個位置。比如 SMB 的目標就是讓瑪麗從出生點到達旗桿，再比如之前介紹過的華容道玩具的目標就是讓特定的滑塊移動到出口，再再比如 STG 游戲就是操縱可以發(fā)射子彈的角色避開敵方彈幕和地形到達關(guān)底。

框架使用的歸約問題是經(jīng)典的 3-SAT 問題（3-conjunctive normal form satisfiability，3 - 合取范式可滿足問題）。該問題指的是給定一個由若干子句的合取構(gòu)成的公式，其中每個子句包含 3 個項，判斷是否存在對變量的賦值使得該公式可滿足。我們希望通過使用 2D 游戲模擬 3-SAT 問題，從而將 3-SAT 歸約到 2D 游戲。

我們用一個例子來說明如何進行這樣的模擬。對于公式

我們可以構(gòu)造如下圖的 2D 游戲框架

玩家操控角色從 start 部件出發(fā)，然后進入一個對應變量 x 的 variable 部件，玩家需要在兩個出口之間選擇一個，這模擬了對變量 x 的取值。假設選擇對 x 賦值為 T，那么玩家操控的角色就從 variable 部件的左側(cè)出口離開，接下來角色可以到達兩個 clause 部件并打開這兩個部件，這模擬了

和

這兩個子句中的 x 為 T 后整個子句就為 T。接下來無論選擇的是從 variable 部件的左側(cè)出口還是右側(cè)出口離開，角色都將進入到第二個 variable 部件，繼續(xù)對變量 y 的賦值進行模擬。當所有變量的賦值都確定后，角色進入到驗證過程（check in 路徑），角色需要從右側(cè)依次通過所有的 clause 部件才能最終達到最左側(cè)的 finish 部件。而每個 clause 部件只有當之前角色從上方進入并打開至少一次后，才允許角色從右側(cè)進入并通過。

為了實現(xiàn)這個 NP-hard 框架，我們需要在 2D 游戲中實現(xiàn) 5 個部件，分別是 start、finish、variable、crossover、clause，其中 crossover 部件用于處理框架中路徑的交叉。容易驗證，如果某個 2D 游戲能夠?qū)崿F(xiàn)這些部件，那么就能用這個游戲模擬 3-SAT 的任意實例，也就是說 3-SAT 可以歸約到這個 2D 游戲，從而就說明這個游戲就屬于 NP-hard 了。

不過，有時候在游戲中直接構(gòu)造 variable 和 clause 部件可能會比較復雜，所以我們可以對這個框架進行一些修改，使得部件更加原子化一點。修改之后的框架含有 start、finish、turn、switch、merge、one-way、crossover、door 這些部件。start 和 finish 部件的含義與修改之前是一樣的；turn 部件用于路徑的轉(zhuǎn)向；switch 和 merge 部件其實是同樣的，通常是一個三叉路口；one-way 部件保證游戲角色只能向一個方向移動，功能類似單行道；door 部件包含兩條互不連通的路徑，當一條路徑被角色通過后（開門），角色才能通過另一條路徑。

對于公式

，對應的修改后的框架如下。

游戲角色還是從 start 部件出發(fā)，接著進入 switch 部件選擇變量的賦值，賦值后可以打開對應的 door 部件，然后回到 merge 部件，接著選擇下一個變量的賦值。直到所有變量的賦值被確定進入子句驗證過程，角色進入右下方的 switch 部件，然后它需要在三個出口中選擇一個已經(jīng)被打開的 door 部件通過。當所有子句都驗證完成后，角色最終進入 finish 部件。

2. 超級瑪麗屬于 NP-hard

我們使用上一節(jié)的框架來說明「超級瑪麗」屬于 NP-hard，為此我們需要在游戲中實現(xiàn) start、finish、variable、crossover、clause 這些部件，我們逐一進行說明。

start 部件：瑪麗的出生點有一個蘑菇，吃了之后可以變成大瑪麗。

finish 部件：需要以大瑪麗的狀態(tài)從左下方進入部件，撞掉一個磚塊后才能到達旗桿；如果以小瑪麗的狀態(tài)進入則不能通關(guān)。

variable 部件：瑪麗從上方進入部件后，可以在左下和右下兩個出口中選擇，一旦決定后就不能再返回了。

crossover 部件：該部件中有兩條交叉的路徑，第一條由左上至右上，第二條由左下至中間上方。在第一條路徑中，大瑪麗進入后需要碰一下怪物變成小瑪麗后才能通過狹小的通道，注意右上方的問號方塊中有一個蘑菇，瑪麗吃了后可以變回大瑪麗狀態(tài)。在第二條路徑中，瑪麗達到底部后一路向上，注意由于處于大瑪麗狀態(tài)，他可以撞開磚塊后繼續(xù)向上移動，但卻不能進入第一條路徑。

clause 部件：該部件中瑪麗需要從最左側(cè)到達最右側(cè)才算是驗證成功，但是注意到右側(cè)有足夠多的火墻，這使得瑪麗即使以最快的速度移動也無法避開。因而我們需要使用游戲中另的一個元素——無敵星星，部件中的三個問號方塊都有無敵星星，如果瑪麗吃到星星就可以穿過火墻。因此，只有當這三個問號方塊中至少有一個方塊被撞開過，瑪麗才能在驗證時中通過 clause 部件。

現(xiàn)在所有的部件都實現(xiàn)了，而且歸約顯然可以在多項式時間內(nèi)完成，所以我們就有以下定理

定理 1：「超級瑪麗」屬于 NP-hard。

3. PSPACE-hard 框架

接著，我們介紹一個用于證明 2D 游戲?qū)儆?PSPACE-hard 的框架，這個框架來自文獻 [1] 和 [3]。它使用的歸約問題是 TQBF 問題（True Quantifified Boolean Formula），指的是問某個含有「存在」和「任意」符號的邏輯公式是否可滿足，比如問公式

的真值是否是 T。

這里我們對原始論文中的框架作了一些修改，希望能夠幫助理解。和之前 NP-hard 框架一樣，我們需要定義一些部件。NP-hard 框架中討論的部件我們就不再重復定義了，這里我們主要定義兩個部件，open-close door 和 alternation 部件。

上圖是一個 open-close door 部件，它包含三條平行的、不連通的路徑，從上到下依次為 open 路徑、traverse 路徑和 close 路徑。traverse 路徑上有一扇門，只有當門在打開的狀態(tài)下，角色才能穿過 traverse 路徑；當角色通過 open 路徑時，它可以打開這扇門；而當角色通過 close 路徑時，它必須關(guān)上這扇門。

這個 open-close door 相當于是一個狀態(tài)存儲器，門的開閉相當于 0 和 1，每一個 open-close door 部件保存了 1bit 的信息。這也是為什么加上這個部件后，框架的復雜性可以到達 PSPACE-hard。

接著我們介紹 alternation 部件，它其實是一個輔助部件，用于簡化框架的描述。我們可以用其他部件的組合來實現(xiàn) alternation 部件，不必真的在 2D 游戲中實現(xiàn)它。

上圖是 alternation 部件的結(jié)構(gòu)。該部件中包含兩個 open-close door 部件，其中一個 door 處于打開狀態(tài)，另一個處于關(guān)閉狀態(tài)。不妨假設現(xiàn)在上方的 door 是打開的，下方的 door 是關(guān)閉的。角色從左上進入 switch 部件，它只能通過上方的 open-close door 的 traverse 路徑，然后再通過 close 路徑，這樣上方的 door 就被關(guān)閉，接著角色通過下方 open-close door 的 open 路徑，這樣下方的 door 就被打開。可以看到，每次角色通過 alternation 部件后，兩個 open-close door 部件的狀態(tài)就會翻轉(zhuǎn)，這樣一來，角色就會從兩個出口交替離開。也就是說，當角色第一次進入 alternation 部件時，它會從下方的出口離開，當角色第二次進入時，它會從上方出口離開，以此類推。

現(xiàn)在我們就可以用例子來說明如何構(gòu)造 PSPACE-hard 框架，對于公式

2D 游戲的框架如下圖

角色從 start 部件出發(fā)，進入對應變量 x1 的部件，由于限制 x1 的量詞是「任意」所以這里是 alternation 部件，因為是第一次進入，角色只能選擇從對應 x1 的出口離開，接著角色打開所有對應于 x1 的 open-close door，并關(guān)閉所有對應于非 x1 的 open-close door。完成這些后角色來到 merge 部件，之后進入對應變量 x2 的部件，由于限制 x2 的量詞是「存在」所以這里是 switch 部件。就這樣，角色完成所有變量的一次賦值后進入驗證過程，這個驗證過程與修改后的 NP-hard 框架是類似的。完成一次驗證后，角色進入中間上方的 alternation 部件，注意這時角色是第一次進入該 alternation，所以角色只能從左側(cè)出口離開，接下來角色將再次進入對應于 x3 的 alternation 部件，這時角色只能選擇對應于非 x3 的出口，在操作完對應的 open-close door 后又一次進入驗證過程，這其實就模擬了「...... 對任意 x3 的賦值公式的值為 T」。所以，當公式中有 n 個「任意」量詞時，框架中的驗證過程可能會被通過 2^n 次，只有當角色完成了所有的驗證過程后，才能最終到達 finish 部件。

容易驗證，這個框架模擬了 TQBF 問題。因此，如果 2D 游戲中能實現(xiàn) start、finish、turn、switch、merge、one-way、crossover、open-close door 這些部件，那么這個 2D 游戲就屬于 PSPACE-hard。

另外有一點需要提一下，NP-hard 框架中的部件的每條路徑只會被角色通過一次，而 PSPACE-hard 框架中的路徑就可能會被通過很多次了，這在構(gòu)造部件時是需要注意的。

4. 超級瑪麗屬于 PSPACE-complete

為了證明「超級瑪麗」屬于 PSPACE-hard，我們需要在游戲中實現(xiàn) start、finish、turn、switch、merge、one-way、crossover、open-close door 部件，其中很多部件是非常簡單的，就不提了，這里就介紹一下 crossover 和 open-close door。

注意，這里與 NP-hard 證明中不同的是，瑪麗總是處于小瑪麗狀態(tài)的。

上圖就是 crossover 部件，瑪麗需要以最快的速度移動才能從左上到達右下（或從右上到達左下）。容易發(fā)現(xiàn)，這兩條路徑不會互相干擾，而且瑪麗可以無限次地通過這個部件。

上圖是一個 open-close door 部件。open、traverse 和 close 三條路徑在圖上已經(jīng)標出來了。該部件中刺猬怪物的所在位置表示門的開閉，上圖中門處于打開狀態(tài)。當瑪麗從 close 路徑進入時，由于刺猬的存在瑪麗無法通過，所以它必須到達磚塊下方，等刺猬移動到磚塊上方時，在合適的時機撞擊磚塊，使得刺猬跳過一個方塊到達左側(cè)，而后才能通過 close 狀態(tài)。注意這時門就處于關(guān)閉狀態(tài)了，因為瑪麗無法通過 traverse 路徑。下面的圖展示了具體的過程

現(xiàn)在，我們已經(jīng)基本證明了超級瑪麗屬于 PSPACE-hard。而又因為「超級瑪麗」游戲的所有狀態(tài)都能夠存儲在多項式空間內(nèi)，所以「超級瑪麗」屬于 NPSPACE。再根據(jù) Savitch's Theorem，NPSPACE=PSPACE，「超級瑪麗」就屬于 PSPACE-complete 了。

5. 完善歸約

在給出最后的定理前，歸約中的兩個小 bug 可能需要再討論一下。

一個 bug 是 open-close door 部件中央的火球。在「超級瑪麗」原始游戲中，似乎沒有像這樣將火墻（球）放置在空格中的例子。不過這個問題比較好解決，只要把中央的火球替換成下面這樣的一大排火墻就行了。這樣一來，刺猬的移動不受影響，但是瑪麗無法通過這些火墻。

另一個 bug 是關(guān)于刺猬怪物的生成。在歸約中我們需要將刺猬放置在指定的位置，但在「超級瑪麗」原始游戲中，一個在天空中移動的怪物會有規(guī)律地拋出怪物蛋，當?shù)奥涞睾蟛判纬纱题．斎唬@個問題的解決方法也已經(jīng)在論文中給出了。我們可以將所有 open-close door 放到整個地圖的上部排成一行，當游戲開始時瑪麗在這些 door 的上方移動，空中的怪物有規(guī)律地拋出刺猬，這些刺猬將通過一些漏斗進入各個 door 部件。我們可以設置合適的距離，使得即使瑪麗以最快的速度移動，每個 door 都會有一個刺猬進入。完成這些之后，瑪麗可以踩死空中的怪物，然后就進入上面框架中提到的 start 部件。

處理掉這兩個小 bug 后，我們終于能放心地得到下面的定理了

定理 2：「超級瑪麗」屬于 PSPACE-complete。

6. 總結(jié)

我們介紹了兩個用于證明 2D 游戲計算復雜性的框架，并詳細解釋了如何用這兩個框架討論「超級瑪麗」的計算復雜性。「超級瑪麗」最終被證明是屬于 PSPACE-complete。事實上，文獻 [2] 還討論了一些含有其他元素（比如使用管道移動、獲得金幣獎勵生命）的「超級瑪麗」游戲的復雜性。

如果要評選最有趣的關(guān)于電子游戲計算復雜性的論文，我相信「超級瑪麗」這個肯定能上榜。最后附一下論文的截圖

參考資料：

[1] Greg Aloupis, Erik D Demaine, Alan Guo, and Giovanni Viglietta. Classic Nintendo games are (computationally) hard. Theoretical Computer Science, 586:135–160, 2015. arXiv 鏈接

[2] Erik D. Demaine , Giovanni Viglietta, and Aaron Williams. Super Mario Bros. Is Harder/Easier than We Thought. 8th International Conference on Fun with Algorithms (FUN 2016).

[3] Giovanni Viglietta. Gaming is a hard job, but someone has to do it! Theory of Computing Systems, 54(4):595–621, 2014. arXiv 鏈接