PCG —— 程序內容生成，通過算法創建游戲內容，例如游戲規則，關卡，角色，背景故事，紋理和聲音。近年來國際會議組織了各種比賽，例如馬里奧AI級別生成比賽，Platformer AI比賽，AI鳥類等級生成比賽和一般視頻游戲AI（GVGAI）等級生成比賽 。今天為大家介紹一項關于 PCGML 的最新研究（PCG 通過機器學習的例子），這篇論文也被 GECCO 2018提名為 Best Paper Award ，這也是一個新興的研究領域。

研究中以無監督學習方式訓練生成對抗網絡（近期關于無監督學習與GAN的內容我們也給大家介紹了不少），模型根據視頻游戲級語料庫中的實際游戲級別進行訓練。并引入了隱變量進化（LVE）的概念；為了在這個潛在空間內找到最佳水平段，進化算法協方差矩陣自適應進化策略（CMA-ES）用于找到產生水平段的潛在向量，由此產生的系統有助于發現人類專家創建的示例空間中的新級別。

▌摘要

生成性對抗網絡(GAN)是能夠在給定的訓練樣本空間內生成新的樣本輸出的一種機器學習方法。視頻游戲中的程序內容生成(PCG)可以從這種模型中受益，特別是對于那些預先存有語料信息的游戲。本文，我們利用視頻游戲語料庫，訓練一個GAN模型為超級馬里奧兄弟生成游戲級別(Super Mario Bros)。

我們的方法不僅能夠成功地生成與原始視頻語料庫中級別相當的各種游戲，還能通過應用協方差矩陣自適應進化策略(CMA-ES)進一步改進游戲級別。具體地說，我們使用各種適應度函數(fitness function)來探索GAN模型潛在空間水平，以最大化期望屬性，而諸如tile類型分布的靜態屬性都能夠被進一步優化。此外，我們使用2009版Mario AI比賽的冠軍A*智能體，用于評估游戲級別的可玩性，以及需要多少跳躍動作來擊敗它。這些適應度函數允許模型在專家設計的樣本空間中探索各種游戲級別，并指導進化朝著滿足一個或多個指定目標水平的方向。

▌方法

我們的方法分為兩個主要階段，如下圖1所示。

圖1 GAN訓練流程及隱向量進化概述。我們的方法可以分為兩個截然的階段。在第一階段中，GAN以無監督學習的方式進行訓練并生成馬里奧游戲水平。在第二階段，我們搜索潛在向量空間產生具有特定屬性的游戲級別。

首先，GAN在現有的Mario級別上進行訓練(下圖2所示)。該級別將被編碼為多維數組，并在黃色框中描繪。模型中生成器(用綠色表示)輸入的是高斯噪聲向量(用紅色表示)，并以相同表征水平輸出。而判別器用于區分現有級別和生成級別之間的差異性。我們使用對抗性學習的原則來訓練生成器和判別器。

圖2訓練水平。通過水平從左向右滑動一個28×14窗口生成訓練數據。

一旦訓練過程完成，生成器網絡可以被視為是我們學習到的genotype-to-phenotype映射，它能夠將潛在的實數向量(用藍色表示)作為輸入(我們的論文實驗中將其大小設置為32)，并產生一個tile-level的馬里奧游戲級別。相比于簡單地繪制來自潛在空間的獨立隨機樣本，我們在進化控制策略下(在這種情況下使用CMA-ES)進行探索。換句話說，我們在隱向量空間搜索并產生想要的不同屬性的游戲級別，如tile分布，難度等。

CMA-ES

協方差矩陣自適應進化策略(CMA-ES)是一種功能強大而又廣泛使用的進化算法，特別適合于實數向量的進化過程。CMA-ES是一種二階方法，通過有限差異法不斷迭代估計協方差矩陣。它無需依賴一個光滑的自適應先驗，而能夠有效地處理連續域中非線性、非凸問題的優化。我們采用CMA-ES策略來進化潛在向量，并生成的游戲級別上應用幾種自適應度函數。所使用的自適應函數是基于生成的游戲級別的靜態屬性，或使用人工智能體進行游戲模擬結果。

游戲級別表征

在視頻游戲中，馬里奧游戲級別有不同的表征Level Corpus (VGLC)和Mario AI框架，這兩種都是基于tile的表征形式。具體地說，以VGLC表征的馬里奧級別使用特定的字符符號來表示每個可能的tile類型。然而，應該注意的是這個VGLC表征主要是關注tile的功能特性而不是其藝術屬性，因此無法區分視覺上某些特定的tile類型。此外，通過僅提供的單個字符符號來表示不同的敵人類型，VGLC編碼忽略了不同敵人之間的功能差異，因此我們可以選擇將其映射到通用的Goomba敵人類型上。

