基于深度強化學習實時戰(zhàn)略卡牌游戲?qū)?zhàn)設(shè)計

杜智華，賴振清

(深圳大學計算機與軟件學院，廣東 深圳 518000)

1 引言

目前深度強化學習已經(jīng)成為機器學習里一個非常熱門的研究方向，在2019年的人工智能頂級會議ICLR上，強化學習是最熱門的關(guān)鍵詞。強化學習的應(yīng)用非常廣泛，在機器人[1]、翻譯[2]、智能交通[3]、廣告推薦[4]、計算機視覺[5]、自動駕駛[6]等領(lǐng)域都有非常具體的應(yīng)用。而在這些領(lǐng)域中，強化學習在游戲中的應(yīng)用最引人注目且成功，從DeepMind公司使用DQN玩Atari游戲，到開發(fā)AlphaGo擊敗圍棋世界冠軍，還有OpenAI組織使用強化學習在MOBA游戲Dota 2中擊敗世界冠軍隊伍等，強化學習一直與游戲相輔相成，互相促進。游戲多樣的環(huán)境為強化學習提供了很好的訓練材料，而強化學習在游戲中的成功應(yīng)用則給游戲注入了新的活力和更多樣的玩法。盡管強化學習在游戲中的應(yīng)用非常多，在棋類游戲、視頻類游戲、MOBA對戰(zhàn)游戲中都有非常多的應(yīng)用，但在即時策略的卡牌類游戲的應(yīng)用卻很少，這類游戲狀態(tài)空間大，策略具有多樣性而且信息并不完全。《皇室戰(zhàn)爭》就是一款即時策略卡牌游戲，由游戲公司Supercell在2016年推出，發(fā)行之后就霸占各個排行榜。游戲開始前，玩家選取8張卡牌進入游戲，在限定時間內(nèi)通過卡牌拆毀對方防御塔并保護己方防御塔來贏得游戲勝利。由于進入游戲時無法獲得對方卡牌的信息，所以這是一款不完全信息的游戲博弈，另外由于放置卡的位置非常多，它還具有狀態(tài)空間巨大的特點，根據(jù)戰(zhàn)場局勢不同出卡的策略也有很大差異，所以還具有策略多樣性的特點。所以將深度強化學習方法應(yīng)用到《皇室戰(zhàn)爭》中是個不小的挑戰(zhàn)。為解決這些問題，程序在深度強化學習方法的基礎(chǔ)上，使用了簡化狀態(tài)空間的方法，使得程序的實現(xiàn)成為可能。

最早引起學術(shù)界深度強化學習熱度的是2013年的論文《Playing Atari with Deep Reinforcement Learning》[7]，將深度強化學習應(yīng)用到Atari游戲中，效果非常顯著，在實驗的大部分游戲中，超過了之前的方法。對于將深度學習、強化學習應(yīng)用到游戲中，最知名、引起廣泛大眾熱度的則是DeeepMind公司開發(fā)的AlphaGo[8][9]，采用了深度學習方法，在2016年擊敗世界冠軍李世石。其之后的版本AlphaGo Zero則采用的是強化學習，對戰(zhàn)舊版AlphaGo的戰(zhàn)績?yōu)椋?00：0。圍棋屬于完全可觀測游戲，雙方能獲得全部的信息，這與《皇室戰(zhàn)爭》不同。對于深度強化學習在部分可觀測游戲中的應(yīng)用，有OpenAI開發(fā)的用于Dota 2對戰(zhàn)的程序，曾擊敗世界冠軍隊伍OG，還有知名Atari第一射擊游戲《毀滅戰(zhàn)士》，在VIZDOOM平臺上舉行的2016年競賽中，田淵棟和吳育昕的 F1 團隊獲得限制賽道冠軍[10]，2017年競賽中，Arnold獲得了完整版賽道的冠軍[11]，marvin獲得了限制版賽道的冠軍，它們都使用了深度強化學習。

2 相關(guān)技術(shù)介紹

本節(jié)先從程序的核心算法Deep Q-learning(DQN)開始介紹，然后介紹程序中用于獲得游戲狀態(tài)的YOLO V3對象檢測算法，最后介紹程序中用來識別手中卡牌的CNN圖像識別技術(shù)。

