作者 | Ekaterina Nikonova，Jakub Gemrot
譯者 | Tianyu
出品 | AI科技大本營（ID:rgznai100）
現在說起《憤怒的小鳥》遊戲，要把人的回憶一下拉扯到差不多十年前了。
它是一款當時一經推出就廣受歡迎的遊戲，玩家可以用彈弓把若干只小鳥彈射出去，目標是摧毀所有綠色的豬，並獲得儘可能高的分數，經常有很多豬藏在複雜的結構之中。由於順序的決策、不確定的遊戲環境、複雜的狀態和動作、功能特性不同的鳥，以及最佳彈射時機等因素，都使得《憤怒的小鳥》很難擁有一款好的 AI 代理。
近日，來自捷克查理大學的研究者發佈論文《Deep Q-Network for Angry Birds》稱，他們採用 DDDQN（Double Dueling Deep Q-network）算法實現了一款深度強化學習應用，可以用來玩《憤怒的小鳥》。他們的目的之一是創造一個遊戲智能體，可以基於之前玩家在前21關的遊戲記錄來進行遊戲闖關。
為了實現這一目的，他們收集了遊戲記錄的數據集，為 DQN 遊戲代理提供了多種多樣的方案。遊戲中需要做很多有關順序的決策，兩次彈射之間會相互影響，每一次彈射的精準度也很重要。例如，一次糟糕的決策可能會導致一隻豬被若干個物體卡住。因此，為了更好地完成遊戲中的任務，遊戲代理要有基於決策對結果進行預測和模擬的能力。
以下為《Deep Q-Network for Angry Birds》論文的內容概述：
相關工作
2012年，首次舉辦了《憤怒的小鳥》 AI 大賽，隨之出現了很多款遊戲代理。在這裡介紹兩款比較優秀的代理，第一個是由來自捷克技術大學的隊伍所開發的 Datalab Birds 2014，該遊戲代理至今保持著第三名的位置。就像他們在論文中描述的，他們的主要思想是基於當前環境、可能的彈射軌跡和鳥的類型來制定最佳策略。第二個是由滑鐵盧大學和 Zazzle 在 2017 《憤怒的小鳥》AI 大賽中共同開發的 Eagles Wings 智能玩家，他們的代理目前排在第 16 位。據稱，該遊戲代理基於人工調試過的結構分析，即在多個策略中做選擇，開發了一項簡單的多策略能力。他們使用了機器學習算法 xgboost 學習決策制定能力。
背景介紹
為了解決《憤怒的小鳥》中的順序決策問題，我們基於每個時間步長來考慮遊戲環境 ε 。在每個時間步長 t，代理都會得到觀察值St，然後從可能的動作集中選擇一個動作
，接下來會得到獎勵項
。接下來代理的目標是基於下面的公式將獎勵項最大化：
在上面的公式中，s 為當前狀態，a 為所選的動作，為獎勵項，
是權重係數，來決定獎勵項對未來結果的重要性。現在我們定義最佳 Q 值如下：
在每個狀態選擇最大值所對應的動作，我們就可以獲得最佳策略。
DQN 算法理論基礎
為了模擬最佳 action-value 函數，我們使用深度神經網絡作為非線性函數逼近器，我們定義一個逼近函數：
其中，
為 Q 網絡進行第 i 次迭代的權重。
如論文中所說，將強化學習算法與非線性函數逼近器，如神經網絡，結合使用會不穩定，甚至產生偏移，原因如下：a) 序列中觀察值之間的關聯性；b) Q 值與 target 值
之間的關聯性；c) 該方法對 Q 值的變化極其敏感。
Deep Q-learning 試圖用技術解決第一個問題，即經驗回放。該技術通過將所收集的數據隨機化，去除了序列中觀測值之間的相關性。我們對經驗的定義如下：
其中，
為 t 時刻的狀態，
為 t 時刻採取的動作，
為 t+1 時刻的獎勵，
為執行後的狀態。我們將經驗保存在經驗集中：
接下來，我們從經驗集 M 中抽樣出部分經驗，在 Q 網絡中對 Q 值進行更新。
為了解決第二個問題，需要用到下面的損失函數：
其中，i 為迭代次數，
為權重係數，
為實時網絡的權重，
為目標網絡的權重。
接下來，我們 DQN 的目標如下：
A. Double Deep Q-Networks
原始的 DQN 算法對動作選擇和動作表現的評估兩個步驟都採用了最大值，這很可能導致過度估計。基於這一缺陷，Double Q-learning 算法產生了。不同於傳統 DQN 算法僅使用一個神經網絡，如今我們使用一個網絡選擇動作，再使用另一個網絡對所做的決策進行評估。因此，我們可以將原始的 Q-learning 目標改寫為：
其中，
為實時權重，
為第二個權重集，即用實時權重進行動作選擇，用第二個權重對其評估。幸運的是，同樣的方法也可以應用到 DQN 算法中，我們可以對更新函數進行替換，如下：
其中，為 DQN 的實時權重，
為目標 DQN 的權重。
B. Dueling Deep Q-Networks
在某些場景中，不同動作獲得的值是很接近的，沒必要對每個動作進行評估。在《憤怒的小鳥》中，有時候玩家會陷入某種無解的處境，如豬被一些物體卡住了。在這種情況下，無論採取什麼動作都是一樣的結果，因此任何動作的得分都是幾乎一樣的，而我們只在意這個狀態本身的分數。考慮到對這些場景的優化，Dueling 結構應運而生了。為了實現 Dueling Q-learning 結構，我們需要使用兩個全連接層。將卷積層的輸出分成兩部分後，我們需要再把它們結合以獲得 Q 函數。首先定義價值函數：
優勢函數為：
也就是說，價值函數可以告訴我們某個具體狀態的好壞程度，而優勢函數告訴我們每個動作的重要性。這樣我們可以構造我們的第一個全連接層，得到輸出
，以及第二個全連接層，可得到輸出
，此處的 α 和 β 都是全連接層的權重，θ 為卷積層的權重。為了將兩個值結合並獲得 Q 值，我們定義網絡的最後一個模塊如下：
這樣我們就得到了價值估計函數和優勢估計函數，將其與之前定義好的 Deep Q-network 和 Double Q-learning 結合使用，就可以用在《憤怒的小鳥》這款遊戲中了。
將 DQN 應用於 AIBIRDS
為了將 DQN 應用於《憤怒的小鳥》，我們首先需要定義：a) 狀態，b) 動作，c) Q-network 結構，d) 獎勵函數。AIBirds 競賽組織方提供了可以對遊戲進行截圖的軟件，可以得到 840x480 像素的圖片。圖1為逐步處理圖片的過程。
圖1：遊戲截圖的處理過程，從左到右：原始截圖，剪裁，調整大小，標準化
我們規定動作為
，其中每個數字代表射出的角度。接下來，我們基於軟件為每個給定角度找到最終的釋放點。為了計算釋放點，軌跡模塊首先尋找彈弓的參考點，然後計算釋放點。
我們的 DQN 結構是基於 Google DeepMind DQN 的，圖2為我們的 DQN 結構。該模型包括4個卷積層，kernel 分別為 8x8，4x4，3x3，7x7，strides 分別為 4x4，2x2，2x2，1x1。最後一個卷積層後面連接了兩個 flatten 層，最後結合生成 Q 值。
圖2：
Double Dueling DQN 結構
獎勵函數所使用的技術通常被稱為獎勵修剪（reward clipping）。這種方法將很大或很小的分數修剪為1或-1分的得分，來代表一個好動作或壞動作。《憤怒的小鳥》這款遊戲的主要目標除了過關，還要活得儘可能高的分數。考慮到這一點，我們需要改變獎勵函數，如下：
上式中，score 為 s 狀態下采用動作 a 後的分數，maximum score of current level 為當前關卡的歷史最高得分。基於這個公式，我們期望遊戲代理可以學習分數的重要性，並通過學習動作的獎勵機制來刷新當前關卡的得分。
A. 訓練集
我們的訓練集包括《憤怒的小鳥》經典系列的21個關卡。在訓練階段，遊戲代理基於 115000 張圖進行網絡的訓練。在遊戲截屏前，代理需要等候5秒鐘。這一項小調整是必需的，為了讓鳥被髮射後所產生的震動得以平復下來。
B. 驗證集
我們的驗證集包括《憤怒的小鳥》經典系列的10個關卡。由於代理的訓練集中只有紅鳥、藍鳥和黃鳥，所以我們不得不挑選沒有新鳥的關卡作為驗證集。從第二頁和第三頁挑選的關卡比第一頁的難度要高一些。在玩這些關卡時，玩家必須找到一些不太明顯的結構上的弱點，並提前仔細規劃策略。
結果
我們對競賽中幾個參賽結果進行了對比，如圖3。對不同的代理結果進行對比，可以幫助我們瞭解哪項 AI 技術更適用於《憤怒的小鳥》這款遊戲。然而我們仍然無法搞清楚的是，和人類比起來這些遊戲代理表現如何。
圖3：幾個不同的 DQN 代理對比
本篇論文中，我們還進行了 AI 和人類的對比。人類參賽者可以進行無數次嘗試，直到參賽者覺得已經獲得了自己的最佳分數。我們從不同水平的人中挑選參與實驗者，玩家1和玩家3有玩《憤怒的小鳥》的4年遊戲經驗。玩家2很久之前玩過幾次這款遊戲，沒有太多經驗。玩家4過去常常玩這款遊戲，但最近沒怎麼玩過。
如圖4所示，我們的遊戲代理在總分上超過了一個人類玩家，而輸給了其他玩家。產生這一結果的主要原因是，代理無法通過第18關。在其他關卡中，代理可以在某些關卡上超過一些玩家。總的來說，我們的 DQN 代理在前21關獲得了 1007189 分，它敗給了四位人類玩家中的三位。因此我們的代理還存在非常大的提升空間。
圖4：DQN 代理與人類玩家的遊戲得分對比
圖5位代理在驗證集上的表現。如我們所料，對於代理之前沒有見過的關卡，大都無法通過。
圖5：DQN 代理在驗證集上的結果
《憤怒的小鳥》 AI 大賽結果
除了將我們的代理與人類玩家進行對比以外，我們在 IJCAI-2018 大會上做了展示，參加了《憤怒的小鳥》 AI 大賽。該競賽本身包括三輪：四分之一決賽、半決賽和總決賽。每一輪中，參賽的遊戲代理要面對 8 個之前未見過的關卡。
表1展示了四分之一賽中全部遊戲代理的總分數，在全部基於神經網絡的代理中，我們的 DQ-Birds 表現最好，通過了 8 個關卡中的 3 個。MYTBirds 也使用了神經網絡，但只通過了一個關卡。其它代理均使用了除神經網絡以外的方法。
表1
結論
對於 AI 代理來說，《憤怒的小鳥》這款遊戲始終是一項艱鉅的任務。我們提出了一種基於 Double Dueling DQN 的遊戲代理來試圖解決遊戲中的順序決策問題。在目前的研究工作中，我們沒有達成的目標是在這款遊戲中超越人類玩家。但好的一點是，我們的代理只需要一次機會就可以通關。另外有趣的是，在大多數情況下，它只用了一次精準的彈射就擊中了關鍵點，通過了關卡。
總之，儘管我們的代理超過了部分之前的玩家，並在 AIBirds 比賽中超過了部分參賽者，但仍存在很大的進步空間。例如，我們可以嘗試在獎勵函數中加入超參數。我們還可以嘗試如今已公開的全部深度強化學習優化技術。下一步，我們計劃基於更多的遊戲關卡對遊戲代理進行訓練。
（*本文為 AI科技大本營編譯文章，轉載請微信聯繫 1092722531）
◆
◆
"閱讀更多 AI科技大本營 的文章
