陳 鵬,王子磊

(中國(guó)科學(xué)技術(shù)大學(xué) 自動(dòng)化系,合肥 230027)

0 概述

機(jī)器博弈[1]又稱為計(jì)算機(jī)博弈,主要研究如何使計(jì)算機(jī)模擬人類進(jìn)行游戲?qū)?是人工智能領(lǐng)域最具挑戰(zhàn)性的研究方向之一。繼以圍棋[2-4]、五子棋[5]、亞馬遜棋[6]、兵棋[7]等棋類游戲?yàn)榇淼男蜇灢┺膯栴}得以解決后,以實(shí)時(shí)策略(Real-Time Strategy,RTS)游戲[8]為代表的同步博弈問題成為機(jī)器博弈領(lǐng)域的研究熱點(diǎn),如星際爭(zhēng)霸(StarCarft)[9-11]、Dota 2、王者榮耀[12]等。通常,RTS游戲職業(yè)玩家或RTS AI 程序(Bot)的操作可劃分為宏觀操作和微觀操作兩部分[8],分別稱為宏操、微操。宏操側(cè)重于對(duì)整個(gè)戰(zhàn)局的調(diào)控,用于保證玩家占有經(jīng)濟(jì)和科技優(yōu)勢(shì);微操側(cè)重于遭遇戰(zhàn)中作戰(zhàn)單元的控制,用于保證玩家占有軍事優(yōu)勢(shì)?？梢?RTS游戲微操是RTS游戲AI研究的基礎(chǔ)問題,也是RTS AI Bot的核心模塊。

相較于棋類游戲中參與者輪流行動(dòng),RTS游戲微操要求參與者同時(shí)采取行動(dòng),實(shí)時(shí)性更強(qiáng),且雙方作戰(zhàn)單元數(shù)目不定,導(dǎo)致動(dòng)作空間規(guī)模隨作戰(zhàn)單元數(shù)量的增加而呈指數(shù)級(jí)增長(zhǎng)。目前,常見的解決思路分為搜索方法和強(qiáng)化學(xué)習(xí)方法兩種,兩者相互獨(dú)立。但在面對(duì)大規(guī)模戰(zhàn)斗場(chǎng)景時(shí),搜索方法存在搜索速率下降和搜索空間有限的問題,難以保證求解的最優(yōu)性,而強(qiáng)化學(xué)習(xí)[13-15]方法存在學(xué)習(xí)困難的問題,且訓(xùn)練好的強(qiáng)化學(xué)習(xí)模型往往局限于固定的戰(zhàn)斗場(chǎng)景。因此,現(xiàn)有方法難以解決大規(guī)模戰(zhàn)斗場(chǎng)景下的RTS游戲微操問題。

采用深度學(xué)習(xí)與搜索相結(jié)合的思路,可以實(shí)現(xiàn)學(xué)習(xí)模型對(duì)搜索方法的合理指導(dǎo),使得在實(shí)時(shí)性約束下,盡可能地搜索大概率存在最優(yōu)解的動(dòng)作空間,如AlphaGo[3]、AlphaGoZero[4]在圍棋上取得的巨大成功,為解決RTS微操問題提供可能。考慮到采用強(qiáng)化學(xué)習(xí)方式,難以訓(xùn)練適用于多變戰(zhàn)斗場(chǎng)景的學(xué)習(xí)模型,參考AlphaGo[3]的思路,采用監(jiān)督學(xué)習(xí)方式訓(xùn)練深度學(xué)習(xí)模型。基于此,本文提出融合深度學(xué)習(xí)與搜索的RTS游戲微操方法。根據(jù)作戰(zhàn)狀態(tài)表達(dá)方法,將游戲狀態(tài)映射為多通道特征圖,給出一種基于卷積神經(jīng)網(wǎng)絡(luò)的聯(lián)合策略網(wǎng)絡(luò)(Joint Policy Network,JPN),不同于大多數(shù)模型僅能學(xué)習(xí)游戲狀態(tài)至個(gè)體動(dòng)作映射的策略模型,JPN可以實(shí)現(xiàn)多智能體聯(lián)合動(dòng)作的端到端學(xué)習(xí),并將JPN與組合貪婪搜索(PGS)[16]、組合在線演化(POE)[17]、自適應(yīng)分層策略選擇(SSS+)[18]相結(jié)合,提出了3種改進(jìn)方法,分別為PGS w/JPN、POE w/JPN、SSS+w/JPN。

1 相關(guān)工作

現(xiàn)有的RTS游戲微操方法分為搜索方法和強(qiáng)化學(xué)習(xí)方法兩類,搜索方法是在有限時(shí)間內(nèi)進(jìn)行在線搜索,由搜索到的局部最優(yōu)解決定最終行動(dòng);強(qiáng)化學(xué)習(xí)是通過環(huán)境交互完成模型學(xué)習(xí),使用時(shí)由模型決定最終行動(dòng)。

