基于改进遗传算法的坦克大战游戏设计

梁品策，王绍一，于琪佳

（北方工业大学信息学院，北京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 结语

在最初的几次子代中，攻守双方大多是毫无意义的采取龟缩战术。在经过几轮的自然选择后，已经出现了具有了一定的攻击欲望的得分比较高的样本。在经过几十代的自然选择后攻守双方出现了合作意识，出现了集体进攻以及集体防御的趋势。相信在系统的继续繁衍下，每个样本将会更加智能。

然而这一方法依然有缺陷，由于其训练时间与每次游戏的时长成正相关，若游戏时长不断增长其训练的时间成本也必然攀升。对此，可考虑在下一步的改进中加入多线程训练，进而克服此类问题。