標籤：

遊戲人工智慧 讀書筆記（八）遊戲與強化學習

08-20
遊戲人工智慧 讀書筆記（八）遊戲與強化學習

來自專欄第九藝術魅影13 人贊了文章

作者： Jing-Wen Yang @ Tencent Game AI Research Center (TGAIRC)

本文內容包含（但不限於）以下章節：

Chapter 2 AI Methods

Chapter 2.6 Reinforcement Learning

本書英文版： Artificial Intelligence and Games - A Springer Textbook4

強化學習這個名詞說起來大家可能不是很熟悉（也有很多地方翻譯為增強學習）。但是說起AlphaGo，大家就很熟悉了，其實AlphaGo就是強化學習應用極其成功的一個例子（當然它的成功還得益於蒙特卡洛樹搜索和深度神經網路的技術）。實際上，相比傳統的監督學習，強化學習與遊戲有著更深的淵源。這篇文章我們就簡單介紹一下強化學習與遊戲的前世今生。

什麼是強化學習？

強化學習講究在一系列的情景之下，通過多步的決策來達到一個目標，是一種序列多步決策的問題。我們拿大家熟悉的植物大戰殭屍這個遊戲來舉例子。

在與殭屍對抗的過程中，需要選擇播種的植物，選擇播種的位置，收集陽光，選擇植物成長......等等這麼多操作之後才能擊敗殭屍。但是往往要到最後所有殭屍過來了，我們才知道我們播種的植物品種好不好，位置好不好。也就是說，我們在播種植物的過程中，僅能得到一個當前的反饋，比如收集的陽光多了，可以播種的植物更多了，每一條路徑上都有植物守護了這些與勝負有關，但又不決定最後勝負的一些信息（我們通常它們稱為即時獎賞）。如何才能玩好這個遊戲呢？如果沒人教的話，我們就需要不斷的去玩，通過不斷的嘗試播種策略才能總結出一個好的玩遊戲的策略。

通過這個過程我們可以看到強化學習有別於監督學習，它不能實時獲得最終勝負的標記，但是能夠得到與之相關的獎賞，因此可以說強化學習是一種標記延遲的監督學習，是監督學習的一種特例。另外一方面，強化學習實際上和我們人類與環境的交互方式類似。是一套非常通用的框架，可以用來解決各種各樣的人工智慧的問題。

總結來說，強化學習的目標就是要尋找一個能使得我們獲得最大累積獎賞的策略。為啥是累積獎賞？因為我們往往不是說打敗殭屍就可以，還需要評分高，比如收集到很多的陽光之類的

數學上，累積獎賞表示為

J_t = r_{t+1}+gamma r_{t+2}+gamma^2 r_{t+3}+cdots

其中 gamma (0 leq gamma leq 1) 為折扣係數， t 表示第幾步。引入折扣係數這個東西，主要是出於獎賞對於不同的階段帶來的收益應當是有差別的。比如大家做買賣都喜歡現錢，因為如果通貨膨脹錢貶值了，那就相當於少賺了。

策略一般是用 pi(s)=a 來表示，也就是在狀態 s 下，根據 pi 策略，我們採取 a 動作。有了策略的定義，我們還得知道一個策略到底好不好？最直接的就是用一個值函數來評估，值越高越好唄。比如可以定義一個值函數 Q^pi(s, a) ，它表示在策略 pi 下，從狀態 pi 出發，執行動作 a 所帶來的累積獎賞。

強化學習的基本演算法

這兩個基本的概念實際上給我們指了兩條可以求解強化學習的明路。一種就是直接去尋找一個好的策略。另外一種就是能求解一個最優的值函數，這個最優的值函數能夠告訴我們在這個狀態下，選取哪個動作能得到的期望值最高，不管在什麼狀態，我們總是能從值函數表那裡查表獲得應該選取哪個動作。這個表實際上也就可以作為策略了。

我們首先來看看怎麼直接尋找策略。前面也提到了策略實際上就是一個從狀態到動作的一個映射，那麼就可以用個參數 heta 的模型去近似它（表示為 a=pi_ heta(s) ）。既然目標就是要讓累積的獎賞最大，我們只要以這個目標求梯度 abla_ heta J ，按照梯度不斷更新 heta 值，就可以最終得到期望的策略。

然後再來看看基於值函數的方法。幾乎所有的強化學習的模型都是定義在Markov決策過程上的。這個是什麼呢？其實就是包含了上面我們說的那些狀態，動作，獎賞，以及影響狀態轉移的概率，在這個模型下，未來的狀態只與當前狀態有關，與以前的沒有關係（即Markov性質）。一個Markov決策過程可以表示為

s_0, a_0, r_1, s_1, a_1, ldots

基於這個假設，很容易得到值函數是滿足一個遞歸式子的。

Q(s,a) = E[r_{t+1}+gamma r_{t+2} + gamma^2 r_{t+3}+cdots | s_t = s, a_t = a]

=E[r_{t+1} + gamma(r_{t+2} + gamma r_{t+3} + cdots)|s_t = s, a_t = a]

=E[r_{t+1} + gamma Q(s, a)|s_t = s, a_t = a]

最優值函數也是一樣

Q^*(s,a) = E[r_{t+1}+gamma Q^*(s,a)|s_t=s, a_t=a]

