英语原文共 11 页，支付完成后下载完整资料
实时策略游戏中基于案例规划的神经进化模型
摘 要
实时策略游戏AI的开发是一项具有挑战性和难度的任务，因为在寻找最佳策略时存在着实时性的限制和较大的搜索空间。本文提出了一种基于遗传算法和人工神经网络的机器学习方法，建立了基于案例的实时策略(RTS)规划的神经进化模型。该模型为解决RTS游戏问题提供了高效、公平、自然的游戏AI。实验结果支持了我们的观点。该模型可以与战场上的作战机器人集成，无论是真实的还是合成的，在未来模拟类似人类的行为。
许多有趣的问题都是以游戏的形式出现的。军事、外交使团和商界广泛使用游戏来协助规划未来的行动路线和决策。在研究中，游戏经常被用作开发问题解决技术的场所。研究游戏的解决方案，即使是简单的解决方案，也是有意义的，因为学到的经验教训可以应用到现实世界的情况中。
一段时间以来，博弈一直是计算科学研究的一个主题。像八到十五张拼图、井字游戏和河内塔这样的问题经常被使用。这些在本质上都相当简单。更复杂的游戏，如跳棋和国际象棋也被解决。在这些游戏中，像结束游戏策略这样的子问题可能是调查的主题，也可能是整个游戏本身的主题。
一般来说，游戏和战争游戏都可能包含不确定性。一种不确定性与在游戏规则框架内工作的变量有关。敌人会采取什么行动，掷什么骰子，或者出什么牌，这些都是不确定的。第一类不确定性可以在战争游戏以及许多其他类型的游戏中找到。第二种不确定性与游戏规则本身的不确定性有关，这种不确定性存在于战争游戏中，但并非大多数其他游戏中。在现实世界中，比如战争游戏所模拟的情况中，获胜所需的具体细节通常是未知的。举个例子，一个军事对手在投降前会接受多少惩罚是事先不知道的。他们可能愿意战斗到最后。他们也可能只愿意容忍一定程度的经济和军事破坏，然后才会为了确保政权的存续而认输。规则的不确定性使确定好的战争游戏策略的任务复杂化。
关键词：基于案例的规划；实时策略(RTS)博弈；遗传算法；人工神经网络
第1章 绪论
计算机游戏为人工智能(AI)研究提供了一个理想的平台。例如，传统的技术，如有限状态机、搜索、逻辑和基于规则的推理，已经被证明对开发游戏AI应用程序非常有用。
在人工智能领域，已经开发出各种方法来玩各种各样的机器游戏。对于像8或15个没有活跃竞争对手的谜题游戏，可以使用状态空间树来表示问题。启发式搜索技术，如A*算法，用于搜索树的目标节点。评估函数用于估计当前节点到目标节点的距离。这种方法很难适用于规则不确定的战争游戏。由于不知道目标节点的位置，状态空间变得难以定义。估计到目标节点的距离以便评估要采取的几种路径中的哪一种也比较困难。在战争游戏中，可能有不止一个潜在的目标。达到任何一个目标都能赢得比赛。每次比赛时，这些目标的价值都会改变。像跳棋这样有两名玩家的游戏中，状态机树表示被机器所使用。状态机的搜索使用了一种类似于极大极小算法的技术。评估函数用于估计由移动和对手的反移动产生的位置值。使用计算机玩跳棋和类似游戏的大部分工作还涉及积累专家知识和应用强大的计算资产进行广泛的搜索。
依赖人工智能的即时战略游戏《魔兽争霸》(Blizzard Entertainment, Inc.)和《帝国时代》(Microsoft Inc.)吸引了全球数百万用户通过互联网在线玩游戏。这些游戏不仅提供了一个娱乐平台，而且提供了一个交友、聊天、广告、交易等社交活动的互动环境。在这些RTS游戏中，有许多吸引人的功能，例如有趣的3D景观，吸引人的化身，虚拟货币和资源，这些都是由游戏玩家和第三方制作、控制、操纵或收集的。然而，目前的游戏应用架构并不能很好地支持利用用户贡献的内容来获得更好的游戏可玩性。困难在于，目前电脑游戏中使用的人工智能算法大多是基于启发式的。算法的可移植性较差。例如, 游戏开发者可以通过启发式规则在一个预定义的地图指定计算机生成RTS游戏团队角色,但在一个新的地图创建的用户由于缺少规则来处理这个新情况导致可能无法正确的运行。为了解决这一不足，我们建议在游戏中构建一个机器学习组件，这样角色就可以直接从数据中学习决策和行动，而无需使用启发式。我们已经建立了一个原型系统来测试我们的想法。该系统旨在模仿人类的能力，人们可以学习和计划解决问题，首先尝试和努力找出“好的”解决方案，然后记住正确的答案，以便在未来快速做出决定。结果表明了该方法的可行性和有效性。
本文由六个主要部分组成。第二部分介绍了问题及其背景。第三部分提出了我们的方法和算法。第四部分给出了实验结果，第五部分给出了结论。
第2章 问题背景及描述
当前的游戏AI方法类似于“上帝”AI。即它知道所有的用户操作。但在这种安排下，玩家很快就会失去兴趣。例如，当使用有限状态机[1]设计和表示游戏逻辑时(通常基于硬编码参数的输入)，一旦发现使用了重复的模式，玩家可能会很快失去兴趣。此外，此过程需要大量时间来微调参数，并且常常依赖于试错法。一旦玩家发现游戏行为有些“硬编码”，他们可能会感到失望。因此，机器学习方法可能是引入类人行为的更好选择。Hsieh[2]使用300名专业游戏玩家的回放，在一个战场上训练决策系统。结果是在战斗中，机器人的行为更像人类。 Zanetti[3]和Nicholas Cole[4]使用遗传算法开发第一人称射击游戏AI。Salge[5]也将机器学习技术应用于回合策略游戏中。Louis[6]开发了一种用于RTS游戏中NPC动作的案例注入遗传算法。这些研究告诉我们AI在RTS游戏中越来越受欢迎。我们将在接下来的章节中扩展这个机器学习的概念，并介绍我们的技术和仿真数据。
2.1 遗传算法
遗传算法(GA)于1975年由John Henry Holland[7]首次提出。它是一种基于人类进化概念寻找近似解的搜索技术。遗传算法是为大型、非线性和难以理解的搜索空间设计的，在这些搜索空间中，启发式搜索是不合适的。在RTS博弈中，遗传算法可以作为一种基于自然选择的引导随机游走技术来寻找最优解。然而，使用遗传算法开发RTS游戏策略也面临一些困难。首先是如何设计针对大型复杂问题的遗传算法编码方案，如计算机游戏。在美国，使用二进制DNA很难代表整个战场。其次是如何设计适合度函数来评价染色体。第三是实时约束。
2.2 人工神经网络
人工神经网络是一种基于生物神经网络的数学模型或计算模型。神经网络作为一种自适应学习系统，可以根据外部信息改变其权重。同样，ANN很少用于游戏开发。直到最近，David M. Bourg和Glenn Seemann[8]才开始讨论在游戏中使用ANN。
第3章 问题描述和提出的方法
在任何RTS游戏中都有许多可能的游戏玩法，在本文中，我们选择了一个基础防御场景作为我们技术的测试平台(例如《魔兽争霸》中的塔防)。情况描述如下。
1. 在战场上创建两个团队。一个是攻击队(敌人)。另一个是防守队员。
2. 敌人必须移动到防御队的基地并进攻。
3.防御小组可以在战场上设置一些加农炮(例如，10门或15门)，当敌人接近他们的基地时就可以杀死他们。
4. 目标是创造最大的伤亡给敌人，无论他们选择哪条道路接近基地。
3.1 分而治之
由于在遗传算法中很难设计一个二进制染色体来表示整个RTS游戏，所以我们的概念是将游戏分成更小的部分。这也使得适应度函数更容易表述。因此，在本研究工作中，染色体编码只关注基地防御。与[9]空间推理的概念相似，战场也可以划分为不同的较小的子域和不同的峡谷。在我们的仿真中，我们可以将战场划分为四个不同的较小的子域 (或地图)，如图1所示 。
峡谷1 峡谷2 峡谷3 峡谷4
图1所示。四个不同的峡谷。它们代表了RTS游戏中的共同场景。
将战场划分为更小的子战场也给了我们两个优势。首先，适应度函数可以更有效地工作。没有峡谷的开放区域将不被考虑，因为它不会影响解决方案，但是会因为搜索空间的增加而增加运行时间。
3.2遗传算法
遗传算法需要设计两个关键的组件。首先是二进制编码方案。它是解的遗传表示。
编码所需的长度取决于战场的面积和可能的障碍。这里我们用一个例子来演示编码思想，如图2所示。在战场上使用一张5x5单位的地图和5门大炮。在这里，白色圆圈表示可以设置大炮的开放区域(即位置)。黑色圆圈表示无法设置火炮的障碍物。灰色圆圈表示加农炮设置的位置。编码的总比特数取决于可用于设置大炮的开放区域的大小(即编码位=总面积-屏障面积)。在这个例子中，它是13位。在地图上随机设置五门大炮，如图2所示。炮的每个分布的编码被表示为一个染色体。
图2 演示了遗传算法的编码
在这个模拟中，将使用50x50单位地图，并在地图上设置15门大炮。染色体的长度如表1所示。
表1 染色体的长度
另一个重要的组成部分是评估解决方案的适应度函数。在我们的模拟中，为了更好更快地收敛遗传过程，每一代选择50条染色体。评估功能测量敌人的伤亡(或对他们造成的伤害)。
在15门加农炮设置好后，敌人会试图找到攻击玩家基地的最佳路径。敌人被给予一定的速度(v)。它将在大炮的攻击范围内受到伤害。伤害(命中点)按上面式(1)计算。将不同加农炮所造成的各炮种的损伤进行综合计算，得到总损伤值，成为本次仿真的适应度值。敌人受到的伤害越大，大炮的位置就越合适。加农炮的位置将根据这个适应度值进行排序，并用于产生子代弹簧片。
第4章 测试安排及结果
这个模拟是使用Intel Pentium IV 2.4GHz机器，在Windows XP下使用1.5 GB 内存完成的。仿真工具为MathWorks Matlab 7.0。结果如图3所示。
图3所示。火炮分布(GA优化)
4.1不同世代的结果
评估功能是根据对敌人造成的伤害来设计的。在仿真过程中，经过100代后，适应度并没有明显的变化，如图4所示，即结果稳定下来。这一稳定结果与ChuenTsai Sun [10]和Yi Jack [11]的结果相似。
图4所示 对不同世代的敌人造成伤害
4.2 利用人工神经网络加速过程
遗传算法是一个耗时的过程。表2为不同峡谷数GA的运行时间。使用遗传算法的平均运行时间为1947秒，这在RTS游戏和现实世界战场中是不可接受的。
表2 使用GA的运行时间(人口规模:50，世代:150)
为了克服这个问题，我们建议使用人工神经网络(ANN)来加速整个过程。我们提出的神经进化模型如图5所示。首先，将确定火炮分布的给定地形信息编码为染色体。染色体产生了不同的世代。通过健康评估，将产生最好的后代（即炮火分布）。这些最佳的火炮分布可以作为神经网络训练的输入。在此基础上，针对不同地形的新战场，提出了一种快速、直观的火炮位置预测方法。
图5 进化神经网络模型
模型中基于案例的规划思想如下。我们使用与遗传算法训练得到的1、2、3和4个峡谷对应的4个最佳解(案例)作为ANN的输入。对于每种情况，具有一定半径的每个点都将被视为ANN的一个输入。例如，图6中所示的点A将是一个输入。围绕点A的8个点将被编码。“-1”表示障碍，“1”表示开放区域，最后一个数字“d”表示点A到球员底端的距离。
图6 点A编码
编码变成[-1 -1 -1 -1 -1 -1 -1 - d]。ANN学习的目的是近似我们在式(2)中得到的最优位置函数，其定义为数值越大，设置火炮的位置越好。它是基于A点目前的地形，以前使用遗传算法找到的大炮位置和到基地的距离之间的关系。
(A1, A2)为a点坐标，n为炮身总数，即， n=15。(K1, K2)为火炮K的坐标，r为控制f(点a)扩散的参数，神经网络训练采用反向传播和log-sigmoid输出函数。隐藏层的数量计算为编码字符串长度的平方根。在这个例子中，它将是，如图7所示。
图7 人工神经网络结构
人工神经网络的训练时间为125.95秒。图8给出了遗传算法和人工神经网络的计算结果。它在火炮分布上显示了类似的结果，但是在运行时间上有了很大的改进，如表3所示。
图8所示 火炮分布(遗传算法与人工神经网络比较)
表3 人工神经网络的运行时间(人口规模:50，世代:150)
4.3 将所有结果合并成一个战场
经过人工神经网络的训练，我们的机器学习组件变得非常有用。在图9(a)中，它显示了RTS游戏中常见的战场(例如，场景中的许多峡谷)。遗传算法和人工神经网络的计算结果相似，但在Pentium IV环境下，战场上分配火炮的运行时间仅为21.266秒。如图9(b)和图10所示，该组件在更“真实世界”的战场上也非常有用。
图9所示 (a)遗传算法与人工神经网络的比较。(b)使用人工神经网络的结果
图10所示 利用神经网络在随机战场上分布火炮
第五章 结论与未来任务
本文提出了一种基于案例的实时策略博弈神经进化模型。我们相信这一研究方向能够为RTS游戏提供一个高效、公平、自然的AI开发。基地防御将只是我们当前和未来工作评估的一部分。我们将在未来的研究中扩展这一理念并结合RTS游戏中的其他关键组件，如资源管理和战斗策略。
参考文献
1. Lent, M.V.,
资料编号：[3175]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
