梁品策，王紹一，于琪佳

（北方工業(yè)大學(xué)信息學(xué)院，北京100144）

0 引言

在最近的幾年中，隨著中國(guó)電子計(jì)算機(jī)的飛速發(fā)展。游戲行業(yè)特別是對(duì)戰(zhàn)類游戲得到了飛速的發(fā)展。市場(chǎng)上類似《邊境》、《黑神話悟空》等佳作也走入了大眾的視野。但隨著現(xiàn)代圖形開發(fā)技術(shù)的發(fā)展，決定一款游戲的好壞不再?zèng)Q于游戲畫面的好壞，高可玩性也成為了一款游戲是否優(yōu)秀的重要指標(biāo)。

無(wú)論是第一人稱對(duì)戰(zhàn)游戲還是策略對(duì)戰(zhàn)游戲，一個(gè)優(yōu)秀的游戲AI 將會(huì)極大地提升游戲的可玩性。但在目前的對(duì)戰(zhàn)游戲中，很少有利用遺傳算法的對(duì)AI 進(jìn)行訓(xùn)練的案例。有之前的研究中，有研究人員利用遺傳算法對(duì)FC 經(jīng)典游戲洛克人的游戲AI 進(jìn)行訓(xùn)練。在該實(shí)驗(yàn)中研究人員通過(guò)不同AI 之間相互的戰(zhàn)斗，針對(duì)每個(gè)AI 的存活率、命中率等一系列標(biāo)準(zhǔn)篩選強(qiáng)大的個(gè)體。在經(jīng)歷了多次的訓(xùn)練以及迭代后，新AI 可以對(duì)玩家的攻擊進(jìn)行規(guī)避，并且擁有了更強(qiáng)的攻擊欲望以及攻擊精度。獲得了相較于原AI 更加具有挑戰(zhàn)性的游戲AI。該研究證明遺傳算法可以運(yùn)用到游戲AI 的訓(xùn)練中。但目前的研究中尚未有人將遺傳算法運(yùn)用到三維對(duì)戰(zhàn)游戲中。本次研究中將制作一個(gè)簡(jiǎn)易的三維坦克大戰(zhàn)游戲，并運(yùn)用遺傳算法訓(xùn)練其中的AI。

相較于二維游戲，三維游戲中AI 面對(duì)的環(huán)境相較于二維游戲更加復(fù)雜，所包含的行動(dòng)也更加豐富，以移動(dòng)為例，在二維游戲中，AI 只用操縱角色左右移動(dòng)，但在三維游戲中，AI 不僅要操縱角色前進(jìn)后退，還要操縱角色旋轉(zhuǎn)，在更為復(fù)雜的游戲中，還要操縱角色的跳躍功能。若使用傳統(tǒng)遺傳算法將會(huì)導(dǎo)致訓(xùn)練成本無(wú)限增大。因此在本實(shí)驗(yàn)中將行為樹結(jié)構(gòu)應(yīng)用于遺傳算法中，以此提升遺傳算法AI 的訓(xùn)練效率。

遺傳算法訓(xùn)練出優(yōu)秀的游戲AI 從而提高游戲可玩性將會(huì)是本研究的主要目標(biāo)。

1 遺傳算法和行為樹

1.1 遺傳算法簡(jiǎn)介

遺傳算法（Genetic Algorithm，GA）最早是由美國(guó)的John Holland 于20 世紀(jì)70 年代提出。它將達(dá)爾文進(jìn)化論的原理引入編碼串集合中，通過(guò)對(duì)自然界中的動(dòng)物基因變異，遺傳，交換等現(xiàn)象的模擬，在編碼串群體間進(jìn)行有規(guī)律的但又具有一定隨機(jī)性的交換。隨著交換的進(jìn)行，根據(jù)“優(yōu)勝劣汰”的原則，適應(yīng)性高的個(gè)體被保留下來(lái)并重新組合，進(jìn)而產(chǎn)生新的個(gè)體，直至產(chǎn)生最優(yōu)解。

基于傳統(tǒng)遺傳算法的AI 訓(xùn)練的步驟如下：