這個式子指導我們通過不斷迭代就能夠得到最優的值函數。如圖所示，一個實心點就是值函數Q，白圈表示狀態。上述的Bellman Equation實際上可以按照Markov決策過程展開成一個樹狀的結構，我們不斷向前看，探索後面的情況，然後將這些得到的獎賞綜合起來。然後就能得到一步一步往狀態動作值函數里填。

目前最常用的求解演算法是Q-learning，演算法流程很簡單，如下圖所示

其中的Q的更新方式為

這個更新策略簡單來說就是用新的Q值和之前估計的狀態轉換得到的Q值的一個加權平均，不斷迭代下去，Q值函數就能收斂。

那麼上面的 epsilon-greedy 準則又是啥呢？其實就是 epsilon 的概率從所有動作中均勻隨機選取一個，以 1-epsilon 的概率選取當前策略給出的最優動作。這樣做的目的是為了不讓機器做井底之蛙，有時候如果只選當前最優的策略，可能只是在當前認知範圍內最好的，這樣極容易造成「自我滿足」，從而停滯不前。世界太大，我們需要出去看看！當然這只是一個簡單的處理方法，這裡涉及到exploitation & exploration dilemma的問題，在多臂賭博機（Multi-armed Bandit Problem） 中有相當多的研究。

強化學習與遊戲

由於強化學習當前演算法的仍有很大的局限性，對於目前市面上複雜的電子遊戲而言，還難以直接處理，因此目前還沒有看到在商用遊戲中的廣泛應用。但是相信這一天很快就到來了！因為目前在學術研究中已經有很多令人欣喜的成就！

除了AlphaGo之外，其實早在1992年，IBM就利用強化學習在一個古老的桌面遊戲Backgammon上取得了巨大的成功，成為了當時這個遊戲最強的玩家。

而在其他棋類遊戲上，並沒有取得如此巨大的成功，比如在象棋上，也有像NeuroChess這樣的工作，但是並沒有取得令人矚目的成績，大獲成功的深藍計算機也並不是因為強化學習而取勝。這一方面是由於棋盤的特徵表示是比較困難的（雖然圍棋的難度更大，但是棋盤和棋子相比象棋卻更為簡單）；另一方面也有研究表明象棋類遊戲狀態空間的採樣有很大的難度，如果自我對弈設置不合理，就很容易陷入一個局部最優解。

除了這些棋類遊戲，在視頻類遊戲上，DeepMind在廣為人知的AlphaGo之前就已經利用強化學習來玩Atari遊戲了。這也是深度學習與強化學習（所謂深度強化學習）一個非常經典的研究。

這個工作主要是利用上了當前深度學習在抽取特徵上的優勢，並且利用諸如Replay Memory（存儲原來的樣本，一同參與採樣）這樣的技術提高了強化學習的學習效率。以一個端到端的模型，在很多小遊戲上達到甚至超過了人類的水平。

在射擊遊戲上也是有很多研究工作，以VizDoom為平台的比賽每年都會吸引大量頂尖團隊參加。

在AlphaGo在圍棋上取得巨大成功之後，更多的研究者開始把目光放到了更為複雜的即時戰略遊戲中，DeepMind聯合暴雪公布了基於星際爭霸2的開發環境sc2le

並且在最近公布了一個新的成果，能夠利用邏輯推斷進行關係型強化學習，在6個小任務中都取得了當前最佳的表現，並且在其中4個超過了人類高手的水平。

Facebook也在跟進這方面的研究，也開源了自己的遊戲智能研究平台ELF，也偷偷參加了AIIDE（The Artificial Intelligence and Interactive Digital Entertainment）的星際爭霸比賽，可惜名次並不佳。

星際爭霸中包含了諸多的關於人工智慧的重要問題，詳細可以參見我之前寫的文章 為什麼要研究星際爭霸的AI？，如果星際爭霸上取得了突破性的進展，相信強化學習在遊戲中的應用會變得更為廣泛（當然這個技術突破的影響就不在僅僅局限於遊戲範疇了）

總結

強化學習有別於傳統的監督學習，它不需要大量的標記樣本，就可以自動的完成複雜任務的學習。對於遊戲這樣，天生具有出色的模擬環境的場合，強化學習的技術可以非常容易的得到施展，幫助遊戲開發者創造水平極高的遊戲智能。

但是他的局限目前也很多，他需要使用者去精心設計反饋函數，因為很多複雜遊戲中（比如王者榮耀，吃雞等）很難說用一個像Atari那樣簡單的實時評分就可以作為反饋獎賞的，而另外一方面，複雜遊戲的狀態和動作空間也都往往非常大（比如王者榮耀中，每個英雄的技能都大不相同，當前攜帶的銘文，釋放的方式，角度，時機，對位的英雄是誰都會對動作的選擇有非常大的影響），這些對於強化學習的學習效率也提出了非常高的要求。如何能夠在商業級遊戲中應用強化學習，還需要我們應對很多挑戰！

參考資料

  • 這個領域最經典的教材就是Richard Sutton教授的Reinforcement Learning: An Introduction
  • 還有他的學生David Silver（也是現在DeepMind的核心成員）在UCL 開的公開課程Reinforcement Learning，搭配食用更佳 : )

推薦閱讀：

TAG:遊戲 | 強化學習ReinforcementLearning | 人工智慧 |