搜索方法應(yīng)用于RTS游戲微操始于Churchill等人提出的ABCD[19]和UCTCD[16],這兩種算法由廣泛應(yīng)用于棋類游戲的Alpha-Beta搜索和UCT算法演變而來。后來的研究工作主要圍繞如何在搜索方法中引入精煉機(jī)制,包括動(dòng)作精煉和狀態(tài)精煉兩類,即通過減小動(dòng)作空間或狀態(tài)空間的規(guī)模來加快搜索效率。動(dòng)作精煉一般將原始動(dòng)作替換為固定規(guī)則(Script)動(dòng)作,如組合貪婪搜索(PGS)[16]、基于Script的UCT[20]、組合在線演化(POE)[17]等;狀態(tài)精煉則是合并相似狀態(tài)的作戰(zhàn)單元,如基于空間聚類的UCT[20]、基于類型系統(tǒng)的分層策略選擇(SSS)[18]、自適應(yīng)分層策略選擇(SSS+)[18]等。然而,動(dòng)作空間規(guī)模隨作戰(zhàn)單元數(shù)量的增加而呈指數(shù)級(jí)增長(zhǎng),當(dāng)作戰(zhàn)單元數(shù)量較多時(shí),實(shí)時(shí)性約束(一般為42 ms)下的精煉機(jī)制也只能搜索有限的動(dòng)作空間,所求解的最優(yōu)性仍不足。

強(qiáng)化學(xué)習(xí)[13-15]方法通常將RTS游戲微操問題建模為多智能體馬爾科夫決策過程,其目標(biāo)是讓多智能體學(xué)會(huì)合作式行動(dòng)。主流方法是將多智能體強(qiáng)化學(xué)習(xí)與深度學(xué)習(xí)相結(jié)合,研究方向包括學(xué)習(xí)架構(gòu)、學(xué)習(xí)策略及多智能體溝通機(jī)制。學(xué)習(xí)架構(gòu)涉及多智能體強(qiáng)化學(xué)習(xí)框架的設(shè)計(jì),主要圍繞傳統(tǒng)強(qiáng)化學(xué)習(xí)中的行動(dòng)家-評(píng)判家框架,如相互獨(dú)立的行動(dòng)家-評(píng)判家[21-23]框架、分布式行動(dòng)家-集中式評(píng)論家[24]框架等。學(xué)習(xí)策略主要用于提升強(qiáng)化學(xué)習(xí)的學(xué)習(xí)效率,如文獻(xiàn)[22]采用課程學(xué)習(xí)逐步將強(qiáng)化學(xué)習(xí)模型由簡(jiǎn)單場(chǎng)景遷移至復(fù)雜場(chǎng)景,文獻(xiàn)[23]利用職業(yè)玩家先驗(yàn)知識(shí)預(yù)訓(xùn)練強(qiáng)化學(xué)習(xí)模型。多智能體溝通機(jī)制涉及多智能體信息傳遞的顯性建模,如文獻(xiàn)[25]由單個(gè)溝通網(wǎng)絡(luò)實(shí)現(xiàn)多智能體間信息傳遞、文獻(xiàn)[26]采用雙向遞歸神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)各個(gè)智能體的信息傳遞。強(qiáng)化學(xué)習(xí)模型的訓(xùn)練難度正比于狀態(tài)空間、動(dòng)作空間規(guī)模,導(dǎo)致現(xiàn)有方法難以應(yīng)對(duì)大規(guī)模場(chǎng)景。另外,現(xiàn)有強(qiáng)化學(xué)習(xí)方法往往局限于單一場(chǎng)景,雙方作戰(zhàn)單元的種類、數(shù)目固定,難以應(yīng)對(duì)多變的復(fù)雜場(chǎng)景。

綜上,搜索方法和強(qiáng)化學(xué)習(xí)方法相互獨(dú)立,均難以解決大規(guī)模戰(zhàn)斗場(chǎng)景下的RTS游戲微操問題。本文方法融合了搜索方法、學(xué)習(xí)方法的優(yōu)勢(shì),有利于拓展RTS游戲微操的研究思路。

2 問題描述

RTS游戲微操問題涉及作戰(zhàn)環(huán)境、敵我雙方控制的作戰(zhàn)單元,參與者要求控制各自的作戰(zhàn)單元進(jìn)行實(shí)時(shí)對(duì)抗,直至一方所有作戰(zhàn)單元消滅殆盡,屬于零和同步博弈問題。本文關(guān)注二人零和的RTS游戲微操問題,假設(shè)參與者為P={i,-j},己方i控制m(m≥1)個(gè)作戰(zhàn)單元,敵方-j控制n(n≥1)個(gè)作戰(zhàn)單元,分別對(duì)應(yīng)作戰(zhàn)單元集合Ui=(u1,u2,…,um)、U-j=(u-1,u-2,…,u-n)。由此,RTS游戲微操問題可以被建模為包含m+n個(gè)智能體的馬爾科夫決策過程,該問題可以表示為一個(gè)四元組G={S,A,Γ,R},S表示所有作戰(zhàn)單元U=Ui∪U-j可能經(jīng)歷的狀態(tài),A表示作戰(zhàn)單元的所有可行動(dòng)作。在任意狀態(tài)s∈S下,待命單元選取各自動(dòng)作α∈A構(gòu)成聯(lián)合動(dòng)作{{αi}i=1,2,…,m,{α-j}j=1,2,…,n},依據(jù)狀態(tài)轉(zhuǎn)移函數(shù)Γ:S×Am+n×S→[0,1]可以實(shí)現(xiàn)作戰(zhàn)場(chǎng)景的狀態(tài)轉(zhuǎn)移,并依據(jù)獎(jiǎng)勵(lì)函數(shù)R:S×Am+n→[0,1]獲得即時(shí)回報(bào)。本文采用監(jiān)督學(xué)習(xí)方式訓(xùn)練策略模型,在此忽略獎(jiǎng)勵(lì)函數(shù)的定義及使用。