2.1 DQN算法

DQN算法屬于強化學習算法中的一種，所以在介紹DQN算法之前，先來簡單介紹下強化學習。強化學習是智能體通過試錯的方式進行學習，通過與環(huán)境交互獲得獎勵來指導行為，最終目的是最大化期望累積獎勵。強化學習的主要特征有：1反饋具有延遲性，不是瞬時獲得；2沒有監(jiān)督，只有獎勵；3時間對于數(shù)據(jù)影響很大；4 智能體的動作會影響之后獲得的數(shù)據(jù)。

強化學習的四個主要要素：動作、狀態(tài)、策略、獎勵，根據(jù)這四個要素，強化學習可以解釋為在當前狀態(tài)下，應(yīng)用策略采取動作來獲得當前獎勵，并根據(jù)得到的反饋，更新策略，不斷進行這些步驟從而使長期累積獎勵最大化的過程。DQN算法屬于強化學習算法的一種，為了得到一個策略使得長期累加獎勵最大化，需要評估一個策略的期望回報，因此需要定義值函數(shù)，而對于狀態(tài)非常龐大的環(huán)境，精確的值函數(shù)定義并不現(xiàn)實，因此DQN采用了神經(jīng)網(wǎng)絡(luò)的方法來近似值函數(shù)，這就是Q網(wǎng)絡(luò)。另外，為了更好地訓練網(wǎng)絡(luò)，DQN算法采用了經(jīng)驗回放技術(shù)和e-greedy策略。

2.2 YOLO V3對象檢測算法

對象檢測就是在圖像中，識別出物體的種類，以及該物體的坐標。YOLO(You Only Look Once)是一種基于深度學習的目標檢測算法，目前已經(jīng)發(fā)展到Y(jié)OLO v3[16，17]，YOLO v3 是目前為止性能最好的YOLO系列的目標檢測模型。YOLO的思想是直接對輸入圖像中的目標位置和目標 類別進行回歸預(yù)測，這使得YOLO具有更快的檢測速 度。在YOLOv3中，直接對圖像進行推斷，便能獲得物體的位置、類別以及物體屬于某種類別的概率。YOLO檢測網(wǎng)絡(luò)包含2個全連接層和24個卷積層，其中全連接層，也就是輸出層，用來預(yù)測圖像中物體的位置和物體所屬類別的概率值，卷積層則用來提取圖像的特征。YOLO將輸入圖像分成S × S個格子，每個格子負責檢測在其中的物體，輸出多個物體屬于哪種類別的概率以及物體中心點的坐標，然后選擇概率最高的那個類別，所以一個格子只能識別出一個物體，即使其中有多個物體，這也是對于密集物體的檢測，YOLO精確度不夠高的原因。在檢測時，YOLO訓練模型只支持分辨率為448 × 448的圖像，這個分辨率與YOLO的訓練圖像一致。

2.3 CNN圖像識別技術(shù)

卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Networks，CNN)，在深度學習領(lǐng)域占據(jù)很重要的位置，對深度學習的發(fā)展起到很大的作用，主要用來進行圖像處理。

CNN中有三個基本概念：池化、共享權(quán)值以及局部感受野。

1)池化。為了簡化卷積網(wǎng)絡(luò)計算的復雜度，采用類似于圖像壓縮的方法，對圖像進行卷積，然后進行下采樣，從而減小圖像大小。

2)共享權(quán)值。在CNN的卷積層中，多個神經(jīng)元共享同一個權(quán)值，從而減少訓練的參數(shù)量。

3)局部感受野。這一步同樣是為了減少參數(shù)訓練量，采用的方式是將每一個隱藏節(jié)點只連接到圖像的某個局部區(qū)域，而不是圖像中的每個像素點。

程序?qū)D像進行分類主要使用的CNN網(wǎng)絡(luò)為LeNet。LeNet-5[15]是Yann LeCun等人提出的卷積神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，是最早出現(xiàn)的卷積神經(jīng)網(wǎng)絡(luò)之一。LetNet-5雖然比較小，但是包含了深度學習的基本模塊：池化層、卷積層和全連接層。LeNet-5包含7層網(wǎng)絡(luò)，包括三個卷積層，一個全連接層以及兩個池化層和一個輸入層，輸入數(shù)據(jù)為32 × 32像素的圖片。

