溫葉廷，黃海于

(西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 611756)

0 引言

實(shí)時(shí)戰(zhàn)略游戲(RTS)在過(guò)去十年中一直是人工智能研究領(lǐng)域的一個(gè)熱點(diǎn)[1]。由于RTS游戲復(fù)雜性、部分可觀察和動(dòng)態(tài)實(shí)時(shí)變化戰(zhàn)局等游戲特點(diǎn)使得研究變得比較困難，因此對(duì)于獲勝者的預(yù)測(cè)成為了人工智能研究的一個(gè)高度相關(guān)的主題。

現(xiàn)有的研究主要集中在MOBA游戲DOTA2中,比如，文獻(xiàn)[2]使用兩種不同的方法對(duì)游戲勝負(fù)做出了預(yù)測(cè)，第一種使用完整的賽后數(shù)據(jù)，第二種在英雄選擇階段，上述的兩種方法是用來(lái)預(yù)測(cè)整局游戲的勝負(fù)，而不是實(shí)時(shí)勝率；文獻(xiàn)[3]將賽前特征與比賽期間的特性相結(jié)合，使用邏輯回歸，得到了實(shí)時(shí)游戲預(yù)測(cè)勝率的準(zhǔn)確率為71.49%。雖然目前研究在游戲勝負(fù)預(yù)測(cè)方面已經(jīng)有了一些成果，但是由于游戲不同，RTS與MOBA游戲有著很大的區(qū)別，而被廣泛認(rèn)為是最具挑戰(zhàn)性的RTS游戲的星際爭(zhēng)霸II[4]仍然沒(méi)有得到解決。星際爭(zhēng)霸II與其他的即時(shí)戰(zhàn)略游戲一樣分為雙人或多人游戲。每一名玩家可以選擇不同的種族(人族T、蟲(chóng)族Z和神族P)并且可以組建一支軍隊(duì)來(lái)?yè)魯橙?，而且每一位玩家可能在一?chǎng)游戲中同時(shí)操作很多單位。想要建立軍隊(duì)，玩家就需要開(kāi)采資源、建造建筑、研究科技和訓(xùn)練單位。最后通過(guò)摧毀敵方建筑獲得勝利。

本文基于SC2LE公開(kāi)的星際爭(zhēng)霸II游戲數(shù)據(jù)集，該數(shù)據(jù)集是天梯賽1V1數(shù)據(jù)，總計(jì)106萬(wàn)場(chǎng)。本文通過(guò)對(duì)海量的游戲數(shù)據(jù)信息進(jìn)行處理，得到了一些與游戲勝負(fù)相關(guān)的特征，這些特征主要分為兩類：基礎(chǔ)特性和統(tǒng)計(jì)特性，通過(guò)實(shí)驗(yàn)表明，與單獨(dú)使用基礎(chǔ)特性相比，加入統(tǒng)計(jì)特性能夠提高實(shí)時(shí)勝率預(yù)測(cè)的準(zhǔn)確率。

1 構(gòu)建游戲數(shù)據(jù)集

1.1 數(shù)據(jù)預(yù)處理

利用游戲的回放數(shù)據(jù)去預(yù)測(cè)游戲的勝負(fù)是一種科學(xué)有效的方法。但是游戲數(shù)據(jù)集的質(zhì)量好壞是影響預(yù)測(cè)結(jié)果的重要因素，因此，如何從106萬(wàn)局游戲中篩選出高質(zhì)量的回放數(shù)據(jù)是至關(guān)重要的。本文構(gòu)建游戲數(shù)據(jù)集基于以下原則:(1)選擇高水平玩家的對(duì)局；(2)根據(jù)不同匹配對(duì)局游戲時(shí)長(zhǎng)的均值和標(biāo)準(zhǔn)差選取游戲時(shí)間。

選取高水平玩家的對(duì)局主要使用兩個(gè)指標(biāo)：MMR(星際爭(zhēng)霸II大區(qū)中比賽匹配等級(jí)，Match Making Ration)和APM(玩家的每分鐘操作數(shù)，Actions Per Minute)。圖1所示為T(mén)vZ對(duì)局中MMR與APM的散點(diǎn)圖，從圖中可以看出兩者沒(méi)有相關(guān)性，而且高的MMR并不一定會(huì)有高的APM，反之亦然。因此，應(yīng)該將兩者結(jié)合使用。