固定規(guī)則常被用于輸出智能體的個(gè)體行動(dòng),可將其定義為σ:S×U→A,在任意狀態(tài)s∈S下,依據(jù)固定規(guī)則輸出單元u∈U的動(dòng)作決策α∈A。通常以UCTCD為代表的樹搜索方法事先建立博弈樹,搜索樹根節(jié)點(diǎn)(Root)至葉子節(jié)點(diǎn)的最佳路徑對(duì)應(yīng)局部最優(yōu)解。博弈樹中各個(gè)節(jié)點(diǎn)對(duì)應(yīng)S中各個(gè)可能狀態(tài),若狀態(tài)si與狀態(tài)sj間存在邊,則兩狀態(tài)間存在狀態(tài)轉(zhuǎn)移。不同于樹搜索方法,PGS、POE、SSS+不要求建立博弈樹,基本思想是在初始解的基礎(chǔ)上,采用不同的迭代策略使得初始解朝最優(yōu)解方向演變。搜索方法結(jié)合固定規(guī)則σ和靜態(tài)評(píng)估函數(shù)ψ來評(píng)估出現(xiàn)狀態(tài)s∈S的價(jià)值,前者用于模擬狀態(tài)轉(zhuǎn)移,后者用于評(píng)估終局局勢(shì),典型的LTD2函數(shù)如式(1)所示:

(1)

其中,hp(ui)、dpf(ui)表示單元ui∈Ui的當(dāng)前生命、單幀可造成的傷害。

假定φ(s,ui)表示從單元ui∈Ui視角出發(fā),狀態(tài)s∈S對(duì)應(yīng)特征圖,則多智能體強(qiáng)化學(xué)習(xí)方法依據(jù)π:φ(s,ui)→αi生成單元ui∈Ui的動(dòng)作決策。假定φ(s,Ui)表示從己方所有單元視角出發(fā),狀態(tài)s∈S對(duì)應(yīng)特征圖,本文提出方法的決策過程如下:1)JPN依據(jù)π:φ(s,Ui)→ρ(s,Ui)生成己方所有單元的動(dòng)作概率分布;2)由生成的概率分布指導(dǎo)搜索方法,依據(jù)T:〈s,φ(s,Ui)〉→{αi}i=1,2,…,m輸出己方所有單元的最終行動(dòng)。

3 RTS游戲微操方法

本節(jié)描述融合深度學(xué)習(xí)與搜索的RTS游戲微操方法,給出整體解決方案描述各部分的邏輯關(guān)系,介紹策略模型,包括狀態(tài)表達(dá)、動(dòng)作表達(dá)、JPN等,并對(duì)PGS w/JPN、POE w/JPN、SSS+ w/JPN 3種改進(jìn)方法進(jìn)行說明。

3.1 整體方案

梳理傷害機(jī)制密切相關(guān)的單元屬性,完成作戰(zhàn)狀態(tài)表達(dá),利用特征圖表達(dá)原始狀態(tài);采用動(dòng)作精煉的思路,完成作戰(zhàn)單元的動(dòng)作表達(dá),運(yùn)用Script動(dòng)作表達(dá)原始動(dòng)作。RTS游戲微操的整體方案如圖1所示。對(duì)于當(dāng)前游戲狀態(tài)s∈S,經(jīng)狀態(tài)表達(dá)生成特征圖φ(s,Ui),輸入至JPN,生成動(dòng)作的概率分布;搜索方法在此先驗(yàn)概率分布指導(dǎo)下,循環(huán)執(zhí)行搜索過程直至有限決策時(shí)間到達(dá);最后將Script動(dòng)作轉(zhuǎn)換為實(shí)際動(dòng)作,輸出至RTS游戲?qū)嶒?yàn)平臺(tái),作為最終決策。

圖1 融合深度學(xué)習(xí)與搜索的RTS游戲微操方法

3.2 狀態(tài)表達(dá)

狀態(tài)表達(dá)是將原始游戲狀態(tài)轉(zhuǎn)換為多通道特征圖。鑒于RTS游戲涉及單元種類繁多,本文參考之前搜索方法和多智能體強(qiáng)化學(xué)習(xí)方法的設(shè)置,選取StarCarft中4種采用物理攻擊的作戰(zhàn)單元,分別是Zergling、Zealot、Dragoon、Marine。在狀態(tài)特征設(shè)計(jì)上,主要考慮與空間分布、傷害機(jī)制密切相關(guān)的單元屬性,具體如表1所示,己方、敵方各對(duì)應(yīng)一半。其中,不同單元之間可造成的傷害由單元類型、攻擊類型、體型共同決定,單元生命按基數(shù)、比率、序數(shù)劃分為3種特征,基數(shù)、序數(shù)分別對(duì)應(yīng)當(dāng)前生命、生命排行,比率表示當(dāng)前生命與最大生命的比值。

表1 特征描述

特征編碼采取one-hot編碼方式,每一種連續(xù)或離散特征對(duì)應(yīng)多通道的0/1特征圖,共編碼為56通道特征圖。如圖2所示,單元所屬被編碼為2通道特征圖,分別對(duì)應(yīng)己方所屬、敵方所屬。考慮到實(shí)際游戲狀態(tài)的稀疏性,作戰(zhàn)單元僅占據(jù)很小的空間,特征編碼在變化的作戰(zhàn)場(chǎng)景尺度上進(jìn)行。具體地,若作戰(zhàn)場(chǎng)景尺度為H×W,則特征圖尺度為λH×λW,λ≤1為縮放系數(shù),單元在作戰(zhàn)場(chǎng)景中的真實(shí)坐標(biāo)可以映射為特征圖的像素坐標(biāo)。

