南大AI用分層強(qiáng)化學(xué)習(xí)，一天時(shí)間單機(jī)訓(xùn)練擊敗《星際爭(zhēng)霸2》內(nèi)置AI

南京大學(xué)團(tuán)隊(duì)使用分層強(qiáng)化學(xué)習(xí)，結(jié)合宏動(dòng)作學(xué)習(xí)、課程學(xué)習(xí)等方法，僅使用12個(gè)物理CPU核和48個(gè)線程，單機(jī)訓(xùn)練一天時(shí)間內(nèi)，擊敗了《星際爭(zhēng)霸2》內(nèi)置AI。

9月19日，騰訊AI Lab團(tuán)隊(duì)號(hào)稱“首次在《星際爭(zhēng)霸2》完整的蟲族VS蟲族比賽中擊敗了游戲的內(nèi)置AI Bot”，這是首個(gè)能在正式比賽中擊敗內(nèi)置機(jī)器人的AI系統(tǒng)，堪稱研究道路上的一大突破。

根據(jù)發(fā)表在arXiv上的預(yù)印版論文，騰訊AI Lab團(tuán)隊(duì)使用的方法是人工定義大量的宏動(dòng)作（macro-action）、人工編碼科技樹建造建筑，用蟲族（擅長(zhǎng)快推）在3000多個(gè)CPU上取得了這一成果。

實(shí)際上，在更早的4月份，來(lái)自南京大學(xué)的俞揚(yáng)團(tuán)隊(duì)也深入研究了《星際爭(zhēng)霸2》的分層強(qiáng)化學(xué)習(xí)方法。與騰訊AI Lab不同的是，南京大學(xué)團(tuán)隊(duì)不依賴人工定義的宏動(dòng)作，而是從人類的演示數(shù)據(jù)中自動(dòng)學(xué)習(xí)宏動(dòng)作。再依靠強(qiáng)化學(xué)習(xí)自動(dòng)學(xué)習(xí)基地運(yùn)營(yíng)和戰(zhàn)斗調(diào)度，并僅在12個(gè)物理CPU核、48個(gè)線程、智能體設(shè)定為神族、對(duì)手設(shè)定為人族的情況下，取得了突破性的成果。

在“《星際爭(zhēng)霸2》學(xué)習(xí)環(huán)境”SC2LE上的實(shí)驗(yàn)結(jié)果表明，南大團(tuán)隊(duì)通過(guò)分層強(qiáng)化學(xué)習(xí)和課程學(xué)的方法，在最困難的非作弊內(nèi)置AI（level-7）中獲勝的概率超過(guò)了93%，是當(dāng)前最佳成績(jī)。

負(fù)責(zé)這項(xiàng)研究的南京大學(xué)計(jì)算機(jī)系副教授俞揚(yáng)博士表示：

《星際爭(zhēng)霸》這一款超大規(guī)模游戲是強(qiáng)化學(xué)習(xí)的一大挑戰(zhàn)。擊敗內(nèi)置AI只是小小的并不值得宣揚(yáng)的第一步，其實(shí)我們的研究目標(biāo)在于探索適用于大規(guī)模問(wèn)題而又不失通用性的強(qiáng)化學(xué)習(xí)方法，因此我們必須找到在盡可能避免手工設(shè)定、使用少量計(jì)算資源的條件下仍能高效學(xué)習(xí)的方法。在這一篇工作中，我們結(jié)合分層強(qiáng)化學(xué)習(xí)、宏動(dòng)作學(xué)習(xí)、課程學(xué)習(xí)、獎(jiǎng)賞設(shè)計(jì)等多種不同的強(qiáng)化學(xué)習(xí)技巧，達(dá)到了只使用單機(jī)計(jì)算資源在一天時(shí)間單機(jī)訓(xùn)練可達(dá)到擊敗《星際爭(zhēng)霸2》內(nèi)置AI的水平，為未來(lái)大規(guī)模強(qiáng)化學(xué)習(xí)方法提供參考。

現(xiàn)在，這篇論文的預(yù)印版已經(jīng)可以在arXiv上公開訪問(wèn)，地址如下：

https://arxiv.org/abs/1809.09095

