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

「超級瑪麗」（Super Mario Bros.）應(yīng)該算是紅白機(jī)上最著名的游戲了，大部分 80 后、 90 后應(yīng)該都玩過吧。對于這樣經(jīng)典的游戲，「無聊」的游戲計(jì)算復(fù)雜性研究人員當(dāng)然不會放過啦。2015 年，Aloupis, Demaine, Guo 和 Viglietta [1] 證明了「超級瑪麗」屬于 NP-hard。2016 年，Demaine , Viglietta 和 Williams [2] 證明了「超級瑪麗」屬于 PSPACE-complete。 今天我們就來詳細(xì)介紹一下關(guān)于這個游戲的計(jì)算復(fù)雜性的研究。在文中我們將看到如何設(shè)置地圖使得超級瑪麗能夠模擬一些計(jì)算困難的問題，從而說明該游戲在計(jì)算理論的角度下是難解的。 本篇的第 1 節(jié)介紹一個 NP-hard 框架；第 2 節(jié)介紹應(yīng)用框架證明「超級瑪麗」屬于 NP-hard；第 3 節(jié)介紹一個 PSPACE-hard 框架；第 4 節(jié)介紹「超級瑪麗」屬于 PSPACE-hard 的歸約；第 5 節(jié)說明如何使歸約更完善；第 6 節(jié)進(jìn)行總結(jié)。 1、NP-hard 框架 我們先來介紹一個用于證明一類 2D 游戲困難性的框架，這個框架來自文獻(xiàn) [1] 。我們假設(shè)在這類 2D 游戲中，玩家操控一個角色在地圖上移動，玩家的目的是使該角色到達(dá)地圖上的某個位置。比如 SMB 的目標(biāo)就是讓瑪麗從出生點(diǎn)到達(dá)旗桿，再比如之前介紹過的華容道玩具的目標(biāo)就是讓特定的滑塊移動到出口，再再比如 STG 游戲就是操縱可以發(fā)射子彈的角色避開敵方彈幕和地形到達(dá)關(guān)底。 框架使用的歸約問題是經(jīng)典的 3-SAT 問題（3-conjunctive normal form satisfiability，3 - 合取范式可滿足問題）。該問題指的是給定一個由若干子句的合取構(gòu)成的公式，其中每個子句包含 3 個項(xiàng)，判斷是否存在對變量的賦值使得該公式可滿足。我們希望通過使用 2D 游戲模擬 3-SAT 問題，從而將 3-SAT 歸約到 2D 游戲。 我們用一個例子來說明如何進(jìn)行這樣的模擬。對于公式

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

玩家操控角色從 start 部件出發(fā)，然后進(jìn)入一個對應(yīng)變量 x 的 variable 部件，玩家需要在兩個出口之間選擇一個，這模擬了對變量 x 的取值。假設(shè)選擇對 x 賦值為 T，那么玩家操控的角色就從 variable 部件的左側(cè)出口離開，接下來角色可以到達(dá)兩個 clause 部件并打開這兩個部件，這模擬了?和這兩個子句中的 x 為 T 后整個子句就為 T。接下來無論選擇的是從 variable 部件的左側(cè)出口還是右側(cè)出口離開，角色都將進(jìn)入到第二個 variable 部件，繼續(xù)對變量 y 的賦值進(jìn)行模擬。當(dāng)所有變量的賦值都確定后，角色進(jìn)入到驗(yàn)證過程（check in 路徑），角色需要從右側(cè)依次通過所有的 clause 部件才能最終達(dá)到最左側(cè)的 finish 部件。而每個 clause 部件只有當(dāng)之前角色從上方進(jìn)入并打開至少一次后，才允許角色從右側(cè)進(jìn)入并通過。 ? 為了實(shí)現(xiàn)這個 NP-hard 框架，我們需要在 2D 游戲中實(shí)現(xiàn) 5 個部件，分別是?start、finish、variable、crossover、clause，其中 crossover 部件用于處理框架中路徑的交叉。容易驗(yàn)證，如果某個 2D 游戲能夠?qū)崿F(xiàn)這些部件，那么就能用這個游戲模擬 3-SAT 的任意實(shí)例，也就是說 3-SAT 可以歸約到這個 2D 游戲，從而就說明這個游戲就屬于 NP-hard 了。 ? 不過，有時(shí)候在游戲中直接構(gòu)造 variable 和 clause 部件可能會比較復(fù)雜，所以我們可以對這個框架進(jìn)行一些修改，使得部件更加原子化一點(diǎn)。修改之后的框架含有?start、finish、turn、switch、merge、one-way、crossover、door?這些部件。start 和 finish 部件的含義與修改之前是一樣的；turn 部件用于路徑的轉(zhuǎn)向；switch 和 merge 部件其實(shí)是同樣的，通常是一個三叉路口；one-way 部件保證游戲角色只能向一個方向移動，功能類似單行道；door 部件包含兩條互不連通的路徑，當(dāng)一條路徑被角色通過后（開門），角色才能通過另一條路徑。 ? 對于公式

