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

Question

我正在设计一种实时战略战争游戏，其中AI将负责控制大型六边形地图上的大量单位（可能是1000多个）。

一个单位有许多行动要点，这些行动要点可以用于移动，攻击敌方单位或进行各种特殊行动（例如建造新单位）。例如，一个有5个动作点的坦克可能会花费3进行移动，然后花费2进行射程内的敌人射击。不同的单位对不同的操作等具有不同的成本。

一些附加说明：

• AI的输出是对任何给定单元的“命令”
• 动作点是在一个时间段的开始分配的，但可以在该时间段内的任何时间花费（这是为了进行实时多人游戏）。因此，“不执行任何操作并保存行动点以备后用”是一种潜在的有效策略（例如，炮塔无法移动，等待敌人进入射击范围）
• 游戏正在实时更新，但AI可以随时获取游戏状态的一致快照（由于游戏状态是Clojure的持久数据结构之一）
• 我不期望“最佳”行为，只是一些显然不是愚蠢的事情，并且可以提供合理的乐趣/挑战来对抗

对于可以在效率和合理的智能行为之间取得适当平衡的特定算法/方法，您有什么建议？

Answer 1

首先，您应该努力使您的游戏回合在某个程度上基于AI（即即使您可能不完全基于回合，也可以以某种方式对它进行回合建模，在RTS中，您可以将离散的时间间隔分成回合。
）其次，您应该确定AI应该使用多少信息。就是说，如果允许AI作弊并知道对手的一举一动（从而使其更强壮），或者它应该了解的更多或更少。第三，您应该定义状态的成本函数。想法是，更高的成本意味着计算机将处于更差的状态。第四，您需要移动生成器，生成AI可以从给定状态转换为所有有效状态的所有状态（这可以是同质的（与状态无关）或异构的）
[取决于状态]。

问题是，成本函数将很大程度上取决于您确切定义的状态。您在状态中编码的信息越多，您的AI就会越平衡，但执行起来就越困难，因为它必须对包含的每个其他状态变量进行指数搜索（详尽搜索）。

如果提供状态和成本函数的定义，则您的问题将转换为AI中的一般问题，可以使用您选择的任何算法来解决。

以下是我认为效果很好的摘要：

1. 如果您花了足够的精力，进化算法可能会很好地工作，但是进化算法会增加一层复杂性，这会为错误以及其他可能出错的地方创造空间。它们还需要对健身功能等进行大量调整。我在处理这些功能方面经验不足，但是如果它们像神经网络一样（我相信它们都是自生物学模型启发而来的启发式方法），您将很快发现他们善变，远非一贯。最重要的是，我怀疑它们是否会比我在3中描述的选项增加任何好处。

2. 定义了成本函数和状态后，从技术上讲，您可以应用适当的梯度（假设状态函数是可微的，并且状态变量的域是连续的），但这可能会产生较差的结果，因为最大的缺点是下降的梯度陷入局部极小值。举个例子，这种方法很容易发生像总是尽可能快地攻击敌人的事情，因为消灭敌人的机会不为零。显然，这可能不是游戏的理想行为，但是，像样的渐变是一种贪婪的方法，而且并不了解。

3. 此选项是我最推荐的选项：模拟退火。模拟退火（IMHO）具有1.的所有优点，而没有增加复杂性，同时比2更为健壮。本质上，SA只是状态之间的随机游动。因此，除了成本和状态外，您还必须定义一种在状态之间随机转换的方法。SA也不容易陷入局部最小值，同时会始终如一地产生非常好的结果。SA所需的唯一调整就是冷却计划-决定了SA收敛的速度。我发现SA的最大优点是，它在概念上简单，并且凭经验得出的结果优于我尝试过的其他大多数方法。可以在此处找到有关SA的信息，并在底部有一长串通用实现。

3b。（ 稍后再添加
）上面列出的SA和技术都是通用的AI技术，并不是专门用于游戏的AI。通常，算法越专业，其执行性能越好。参见无免费午餐定理2。3的另一个扩展是所谓的并行回火，它通过帮助SA避免局部最优而极大地提高了SA的性能。有关平行回火的原始论文中有些过时了3，但另一些则进行了更新4。

不管最终选择哪种方法，将其分解成状态和成本函数都是非常重要的，正如我之前所说。根据经验，我将从20-50个状态变量开始，因为您的状态搜索空间的数量成指数倍。