《星際爭(zhēng)霸2》為何如此難以攻克？

從資源的角度來(lái)看，在剛剛進(jìn)入游戲界面時(shí)，每方都擁有晶體礦（左上角水晶）和氣礦（頂部綠色氣體彌漫的礦山）兩種資源。

從人口單位來(lái)看，截圖中的兵種包括農(nóng)民和狂熱者，都屬于最初級(jí)人口單位。

截圖中的建筑包括主控基地（生產(chǎn)農(nóng)民、母艦，可解鎖其它建筑）、采氣廠（用于采集氣礦）、水晶塔（提高人口單位上線）、傳送門（可生產(chǎn)狂熱者、追蹤者以及其它高級(jí)兵種）。

在開局一段時(shí)間后，單從人口單位上來(lái)看，需要操縱的智能體數(shù)量已然遠(yuǎn)遠(yuǎn)超過(guò)類似Dota2僅需操縱5個(gè)智能體的游戲。而在后期階段，隨著基地的不斷發(fā)展與擴(kuò)大，人口會(huì)隨之大幅度增加，需操縱的人口單位也隨之上升。

在戰(zhàn)略層面上，由于人口單位種類、功能的不同，也會(huì)大幅提高策略的難度。

其次，建筑物之間存在解鎖新功能的關(guān)系，所以建筑物的生成順序也是需要考慮的策略之一。

最后，游戲中的視野是有限制的，派遣兵種開拓視野也要考慮在決策范疇之內(nèi)。

總而言之，觀察空間巨大、動(dòng)作空間連續(xù)、無(wú)窮，并且視野受限等諸多原因促使《星際爭(zhēng)霸2》成為史上最難攻克的游戲！

并且在以往的研究中，重點(diǎn)往往放在對(duì)游戲局部信息的處理上，主要分為微操和宏操。例如在游戲開局前，預(yù)先設(shè)定好雙方兵力的數(shù)量，只需對(duì)這些兵力進(jìn)行把控，便可取得游戲勝利；或者對(duì)建筑序列做預(yù)測(cè)，在游戲進(jìn)程當(dāng)中，判斷當(dāng)前戰(zhàn)局下應(yīng)該建造什么樣的建筑。

而南大團(tuán)隊(duì)此次不僅在《星際爭(zhēng)霸2》游戲本身的難度基礎(chǔ)上對(duì)大規(guī)模強(qiáng)化學(xué)習(xí)技術(shù)做研究，更是將重點(diǎn)著眼于完整的游戲，全面且綜合的考慮到了一局完整游戲過(guò)程中涉及到的所有局部信息以及相應(yīng)的技術(shù)處理問(wèn)題。并且以高勝率打敗了Level7（非作弊最高級(jí)別）的內(nèi)置AI。

用分層強(qiáng)化學(xué)習(xí)，一天時(shí)間單機(jī)訓(xùn)練擊敗《星際爭(zhēng)霸2》內(nèi)置AI

為了提高強(qiáng)化學(xué)習(xí)的能力，像星際爭(zhēng)霸這樣的復(fù)雜戰(zhàn)略游戲已經(jīng)成為許多機(jī)構(gòu)的完美模擬環(huán)境。

《星際爭(zhēng)霸2》為強(qiáng)化學(xué)習(xí)提出了巨大的挑戰(zhàn)。而《星際爭(zhēng)霸2》之所以如此困難，是因?yàn)樗挠^察空間巨大、動(dòng)作空間連續(xù)、無(wú)窮，并且視野受限。

《星際爭(zhēng)霸2》包含10個(gè)難度較高的內(nèi)置AI，它們都是由規(guī)則和腳本編寫的。從1級(jí)到10級(jí)，內(nèi)置AI的能力不斷提高:

南大團(tuán)隊(duì)研究了《星際爭(zhēng)霸2》的分層強(qiáng)化學(xué)習(xí)方法。層次結(jié)構(gòu)涉及兩個(gè)抽象層次。

一個(gè)是從專家的游戲錄像中自動(dòng)提取宏動(dòng)作，將原始復(fù)雜的動(dòng)作空間拆分整合成一個(gè)新的動(dòng)作空間。

