深度學習因為其強大的表征能力，在很多方面都有非常優秀的性能，它不論是在計算機視覺、自然語言處理，還是在游戲智能體上都能構建出優秀的模型。而最近圖盧茲聯邦大學等研究者表示進化算法也有著與深度學習相類似的潛力，它可以進化出一些能玩 Atari 游戲的智能體，并取得與人類相匹配的性能。

近期街機學習環境（ALE）被用于對比不同的控制器算法，從深度 Q 學習到神經進化算法。Atari 游戲的環境在一個通用界面上提供了大量不同任務、可理解的獎勵度量和令人興奮的研究領域，且它所需的計算資源相對有限。無怪乎該基準套件得到了如此廣泛的應用。

Atari 領域中的一個困難在于使用純像素的輸入。盡管與現代游戲平臺相比，Atari 的屏幕分辨率不算高，但處理這類視覺信息對于人工智能體來說仍然是個挑戰。人們使用目標表征和像素縮減方法，將該信息壓縮成更適合進化控制器的形式。這里深度神經網絡控制器表現更加優秀，原因在于卷積層和在計算機視覺領域的長期應用。

笛卡爾遺傳規劃（Cartesian Genetic Programming，CGP）在計算機視覺領域的應用也有很長的歷史，盡管比深度學習稍微短了一些。CGP-IP 能夠創建圖像濾波器，用于去噪、目標檢測和質心定位（centroid determination）。在強化學習任務中使用 CGP 的研究相對較少，本論文將展示首次使用 CGP 作為游戲智能體的研究。

簡單而言，笛卡爾遺傳規劃是遺傳規劃的一種形式，其中程序表征為有向的、通常由笛卡爾坐標索引的非循環圖。其中功能性節點通常由一組進化的基因定義，并通過它們的坐標連接輸入與其它功能性節點。程序的輸出由任何內部節點或程序輸入基于進化的輸出坐標得出。

ALE 提供了 CGP 和其他方法之間的定量對比。直接將 Atari 游戲分數與之前研究中的不同方法結果進行對比，以對比 CGP 與其他方法在該領域的能力。

CGP 的獨特優勢使得其應用在 ALE 上非常合適。通過定長的基因組，小型程序能通過進化生成并被讀取以理解。雖然深度 actor 或進化神經網絡的內部機制可能難以了解，但 CGP 進化的程序可以讓我們深入理解玩 Atar 游戲的策略。最后，通過使用用于矩陣運算的函數集，CGP 能夠僅使用像素輸入而不使用先驗游戲知識，在多種游戲上實現與人類相當的性能。

論文：Evolving simple programs for playing Atari games

論文地址：https://arxiv.org/abs/1806.05695

項目地址：hps://github.com/d9w/CGP.jl

摘要：笛卡爾遺傳規劃（Cartesian Genetic Programming，CGP）之前已被證明在圖像處理任務中具備使用計算機視覺專用的函數集來進化程序的能力。類似的方法也可用于 Atari 游戲。使用混合型 CGP 和適用于矩陣運算的函數集（包括圖像處理）來進化程序，但是允許出現控制器動作。盡管這些程序相對較小，但很多控制器的性能與 Atari 基準集的最優方法不相上下，且需要的訓練時間更短。通過評估最優進化的程序，我們可以找到簡單卻有效的策略。

3 方法

盡管有很多在圖像處理中使用 CGP 的案例，但在玩 Atari 游戲時這些實現必須進行修改。最重要的是，輸入像素必須通過進化程序處理以確定標量輸出，這需要程序減少輸入空間。本研究選擇的方法可確保和其它 ALE 結果的可比較性，同時鼓勵有競爭力且簡單的程序的進化。

圖 1：使用 CGP 來玩 Atari 游戲，藍色像素矩陣是進化程序的輸入，進化的輸出決定最后的控制器動作。這里展示了所有控制器動作，但大多數游戲僅使用可用動作的子集。帶紅色標記的動作表示一個按鈕。

4 結果

圖 2： Kung-Fu Master 游戲的蹲伏方法和玩家功能圖。為簡潔起見，這里忽略未激活的輸出和導致這些輸出的計算圖。

圖 3：Centipede 玩家，僅激活了輸出 17，下-左-開火。所有其它輸出導致空值或恒定零輸入，此處未展示。

圖 4：Boxing 游戲，使用像素輸入來連續移動和采取不同動作。這里，CGP 智能體通過不斷打擊 Atari 玩家來緩慢移動，將 Atari 玩家逼到圍繩處。