3 基于強化學習動態(tài)對戰(zhàn)策略介紹

3.1 游戲背景介紹

《皇室戰(zhàn)爭》是一款曾經(jīng)風靡全球的實時策略卡牌手游，游戲過程中，兩位玩家通過手中的卡牌，在規(guī)定的時間內(nèi)摧毀比對方更多的防御塔來獲得勝利。雙方各有兩座公主塔，一座國王塔，任何一方摧毀了國王塔都會直接獲勝，相當于摧毀了三座塔。該游戲運行在電腦安裝的逍遙模擬器中。

游戲開始前，玩家選擇8張卡牌進入游戲。游戲開始后的對戰(zhàn)界面如圖1。圖1最大的黑色矩形框圈出來的就是作戰(zhàn)區(qū)域，所有卡牌釋放不會超過那個范圍，雙方有兩座公主塔，一座國王塔。每人手上有四張卡牌，一開始4張卡牌出現(xiàn)的順序是隨機的，當你用完一張卡后，就像棧一樣，那張卡會壓到最底下，在其余七張卡出現(xiàn)過后再次出現(xiàn)。不同的卡有不同的特性，卡牌之間有一定的克制關(guān)系，利用這種關(guān)系來獲得對戰(zhàn)的優(yōu)勢。場上的作戰(zhàn)隊伍如圖1圈出來的作戰(zhàn)區(qū)域內(nèi)的兩個矩形框。最下方的是圣水數(shù)量，它會隨著時間而增加，每2.8秒增加一滴，加時賽速度翻倍，最多能保存10滴，使用卡牌則會消耗卡牌對應(yīng)的圣水。右上角則是剩余時間，如果在3分鐘內(nèi)沒有決出勝負，則進入加時賽，加時賽任意一方推掉一座塔即獲勝。

圖1 游戲開始前選擇卡牌界面

3.2 基于強化習動態(tài)對戰(zhàn)策略框架

程序?qū)?zhàn)策略是通過強化學習網(wǎng)絡(luò)來動態(tài)實施對戰(zhàn)策略，并通過python調(diào)用win api操縱電腦進行游戲。實時采集對戰(zhàn)訓練營動作，經(jīng)過圖像識別和對象檢測技術(shù)完成實時狀態(tài)識別和位置識別，然后分析對戰(zhàn)訓練營狀態(tài)，并轉(zhuǎn)換為對戰(zhàn)策略的動態(tài)控制數(shù)據(jù)，從而控制游戲人物做出與玩家運動相應(yīng)的動作，并根據(jù)游戲規(guī)則判斷游戲是否結(jié)束，更新游戲狀態(tài)，直到游戲結(jié)束。具體算法1如下所示。

算法1 強化學習的動態(tài)對戰(zhàn)策略

程序流程圖如圖2所示，其中程序通過YOLO V3對象檢測技術(shù)以及CNN圖像識別技術(shù)實時獲取游戲狀態(tài)(圖中①截圖)。獲取游戲狀態(tài)具體描述如圖3所示。

圖2 程序流程圖

圖3 實時獲取游戲狀態(tài)的策略

3.2.1 DQN網(wǎng)絡(luò)構(gòu)成及更新

DQN算法使用神經(jīng)網(wǎng)絡(luò)來近似值函數(shù)，該神經(jīng)網(wǎng)絡(luò)就稱為Q網(wǎng)絡(luò)。構(gòu)成：Q網(wǎng)絡(luò)由兩個隱藏層，三個卷積層以及兩個完全連接層構(gòu)成，輸入層為64 x 64 x 4。

更新：每次訓練從經(jīng)驗回放集中抽取m個樣本{Sj，Aj，Rj，S’j，game＿overj}，j=1，2，…，m，計算當前網(wǎng)絡(luò)Q值Yj。如式(1)所示，其中γ為衰減因子，程序中設(shè)定為0.9，w為網(wǎng)絡(luò)參數(shù)

(1)

求得當前網(wǎng)絡(luò)Q值后，使用均方差損失函數(shù)，通過神經(jīng)網(wǎng)絡(luò)的梯度反向傳播來更新Q網(wǎng)絡(luò)的所有參數(shù)w。