另一種是兩層的分層結(jié)構(gòu)，由上層的控制器（controller） 來(lái)選擇下層不同的子策略（sub-policies）。

除此之外，論文中還提供了該結(jié)構(gòu)的分層強(qiáng)化學(xué)習(xí)的訓(xùn)練算法。在64×64的地圖上，使用有限的人口和建筑單位，在挑戰(zhàn)難度級(jí)別為2的內(nèi)置AI中的勝率超過(guò)了90%。

之后再通過(guò)課程學(xué)習(xí)的方法，在最困難的非作弊內(nèi)置AI（level-7）中獲勝的概率超過(guò)了93%。

在SC2LE上的實(shí)驗(yàn)結(jié)果表明，該方法達(dá)到了目前為止最好的結(jié)果。

具體研究方法：分層強(qiáng)化學(xué)習(xí)，自動(dòng)生成宏動(dòng)作，課程學(xué)習(xí)

南大團(tuán)隊(duì)使用了兩層的分層框架，如下圖所示。每隔一個(gè)較長(zhǎng)的時(shí)間間隔，控制器根據(jù)當(dāng)前的全局信息，選擇一種子策略。之后，子策略會(huì)每隔一個(gè)較短的時(shí)間間隔來(lái)選擇一個(gè)宏動(dòng)作。

圖1 總體架構(gòu)

分層結(jié)構(gòu)的優(yōu)點(diǎn)在于：

該分層結(jié)構(gòu)可以讓底層的每個(gè)子策略和高層的控制器擁有不同的狀態(tài)和動(dòng)作空間，能夠?qū)⒃瓉?lái)巨大的狀態(tài)空間進(jìn)行簡(jiǎn)化。

這其實(shí)也不難理解，對(duì)于高層的控制器來(lái)說(shuō)，它只需要關(guān)注少量的全局信息就可以做出選擇。而對(duì)于一個(gè)負(fù)責(zé)戰(zhàn)斗的底層子網(wǎng)絡(luò)來(lái)說(shuō)，它只需要戰(zhàn)場(chǎng)上的相關(guān)信息即可。

宏動(dòng)作的生成

在星際爭(zhēng)霸中，原始動(dòng)作空間是巨大且零碎的，人類玩家總是需要連續(xù)做好幾個(gè)原始動(dòng)作才能達(dá)到一個(gè)簡(jiǎn)單的目的。

例如，如果想要在游戲中建造一個(gè)建筑物，必須先選擇一個(gè)農(nóng)民，然后命令它在特定位置建造建筑物，在完成后讓它回來(lái)繼續(xù)采礦。這些原始動(dòng)作的序列往往是我們?nèi)祟愅婕疫M(jìn)行游戲時(shí)的一些固定序列。

因此，通過(guò)對(duì)專家的游戲錄像數(shù)據(jù)進(jìn)行挖掘，生成一些宏動(dòng)作, 以此生成的宏動(dòng)作空間來(lái)取代原始動(dòng)作空間。 這將極大地提高學(xué)習(xí)效率和運(yùn)行速度。

訓(xùn)練算法

算法1給出了該結(jié)構(gòu)的訓(xùn)練過(guò)程：

算法1 強(qiáng)化學(xué)習(xí)訓(xùn)練算法

課程學(xué)習(xí)

課程學(xué)習(xí)是一種有效的強(qiáng)化學(xué)習(xí)方法。它的思路是將一個(gè)復(fù)雜的任務(wù)分解成若干個(gè)難度遞增的子任務(wù)。智能體先從最簡(jiǎn)單的任務(wù)開始學(xué)習(xí)，隨著它的能力不斷提高，再切換到較為困難的任務(wù)，最終能夠解決原始的復(fù)雜任務(wù)。

星際爭(zhēng)霸2一共有十個(gè)難度，包括非作弊和作弊的。不難想象，若直接讓智能體在較高難度上開始學(xué)習(xí)，那么它只能得到較少的積極反饋，使其學(xué)習(xí)過(guò)程變得十分困難。因此，我們需要設(shè)計(jì)了一個(gè)合適的學(xué)習(xí)序列：首先讓智能體在低難度中進(jìn)行訓(xùn)練，然后再使用這個(gè)預(yù)訓(xùn)練的模型在高難度上繼續(xù)訓(xùn)練。