圖2 單元所屬特征編碼示意圖

3.3 動(dòng)作表達(dá)

與狀態(tài)表達(dá)類似,動(dòng)作表達(dá)是編碼作戰(zhàn)單元的移動(dòng)動(dòng)作、攻擊動(dòng)作。本文采用PGS[16]、POE[17]、SSS+[18]為基準(zhǔn)搜索方法,因此使用這3種算法的Script作為單位動(dòng)作,分別為NOK-AV、Kiter、BackFar、BackClose、Forward、ForwardFar及Cluster共計(jì)7種。通常,Script動(dòng)作可分為攻擊前移動(dòng)、攻擊時(shí)目標(biāo)選擇和攻擊間隙移動(dòng)3個(gè)階段,前6種Script動(dòng)作在攻擊前朝最近的敵方單元移動(dòng),攻擊時(shí)優(yōu)先選擇dpf/hp最高的敵方單元,但它們?cè)诠糸g隙的移動(dòng)動(dòng)作有所不同[16-17],如NOK-AV在攻擊間隙原地等待、Kiter在攻擊間隙朝遠(yuǎn)離最近敵方單元的方向移動(dòng)等。Cluster僅涉及移動(dòng)動(dòng)作,表示朝友方單元的中心移動(dòng)[18]。與特征編碼一致,動(dòng)作編碼采用one-hot編碼方式生成7通道的0/1動(dòng)作圖,其動(dòng)作圖尺度為λH×λW,單元在作戰(zhàn)場(chǎng)景中的真實(shí)坐標(biāo)可以映射為動(dòng)作圖中的像素坐標(biāo)。

3.4 基于卷積神經(jīng)網(wǎng)絡(luò)的聯(lián)合策略模型

策略模型的目標(biāo)是在給定56通道特征圖下,計(jì)算己方所有單元的動(dòng)作概率分布,本節(jié)將描述具體的網(wǎng)絡(luò)結(jié)構(gòu)、損失函數(shù)。

3.4.1 網(wǎng)絡(luò)結(jié)構(gòu)

考慮到編碼-解碼卷積架構(gòu)在圖像分割[27]領(lǐng)域的成功,本文提出面向RTS游戲微操的聯(lián)合策略網(wǎng)絡(luò)。JPN的結(jié)構(gòu)設(shè)計(jì)參考SegNet,如圖3所示,主要不同點(diǎn)是移除了大量卷積層,以保證前向運(yùn)算的速度。具體地,JPN的編碼部分包含5層卷積層、4層最大池化層,解碼部分包含5層卷積層、4層上采樣層,最后一層接Softmax層。其中,10層卷積層的卷積核大小都為3×3,第1層、第10層卷積層的卷積核數(shù)量為64,第2層、第9層卷積層的卷積核數(shù)量為128,第3層、第8層卷積層的卷積核數(shù)量為256,其余卷積層的卷積核數(shù)量都為512;4層最大池化層與4層上采樣層一一對(duì)應(yīng),采樣步長(zhǎng)都為2,兩部分分別實(shí)現(xiàn)輸入特征圖的16倍尺度縮小、放大,使得輸入、輸出的尺度均為λH×λW。

圖3 聯(lián)合策略網(wǎng)絡(luò)示意圖

3.4.2 損失函數(shù)

采用交叉熵?fù)p失函數(shù)作為JPN的目標(biāo)函數(shù),考慮到不同類別動(dòng)作之間的不均衡性,構(gòu)建一種加權(quán)交叉熵?fù)p失函數(shù):

(2)

(3)

3.5 改進(jìn)搜索方法

本節(jié)將JPN與3種典型的搜索方法(PGS[16]、POE[17]、SSS+[18])相結(jié)合,提出3種改進(jìn)方法,即PGS w/JPN、POE w/JPN、SSS+ w/JPN。3種改進(jìn)方法的思路類似。具體地,由JPN輸出己方單元在7種Script動(dòng)作上的概率分布;將最大概率Script動(dòng)作設(shè)定為初始解;由先驗(yàn)概率分布指導(dǎo)初始解的優(yōu)化過程,若采用狀態(tài)精煉來合并相似狀態(tài)的作戰(zhàn)單元,則面向群體展開搜索過程,群體內(nèi)單元共享相同的Script動(dòng)作,否則面向個(gè)體展開搜索過程,直至決策時(shí)間消耗殆盡;輸出有限時(shí)間內(nèi)搜索到的局部最優(yōu)解。

3.5.1 PGS w/JPN方法

PGS w/JPN的算法流程如算法1所示,主要分為設(shè)定初始解(第2行、第3行)、產(chǎn)生可能動(dòng)作子集(第4行)、迭代優(yōu)化(第5行～第12行)3個(gè)部分。

算法1PGS w/JPN方法

輸出己方單元聯(lián)合動(dòng)作Ai={α1,α2,…,αm}

1.計(jì)算先驗(yàn)概率分布ρπ(s,Ui)=π(φ(s,Ui);θ)

2.設(shè)定己方初始解{σ1,σ2,…,σm}←Max(ρπ(s,Ui))

5.While 消耗時(shí)間小于t do

6.for i=1→m do

