logo标签列表

实时策略战争游戏人工智能的算法

algorithmartificial-intelligence
23

我正在设计一款实时策略战争游戏，其中人工智能将负责控制大量单位（可能超过1000个）在一个大的六边形地图上移动。

每个单位都有一定数量的行动点数，可以用于移动、攻击敌方单位或各种特殊行动（例如建造新单位）。例如，一辆坦克有5个行动点，可以花费3个点进行移动，然后花费2个点攻击射程内的敌人。不同的单位对不同的行动有不同的花费等等。

以下是一些额外的说明：

  • AI的输出是针对任何给定单位的“指令”
  • 行动点数分配在时间段开始时，但可以在时间段内的任何时间点使用（这是为了允许实时多人游戏）。因此，“什么也不做并保存行动点以便以后使用”是一种潜在有效的策略（例如一个不能移动的炮塔等待敌人进入射程）
  • 游戏更新是实时的，但AI可以在任何时候得到游戏状态的一致快照（由于游戏状态是Clojure的持久数据结构之一）
  • 我不期望“最优”的行为，只是希望AI表现得不会明显愚蠢，并提供合理的乐趣/挑战

您可以推荐哪些具体算法/方法，以实现效率和合理智能行为之间的正确平衡？

1
这是实时的吗？使用行动点进行移动和射击听起来更像回合制游戏？在实时游戏中，我期望听到移动速度和射击速率。行动点如何“充电”？ - deft_code
AP的设计更多是基于回合制，但我正在努力确保游戏可以实时运行，以便在多人游戏中使用。我目前尝试的概念是在定期间隔内刷新行动点数。 - mikera
1
好的，我现在已经在亚马逊上运行了一个演示版本，如果有人感兴趣可以访问：http://184.73.157.186/ - mikera
5个回答
11
如果你阅读Russell and Norvig，你会发现为每个目的更新到今天的最新算法。话虽如此，我惊讶于有多少不同的问题类可以成功地用贝叶斯算法解决。
然而，在你的情况下，我认为让每个单元都有自己的Petri网或推理引擎是一个坏主意……只有那么多的CPU、内存和时间可用。因此，采取不同的方法：
尽管在某些方面可能是个怪人，Stephen Wolfram已经证明了可以基于非常简单的规则编程出极其复杂的行为。他勇敢地从生命游戏推断到量子物理和整个宇宙。
同样，许多小型机器人的研究正在关注 emergent behavior 或 swarm intelligence 。虽然经典的 军事战略 和实践强烈依赖于等级制度，但我认为一支完全无私、无畏的战士队伍（正如在您的计算机中找到的那样）如果作为自组织集群运作，可以非常有效。
这种方法可能更适合Erlang或Scala的基于actor的并发模型，而不是Clojure的STM：我认为自组织和actors非常搭配。尽管如此，我可以想象每个回合运行单位列表，并且让每个单位评估一小撮非常简单的规则来确定其下一个动作。如果您尝试过这种方法，以及它的效果如何，我会非常感兴趣听到您的看法！
编辑
还有一些事情一直在我脑海中，但我在写作时又忘了：如果将其与遗传或进化编程相结合，您可以从这种方法中获得显着的结果；即让您的虚拟玩具士兵在您睡觉时互相战斗，让它们编码其策略并混合、匹配和突变其代码以用于这些策略；然后让一个裁判程序选择更成功的战士。
我已经读到一些惊人的成功案例，其中单位以我们从未想到的方式运作。我听说过使用这些原则的AI必须有意降低难度，以避免挫败人类对手。
1
AIMA是人工智能的很好入门，但它远未达到最先进的水平。 - Cerin
8

这个问题的范围非常广泛，基本上是在问如何编写策略游戏。

有大量的书籍和在线文章可以提供相关信息。我强烈推荐 Game Programming Wisdom 系列和 AI Game Programming Wisdom 系列。特别是，AI Game Programming Wisdom 的第一卷第6节涵盖了一般架构，第7节涵盖了决策架构，第8节涵盖了特定类型的架构（8.2 是 RTS 类型）。