使用混合作戰(zhàn)模型與規(guī)則，在1~7難度下均取得最佳結(jié)果

設(shè)置

結(jié)構(gòu)設(shè)置如下：控制器每8秒選擇一個(gè)子策略，子策略每1秒執(zhí)行宏動(dòng)作。子策略池中有兩個(gè)子策略。 一個(gè)子策略控制著基地的建筑物和人口單位的生產(chǎn)，稱為基地網(wǎng)絡(luò)（base network）。另一個(gè)子策略負(fù)責(zé)控制戰(zhàn)斗，稱之為戰(zhàn)斗網(wǎng)絡(luò)（battle network）。

1v1模式下SC2的一局完整的游戲過(guò)程如下：首先，兩個(gè)玩家在地圖不同的隨機(jī)點(diǎn)上“誕生”，并開始積攢資源。而后開始建造一些必要的建筑。接著，開始生產(chǎn)作戰(zhàn)部隊(duì)。最后，攻擊并摧毀對(duì)手的所有建筑，如圖2所示。

圖2 《星際爭(zhēng)霸2》截圖

為了簡(jiǎn)單起見，智能體的種族設(shè)置為神族，并將對(duì)手AI的種族設(shè)置為人族。

使用的地圖是SC2LE上的64x64地圖simple64。將每場(chǎng)比賽的最長(zhǎng)時(shí)間設(shè)置為不超過(guò)15分鐘。智能體不開分礦，只使用了神族中的狂熱者和跟蹤者這兩個(gè)初級(jí)兵種。

戰(zhàn)斗網(wǎng)絡(luò)可以有三種不同的策略模型。

作戰(zhàn)規(guī)則（combat rule）。該規(guī)則是最簡(jiǎn)單的戰(zhàn)斗策略，其中敵人的位置由先驗(yàn)知識(shí)自動(dòng)選擇。

作戰(zhàn)規(guī)則的動(dòng)作只有一個(gè)：就是攻擊。由于攻擊的結(jié)果完全取決于基地的建設(shè)和人口單位的生產(chǎn)。這種設(shè)置就促進(jìn)了在基地建設(shè)和人口單位生產(chǎn)方面的訓(xùn)練。

如下GIF，演示了采用作戰(zhàn)規(guī)則策略模型的效果：

視頻鏈接：

https://v.qq.com/x/page/q0716bthkjz.html

作戰(zhàn)網(wǎng)絡(luò)（combat network）。雖然作戰(zhàn)規(guī)則簡(jiǎn)單有效，但是在更大、更復(fù)雜的地圖上可能會(huì)失敗。因此采用更為智能的方法，就是作戰(zhàn)網(wǎng)絡(luò)。作戰(zhàn)網(wǎng)絡(luò)被構(gòu)造為卷積神經(jīng)網(wǎng)絡(luò)，接收小地圖和屏幕中的“特征地圖”（feature-map）。如圖3所示。作戰(zhàn)網(wǎng)絡(luò)的輸出包括3個(gè)動(dòng)作和1個(gè)位置矢量。3個(gè)動(dòng)作分別是：全體進(jìn)攻某個(gè)位置、全軍撤退或者不做任何動(dòng)作。

圖3 作戰(zhàn)網(wǎng)絡(luò)結(jié)構(gòu)

混合模型（mixture module）。研究者發(fā)現(xiàn)，當(dāng)把作戰(zhàn)規(guī)則和作戰(zhàn)網(wǎng)絡(luò)進(jìn)行結(jié)合以后，會(huì)獲得比兩者更好的結(jié)果。當(dāng)在作戰(zhàn)網(wǎng)絡(luò)的位置向量中預(yù)測(cè)到某一值時(shí)，軍隊(duì)的攻擊位置將變?yōu)橛上闰?yàn)知識(shí)計(jì)算出來(lái)的位置。這就是混合模型策略。

訓(xùn)練方法比較