7.for j=1→M1do

8.己方當(dāng)前解Σ={σ1,σ2,…,σm}

9.對(duì)方當(dāng)前解Σ-1={σ-1,σ-2,…,σ-n}

11.if ζ(S,Σ,Σ-1)<ζ(S,Σ′,Σ-1) then

13.計(jì)算并返回己方單元聯(lián)合動(dòng)作Ai←{σ1,σ2,…,σm}

將最大概率Script動(dòng)作設(shè)定為己方初始解(第2行),將默認(rèn)Script動(dòng)作設(shè)定為對(duì)方初始解(第3行),而原始的PGS采用迭代方式確定雙方初始解。由先驗(yàn)概率分布產(chǎn)生可能動(dòng)作子集(第4行),在給定先驗(yàn)概率分布下,采取排序方式,按從大到小的原則確定不同Script動(dòng)作對(duì)于各個(gè)單元的優(yōu)先級(jí),若可能動(dòng)作子集大小設(shè)定為M1,則按優(yōu)先級(jí)從大到小選取前M1個(gè)Script動(dòng)作構(gòu)成各個(gè)單元的可能動(dòng)作子集。在給定可能動(dòng)作子集下,逐個(gè)優(yōu)化己方單元的當(dāng)前解(第10行),類似PGS,采用動(dòng)態(tài)評(píng)估方法ζ來評(píng)價(jià)解的好壞,先由當(dāng)前解模擬狀態(tài)轉(zhuǎn)移,再由靜態(tài)評(píng)估函數(shù)評(píng)估終局局勢(shì),選取評(píng)分最高的Script動(dòng)作(第11行、第12行)。待決策時(shí)間消耗殆盡,將局部最優(yōu)解轉(zhuǎn)換為具體的動(dòng)作指令(第13行)。

3.5.2 POE w/JPN方法

POE w/JPN的算法流程如算法2所示,類似演化算法,主要分為初始化基因組(第2行～第5行)、產(chǎn)生可能動(dòng)作子集(第6行、第7行)、突變(第9行～第12行)、交叉(第13行)和選擇(第14行)5個(gè)部分。這里的改進(jìn)主要集中在前3個(gè)部分,后兩部分與POE完全一致,交叉對(duì)所有基因進(jìn)行隨機(jī)兩兩交換,選擇篩選優(yōu)良基因。

算法2POE w/JPN方法

輸出己方單元聯(lián)合動(dòng)作Ai={α1,α2,…,αm}

1.計(jì)算先驗(yàn)概率分布ρπ(s,Ui)=π(φ(s,Ui);θ)

2.for i=1→size do

3.for j=1→step do

4.設(shè)定己方初始基因Σij←Max(ρπ(s,Ui))

8.While 消耗時(shí)間小于t do

9.for i=1→size do//執(zhí)行突變步驟

10.for j=1→step do

12.Σij←Random(Σij,offsprings,ε′)

13.執(zhí)行交叉步驟Σ←Cross(Σ,select)

14.執(zhí)行選擇步驟Σ←Select(Σ,select,ψ)

15.計(jì)算并返回己方單元聯(lián)合動(dòng)作Ai←Σ11

在初始化基因組階段,由最大概率Script動(dòng)作設(shè)定為己方初始基因(第4行),將默認(rèn)Script動(dòng)作設(shè)定為對(duì)方初始基因(第5行),而原始的POE完全采取默認(rèn)初始解,其中基因?qū)?yīng)己方單位或?qū)Ψ絾挝坏腟cript動(dòng)作組合。在產(chǎn)生可能動(dòng)作子集階段,類似PGS w/JPN,若可能動(dòng)作子集大小設(shè)定為M2,按照優(yōu)先級(jí)排序方式選取前M2個(gè)Script動(dòng)作構(gòu)成各個(gè)單元的可能動(dòng)作子集(第6行),并計(jì)算這M2個(gè)Script動(dòng)作的歸一化概率分布,其他Script動(dòng)作的概率取0(第7行)。在突變階段,在可能動(dòng)作子集內(nèi)執(zhí)行基因變異操作,朝向各個(gè)Script動(dòng)作的變異率由默認(rèn)變異率和歸一化概率分布共同決定(第11行),這意味著同一個(gè)基因朝不同動(dòng)作的變異率可能不同。

3.5.3 SSS+ w/JPN方法

SSS+ w/JPN的算法流程如算法3所示,主要分為設(shè)定初始解(第2行、第3行)、劃分群體(第4行)、產(chǎn)生可能動(dòng)作子集(第5行)和迭代優(yōu)化(第6行～第13行)4個(gè)部分。

算法3SSS+ w/JPN方法

輸出己方單元聯(lián)合動(dòng)作Ai={α1,α2,…,αm}

1.計(jì)算先驗(yàn)概率分布ρπ(s,Ui)=π(φ(s,Ui);θ)

2.設(shè)定己方初始解{σ1,σ2,…,σm}←Max(ρπ(s,Ui))

4.己方單元?jiǎng)澐秩后w{g1,g2,…,gk}←types(Ui)

6.While 消耗時(shí)間小于t do

7.for i=1→k do

8.for j=1→M3do

9.己方當(dāng)前解Σ={σ1,σ2,…,σm}

10.對(duì)方當(dāng)前解Σ-1={σ-1,σ-2,…,σ-n}

12.if ζ(S,Σ,Σ-1)<ζ(S,Σ′,Σ-1) then