圖1 TvZ對(duì)局的MMR和APM散點(diǎn)圖

游戲時(shí)間的篩選也是判斷游戲質(zhì)量的指標(biāo)，游戲時(shí)間太短或太長(zhǎng)的對(duì)局，會(huì)造成數(shù)據(jù)偏差太大。通過(guò)計(jì)算不同匹配組合游戲時(shí)間的均值和標(biāo)準(zhǔn)差來(lái)選擇游戲時(shí)長(zhǎng)的范圍。如表1所示，由于游戲中有3種不同的種族，因此會(huì)有6種不同的匹配對(duì)局，分別為：PvT、PvZ、TvZ、PvP、ZvZ和TvT。范圍中的下限使用均值向下取整與標(biāo)準(zhǔn)差向上取整相減所得，上限使用均值向上取整與標(biāo)準(zhǔn)向上取整相加所得。

表1 不同匹配對(duì)局的均值、標(biāo)準(zhǔn)差和選擇區(qū)間 (min)

這里將使用表1中的時(shí)間區(qū)間，并結(jié)合MMR(大于4 000)、APM(大于150，接近專業(yè)玩家水平)進(jìn)行篩選。篩選前后對(duì)局?jǐn)?shù)量如表2所示，F(xiàn)TS表示原始數(shù)據(jù)中的對(duì)局?jǐn)?shù)量，ATS表示篩選后的對(duì)局?jǐn)?shù)量。

表2 篩選前與篩選后的對(duì)局?jǐn)?shù) (萬(wàn)局)

1.2 解析數(shù)據(jù)

將篩選下來(lái)的高質(zhì)量對(duì)局通過(guò)使用pysc2進(jìn)行數(shù)據(jù)提取，在回放的每一幀都會(huì)返回Observation，使用ProtoBuf進(jìn)行解析，解析后的每個(gè)觀察值包括以下信息：

(1)玩家所擁有的建筑、單位和技術(shù)；

(2)玩家擁有的人口情況；

(3)玩家所使用和擁有的資源；

(4)玩家所觀察到的敵人單位和建筑。

1.3 特征提取

1.3.1 基本特征

從游戲回放中解析出游戲狀態(tài)，在這里，首先提取出基本的特征。這些基本特征主要包括：

(1)資源信息：包括當(dāng)前時(shí)刻的瓦斯數(shù)量和晶體礦的數(shù)量。

(2)人口信息：包括當(dāng)前時(shí)刻人口上限、已使用的人口數(shù)和未使用的人口數(shù)。

(3)單位信息：包括每種單位的數(shù)量，已經(jīng)訓(xùn)練完畢的單位數(shù)量，正在建造的數(shù)量，快要建造完畢的數(shù)量，剛開(kāi)始建造的數(shù)量以及平均建造數(shù)量。

(4)研究科技信息：包括已經(jīng)升級(jí)的科技。

(5)觀測(cè)到的敵方玩家建筑和單位的數(shù)量。

將上面的信息進(jìn)行序列化，但是由于種族不同，單位的類型數(shù)量以及研究科技的種類也不相同，因此不同的對(duì)局對(duì)應(yīng)的序列長(zhǎng)度也不一樣，如表3所示。

表3 不同種族對(duì)應(yīng)的單位類型數(shù)量與科技研究種類

每場(chǎng)游戲的基本回放特征會(huì)被組織成一個(gè)N×M1大小的矩陣，N指行數(shù)，與游戲時(shí)間相關(guān)；M1根據(jù)使用的種族和對(duì)戰(zhàn)種族不同而不同。表4所示為M1的組織形式。不同的種族由于其單位種類和研究種類數(shù)量上的差異，特征序列的長(zhǎng)度也不相同，如表5所示。

表4 序列對(duì)應(yīng)的每個(gè)字段的含義

注：(1)R大小為種族的研究數(shù)量(見(jiàn)表3)加20；

(2)S(U)大小為R加上6×種族的單位種類數(shù)量(見(jiàn)表3)；

(3)E(U)大小為S(U)加上敵方單位種類數(shù)量(見(jiàn)表3)。

表5 不同匹配對(duì)局不同種族的特征序列長(zhǎng)度