在訓(xùn)練初期，智能體會(huì)構(gòu)建許多冗余的建筑物，而在訓(xùn)練后，智能體將更有效地利用建筑資源，并且控制每種人口單位的生產(chǎn)數(shù)量比例。

南大的研究團(tuán)隊(duì)還研究了各種的訓(xùn)練方法對(duì)學(xué)習(xí)效果的影響性。

圖a到圖d分別演示了課程學(xué)習(xí)的有效性（圖a），模塊化訓(xùn)練的作用（圖b），以及使用戰(zhàn)斗規(guī)則（圖c）和戰(zhàn)斗網(wǎng)絡(luò)（圖d）時(shí)同時(shí)更新（simultaneous）與交替更新（alternative）的區(qū)別。

圖4 訓(xùn)練過(guò)程中的勝率曲線

作戰(zhàn)模型比較

在難度級(jí)別1-10的條件下做了評(píng)估測(cè)試。在每個(gè)難度條件下進(jìn)行了100場(chǎng)比賽。從表1中可以看到，在難度1-7的條件下，智能體的表現(xiàn)非常良好。在難度8、難度9和難度10條件下，由于智能體沒有在這些難度下進(jìn)行訓(xùn)練，并且內(nèi)置bot具有不同的作弊技巧，所以它們對(duì)智能體的泛化性要求很高。然而，可以看出智能體在與他們的戰(zhàn)斗中仍然有很好的表現(xiàn)。

表1 評(píng)估結(jié)果

作戰(zhàn)網(wǎng)絡(luò)的表現(xiàn)似乎并不如作戰(zhàn)規(guī)則，這是由于作戰(zhàn)網(wǎng)絡(luò)在對(duì)局中產(chǎn)生了過(guò)多的平局。如果把平局的表現(xiàn)也考慮進(jìn)去的話，那么作戰(zhàn)網(wǎng)絡(luò)的性能也具備可比性。

值得一提的是，通過(guò)表1，可以發(fā)現(xiàn)作戰(zhàn)網(wǎng)絡(luò)和作戰(zhàn)規(guī)則的混合模型在1-7難度級(jí)別中取得了最佳的結(jié)果。

為了驗(yàn)證訓(xùn)練出的智能體的泛化性，研究團(tuán)隊(duì)還測(cè)試了智能體對(duì)抗其他兩個(gè)種族的勝率表現(xiàn)。如表2所示：

表2 與其他兩個(gè)種族對(duì)抗的測(cè)試結(jié)果

設(shè)置比較

研究團(tuán)隊(duì)還實(shí)驗(yàn)了各種不同的設(shè)置對(duì)于訓(xùn)練結(jié)果的影響。

結(jié)果如圖5所示，顯示出了分層結(jié)構(gòu)、獎(jiǎng)勵(lì)設(shè)置以及超參數(shù)對(duì)結(jié)果的重要影響。

圖5 設(shè)置的比較

為大規(guī)模強(qiáng)化學(xué)習(xí)現(xiàn)實(shí)應(yīng)用提供啟示

在這篇論文中，南京大學(xué)團(tuán)隊(duì)研究了用于完整長(zhǎng)度《星際爭(zhēng)霸2》游戲的分層強(qiáng)化學(xué)習(xí)方法。

該結(jié)構(gòu)采用兩級(jí)抽象層次結(jié)構(gòu)。 經(jīng)過(guò)適當(dāng)?shù)挠?xùn)練，本文的結(jié)構(gòu)在當(dāng)前具有挑戰(zhàn)性的平臺(tái)SC2LE上取得了最佳的結(jié)果。

不過(guò)，雖然實(shí)驗(yàn)結(jié)果非常理想，但這項(xiàng)工作仍然存在一些不足。 例如，目前測(cè)試的64x64地圖很小，只使用初級(jí)的兩個(gè)兵種。南大團(tuán)隊(duì)表示，他們將來(lái)會(huì)在更大的地圖上探索、學(xué)習(xí)，并嘗試使用更多的武器和兵種來(lái)組織戰(zhàn)術(shù)。

希望這個(gè)框架可以為今后強(qiáng)化學(xué)習(xí)在現(xiàn)實(shí)世界問(wèn)題上的研究提供一些啟示。