（1）根據(jù)需求制定合適的數(shù)據(jù)結(jié)構(gòu)，作為接下來(lái)實(shí)現(xiàn)算法的基因。

（2）明確獎(jiǎng)勵(lì)機(jī)制，作為基因進(jìn)行自然選擇的標(biāo)準(zhǔn)。

（3）確定遺傳算法的適應(yīng)函數(shù)，以及交叉概率、變異概率。

（4）隨機(jī)生成一定數(shù)量的樣本。

（5）對(duì)樣本使用適應(yīng)函數(shù)，計(jì)算出其在該環(huán)境下獲得的分?jǐn)?shù)。

（6）根據(jù)得分對(duì)樣本進(jìn)行淘汰。

（7）判斷AI 是否已經(jīng)訓(xùn)練達(dá)到預(yù)期水平。

1.2 行為樹簡(jiǎn)介

行為樹（Behavior Tree）是一種用于控制AI 決策行為的、包含了層級(jí)節(jié)點(diǎn)的樹狀數(shù)據(jù)結(jié)構(gòu)，高層級(jí)的行為由各個(gè)低層級(jí)的分支行為組成。它通過(guò)類似于決策樹的樹形決策結(jié)構(gòu)來(lái)選擇當(dāng)前環(huán)境下應(yīng)該做出的具體行為。在每次執(zhí)行前，行為樹都會(huì)對(duì)整個(gè)行為樹進(jìn)行一次深度遍歷，然后根據(jù)優(yōu)先級(jí)執(zhí)行行動(dòng)。

行為樹的節(jié)點(diǎn)一般有三種狀態(tài)：未激活、激活和執(zhí)行。每一個(gè)節(jié)點(diǎn)都有一個(gè)狀態(tài)，對(duì)于組合節(jié)點(diǎn)的狀態(tài)就是其每個(gè)子狀態(tài)。這對(duì)于并行節(jié)點(diǎn)來(lái)說(shuō)有點(diǎn)難以判定，因?yàn)槎鄠€(gè)子節(jié)點(diǎn)的狀態(tài)可能不相同。對(duì)此一般有兩種解決方案：

（1）當(dāng)所有子節(jié)點(diǎn)執(zhí)行完畢后再返回狀態(tài)；

（2）當(dāng)?shù)谝粋€(gè)子節(jié)點(diǎn)結(jié)束后，則立刻返回狀態(tài)。

節(jié)點(diǎn)的狀態(tài)判定十分重要，一方面外界需要了解當(dāng)前狀態(tài)，以確定下一步采取的決策；另一方面，只有當(dāng)所有的狀態(tài)執(zhí)行完畢后，行為樹才會(huì)進(jìn)行更新行動(dòng)。

2 基于行為樹的改進(jìn)遺傳算法

2.1 對(duì)于輸入數(shù)據(jù)的處理

當(dāng)一個(gè)AI 接收的信息過(guò)多時(shí)，遺傳算法的輸入將會(huì)不可避免的膨脹，從而導(dǎo)致算法占用大量的內(nèi)存。此時(shí)，模糊邏輯會(huì)起到極大的作用，依然以坦克AI 為例，如果每一種血量都算一個(gè)數(shù)據(jù)的話那么坦克輸入數(shù)據(jù)則會(huì)無(wú)限擴(kuò)大，我們可以根據(jù)血量的不同將血量設(shè)定為高中低三個(gè)狀態(tài)。這將極大地避免內(nèi)存的占用。根據(jù)輸入數(shù)據(jù)的多少，可以組成一個(gè)1×n 矩陣。在本游戲中這將會(huì)是一個(gè)1×4 矩陣。對(duì)應(yīng)坦克感知系統(tǒng)觀測(cè)到的四個(gè)數(shù)據(jù)：①附近友軍數(shù)量，②附近敵軍數(shù)量，③自身血量高低，④最近友方據(jù)點(diǎn)是否安全。

輸入矩陣：X=[x1x2x3x4]。

2.2 行為樹節(jié)點(diǎn)處理