3.2.2 出卡選擇

首先需要用到3.3節(jié)的對象檢測技術(shù)和3.4節(jié)的圖像識別技術(shù)，來獲得場上隊伍最多的區(qū)域和手中的卡牌是什么。程序出卡選擇總共有9種，即出8種卡牌各算一種動作，還有一種動作是不出卡。在圣水數(shù)量沒有4時，采取的動作是不出卡。圣水數(shù)量在4以上時，在當前時刻t，狀態(tài)St的情況下，獲得出手上四張卡以及不出卡對應(yīng)的網(wǎng)絡(luò)值，假設(shè)網(wǎng)絡(luò)參數(shù)為ω，所有動作為a，網(wǎng)絡(luò)值函數(shù)為Q，求得這5種選擇中Q值最高的選擇a′，如式(2)所示

a′=argmax(Q(St，a；w))

(2)

然后用e-greedy貪婪法選擇動作a′，還是隨機的5種動作。e為探索率，隨訓練場次增加而減小，初始設(shè)置為0.5，之后到1000場遞減為0.01。程序產(chǎn)生一個0到1之間的隨機數(shù)k，如果k小于等于1-e，選擇動作a′，如果k> 1-e，選擇隨機的5種動作。

出某張卡確定后，程序需要確定出卡的位置。在獲得游戲狀態(tài)后，程序根據(jù)戰(zhàn)斗隊伍最多的區(qū)域，將作戰(zhàn)區(qū)域劃分成30x18塊，求出每塊區(qū)域的英雄數(shù)，將卡投放到最多英雄的格子里。

3.2.3 計算獎勵

動作a帶來的游戲獎勵Rstep劃分成四個部分：摧毀塔獲得的獎勵Reto、被摧毀塔獲得的獎勵Rmto，擊殺敵方隊伍獲得的獎勵Rtroop，出卡的獎勵Rcard，關(guān)系如式(3)所示

Rstep=Reto+Rmto+Rtroop+Rcard

(3)

摧毀塔獲得的獎勵Reto，由執(zhí)行動作a后摧毀的塔減去執(zhí)行動作a前摧毀的塔獲得，摧毀一座公主塔的獎勵為10，摧毀一座國王塔的獎勵為20。Reto和摧毀公主塔數(shù)Neprincess和摧毀國王塔數(shù)Neking的關(guān)系如式(4)所示

Reto=Neprincess× 10+Neking× 20

(4)

被摧毀塔獲得的獎勵R被摧毀塔，由執(zhí)行動作a后被摧毀的塔減去執(zhí)行動作a前被摧毀的塔獲得。被摧毀一座公主塔的獎勵為-10，被摧毀一座國王塔的獎勵為-20。所以Rmto和被摧毀公主塔數(shù)Neprincess和被摧毀國王塔數(shù)Nmking的關(guān)系如式(5)所示

Rmto=-10 ×Nmprincess-20 ×Nmking

(5)

擊殺敵方隊伍獲得的獎勵，由執(zhí)行動作a前敵方場上的隊伍，減去執(zhí)行動作a后敵方場上共有的隊伍獲得。而摧毀一個敵方英雄的獎勵由該卡消耗的圣水決定，比如飛龍寶寶該卡消耗的圣水為4，則摧毀該英雄獲得的獎勵為4。假設(shè)被摧毀的敵方英雄為1到T，英雄消耗的圣水為N1到NT，則擊殺敵方隊伍獲得的獎勵Rtroop如式(6)所示

(6)

出卡獲得的獎勵，由該卡消耗的圣水決定，出一張卡獲得的獎勵為該卡消耗的圣水的負值，假設(shè)某張卡為k，其消耗的圣水數(shù)量為Nk，則出卡k獲得的獎勵如式(7)所示

Rcard=-Nk

(7)

以上均為一步動作的獎勵，總獎勵為每一步動作獎勵的累加。在訓練的初期，由于出卡帶來的獎勵必為負值，而摧毀敵方隊伍和防御塔則較為困難，為了減少程序因為出卡而獲得更低的獎勵導致的消極行為，摧毀敵方防御塔和摧毀敵方隊伍獲得的獎勵都乘以系數(shù)1.5，這個系數(shù)會在訓練過程中逐漸減少，到200場時為1。

