機(jī)器之心轉(zhuǎn)載

作者：張諸俊

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

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

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

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

1. NP-hard 框架

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

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

我們用一個(gè)例子來說明如何進(jìn)行這樣的模擬。對(duì)于公式

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

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

和

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

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

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

對(duì)于公式

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

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

2. 超級(jí)瑪麗屬于 NP-hard

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

start 部件：瑪麗的出生點(diǎn)有一個(gè)蘑菇，吃了之后可以變成大瑪麗。

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

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

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

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

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

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

3. PSPACE-hard 框架

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

的真值是否是 T。

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

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

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

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

上圖是 alternation 部件的結(jié)構(gòu)。該部件中包含兩個(gè) open-close door 部件，其中一個(gè) door 處于打開狀態(tài)，另一個(gè)處于關(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 部件后，兩個(gè) open-close door 部件的狀態(tài)就會(huì)翻轉(zhuǎn)，這樣一來，角色就會(huì)從兩個(gè)出口交替離開。也就是說，當(dāng)角色第一次進(jìn)入 alternation 部件時(shí)，它會(huì)從下方的出口離開，當(dāng)角色第二次進(jìn)入時(shí)，它會(huì)從上方出口離開，以此類推。

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

2D 游戲的框架如下圖

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

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

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

4. 超級(jí)瑪麗屬于 PSPACE-complete

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

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

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

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

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

5. 完善歸約

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

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

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

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

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

6. 總結(jié)

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

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

參考資料：

[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 鏈接

數(shù)據(jù)工程師專屬福利！1000元服務(wù)抵扣券免費(fèi)領(lǐng)取，直充到 AWS 賬戶用以抵扣服務(wù)消費(fèi)，輕松體驗(yàn)6大應(yīng)用場(chǎng)景。

? THE END

轉(zhuǎn)載請(qǐng)聯(lián)系本公眾號(hào)獲得授權(quán)

投稿或?qū)で髨?bào)道：content@jiqizhixin.com

原標(biāo)題：《從小玩到大的超級(jí)瑪麗，計(jì)算復(fù)雜性是怎樣的？》

閱讀原文