，對應(yīng)的修改后的框架如下。

游戲角色還是從 start 部件出發(fā)，接著進(jìn)入 switch 部件選擇變量的賦值，賦值后可以打開對應(yīng)的 door 部件，然后回到 merge 部件，接著選擇下一個變量的賦值。直到所有變量的賦值被確定進(jìn)入子句驗(yàn)證過程，角色進(jìn)入右下方的 switch 部件，然后它需要在三個出口中選擇一個已經(jīng)被打開的 door 部件通過。當(dāng)所有子句都驗(yàn)證完成后，角色最終進(jìn)入 finish 部件。 2、超級瑪麗屬于 NP-hard 我們使用上一節(jié)的框架來說明「超級瑪麗」屬于 NP-hard，為此我們需要在游戲中實(shí)現(xiàn) start、finish、variable、crossover、clause 這些部件，我們逐一進(jìn)行說明。

start 部件：瑪麗的出生點(diǎn)有一個蘑菇，吃了之后可以變成大瑪麗。 finish 部件：需要以大瑪麗的狀態(tài)從左下方進(jìn)入部件，撞掉一個磚塊后才能到達(dá)旗桿；如果以小瑪麗的狀態(tài)進(jìn)入則不能通關(guān)。

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

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

clause 部件：該部件中瑪麗需要從最左側(cè)到達(dá)最右側(cè)才算是驗(yàn)證成功，但是注意到右側(cè)有足夠多的火墻，這使得瑪麗即使以最快的速度移動也無法避開。因而我們需要使用游戲中另的一個元素——無敵星星，部件中的三個問號方塊都有無敵星星，如果瑪麗吃到星星就可以穿過火墻。因此，只有當(dāng)這三個問號方塊中至少有一個方塊被撞開過，瑪麗才能在驗(yàn)證時(shí)中通過 clause 部件。 現(xiàn)在所有的部件都實(shí)現(xiàn)了，而且歸約顯然可以在多項(xiàng)式時(shí)間內(nèi)完成，所以我們就有以下定理 定理 1：「超級瑪麗」屬于 NP-hard。 3、PSPACE-hard 框架 接著，我們介紹一個用于證明 2D 游戲?qū)儆?PSPACE-hard 的框架，這個框架來自文獻(xiàn) [1] 和 [3]。它使用的歸約問題是 TQBF 問題（True Quantifified Boolean Formula），指的是問某個含有「存在」和「任意」符號的邏輯公式是否可滿足，比如問公式的真值是否是 T。

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

上圖是一個 open-close door 部件，它包含三條平行的、不連通的路徑，從上到下依次為 open 路徑、traverse 路徑和 close 路徑。traverse 路徑上有一扇門，只有當(dāng)門在打開的狀態(tài)下，角色才能穿過 traverse 路徑；當(dāng)角色通過 open 路徑時(shí)，它可以打開這扇門；而當(dāng)角色通過 close 路徑時(shí)，它必須關(guān)上這扇門。 這個 open-close door 相當(dāng)于是一個狀態(tài)存儲器，門的開閉相當(dāng)于 0 和 1，每一個 open-close door 部件保存了 1bit 的信息。這也是為什么加上這個部件后，框架的復(fù)雜性可以到達(dá) PSPACE-hard。 接著我們介紹 alternation 部件，它其實(shí)是一個輔助部件，用于簡化框架的描述。我們可以用其他部件的組合來實(shí)現(xiàn) alternation 部件，不必真的在 2D 游戲中實(shí)現(xiàn)它。

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

2D 游戲的框架如下圖