14.計(jì)算并返回己方單元聯(lián)合動(dòng)作Ai←{σ1,σ2,…,σm}

首先將最大概率Script動(dòng)作設(shè)定為己方初始解(第2行),將默認(rèn)Script動(dòng)作設(shè)定為對(duì)方初始解(第3行),而原始的SSS+完全采取默認(rèn)初始解。然后由當(dāng)前類型系統(tǒng)歸并相似狀態(tài)的單元,所采用的自適應(yīng)類型系統(tǒng)types與SSS+一致,包含5種類型系統(tǒng),分別是{T(c,3),T(c,2),T(c,1),T(c,0),TRGD},前4種類型系統(tǒng)計(jì)算公式如下:

(4)

其中,r(u)與d(u)分別表示單位u的攻擊距離和傷害,hp(u)與hpm(u)分別表示單位u的當(dāng)前生命與最大生命,若兩單位的Tc,l(u)三要素完全一致,則劃分至一類,否則劃分至各自類別;而TRGD將單元分為近戰(zhàn)單元、遠(yuǎn)戰(zhàn)單元兩類。另外,自適應(yīng)類型系統(tǒng)types依據(jù)運(yùn)行情況自動(dòng)調(diào)整所使用的類型系統(tǒng),若給定時(shí)間內(nèi)可以遍歷所有可能解,則增大所使用類型系統(tǒng)的精細(xì)程度,如Tc,2(u)調(diào)整至Tc,3(u);否則,降低所使用類型系統(tǒng)的精細(xì)程度,如Tc,3(u)調(diào)整至Tc,2(u)。接著由先驗(yàn)概率分布產(chǎn)生可能動(dòng)作子集(第5行),采取排序、投票相結(jié)合的方式,先排序確定不同動(dòng)作對(duì)于各個(gè)單元的優(yōu)先級(jí),再在各個(gè)群體內(nèi)執(zhí)行投票,統(tǒng)計(jì)不同動(dòng)作對(duì)于各個(gè)群體的優(yōu)先級(jí),若可能動(dòng)作子集大小設(shè)定為M3,則按優(yōu)先級(jí)從大到小選取前M3個(gè)Script動(dòng)作構(gòu)成各個(gè)群體的可能動(dòng)作子集,群體內(nèi)單元共享相同的可能動(dòng)作子集。最后在給定可能動(dòng)作子集下,逐個(gè)優(yōu)化己方群體的當(dāng)前解(第11行),類似PGS w/JPN,采用動(dòng)態(tài)評(píng)估方法ζ來評(píng)價(jià)解的好壞,選取評(píng)分最高的Script動(dòng)作(第12行、第13行)。待決策時(shí)間消耗殆盡,將局部最優(yōu)解轉(zhuǎn)換為具體的動(dòng)作指令(第14行)。

4 實(shí)驗(yàn)評(píng)估

為評(píng)估JPN和改進(jìn)方法(PGS w/JPN、POE w/JPN、SSS+ w/JPN)的性能,本節(jié)一方面在SparCraft上展開原始方法(PGS[16]、POE[17]、SSS+[18])和改進(jìn)方法的對(duì)比實(shí)驗(yàn),測(cè)試改進(jìn)方法的性能提升,另一方面在StarCraft:BroodWar上展開內(nèi)置AI和改進(jìn)方法的對(duì)比實(shí)驗(yàn),測(cè)試改進(jìn)方法的AI真實(shí)水平。兩個(gè)實(shí)驗(yàn)平臺(tái)的作戰(zhàn)場(chǎng)景類似,單元類型、單元屬性也基本一致。其中,SparCraft顯性建模了RTS游戲微操涉及的狀態(tài)轉(zhuǎn)移,為搜索方法提供了極大的便捷; StarCraft:BroodWar提供了更加真實(shí)的作戰(zhàn)場(chǎng)景,更有利于鑒定改進(jìn)方法的AI水準(zhǔn)?？紤]到目前尚無可用于訓(xùn)練JPN的數(shù)據(jù)集,首先構(gòu)建覆蓋基準(zhǔn)場(chǎng)景的學(xué)習(xí)用數(shù)據(jù)集;然后將訓(xùn)練完成的模型接入改進(jìn)方法,在2個(gè)實(shí)驗(yàn)平臺(tái)上分別開展驗(yàn)證實(shí)驗(yàn)。

4.1 場(chǎng)景設(shè)置

借鑒PGS[16]、POE[17]、SSS+[18]的場(chǎng)景設(shè)置,選取4種采取物理攻擊的作戰(zhàn)單元,分別是Zergling(L)、Zealot(Z)、Dragoon(D)和Marine(M),在多種作戰(zhàn)基準(zhǔn)場(chǎng)景中開展驗(yàn)證實(shí)驗(yàn),統(tǒng)計(jì)1 000場(chǎng)戰(zhàn)斗中改進(jìn)方法對(duì)抗原始方法或內(nèi)置AI的勝率。具體地,為評(píng)估改進(jìn)方法的性能提升,選取了5類基準(zhǔn)場(chǎng)景,各方控制單元的數(shù)量n選取自{4,8,16,32,50},分別為nD vs.nD、nL vs.nL、n/2Dn/2Z vs.n/2Dn/2Z、n/2Dn/2M vs.n/2Dn/2M、n/2Mn/2L vs.n/2Mn/2L,共計(jì)25種基準(zhǔn)場(chǎng)景。為評(píng)估改進(jìn)方法的AI真實(shí)水平,選取了BiCNet[22]中的2種大尺度場(chǎng)景:即10 M vs.13 L、 20M vs.30L,并設(shè)計(jì)了8種變種場(chǎng)景:分別為6M vs.7L、8M vs.10L、12M vs.16L、14M vs.20L、16M vs.24L、18M vs.27L、22M vs.33L、24M vs.36L。由此,共采用了35種作戰(zhàn)基準(zhǔn)場(chǎng)景。