在默認(rèn)的行為樹節(jié)點(diǎn)中每一個(gè)節(jié)點(diǎn)都擁有前置條件以此判斷該節(jié)點(diǎn)是否執(zhí)行，并激活子節(jié)點(diǎn)。但這也使行為樹整體失去了自我進(jìn)化的能力。我們?cè)O(shè)定每一個(gè)節(jié)點(diǎn)擁有四個(gè)權(quán)重w，對(duì)應(yīng)四個(gè)輸入的數(shù)據(jù)。四個(gè)輸入數(shù)據(jù)與四個(gè)權(quán)重一一相乘之后相加獲得最終數(shù)據(jù)y，由y 值判斷該節(jié)點(diǎn)是否被執(zhí)行。

每一個(gè)節(jié)點(diǎn)都將擁有一個(gè)1×4 的權(quán)重矩陣。

節(jié)點(diǎn)權(quán)重矩陣：w=[w1w2w3w4]

每一個(gè)坦克的行為樹，去除根節(jié)點(diǎn)和基本的選擇節(jié)點(diǎn)有5 個(gè)節(jié)點(diǎn)，相應(yīng)的一個(gè)行為樹擁有一個(gè)5×4 的重矩陣。為每一個(gè)節(jié)點(diǎn)的權(quán)重矩陣的相加之和。

行為樹權(quán)重矩陣：W=[w11w12w12w14]

[w21w22w22w24]

[w31w32w32w34]

[w41w42w42w44]

[w51w52w52w54]

將輸入矩陣與行為樹的權(quán)重矩陣的轉(zhuǎn)置矩陣相乘獲得結(jié)果矩陣Y：

X*W.transpose=Y

Y 為一個(gè)1×5 的矩陣。

當(dāng)行為樹的節(jié)點(diǎn)被激活后尋找Y 中的對(duì)應(yīng)數(shù)據(jù)，當(dāng)Y 中的對(duì)應(yīng)數(shù)據(jù)大于4，則執(zhí)行該節(jié)點(diǎn)。

2.3 遺傳算法的運(yùn)用

本研究利用遺傳算法改進(jìn)行為樹，其具體步驟為：

（1）設(shè)定算法的基本參數(shù)。

（2）以行為樹的權(quán)重矩陣作為染色體。

（3）設(shè)定獎(jiǎng)勵(lì)機(jī)制。

戰(zhàn)斗結(jié)束后，獲勝的一方獲得100 分獎(jiǎng)勵(lì)。若在600 秒之內(nèi)獲勝，則根據(jù)剩余時(shí)間給予獲勝方額外分?jǐn)?shù)，并減少失敗方分?jǐn)?shù)。為了加快訓(xùn)練速度，可以設(shè)置一些比較具有攻擊性的獎(jiǎng)勵(lì)機(jī)制如雙方每擁有1 個(gè)據(jù)點(diǎn)便獲得20 分，并根據(jù)雙方造成的傷害獲得分?jǐn)?shù)。這樣將會(huì)鼓勵(lì)更加激進(jìn)的坦克組，避免雙方采取龜縮戰(zhàn)術(shù)導(dǎo)致死局。

（4）初始化

在訓(xùn)練開始之前，初始化20 個(gè)行為樹組，每組含有7 個(gè)行為表，對(duì)應(yīng)7 個(gè)坦克。隨后行為樹組隨機(jī)分為5 組，5 組之間進(jìn)行對(duì)戰(zhàn)。獲得初始樣本。

（5）遺傳與變異

保留得分最高的8 個(gè)行為表組，將剩余12 個(gè)中的8個(gè)進(jìn)行變異：其行為表中的行為有1/4 的幾率變?yōu)槠渌袨?。剩? 個(gè)通過(guò)得分最高的8 個(gè)行為表組兩兩交配獲得：即新的行為表的每一個(gè)行為有一般幾率來(lái)自父方，一般幾率來(lái)自女方。最后將所有樣本的得分清零。

（6）測(cè)試

游戲分為漫游模式以及游玩模式，在漫游模式下，玩家可以觀測(cè)不同樣本之間的對(duì)戰(zhàn)過(guò)程，在游玩模式下，玩家可以指定一組樣本與得分最高的樣本進(jìn)行對(duì)戰(zhàn)，并親自控制一輛坦克參與到游戲當(dāng)中。查看訓(xùn)練的樣本是否已經(jīng)達(dá)到預(yù)期。若已經(jīng)達(dá)到預(yù)期則可以停止訓(xùn)練。若不符合預(yù)期則繼續(xù)進(jìn)行遺傳與變異與測(cè)試適應(yīng)度兩個(gè)流程。