3.2.4 判斷游戲是否結(jié)束及輸贏

程序使用3.4節(jié)中圖像識別技術(shù)獲得初始時間，以及場上防御塔摧毀情況。獲得初始時間，是為了避免網(wǎng)絡(luò)延遲帶來的時間誤差，之后由程序自主計時。

判斷游戲結(jié)束總共分為四部分，一部分是常規(guī)時間3分鐘內(nèi)，程序獲得狀態(tài)時，判斷場上雙方國王塔的情況，任意一方國王塔被摧毀，游戲結(jié)束。第二部分時常規(guī)時間剛好結(jié)束時，任意一方場上的塔數(shù)更多，游戲結(jié)束。第三部分，若三分鐘內(nèi)游戲未結(jié)束，任意一方防御塔減少一座，游戲結(jié)束。第四部分，加時賽的第三分鐘過去，游戲結(jié)束。

判斷輸贏，在判斷游戲結(jié)束后返回輸贏結(jié)果。如果常規(guī)時間內(nèi)游戲結(jié)束了，則誰的國王塔被摧毀，誰失敗。如果常規(guī)時間結(jié)束時游戲結(jié)束了，則根據(jù)雙方的塔數(shù)判斷輸贏，塔數(shù)少的一方失敗。如果加時賽時間內(nèi)結(jié)束，塔數(shù)少的一方失敗。如果加時賽時間過去了，游戲結(jié)束，則存在三種情況，根據(jù)最后一刻的狀態(tài)來判斷，如果雙方塔數(shù)相同，則為平局，如果有一方塔數(shù)更少，則失敗。

3.3 對象檢測

本程序采用YOLO V3對象檢測識別場上英雄的位置和坐標。程序通過python截圖獲得原始圖像，使用精靈標注助手標注圖片，制作并劃分VOC數(shù)據(jù)集，進行訓練。

獲得原始圖片：這步使用python調(diào)用win32 api進行游戲截圖，每隔一秒截圖，多局游戲，共有1050張截圖，每張圖片的名稱格式為：00xxxx.jpg，6位數(shù)字，按順序編號。為了適應(yīng)VOC數(shù)據(jù)集的要求，對圖片長寬進行0.4 x 0.4的壓縮處理，獲得的原始圖片如圖5所示。

圖4 訓練集的原始圖像

圖5 YOLO V3測試識別圖片

YOLO V3則直接通過regression一次既產(chǎn)生坐標，又產(chǎn)生每種類別的概率。

訓練：訓練模型，程序使用的是阿里云GPU計算型 gn4系列NVIDIA M40 12GB的gpu，訓練了大概18個小時。使用訓練出來的模型進行測試的結(jié)果如圖6所示，三個英雄都識別正確，速度只需要兩三毫秒。

3.4 圖像識別

本程序主要使用CNN網(wǎng)絡(luò)結(jié)構(gòu)LetNet來識別游戲中的時間，防御塔摧毀情況，手中的卡牌以及圣水數(shù)量等四種內(nèi)容。這四種內(nèi)容使用的網(wǎng)絡(luò)結(jié)構(gòu)一樣的，訓練次數(shù)均為1800次，只有原始數(shù)據(jù)和種類有所不同。LetNet網(wǎng)絡(luò)使用keras實現(xiàn)，包括了三個模塊：卷積層，池化層，全連接層。網(wǎng)絡(luò)包含14層，其中輸入層為32×32×3。

識別防御塔情況：識別防御塔情況，對于整個程序來說，是比較重要的工作，因為勝負判斷就是靠防御塔摧毀情況來判斷的，而且防御塔摧毀的獎勵在設(shè)定的獎勵計算中也占很大的比重。原始圖像如圖6所示，總共有5張，分別是敵方國王塔、敵方公主塔、防御塔被摧毀、己方國王塔和己方公主塔。公主塔和被摧毀的塔只算一次，是因為對于同一方，公主塔的形狀是一樣的，所有塔被摧毀后也是一樣的。

圖6 用來訓練識別防御塔情況的原始圖像