4.2 基準(zhǔn)算法設(shè)置

采用PGS[16]、POE[17]、SSS+[18]作為基準(zhǔn)搜索方法,采用GMEZO[21]、CommNet[25]、BiCNet[22]以及PS-MAGDS[26]作為基準(zhǔn)多智能體強(qiáng)化學(xué)習(xí)方法。為評(píng)估改進(jìn)方法的性能提升,實(shí)驗(yàn)對(duì)比了原始方法(PGS[16]、POE[17]、SSS+[18])、改進(jìn)方法(PGS w/JPN、POE w/JPN、SSS+ w/JPN),以及結(jié)合隨機(jī)先驗(yàn)概率分布的搜索方法(PGS w/RND、POE w/RND、SSS+ w/RND)。出于公平性,借鑒SSS+[18]中可能動(dòng)作集合的大小,三類搜索方法可能動(dòng)作集合的大小均設(shè)置為3,原始搜索方法默認(rèn)為NOK-AV、Kiter、Cluster,其他搜索方法依據(jù)各自的先驗(yàn)概率分布,從7種Script動(dòng)作中構(gòu)建各自的可能動(dòng)作集合。除此以外,所有搜索方法的參數(shù)一致,如決策時(shí)間限制為40 ms。

4.3 數(shù)據(jù)集構(gòu)建

SSS+是所有開源搜索方法中的最佳方法,因此將其分別接入SparCraft和StarCraft:BroodWar,生成所設(shè)定基準(zhǔn)場(chǎng)景的數(shù)據(jù)集。對(duì)于前25種基準(zhǔn)場(chǎng)景,為增強(qiáng)樣本的質(zhì)量和多樣性,采取了4點(diǎn)特殊設(shè)置:1)將SSS+的可能動(dòng)作集合設(shè)定為7種Script動(dòng)作;2)將決策時(shí)間限制由40 ms延長(zhǎng)至200 ms;3)各方控制單元的數(shù)量n分別隨機(jī)選取自[1,4]、[5,8]、[9,16]、[17,32]、[33,50],每個(gè)基準(zhǔn)場(chǎng)景進(jìn)行100 000場(chǎng)戰(zhàn)斗,共進(jìn)行了2 500 000場(chǎng)戰(zhàn)斗;4)合并相同規(guī)模場(chǎng)景中產(chǎn)生的數(shù)據(jù)集,生成用于4v4、8v8、16v16、32v32、50v50五類場(chǎng)景的數(shù)據(jù)集。對(duì)于場(chǎng)景10 M vs.13 L、 20M vs.30L,鑒于StarCraft:BroodWar產(chǎn)生樣本的速度遠(yuǎn)遠(yuǎn)低于SparCraft,這里僅將可能動(dòng)作集合設(shè)定為7種Script動(dòng)作,未采用其他3點(diǎn)特殊設(shè)置,共進(jìn)行了200 000場(chǎng)戰(zhàn)斗。在上述設(shè)定下,按50幀時(shí)間間隔來隨機(jī)記錄中間狀態(tài),經(jīng)狀態(tài)表達(dá)、動(dòng)作表達(dá)、數(shù)據(jù)打亂,進(jìn)一步地按4:1劃分訓(xùn)練集、測(cè)試集,生成的7組數(shù)據(jù)集分別稱為I4v4、I8v8、I16v16、I32v32、I50v50、I10Mv13L、I20Mv30L,具體如表2所示。

表2 數(shù)據(jù)集統(tǒng)計(jì)情況

4.4 結(jié)果分析

首先在7個(gè)數(shù)據(jù)集上訓(xùn)練并測(cè)試JPN,然后將訓(xùn)練完成的學(xué)習(xí)模型接入各個(gè)搜索方法,分別在2個(gè)實(shí)驗(yàn)平臺(tái)上展開性能評(píng)估實(shí)驗(yàn)。

4.4.1 策略模型的預(yù)測(cè)性能評(píng)估

訓(xùn)練完成的JPN在7個(gè)測(cè)試集上的Top-1預(yù)測(cè)準(zhǔn)確率如圖4所示,此處類別總數(shù)為8(7類Script動(dòng)作和1類背景)。由圖4可知,前5個(gè)測(cè)試集上的最大準(zhǔn)確率、最小準(zhǔn)確率、平均準(zhǔn)確率約為73.10%、69.66%、73.10%,后2個(gè)測(cè)試集上的最大準(zhǔn)確率、最小準(zhǔn)確率、平均準(zhǔn)確率約為57.30%、56.80%、57.05%。可見,JPN可以適應(yīng)復(fù)雜的作戰(zhàn)場(chǎng)景,甚至是單元數(shù)量達(dá)到100的大規(guī)模作戰(zhàn)場(chǎng)景。JPN在前5個(gè)測(cè)試集上的表現(xiàn)優(yōu)于其在2個(gè)測(cè)試集上的表現(xiàn),這主要是由于前5組數(shù)據(jù)集在構(gòu)建過程中所采用的特殊設(shè)置。