澄清一下 - 我更感兴趣的是适用于这种情况的具体算法思想，而不是整体模型。已经编辑问题以反映这一点。 - mikera
8
首先，您应该让AI在某个程度上变成回合制（即使它可能不完全是回合制，在RTS中，您可以将离散时间间隔分解为回合）。其次，您应该确定AI应该使用多少信息。也就是说，如果允许AI作弊并知道对手的每一步（从而使其更强），或者它应该知道更少或更多。第三，您应该定义一个状态的成本函数。这个想法是，更高的成本意味着计算机处于更糟糕的状态。第四，您需要一个移动生成器，从给定状态生成AI可以转换到的所有有效状态（这可以是同质的[状态无关]或异质的[状态相关]）。
事实上，成本函数将受到您如何定义状态的影响。您在状态中编码的信息越多，您的AI平衡性就会更好，但它执行起来就会更困难，因为它必须为每个额外的状态变量进行指数级搜索（在穷举搜索中）。
如果您提供了状态和成本函数的定义，那么您的问题将转化为人工智能中的一般问题，可以用任何选择的算法来解决。
以下是我认为会很好地运作的摘要：
  1. 进化算法可能会表现得很好，但是它们会增加一层复杂性，从而为错误等问题创造空间。它们还需要极大量的适应性函数调整等。我没有太多使用这些算法的经验，但如果它们像神经网络一样（我认为它们是这样的，因为两者都是受生物模型启发的启发式算法），你很快就会发现它们是易变和不一致的。最重要的是，我怀疑它们并没有比我在第3个选择中描述的选项更有益。
  2. 有了成本函数和状态定义，你理论上可以应用梯度下降（假设状态函数可微分且状态变量的域是连续的），但这可能会产生劣质结果，因为梯度下降的最大弱点是陷入局部极小值。举个例子，这种方法容易陷入攻击敌人的陷阱，因为有一定的机率消灭他们。显然，这可能不是游戏中想要的行为，但是梯度下降是一种贪婪的方法，无法更好地处理。
  3. 这个选项是我最高推荐的：模拟退火。模拟退火将具有1的所有优点，而又不会增加复杂性，同时比2更加稳健。实质上，模拟退火只是在状态之间随机游走。因此，除了成本和状态，您还必须定义一种方法来随机转换状态。模拟退火也不容易陷入局部最小值，同时能够相当一致地产生非常好的结果。唯一需要调整的是冷却时间表 - 这决定了模拟退火收敛的速度。我发现模拟退火的最大优点是它概念简单，并且实证上产生比我尝试过的大多数其他方法都更好的结果。有关模拟退火的信息可以在此处找到（链接），其中包含底部的通用实现的长列表。
  4. （编辑添加，很久以后）模拟退火和我上面列出的技术是通用的人工智能技术，而不是真正针对游戏的人工智能。通常，算法越专业化，其性能表现就越好。请参见无免费午餐定理（链接）。3的另一个扩展是称为并行淬火的东西，它通过帮助其避免局部最优来大大提高模拟退火的性能。一些关于并行淬火的原始论文相当陈旧（链接），但其他论文已经更新（链接）。
无论你最终选择哪种方法，像我之前说的那样，将你的问题分解成状态和成本函数将非常重要。作为一个经验法则，我建议从20-50个状态变量开始，因为你的状态搜索空间是这些变量数量的指数级别。
吹毛求疵：你肯定是指卡在局部最大值上了吧？ - Davislor
你知道的，最好的事情就是如果有人展示一下这些类型游戏中“状态”可以是什么样子的例子... - Martin Kosicky
6

这是一个非常重要的问题，其他答案已经指出了一些很棒的资源来研究。

我曾经处理过这个问题，发现简单行为复杂/ emergent behavior方法对于人类设计来说有点难以掌握，除非从遗传/进化的角度来考虑。

最终，我使用了抽象层次的人工智能，类似于现实生活中军队的运作方式。单位将与同类型的附近单位分组成小队，这些小队将与附近的小队分组形成一种迷你营地。在这里可以使用更多的层次（将营地分组在一个区域内等），但最终顶部是高级战略人工智能。

每个层次只能向其下面的层次发布命令。下面的层次将尝试使用手头的资源执行命令（即下面的层次）。

向单个单位发布的命令的一个例子是“去这里”和“朝这个目标开火”。向更高层次发布的更高级别的命令是“确保这个位置”，该级别将处理并向下级发布适当的命令。

最高级别的主人工智能负责非常广泛的战略决策，例如“我们需要更多的____单位”，或者“我们应该朝这个位置移动”。

军队类比在这里起作用; 指挥官和中尉以及指挥链。

0
Google确实有一个可以在特定情况下击败职业星际争霸2玩家的AI。这个AI是一个纯粹的深度神经网络。话虽如此，千万不要为你的AI使用机器学习，因为尽管它们在游戏中有优势（平衡、怪癖、长时间学习期、不擅长修改），但机器学习对于游戏和实时战略游戏来说是最后的选择。
使用一个通用的象棋引擎，即蒙特卡洛树搜索（链接1）。这种方法几乎适用于任何情况，而不需要使用机器学习，尽管这些引擎在实时战略游戏中的可视范围有限时相对较弱。
你的回答可以通过提供更多的支持性信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的回答是否正确。你可以在帮助中心找到关于如何撰写好回答的更多信息。 - undefined
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接