導語
近年來，很多AI技術的突破都離不開游戲的影響，不論是古老的圍棋還是即時戰略類的星際爭霸都體現著這樣的交融。同時，游戲和AI的跨界合作，還在通過算法，生成新的游戲規則上有所展現，從而讓機器學習的算法，具有更強的泛化能力。8月3日的 Nature Machine Intelligence 推出的綜述論文，先介紹了游戲行業中的“過程生成”（Procedural content generation）這一概念，從現有應用，和機器學習的關系，以及面臨的問題，全面闡述了這一新的跨學科研究方向。
完整論文資料清單和更多相關論文，請掃碼獲取：
通過算法，產生游戲中的背景信息，例如游戲中的關卡，任務，環境等，在游戲界被稱為“過程生成”。自從1980年首次提出后，該技術在游戲界得到了廣泛地應用。從最簡單的俄羅斯方塊，到我的世界Minecraft這樣的開放游戲，都能見到該技術的身影。
在著名的策略類游戲“席德梅爾的文明”系列中，每一局游戲的地圖，都會有所不同，正因如此，使得玩家愿意多次玩該游戲。為了保證每局地圖不一致，一種做法是在游戲中預設很多地圖，另一種做法是通過算法，每次開始時自動生成地圖。顯然后者能減少游戲所需的計算機存儲空間。
圖1：游戲《文明6》產生的隨機地圖
如何在產生上述地圖時，既保證每一局游戲的開局都不同，又確保玩家不會由于開局的隨機因素，覺得游戲難度發生顯著變化。一種可能的生產方式是元胞自動機，通過玩家給定的參數，算法能夠從某一點出發，逐步依據游戲設計者預設的規則，逐格擴展，產生新的地圖。
在機器學習中，要想提升模型的泛化能力，一種常用的技巧是數據增強（data argumentation），即在有監督學習范式下，通過加入基于現有訓練數據集，經過特定轉換的模擬數據集，從而擴大訓練數據集包含的多樣性，進而提升訓練得出模型的泛化能力。
具體來看，在貓狗圖像分類任務中，可以將原圖拉伸，翻轉，或者裁剪部分區域，再將新生成的數據和原數據一起進行訓練。如此訓練出的模型，能夠更好的提取貓和狗的本質特征，從而使得模型在新數據集上表現更優，穩健型更強。
在強化學習范式下，通過在訓練環境中引入隨機因素，例如訓練掃地機器人時，每次的環境都有所不同，也可以提升模型的泛化能力。而如果將掃地機器人執行的任務看成一次游戲，那么機器學習中的數據增強，就相當于游戲設計中的“過程生成”。兩者都是通過隨機數據，讓玩家能夠透過現象看到本質。
在機器學習成為主流之前，AI領域常用的方法是從一系列可能的解中，通過搜索找出（局部）最優解。將該類方法，應用到游戲生成中，下面是一個典型的案例[1]，即自動生成超級馬里奧的關卡。
具體方法是將游戲的地圖分為微觀（mirco），中觀（meso）和宏觀（marco）模式，算法的目標是根據不同的難度，設定需要得出的對應宏觀模式，之后通過搜索中觀模式的組合，組成宏觀模式，再通過逐個搜索不同的微觀模式組合，得到對應的中觀模式。
圖2：超級馬里奧中，不同的微觀模式，中觀及宏觀模式示例圖
通過逐層的自下而上的搜索，該算法能夠根據最初的游戲地圖，生成在統計上呈現出相同特征，進而具有相近游戲難度的全新關卡地圖。下圖是超級馬里奧原版的第一關，和由算法生成的第一關。
圖3：真實和生成的游戲地圖對比
未來，研究人員和具有科學頭腦的政策制定者或許可以利用這些進展，對尚未觀測到的復雜網絡現象進行定量預測。
對抗生成網絡（GAN）是近五年來，深度學習中進展最快的領域之一。如果將生成新的超級馬里奧的任務交給GAN，它會怎樣完成？18年的ACM論文給出了回答[2]。
圖4：深度卷積對抗生成網絡結構示意圖
該文采用深度卷積對抗神經網絡，使用已有游戲地圖的一部分，作為訓練數據，通過生成器，產生新的游戲地圖，再通過判別器，判斷生成的游戲地圖，是不是和真實地圖類似。之后通過在最初的圖片中進行修改，據此迭代，不斷改進生成器。
圖5：從最左的圖，隨機變化，生成右圖的幾種可能地圖，并隨機選一個進行下一輪迭代
由此，使得生成的地圖中，先不會諸如出現無法跳過的溝等影響可玩性的特征，再逐漸模仿不同難度的游戲關卡中所會出現的障礙物，使得生成的游戲地圖具有相近的難度。
相比傳統的方法，基于GAN的關卡生成，能夠在玩家游戲的過程中，根據玩家的操作，動態地改變下一關游戲的難度，這是傳統的基于搜索的方法無法實現的。除此之外，還能按照特定的目標，設計關卡。
圖6：最大化和最小化跳躍的關卡
例如，如果想要玩家在游戲中盡可能多的跳躍，通過修改GAN的約束條件，可以生成左圖的地圖，而若想要最小化跳躍，則可以生成類似右圖的關卡。
另一類生成游戲關卡的方式，是強化學習。如果要用強化學習生成超級馬里奧的地圖，算法需要一個估值函數，計算不同游戲圖片，距離理想的關卡有多遠。和GAN類似，強化學習范式下，同樣是從隨機的關卡開始，不斷改進，通過迭代完善設計。不同的是，由于估值函數的存在，每一次的改變不是隨機的，而是有方向的。
圖7：強化學習生成游戲的流程圖
上圖中[3]，關鍵的一點是如何對游戲的設計進行表征，不同的表征，決定了設計出的游戲關卡會具有不同的特征。上圖中的估值函數，除了判斷相比上一次，本次生成的游戲關卡是不是更優，還會判斷生成的關卡是否是“可玩的”，如果是，則停止迭代。
圖8：推箱子游戲地圖的二維表征
例如推箱子這個游戲，玩家通過上下左右，操縱小人行動，推動箱子到指定的位置，則算通關，上圖是推箱子地圖的二維矩陣表示。每輪迭代，修改的就是左圖的矩陣。
設計游戲關卡的智能體（agent），需要在給定箱子和目標的距離時，讓小人走的步數盡可能多，從而提升游戲的難度，這就是前文提到的獎勵函數。
而如何判斷每張地圖需要多少步才能走完，則需要智能體通過搜索完成。如果搜索時，智能體只能記住這一步所走格子和改變的那個格子狀態，那么稱之為狹窄表征；如果能記住運行方向上的每個格子以及自己改變了那些格子的狀態，稱之為Turtle式的表征；而如果能記住當前格子周圍所有格子的狀態，稱為寬表征。
圖9：相同初始條件下，不同表征生成的游戲關卡難度不同
上圖中，最左列是初始的隨機游戲地圖；之后的三列，分別是不同表征下，生成的游戲關卡。如果將18部以內就能完成的關卡定義為簡單難度，那么不同的表征下，產生的簡單關卡的比例分別是86.7%，88.3%，以及67.5%，由此說明不同的表征方式會設計出游戲的難度。
在強化學習的框架下進行游戲設計，該文指出了3條經驗，一是需要初始條件不同，二是需設定合適的估值函數，三是每次迭代變化的比例要小，以免算法收斂到相近的解，使得生成的關卡大同小異。
與通過機器學習，提升游戲中關卡生成相對應的，是利用生成的關卡，來提升機器學習模型的魯棒性。下面的例子，來自Uber的AI實驗室[4]，該研究的目標是訓練一個能夠雙足站立行走的機器人操控算法。
圖10：雙足行走的機器人面對的不同類型的環境，例如深谷，斜坡，障礙物等。
傳統上，通過進化算法，能夠訓練操控算法適應不同的環境。但是通過生成一組包含大量斜坡的訓練環境，再生成一組包含大量深谷的環境，可以定向地訓練操控算法在特定環境下，該如何行走，從而使得算法能夠逐個攻克不同環境中面對的障礙。
圖11：訓練能夠持續下臺階，跳過行進路線中深谷的算法示意圖
在訓練過程中，如果在某類障礙中遇到困難，訓練算法，會生成類似的環境副本，讓智能體先在該環境副本中學習如何越過障礙，之后，再在原環境中行走。
通過引入環境副本，在相同的計算量下，由于智能體采取了更好的，在環境副本中學到的走路姿勢，能夠獲得更高的得分，并有更大的幾率，在挑戰更高的路段上走完全程。由此提升了算法的泛化能力。
圖12：機器手玩魔方的過程示意圖
另一個通過游戲來提升AI泛化能力的例子，來自馬斯克的openAI實驗室，是訓練機器手玩魔方[5]，通過強化學習和卷積神經網絡，借助玩魔方這樣一個封閉環境下的任務，研究者提升了對機械手的控制和手眼協調能力，提升了機械手在實際應用場景下的泛化能力。
在強化學習中，通過生成新的游戲關卡，也可以提升訓練的游戲AI的可泛化性[6]，對比在單一難度，人類設計的關卡，以及由算法設計的關卡上訓練的游戲AI，結果顯示，基于算法設計的關卡，需要更少的訓練時間，能取得更高的訓練精度。
該綜述的最后一部分，討論游戲規則生成相關研究目前面臨著那些挑戰。
首先是相比傳統的機器學習問題，訓練數據集偏小，例如超級馬里奧中，只有36個由人手工設計的關卡。
其次是相比生成游戲中的某個組成部分，由算法產生完整的游戲還相對困難。目前較為成熟的生成完整游戲的案例，是基于生成語言模型CPT-2，產生完整的文本式冒險游戲。這是由于一個好的游戲，本身就會相當復雜，并難以使用一個簡單的公式來衡量可玩性。
第三點是通過持續的生產新的游戲關卡，讓智能體實現終身學習。通過不斷改進已學到的策略，過程生成可以讓智能體不斷適應越來越復雜的環境。
第四點是如何在強化學習范式下，基于過程生成，產生標準的數據集和對應任務金標準。之前的強化學習任務，大多是人類設計的電子游戲。未來，可以讓算法設計出新的任務，這些任務會模擬動物及人類在真實環境下所遇到的問題，從而更加準確地能夠考察強化學習模型是否學到了人類認知能力的本質。
第五是如何讓游戲中的關卡設計，能夠不止應用到模擬環境，還能應用到真實場景中。一個腦洞的例子是：通過算法生成類似極品風車的游戲環境，讓算法在游戲環境中，先做到盡可能安全的駕駛，之后在訓練真實無人駕駛的算法時，借鑒模擬算法所具有的特征。
第六點則是，如何將過程生成的本質，即通過讓學習環境多樣化，提升智能體的泛化能力，應用到諸如人類學習，神經科學等其他領域。例如未來的智能課堂中，要想做到因材施教，就可以通過自動設計的游戲化交互，提升學生的學習效率。
總結來看，對于應對復雜系統帶來的挑戰，仿真建模與試錯，一個是高屋建瓴的重構出全局特征，另一個是自下而上的生成相應的認知地圖。而游戲領域的過程生成，則是打通了上述兩條路，通過模仿多主體之間已有的模式，產生更多樣化的環境，從而避免試錯過程變成了管中窺豹井底觀天。
不論對于強化學習，還是有監督學習，引入過程生成，都可以作為一種升級版的數據增強技巧，提升模型的泛化能力。另一方面，在使用機器學習，產生游戲的過程中，所應用的技術，所展現的能力，不止能用于游戲相關的問題，對眾多其他機器學習領域的任務都有借鑒意義。
參考資料：[1] Steve Dahlskog andJulian Togelius. A multi-levellevel generator. In 2014 IEEE Conference on Computational Intelligence and Games, pages 1–8. IEEE,2014.
[2] Volz, V. et al. Evolving mario levels in the latent space of a deepconvolutional generative adversarial network. In Proc. Genetic andEvolutionary Computation Conf. 221–228 (ACM, 2018)
[3] Khalifa, A., Bontrager, P., Earle, S. & Togelius, J. PCGRL: procedural contentgeneration via reinforcement learning. Preprint at https://arxiv.org/abs/2001.09212
[4] Wang, R., Lehman, J., Clune, J. & Stanley, K. O. Paired open-ended trailblazer(poet): endlessly generating increasingly complex and diverse learningenvironments and their solutions. In Proc. Genetic and Evolutionary
[5] Akkaya, I. et al. Solving Rubik’s cube with a robot hand. Preprint https://arxiv.org/abs/1910.07113 (2019).
[6] Justesen, N. et al. Illuminating generalization in deep reinforcement learningthrough procedural level generation. In NeurIPS 2018 Workshop on DeepReinforcement Learning
綜述題目： Increasing generality in machine learning through procedural content generation 綜述地址： https://www.nature.com/articles/s42256-020-0208-z
作者：郭瑞東
編輯：曾祥軒