圖1 遺傳算法流程圖

3 坦克大戰(zhàn)游戲設(shè)計(jì)與實(shí)現(xiàn)

3.1 游戲設(shè)定以及機(jī)制

本研究將制作一款簡(jiǎn)易的3D 坦克大戰(zhàn)游戲。本該游戲是基于Unity3D 開發(fā)的一款可以用于PC 端的坦克對(duì)戰(zhàn)游戲。

游戲勝利機(jī)制：設(shè)定對(duì)戰(zhàn)雙方各擁有7 輛坦克進(jìn)行對(duì)戰(zhàn)，若玩家加入可操控一輛坦克。場(chǎng)上擁有5 個(gè)據(jù)點(diǎn)，坦克接近據(jù)點(diǎn)后可以占領(lǐng)據(jù)點(diǎn)，占領(lǐng)了全部據(jù)點(diǎn)的一方將會(huì)取得勝利。為了防止在訓(xùn)練中出現(xiàn)死局，設(shè)定600 秒時(shí)間限制，600 秒過(guò)后擁有據(jù)點(diǎn)數(shù)較多的一方獲勝。

坦克單位設(shè)定：每個(gè)坦克單位擁有100 點(diǎn)血量?？梢赃M(jìn)行攻擊，當(dāng)坦克攻擊時(shí)，坦克將會(huì)射出子彈。子彈碰撞到坦克后，坦克的血量將會(huì)減少，為了增加一些對(duì)戰(zhàn)的策略性，我們?cè)O(shè)定當(dāng)坦克的正前方受到傷害時(shí)，減少10 點(diǎn)血量。當(dāng)坦克的側(cè)面受到傷害時(shí)，減少20點(diǎn)血量。當(dāng)坦克的后方受到傷害時(shí)，減少40 點(diǎn)血量。

坦克感知系統(tǒng)：坦克擁有簡(jiǎn)單的視覺系統(tǒng)。可以觀測(cè)到坦克周圍友軍和敵軍的數(shù)量。坦克還有簡(jiǎn)單的感知系統(tǒng)，當(dāng)受到傷害后坦克可以判斷傷害的方向。

3.2 構(gòu)建坦克AI

游戲基礎(chǔ)的坦克AI 基于行為樹系統(tǒng)。坦克的觀察并接收環(huán)境數(shù)據(jù)，并根據(jù)此做出行為判斷，明確坦克在該行為下將會(huì)執(zhí)行那些行為。

坦克接收的信息包括：①附近友軍數(shù)量，②附近敵軍數(shù)量，③自身血量高低，④最近友方據(jù)點(diǎn)是否安全。

游戲中的坦克行為樹結(jié)構(gòu)如圖2 所示。

圖2 坦克行為樹

3.3 游戲截圖

圖3

圖4

4 結(jié)語(yǔ)

在最初的幾次子代中，攻守雙方大多是毫無(wú)意義的采取龜縮戰(zhàn)術(shù)。在經(jīng)過(guò)幾輪的自然選擇后，已經(jīng)出現(xiàn)了具有了一定的攻擊欲望的得分比較高的樣本。在經(jīng)過(guò)幾十代的自然選擇后攻守雙方出現(xiàn)了合作意識(shí)，出現(xiàn)了集體進(jìn)攻以及集體防御的趨勢(shì)。相信在系統(tǒng)的繼續(xù)繁衍下，每個(gè)樣本將會(huì)更加智能。

然而這一方法依然有缺陷，由于其訓(xùn)練時(shí)間與每次游戲的時(shí)長(zhǎng)成正相關(guān)，若游戲時(shí)長(zhǎng)不斷增長(zhǎng)其訓(xùn)練的時(shí)間成本也必然攀升。對(duì)此，可考慮在下一步的改進(jìn)中加入多線程訓(xùn)練，進(jìn)而克服此類問(wèn)題。