為了對訓練的水平進行編碼，我們用不同的整數來表示每種tile類型，它在輸入到判別器前被進一步轉換為一個獨熱編碼(one-hot)。此外，生成器網絡同樣用獨one-hot編碼形式輸出再將其轉換回整數值。基于整數格式的級別隨后將被發送到用于渲染的Mario AI框架。Mario AI框架允許其tile類型產生更廣泛的藝術多樣性，但由于其VGLC編碼的簡單性，只有小部分子集的Mario AI tile是可用的。從VGLC tile類型和符號，到GAN的訓練數字編碼再到最后Mario AI tile的整個可視化流程如下表1所示。

表1生成的Mario游戲級別所使用的tile類型。符號字符是來自VGLC編碼，然后數字標識被映射到相應的值并用于生成可視化的Mario AI框架。在GAN訓練期間，該數字標識值將被擴展為獨熱向量(one-hot)輸入到判別器網絡。

GAN模型

我們采用深度卷積生成對抗網絡DCGAN結構，并使用WGAN算法進行訓練，模型的結構示意圖如下圖3所示。遵循原始的DCGAN架構，判別器網絡中采用跨步長卷積(strided convolutions)，而生成器中采用小步長卷積(fractional-strided convolutions)，在生成器和判別器的每層后都接上batchnorm以正則化。此外，在生成器中每一層我們都使用ReLU激活函數(包括輸出層，原始結構中輸出層采用Tanh激活函數)，我們發現這能帶更好的結果表現。而判別器中每一層我們采用LeakyReLU激活函數。

圖3訓練Mario游戲的DCGAN模型結構

▌實驗結果

為驗證我們的方法，在實驗部分我們通過兩組不同實驗分別進行基于表征測試(representation-based testing)和基于代理測試(agent-based testing)。實驗結果如下。

基于表征測試(representation-based testing)

下圖4顯示了該方法優化的ground tile百分比與特定目標分布的接近程度。結果表明，每次運行中我們幾乎都可以非常接近目標的百分比。

圖4優化不同百分比的ground tiles。運行20次后將平均每次的結果并產生一個標準差。除去20%的地面外，該方法總能夠發現用于生成ground tiles所需目標百分比的潛在編碼。

此外，圖5顯示了逐級遞增的游戲水平難度：其中第1和第2部分的地面覆蓋率達100％，第3-5部分的地面覆蓋率達70％，而第4、5節中我們還同時最大化敵人的總數n。實驗結果表明我們的方法能夠同時優化地面分配以及敵人的數量。

圖5逐級遞增的游戲難度。我們的LVE方法能夠創建含多個組成部分的游戲級別，這些級別的難度逐漸增加(即越來越少的地磚伴隨著越來越多的敵人)。將來，這種方法可以用來創建一個實時的水平，以適應玩家的特殊技能(動態難度適應)。

基于代理測試(agent-based testing)

圖6顯示了自適應函數F1和F2的一些最佳和最差結果。我們可以看到，CMA-ES策略確實可以發現一些不可玩的等級(如圖6c所示)。自適應函數F1的最佳效果(即具有大量所需跳躍操作的可玩級別)如下圖6a和6d所示。而圖6b描述是自適應函數F2所產生的最佳結果(即只需少量跳躍操作的可玩級別)。該級別只需要跳躍一次就能很容易地解決敵人。

圖6基于代理的優化示例。a和b顯示了F1自適應函數下最大化跳躍次數的例子，此時最小化F2函數。c顯示了一個最差的結果，即在F1自適應函數下不可玩的游戲級別例子。在d中顯示了高適應性的結果(即F1下最大化跳躍步數)，但同時破壞了標題的例子。

▌結論

本文提出了一種新的隱變量進化方法，它能夠以無監督學習的方式，在現有的Mario游戲水平上，進化并產生新的Mario游戲級別。我們的方法不僅能夠優化不同分布水平，并將tile類型結合起來，還可以使用基于代理的評估函數來優化游戲級別。雖然我們的GAN模型通常能夠捕捉到高水平的訓練結構，但有時也會產生破碎的結構。將來的工作我們可以通過采用更適合視頻游戲離散表征的GAN模型來優化這個問題，我們希望LVE能夠作為一種很有前景的快速生成方法，擴展到各種視頻游戲以及其他類型的游戲。