1.3.2 統(tǒng)計(jì)特征

除了上述的基本特征以外，這里提出了有關(guān)動(dòng)作和地圖的統(tǒng)計(jì)信息。統(tǒng)計(jì)信息主要分為兩類，一類是對(duì)動(dòng)作做統(tǒng)計(jì)，另一類是對(duì)地圖和距離的部分信息進(jìn)行統(tǒng)計(jì)。

星際爭(zhēng)霸Ⅱ是一個(gè)需要有效利用游戲時(shí)間的游戲，一般在游戲過(guò)程中分為前期、中期和后期三部分，想要在每個(gè)時(shí)期達(dá)到預(yù)期的效果，則采用的命令也就不同。因此，命令的類型以及頻率能夠反映出游戲的狀態(tài)，比如在前期時(shí)會(huì)大力地發(fā)展經(jīng)濟(jì)，所以關(guān)于建造的命令就相對(duì)較多。

首先統(tǒng)計(jì)某類類型的命令頻率。可以發(fā)現(xiàn)最常用的6種命令為：MOVE,BUILD,TECH,TRAIN,SIEGE和BURROW。而且根據(jù)執(zhí)行命令是否使用資源將命令分為兩大類：一類是在執(zhí)行過(guò)程中不使用資源，稱為微觀命令；否則為宏觀命令。

受文獻(xiàn)[5]的啟發(fā)，可以將命令分為三類:控制命令、策略命令和戰(zhàn)術(shù)命令。

動(dòng)作統(tǒng)計(jì)信息包括上述最常用的6種命令，還包括微觀命令、宏觀命令、控制命令、策略命令和戰(zhàn)術(shù)命令，共計(jì)11種命令。這些信息每隔1 min間隔統(tǒng)計(jì)一次。

整形：按照“單主干雙主蔓”的樹(shù)型整形。主干離架下40 厘米處摘心，培養(yǎng)雙主蔓，主蔓長(zhǎng)度為株距一半，主蔓兩側(cè)均勻分布結(jié)果母枝，結(jié)果母枝間距30厘米左右。

SC2LE中的數(shù)據(jù)集主要是收集天梯賽的對(duì)局，天梯賽在每個(gè)版本都會(huì)有幾種不同的地圖。每種地圖都有各自的風(fēng)格，地圖的主要特點(diǎn)主要有補(bǔ)給距離、空間距離、礦區(qū)范圍、礦區(qū)高地口寬度和礦區(qū)的資源數(shù)量。根據(jù)文獻(xiàn)[6]對(duì)于游戲地圖特點(diǎn)的分析，可以得出地圖對(duì)于玩家的勝負(fù)也是較為關(guān)鍵的。

除了基本的地圖統(tǒng)計(jì)信息以外，建筑物的擺放位置對(duì)于游戲勝負(fù)的影響很大，好的擺放位置，可以用來(lái)抵擋敵人[7]，在這里通過(guò)計(jì)算同種類型建筑物的相對(duì)距離和指揮中心周圍建筑與指揮中心的相對(duì)距離兩個(gè)指標(biāo)，來(lái)反映出建筑物的位置信息。式(1)計(jì)算了同種建筑的相對(duì)距離，因?yàn)橛螒虻貓D較大，所以使用指揮中心進(jìn)行分組，將距離某個(gè)指揮中心較近的分為一組,指揮中心的個(gè)數(shù)就是組的個(gè)數(shù)，用m表示。

(1)

其中，uij代表第i類建筑中第j個(gè)單位的位置，n代表某組中某種建筑的數(shù)量，dik代表第k組i類單位的相對(duì)距離。

(2)

Di為i類單位的平均距離。

式(3)表示的是建筑物相對(duì)于指揮中心的距離，同樣也是按照指揮中心分組計(jì)算，一般情況下，建筑物都是圍繞著指揮中心建造的。

(3)

其中ck為第k個(gè)指揮中心的位置，pj為第k組中第j個(gè)建筑的位置，s為第k組的單位個(gè)數(shù)。

式(4)表示指揮中心周圍建筑與指揮中心的相對(duì)距離。對(duì)于建筑物的位置擺放需要集中，過(guò)于分散不利于防守。

(4)

表6 統(tǒng)計(jì)特征每個(gè)字段的含義

