基于改進遺傳算法的坦克大戰游戲設計

梁品策，王紹一，于琪佳

（北方工業大學信息學院，北京100144）

0 引言

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

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

相較于二維游戲，三維游戲中AI 面對的環境相較于二維游戲更加復雜，所包含的行動也更加豐富，以移動為例，在二維游戲中，AI 只用操縱角色左右移動，但在三維游戲中，AI 不僅要操縱角色前進后退，還要操縱角色旋轉，在更為復雜的游戲中，還要操縱角色的跳躍功能。若使用傳統遺傳算法將會導致訓練成本無限增大。因此在本實驗中將行為樹結構應用于遺傳算法中，以此提升遺傳算法AI 的訓練效率。

遺傳算法訓練出優秀的游戲AI 從而提高游戲可玩性將會是本研究的主要目標。

1 遺傳算法和行為樹

1.1 遺傳算法簡介

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

基于傳統遺傳算法的AI 訓練的步驟如下：

（1）根據需求制定合適的數據結構，作為接下來實現算法的基因。

（2）明確獎勵機制，作為基因進行自然選擇的標準。

（3）確定遺傳算法的適應函數，以及交叉概率、變異概率。

（4）隨機生成一定數量的樣本。

（5）對樣本使用適應函數，計算出其在該環境下獲得的分數。

（6）根據得分對樣本進行淘汰。

（7）判斷AI 是否已經訓練達到預期水平。

1.2 行為樹簡介

行為樹（Behavior Tree）是一種用于控制AI 決策行為的、包含了層級節點的樹狀數據結構，高層級的行為由各個低層級的分支行為組成。它通過類似于決策樹的樹形決策結構來選擇當前環境下應該做出的具體行為。在每次執行前，行為樹都會對整個行為樹進行一次深度遍歷，然后根據優先級執行行動。

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

（1）當所有子節點執行完畢后再返回狀態；

（2）當第一個子節點結束后，則立刻返回狀態。

節點的狀態判定十分重要，一方面外界需要了解當前狀態，以確定下一步采取的決策；另一方面，只有當所有的狀態執行完畢后，行為樹才會進行更新行動。

2 基于行為樹的改進遺傳算法

2.1 對于輸入數據的處理

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

輸入矩陣：X=[x1x2x3x4]。

2.2 行為樹節點處理

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

每一個節點都將擁有一個1×4 的權重矩陣。

節點權重矩陣：w=[w1w2w3w4]

每一個坦克的行為樹，去除根節點和基本的選擇節點有5 個節點，相應的一個行為樹擁有一個5×4 的重矩陣。為每一個節點的權重矩陣的相加之和。

行為樹權重矩陣：W=[w11w12w12w14]

[w21w22w22w24]

[w31w32w32w34]

[w41w42w42w44]

[w51w52w52w54]

將輸入矩陣與行為樹的權重矩陣的轉置矩陣相乘獲得結果矩陣Y：

X*W.transpose=Y

Y 為一個1×5 的矩陣。

當行為樹的節點被激活后尋找Y 中的對應數據，當Y 中的對應數據大于4，則執行該節點。

2.3 遺傳算法的運用

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

（1）設定算法的基本參數。

（2）以行為樹的權重矩陣作為染色體。

（3）設定獎勵機制。

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

（4）初始化

在訓練開始之前，初始化20 個行為樹組，每組含有7 個行為表，對應7 個坦克。隨后行為樹組隨機分為5 組，5 組之間進行對戰。獲得初始樣本。

（5）遺傳與變異

保留得分最高的8 個行為表組，將剩余12 個中的8個進行變異：其行為表中的行為有1/4 的幾率變為其他行為。剩余4 個通過得分最高的8 個行為表組兩兩交配獲得：即新的行為表的每一個行為有一般幾率來自父方，一般幾率來自女方。最后將所有樣本的得分清零。

（6）測試

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

圖1 遺傳算法流程圖

3 坦克大戰游戲設計與實現

3.1 游戲設定以及機制

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

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

坦克單位設定：每個坦克單位擁有100 點血量。可以進行攻擊，當坦克攻擊時，坦克將會射出子彈。子彈碰撞到坦克后，坦克的血量將會減少，為了增加一些對戰的策略性，我們設定當坦克的正前方受到傷害時，減少10 點血量。當坦克的側面受到傷害時，減少20點血量。當坦克的后方受到傷害時，減少40 點血量。

坦克感知系統：坦克擁有簡單的視覺系統。可以觀測到坦克周圍友軍和敵軍的數量。坦克還有簡單的感知系統，當受到傷害后坦克可以判斷傷害的方向。

3.2 構建坦克AI

游戲基礎的坦克AI 基于行為樹系統。坦克的觀察并接收環境數據，并根據此做出行為判斷，明確坦克在該行為下將會執行那些行為。

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

游戲中的坦克行為樹結構如圖2 所示。

圖2 坦克行為樹

3.3 游戲截圖

圖3

圖4

4 結語

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

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