角色從 start 部件出發(fā)，進(jìn)入對應(yīng)變量 x1 的部件，由于限制 x1 的量詞是「任意」所以這里是 alternation 部件，因?yàn)槭堑谝淮芜M(jìn)入，角色只能選擇從對應(yīng) x1 的出口離開，接著角色打開所有對應(yīng)于 x1 的 open-close door，并關(guān)閉所有對應(yīng)于 非 x1 的 open-close door。完成這些后角色來到 merge 部件，之后進(jìn)入對應(yīng)變量 x2 的部件，由于限制 x2 的量詞是「存在」所以這里是 switch 部件。就這樣，角色完成所有變量的一次賦值后進(jìn)入驗(yàn)證過程，這個驗(yàn)證過程與修改后的 NP-hard 框架是類似的。完成一次驗(yàn)證后，角色進(jìn)入中間上方的 alternation 部件，注意這時(shí)角色是第一次進(jìn)入該 alternation，所以角色只能從左側(cè)出口離開，接下來角色將再次進(jìn)入對應(yīng)于 x3 的 alternation 部件，這時(shí)角色只能選擇對應(yīng)于 非 x3 的出口，在操作完對應(yīng)的 open-close door 后又一次進(jìn)入驗(yàn)證過程，這其實(shí)就模擬了「...... 對任意 x3 的賦值公式的值為 T」。所以，當(dāng)公式中有 n 個「任意」量詞時(shí)，框架中的驗(yàn)證過程可能會被通過 2^n 次，只有當(dāng)角色完成了所有的驗(yàn)證過程后，才能最終到達(dá) finish 部件。 容易驗(yàn)證，這個框架模擬了 TQBF 問題。因此，如果 2D 游戲中能實(shí)現(xiàn) start、finish、turn、switch、merge、one-way、crossover、open-close door 這些部件，那么這個 2D 游戲就屬于 PSPACE-hard。 另外有一點(diǎn)需要提一下，NP-hard 框架中的部件的每條路徑只會被角色通過一次，而 PSPACE-hard 框架中的路徑就可能會被通過很多次了，這在構(gòu)造部件時(shí)是需要注意的。 4、超級瑪麗屬于 PSPACE-complete 為了證明「超級瑪麗」屬于 PSPACE-hard，我們需要在游戲中實(shí)現(xiàn) start、finish、turn、switch、merge、one-way、crossover、open-close door 部件，其中很多部件是非常簡單的，就不提了，這里就介紹一下 crossover 和 open-close door。 注意，這里與 NP-hard 證明中不同的是，瑪麗總是處于小瑪麗狀態(tài)的。

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

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

現(xiàn)在，我們已經(jīng)基本證明了超級瑪麗屬于 PSPACE-hard。而又因?yàn)椤赋壃旣悺褂螒虻乃袪顟B(tài)都能夠存儲在多項(xiàng)式空間內(nèi)，所以「超級瑪麗」屬于 NPSPACE。再根據(jù) Savitch's Theorem，NPSPACE=PSPACE，「超級瑪麗」就屬于 PSPACE-complete 了。 5、完善歸約 在給出最后的定理前，歸約中的兩個小 bug 可能需要再討論一下。 一個 bug 是 open-close door 部件中央的火球。在「超級瑪麗」原始游戲中，似乎沒有像這樣將火墻（球）放置在空格中的例子。不過這個問題比較好解決，只要把中央的火球替換成下面這樣的一大排火墻就行了。這樣一來，刺猬的移動不受影響，但是瑪麗無法通過這些火墻。

另一個 bug 是關(guān)于刺猬怪物的生成。在歸約中我們需要將刺猬放置在指定的位置，但在「超級瑪麗」原始游戲中，一個在天空中移動的怪物會有規(guī)律地拋出怪物蛋，當(dāng)?shù)奥涞睾蟛判纬纱题．?dāng)然，這個問題的解決方法也已經(jīng)在論文中給出了。我們可以將所有 open-close door 放到整個地圖的上部排成一行，當(dāng)游戲開始時(shí)瑪麗在這些 door 的上方移動，空中的怪物有規(guī)律地拋出刺猬，這些刺猬將通過一些漏斗進(jìn)入各個 door 部件。我們可以設(shè)置合適的距離，使得即使瑪麗以最快的速度移動，每個 door 都會有一個刺猬進(jìn)入。完成這些之后，瑪麗可以踩死空中的怪物，然后就進(jìn)入上面框架中提到的 start 部件。 處理掉這兩個小 bug 后，我們終于能放心地得到下面的定理了 定理 2：「超級瑪麗」屬于 PSPACE-complete。 6、總結(jié) 我們介紹了兩個用于證明 2D 游戲計(jì)算復(fù)雜性的框架，并詳細(xì)解釋了如何用這兩個框架討論「超級瑪麗」的計(jì)算復(fù)雜性。「超級瑪麗」最終被證明是屬于 PSPACE-complete。事實(shí)上，文獻(xiàn) [2] 還討論了一些含有其他元素（比如使用管道移動、獲得金幣獎勵生命）的「超級瑪麗」游戲的復(fù)雜性。 如果要評選最有趣的關(guān)于電子游戲計(jì)算復(fù)雜性的論文，我相信「超級瑪麗」這個肯定能上榜。最后附一下論文的截圖