基于改進(jìn)遺傳算法的坦克大戰(zhàn)游戲設(shè)計

梁品策，王紹一，于琪佳

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

0 引言

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

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

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

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

1 遺傳算法和行為樹

1.1 遺傳算法簡介

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

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

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

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

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

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

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

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

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

1.2 行為樹簡介

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

行為樹的節(jié)點一般有三種狀態(tài)：未激活、激活和執(zhí)行。每一個節(jié)點都有一個狀態(tài)，對于組合節(jié)點的狀態(tài)就是其每個子狀態(tài)。這對于并行節(jié)點來說有點難以判定，因為多個子節(jié)點的狀態(tài)可能不相同。對此一般有兩種解決方案：

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

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

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

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

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

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

輸入矩陣：X=[x1x2x3x4]。

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

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

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

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

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

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

[w21w22w22w24]

[w31w32w32w34]

[w41w42w42w44]

[w51w52w52w54]

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

X*W.transpose=Y

Y 為一個1×5 的矩陣。

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

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

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

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

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

（3）設(shè)定獎勵機(jī)制。

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

（4）初始化

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

（5）遺傳與變異

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

（6）測試

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

圖1 遺傳算法流程圖

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

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

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

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

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

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

3.2 構(gòu)建坦克AI

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

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

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

圖2 坦克行為樹

3.3 游戲截圖

圖3

圖4

4 結(jié)語

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

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