注：S(B)大小為17加上建筑物類型數(shù)量(見(jiàn)表3)減1。

統(tǒng)計(jì)特征不同于基礎(chǔ)特性，其大小與匹配對(duì)局無(wú)關(guān)，只與種族相關(guān)。如表7，統(tǒng)計(jì)特征大小用M2表示。

表7 統(tǒng)計(jì)特征序列長(zhǎng)度

2 實(shí)驗(yàn)結(jié)果與分析

每場(chǎng)游戲的回放特征會(huì)被組織成一個(gè)N×M大小的矩陣，N與回放游戲時(shí)間有關(guān)。在本文中，采取每隔1 min構(gòu)建一個(gè)M，但是在提取數(shù)據(jù)時(shí)為了不丟失動(dòng)作信息是按照每8幀提取一次數(shù)據(jù)[8]，這里M的大小是M1+M2，例如M(T)PvT=M1(T)PvT+M2(T)=428+45=473。經(jīng)過(guò)數(shù)據(jù)處理后，得到每種不同匹配對(duì)局下的數(shù)據(jù)總條數(shù)，對(duì)每局游戲每隔1 min做一次數(shù)據(jù)采樣作為一個(gè)M(游戲剛開(kāi)始不做采樣)，最后每一種匹配的數(shù)據(jù)總條數(shù)如表8所示。

表8 不同對(duì)局下的數(shù)據(jù)條數(shù) (萬(wàn)條)

在本節(jié)中，將使用機(jī)器學(xué)習(xí)算法XGB構(gòu)建模型，將預(yù)測(cè)勝負(fù)轉(zhuǎn)化為一個(gè)二分類任務(wù)。首先，為每一種匹配類型設(shè)計(jì)一個(gè)單獨(dú)的模型，用于預(yù)測(cè)不同對(duì)局下的實(shí)時(shí)勝率。

XGBoost[9]是Gradient Boosting方法的一個(gè)特定實(shí)現(xiàn)，使用更精確的近似來(lái)找到最佳樹(shù)模型。它采用了許多漂亮的技巧，使其非常成功，尤其是結(jié)構(gòu)化數(shù)據(jù)。最重要的是，計(jì)算二階梯度，即損失函數(shù)的二階導(dǎo)數(shù)(類似于牛頓方法)，其提供了關(guān)于梯度方向以及如何達(dá)到損失函數(shù)最小值的更多信息和高級(jí)正則化(L1和L2)，提升了模型的泛化能力[10]。

將數(shù)據(jù)集按照6：2：2分為訓(xùn)練集、驗(yàn)證集和測(cè)試集，在訓(xùn)練過(guò)程中對(duì)樣品進(jìn)行了10次交叉驗(yàn)證。為了避免偏差，對(duì)于任意對(duì)局，樣本要么在訓(xùn)練集中，要么在測(cè)試集中，但不同時(shí)存在。如表9所示，B代表基本特征情況下的準(zhǔn)確率，B+S代表組合特征情況下的準(zhǔn)確率。

表9 基本特征與組合特征下的實(shí)時(shí)準(zhǔn)確率 (%)

從上述實(shí)驗(yàn)結(jié)果可以看出,本文提出的組合特性的預(yù)測(cè)效果比單獨(dú)使用基礎(chǔ)特征的效果要好。

3 結(jié)束語(yǔ)

游戲?qū)崟r(shí)勝率預(yù)測(cè)是游戲AI的重要一環(huán)，本文通過(guò)使用SC2LE公開(kāi)的數(shù)據(jù)集構(gòu)建特征數(shù)據(jù)集，分析了不同匹配對(duì)局下使用基礎(chǔ)特征和統(tǒng)計(jì)特征時(shí)不同模型的研究結(jié)果，結(jié)果表明，在基礎(chǔ)特性中加入統(tǒng)計(jì)特性能夠提升實(shí)時(shí)勝率預(yù)測(cè)的準(zhǔn)確率。通過(guò)使用本文中的預(yù)測(cè)模型，可以解決在游戲AI中使用強(qiáng)化學(xué)習(xí)時(shí)關(guān)于獎(jiǎng)勵(lì)稀疏的問(wèn)題，能夠加快強(qiáng)化學(xué)習(xí)的模型訓(xùn)練。