識別手中卡牌：識別手中卡牌，在游戲中同樣有重要作用，因為除開獲得游戲狀態(tài)的各種工作，程序的核心就是出手中的卡牌，所以能準確識別出手中的卡牌很重要。需要識別的卡牌總共有8張，分別是飛龍寶寶，煉獄飛龍，礦工，獵人，公主，皇家幽靈，騎士，黑暗王子。提供的原始圖片如圖7所示。

圖7 訓練識別手中卡牌的原始圖像

識別圣水數(shù)量：識別圣水數(shù)量，是為了判斷是否有足夠的圣水出某張卡。提供的原始圖片如圖8所示。

圖8 訓練識別圣水數(shù)量的原始圖像

4 實驗結(jié)果與分析

《皇室戰(zhàn)爭》中訓練營總共有14種，訓練營難度會根據(jù)玩家的杯數(shù)逐漸提高，其中4000杯內(nèi)的玩家，進入前十二種訓練營，4000杯到4300杯的玩家進入訓練營格拉維，4300杯以上的訓練營齊達難度最高，擁有無限圣水和滿級傳奇卡。本程序?qū)?zhàn)的是訓練營格拉維，難度僅次于最強訓練營。《皇室戰(zhàn)爭》中，卡牌等級和國王塔等級對對戰(zhàn)都有很大影響，等級越高越強，程序使用的卡牌等級和訓練營相比基本差兩級，國王塔則差三級，所以程序?qū)τ柧殸I開始就處于很大劣勢。

4.1 程序訓練情況

本程序記錄在日志文件中的對局共有2300場對局，如圖9是每百局程序的勝場，x坐標對應(yīng)的是坐標值100的場次，y坐標為勝場數(shù)，可以看到程序從一開始0勝場到500場開始出現(xiàn)勝場，然后勝場數(shù)一直提升，到1500場后，勝場基本穩(wěn)定，每百場18勝場到19勝場之間。如圖10則是每百局程序的平均獎勵，x坐標對應(yīng)的是坐標值 100的場次，y坐標為獎勵數(shù)，從-42.2到后來基本穩(wěn)定在-10多。單局的獎勵為全場摧毀對方防御塔以及作戰(zhàn)部隊的獎勵加上被摧毀防御塔及出卡的負獎勵，獎勵越高，說明程序在對戰(zhàn)中表現(xiàn)越好。由圖10可以看到獎勵逐漸提高，到穩(wěn)定在-10左右，這個曲線和勝場曲線相似，對局中的表現(xiàn)會體現(xiàn)在游戲的輸贏上，而最終獎勵依然為負數(shù)，說明程序的表現(xiàn)還是低于訓練營。

圖9 程序每百局勝場數(shù)

圖10 程序每百局平均獎勵

4.2 與普通玩家的對比

作為程序訓練情況的對比，一共安排了兩名測試人員進行了測試。測試人員1是一名游戲勝場648場，最高獎杯數(shù)為4711的玩家，測試人員2則是游戲勝場475，最高獎杯數(shù)為3973的玩家。如表2，是測試人員各自用同樣的卡組與同樣的訓練營對戰(zhàn)了100局之后的戰(zhàn)績與程序2200場——2300場戰(zhàn)績的對比。可以看到程序最后的戰(zhàn)績比測試人員都更好，勝場比測試人員1高38%，比測試人員2高100%。

表2 普通玩家戰(zhàn)績與程序戰(zhàn)績對比

5 總結(jié)

本程序使用強化學習算法，使程序在多次游戲中不斷完善自己的出卡策略，提高游戲水平。使用CNN來識別卡牌、防御塔以及時間，通過YOLO V3來獲得場上英雄坐標，從而獲得游戲狀態(tài)，通過投放卡牌到最多卡牌的區(qū)域來減少動作空間。從結(jié)果來看，由于卡牌等級被壓制，后期對戰(zhàn)訓練營的戰(zhàn)績勝率在18%左右，超過了4000杯測試玩家的水平。后續(xù)為進一步提高程序勝率，需要進一步識別所有卡牌，并進行玩家間的排位，從而達到最高的段位，并能夠進行多種卡牌的組合，從而獲得多套強勢卡組。