圖4 JPN在7個(gè)測(cè)試集上的預(yù)測(cè)準(zhǔn)確率

4.4.2 原始搜索方法與改進(jìn)搜索方法的對(duì)比分析

改進(jìn)方法(PGS w/JPN、POE w/JPN、SSS+w/JPN)、結(jié)合隨機(jī)先驗(yàn)概率分布的搜索方法(PGS w/RND、POE w/RND、SSS+ w/RND)對(duì)抗原始方法(PGS、POE、SSS+)的實(shí)驗(yàn)結(jié)果如表3所示,其中,第1列指定了場(chǎng)景設(shè)置,第1行指定了測(cè)試的搜索方法。例如在場(chǎng)景4D4Z vs.4D4Z中,PGS w/RND vs.PGS的勝率是47%,PGS w/JPN vs.PGS的勝率是79%,對(duì)應(yīng)地,兩種搜索方法的增益分別是-3%和+29%。

表3 原始搜索方法、改進(jìn)搜索方法的對(duì)比實(shí)驗(yàn)結(jié)果

由表3可得出以下實(shí)驗(yàn)結(jié)論:1)在絕大多數(shù)場(chǎng)景中,相比于改進(jìn)方法,結(jié)合隨機(jī)先驗(yàn)概率分布的搜索方法取得較低的勝率,這表示合適的先驗(yàn)概率分布對(duì)于引導(dǎo)搜索方法至關(guān)重要;2)SSS+ w/RND總是存在增益,POE w/RND在一半場(chǎng)景中有增益,而PGS w/RND在所有場(chǎng)景中無增益,這表示隨機(jī)先驗(yàn)概率分布帶來的多樣性對(duì)于PGS、POE、SSS+影響程度不等,SSS+受益最大;3)在絕大多數(shù)場(chǎng)景中,改進(jìn)搜索方法對(duì)抗原始搜索方法的勝率大于50%,其增益也總是大于結(jié)合隨機(jī)先驗(yàn)概率分布的搜索方法,這證實(shí)了JPN可以有效提升搜索方法;4)PGS w/JPN、POE w/JPN的增益往往大于SSS+ w/JPN的增益,相比于SSS+,JPN更有利于提升PGS、POE,這主要由于采用了SSS+產(chǎn)生的訓(xùn)練集,SSS+的性能優(yōu)于PGS、POE,導(dǎo)致訓(xùn)練產(chǎn)生的學(xué)習(xí)模型更有利于提升PGS、POE。

4.4.3 內(nèi)置AI與改進(jìn)搜索方法的對(duì)比分析

改進(jìn)方法(PGS w/JPN、POE w/JPN、SSS+w/JPN)對(duì)抗內(nèi)置AI的實(shí)驗(yàn)結(jié)果如表4和表5所示,其中,表4在2種基準(zhǔn)場(chǎng)景中對(duì)比了改進(jìn)方法、基準(zhǔn)多智能體強(qiáng)化學(xué)習(xí)方法,表5在8種變種場(chǎng)景中評(píng)估了改進(jìn)方法的泛化能力。例如在表4場(chǎng)景10M vs.13L中,PGS w/JPN vs.內(nèi)置AI的勝率和增益分別是95%和+8%。

表4 改進(jìn)搜索方法、多智能體強(qiáng)化學(xué)習(xí)方法的性能對(duì)比

表5 改進(jìn)搜索方法在8種變種場(chǎng)景中的性能測(cè)試

由表4和表5可得出以下實(shí)驗(yàn)結(jié)論:1)在2種基準(zhǔn)場(chǎng)景中,改進(jìn)方法可以擊敗內(nèi)置AI,PGS w/JPN取得勝率接近最好的基準(zhǔn)方法,分別是95%、99%,這證實(shí)了改進(jìn)搜索方法對(duì)抗內(nèi)置AI的優(yōu)勢(shì),同時(shí),改進(jìn)方法的增益總大于0,這再次表明了JPN可以有效提升搜索方法;2)在8個(gè)變種場(chǎng)景中,改進(jìn)方法同樣可以擊敗內(nèi)置AI,且增益同樣大于0%,這表明訓(xùn)練好的學(xué)習(xí)模型可以泛化至類似場(chǎng)景;3)在絕大多數(shù)場(chǎng)景中,PGS w/JPN的表現(xiàn)好于POE w/JPN、SSS+ w/JPN,但實(shí)際上PGS弱于POE、SSS+,表明學(xué)習(xí)與搜索的結(jié)合機(jī)制對(duì)性能是至關(guān)重要的。

5 結(jié)束語

本文提出一種基于卷積神經(jīng)網(wǎng)絡(luò)的聯(lián)合策略網(wǎng)絡(luò)方法。該方法將所有智能體作為群體,以實(shí)現(xiàn)多智能體聯(lián)合動(dòng)作的端到端學(xué)習(xí)。改進(jìn)搜索方法由JPN輸出的先驗(yàn)概率分布保證初始解,以盡可能地搜索大概率存在最優(yōu)解的動(dòng)作空間。實(shí)驗(yàn)結(jié)果表明,JPN可以有效提升搜索方法。本文主要通過學(xué)習(xí)模型提升搜索方法,后續(xù)將研究學(xué)習(xí)模型與搜索方法相結(jié)合的機(jī)制以進(jìn)一步提升學(xué)習(xí)模型的性能。