首页 文章

实时策略的算法战争游戏AI

提问于
浏览
23

我正在设计一个实时策略战争游戏,其中AI将负责控制大型六边形 Map 上的大量单位(可能是1000) .

一个单位有许多动作点可以用于移动,攻击敌方单位或各种特殊行动(例如 Build 新单位) . 例如,一个有5个动作点的坦克可以在移动中花费3,然后在范围内对敌人射击2 . 不同的单位对不同的行为等有不同的成本

一些额外的说明:

  • AI的输出是任何给定单位的"command"

  • 动作点在一段时间的开始分配,但可以在该时间段内的任何时间点使用(这是为了允许实时多人游戏) . 因此"do nothing and save action points for later"是一种潜在有效的战术(例如无法移动等待敌人进入射程的炮塔)

  • 游戏正在实时更新,但AI可以随时获得游戏状态的一致快照(感谢游戏状态是Clojure的持久性数据结构之一)

  • 我不期待"optimal"行为,只是一些不明显愚蠢的事情,并提供合理的乐趣/挑战

您可以在特定的算法/方法方面推荐什么,以便在效率和合理智能行为之间取得适当的 balancer ?

4 回答

  • 11

    这个问题范围很广 . 你基本上是在问如何编写策略游戏 .

    这些东西有大量的书籍和在线文章 . 我强烈推荐Game Programming Wisdom系列和AI Game Programming Wisdom系列 . 特别是,第一卷AI游戏编程智慧的第6节涵盖了一般架构,第7节涵盖了决策架构,第8节涵盖了特定类型的架构(8.2是RTS类型) .

  • 7

    这是一个很大的问题,其他答案指出了令人惊讶的资源 .

    我过去曾经处理过这个问题,并发现简单行为 - 表现 - 复杂/紧急的行为方法对于人类设计来说有点过于笨拙,除非在遗传/进化上接近 .

    我最终使用抽象的人工智能层,类似于现实生活中军队的工作方式 . 单位将与同一时间的附近单位分组成小队,这些小队与附近的小队分组以创建一个小型营 . 这里可以使用更多层(区域内的集团营等),但最终在顶层有高层战略人工智能 .

    每个图层只能向其正下方的图层发出命令 . 然后,它下面的层将尝试使用手头的资源(即该层下面的层)执行命令 .

    发给单个单元的命令的示例是“Go here”和“shoot at this target” . 发给更高级别的更高级别命令将是“安全此位置”,该级别将处理并向较低级别发出适当的命令 .

    最高级别的主人工智能负责董事会的战略决策,例如“我们需要更多____单位”,或“我们应该朝着这个位置前进” .

    军队的比喻在这里起作用;指挥官和中尉和指挥系统 .

  • 6

    首先,你的目标应该是让你的游戏在某种程度上为AI打开(即使你可以以某种方式模拟它转向,即使它可能不完全基于回合,在RTS中你可以将不连续的时间间隔分成轮流 . )其次,您应该确定AI应该使用多少信息 . 也就是说,如果AI被允许作弊并且知道其对手的每一步动作(从而使其变得更强)或者它应该知道更少或更多 . 第三,你应该定义一个州的成本函数 . 想法是更高的成本意味着计算机处于更糟的状态 . 第四,你需要一个移动生成器,生成AI可以从给定状态转换到的所有有效状态(这可能是同构的[状态无关的]或异构的[状态依赖性]) .

    问题是,成本函数将受到您确定状态的确切影响 . 您在状态中编码的信息越多,您的AI就会越 balancer ,但执行它的难度就越大,因为它必须以指数方式搜索您包含的每个其他状态变量(在详尽的搜索中) .

    如果您提供状态和成本函数的定义,您的问题将转换为AI中的一般问题,可以使用您选择的任何算法进行处理 .

    以下是我认为可行的内容摘要:

    • 如果你付出足够的努力,进化算法可能效果很好,但它们会增加一层复杂性,为其他可能出错的东西创造空间 . 他们还需要对健身功能等进行极大的调整 . 我没有太多使用这些的经验,但如果它们像神经一样网络(我相信它们都是由生物模型启发的启发式方法),你很快就会发现它们变幻无常且远非一致 . 最重要的是,我怀疑他们是否比我在3中描述的选项增加了任何好处 .

    • 在定义成本函数和状态的情况下,技术上可以应用梯度体面(假设状态函数是可微的且状态变量的域是连续的)但是这可能会产生较差的结果,因为最大的梯度下降的弱点正陷入局部极小 . 举一个例子,这种方法很容易像对待敌人一样,因为消灭它们的可能性非零 . 显然,这对于游戏来说可能不是理想的行为,然而,渐变体面是一种贪婪的方法并且不知道更好 .

    • 这个选项是我推荐的最高选项:模拟退火 . 模拟退火(IMHO)具有1的所有优点,没有增加的复杂性,同时比2更强大 . 本质上,SA只是各州之间的随机游走 . 因此,除了成本和状态之外,您还必须定义一种在状态之间随机转换的方法 . SA也不容易陷入局部最小值,同时产生非常好的结果 . SA所需的唯一调整就是制冷时间表 - 这决定了SA的收敛速度 . 我发现SA的最大优点是它在概念上很简单,并且在我尝试的大多数其他方法中凭经验产生了优异的结果 . 有关SA的信息可以在here找到,底部有一长串通用实现 .

    3B . (编辑后来添加了很多)SA和我上面列出的技术是一般的AI技术,而不是专门用于游戏的AI . 一般来说,算法越专业化,它就越有可能表现得更好 . 见免费午餐定理2 . 3的另一个扩展是称为并行回火的东西,它通过帮助它避免局部最优来显着改善SA的性能 . 关于平行回火的一些原始论文非常陈旧3,但其他论文已经更新4 .

    无论你最终选择何种方法,如前所述,将问题分解为状态和成本函数非常重要 . 根据经验,我将从20-50个状态变量开始,因为您的状态搜索空间在这些变量的数量中是指数的 .

  • 8

    如果您阅读Russell and Norvig,那么您最先进了 . 也就是说,我对使用贝叶斯算法成功接近多少个不同的问题类感到惊讶 .

    但是,在你的情况下,我认为每个单元都有自己的Petri网或推理引擎是个坏主意......只有那么多的CPU,内存和时间可用 . 因此,一种不同的方法:

    虽然在某些方面可能是一个疯子,但是Stephen Wolfram已经证明可以在very simple rules的基础上编写非常复杂的行为 . 他勇敢地从量子物理学和整个宇宙中推断出来 .

    同样,很多关于小型机器人的研究都集中在emergent behaviorswarm intelligence上 . 虽然经典military strategy和实践强烈 Build 在层次结构的基础之上,但我认为,如果作为自组织集群运作,那么一群完全无私,无所畏惧的战士(可以在你的计算机中行进)可能会非常有效 .

    对于Erlang或Scala的基于actor的并发模型,这种方法可能比使用Clojure的STM更好一些:我认为自组织和演员可以很好地融合在一起 . 不过,我可以设想在每个回合中运行一个单元列表,让每个单元只评估一小部分非常简单的规则来确定它的下一个动作 . 如果你尝试过这种方法,我会非常有兴趣听听它是怎么回事!

    EDIT

    还有一些在我脑海中浮现但在我写作的时候再次滑落的东西:我认为如果你将它与genetic或进化编程相结合,你可以从这种方法中获得显着的成果;即让你的虚拟玩具士兵在你睡觉时互相发动战争,让他们编码他们的策略,混合,匹配和改变他们的代码以适应这些策略;让裁判计划选择更成功的战士 .

    我已经读到了这些技术取得的惊人成功,单位以我们从未想过的方式运作 . 我听说过工作在这些原则上的认可机构不得不故意愚弄,以免挫败人类对手 .

相关问题