用于实时战略战争AI的算法

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

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

一些额外的说明:

AI的输出是任何给定单位的"命令"

动作点在一段时间的开始时分配,但可以在该时间段内的任何时间点使用(这是为了允许实时多人游戏).因此,"什么也不做,以后再保存动作点"是一种潜在有效的策略(例如,炮塔无法移动等待敌人进入射程范围内)

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

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

对于能够在效率和合理智能行为之间取得适当平衡的特定算法/方法,您能推荐什么？

如果您阅读Russell和Norvig,您会发现各种用途的算法,并更新到今天的最新技术水平.也就是说,我对使用贝叶斯算法成功接近多少个不同的问题类感到惊讶.

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

虽然在某种程度上可能是一个疯子,但斯蒂芬·沃尔夫勒姆已经表明,可以在非常简单的规则的基础上编写非常复杂的行为.他勇敢地从生命游戏推断到量子物理学和整个宇宙.

同样,很多关于小型机器人的研究都集中在紧急行为或群体智能上.虽然经典的军事战略和实践强烈建立在等级制度的基础之上,但我认为,如果作为自组织集群运作,那些完全无私无畏的战士(可以在你的计算机中行进)可能会非常有效.

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

编辑

还有一些其他的东西在我的脑海里,但在我写作的时候再次滑落:如果你将它与遗传或进化编程相结合,我认为你可以从这种方法中获得显着的成果; 也就是说让你的虚拟玩具士兵在你睡觉时互相打仗,让他们编码他们的策略,混合,匹配和改变他们的代码用于那些策略; 让裁判计划选择更成功的战士.

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

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

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

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

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

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

以下是我认为可以正常工作的摘要:

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

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

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

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

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

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

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

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

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

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

最高级别的主人工智能负责董事会的战略决策,例如"我们需要更多的____单位",或"我们应该致力于走向这个位置".

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