我正在设计一款实时战略战争游戏，其中AI将负责控制大量单位（可能超过1000个），地图是一个大型六边形地图。
每个单位都有一定数量的行动点，这些行动点可以用于移动、攻击敌方单位或执行各种特殊行动（例如建造新单位）。例如，一辆拥有5个行动点的坦克可以使用3个点进行移动，然后使用2个点攻击范围内的敌人。不同的单位对于不同的行动会有不同的消耗。
一些补充说明：
- AI的输出是对任何给定单位的“命令”
- 行动点在时间段开始时分配，但可以在时间段内的任何时间点使用（这是为了允许实时多人游戏）。因此，“什么都不做，将行动点留到以后使用”是一种潜在的有效策略（例如，一个无法移动的炮塔等待敌人进入射程）
- 游戏是实时更新的，但AI可以随时获得游戏状态的一致快照（这要归功于游戏状态是Clojure的持久化数据结构之一）
- 我不期望“最优”行为，只希望它不是明显的愚蠢，并且提供合理的乐趣/挑战来对抗
在具体的算法/方法方面，您有什么建议，可以在效率和合理智能的行为之间取得适当的平衡？
回答：
首先，你的目标应该是从某种程度上将你的游戏转变为 AI 的回合制游戏（例如，即使它可能不是完全的回合制，你也可以以某种方式对其进行回合制建模；在 RTS 中，你或许可以将不连续的时间间隔分解为回合）。其次，你应该确定 AI 应该使用多少信息。 也就是说，AI 是否可以作弊并知道其对手的每一个动作（从而使其更强大），或者它应该知道更少或更多。 第三，你应该定义一个状态的成本函数。 想法是，更高的成本意味着计算机所处的更糟糕的状态。 第四，你需要一个移动生成器，它生成 AI 可以从给定状态转换到的所有有效状态（这可能是同质的 [与状态无关] 或异质的 [与状态相关]）。
问题是，成本函数将受到你如何精确定义状态的极大影响。 你在状态中编码的信息越多，你的 AI 就越平衡，但执行起来就越困难，因为它必须为每个包含的额外状态变量呈指数级地搜索更多内容（在穷举搜索中）。
如果你提供状态的定义和成本函数，你的问题就会转变为 AI 中的一个通用问题，可以使用你选择的任何算法来解决。
以下是我认为效果不错的总结：
-
如果你投入足够的精力，进化算法可能会奏效，但它们会增加一个复杂性层次，从而为错误创造空间以及其他可能出错的事情。 它们还需要对适应度函数等进行大量的调整。 我没有太多使用这些算法的经验，但如果它们与神经网络类似（我相信它们是，因为两者都是受生物模型启发的启发式方法），你很快就会发现它们是反复无常的，并且远非一致。 最重要的是，我怀疑它们比我在第 3 点中描述的选项有任何好处。
-
通过定义的成本函数和状态，从技术上讲，你可以应用梯度下降（假设状态函数是可微的，并且状态变量的域是连续的），但这可能会产生较差的结果，因为梯度下降的最大弱点是陷入局部最小值。 举例来说，这种方法很容易做出像尽快攻击敌人的事情，因为有非零的机会消灭他们。 显然，对于游戏来说，这可能不是理想的行为，但是，梯度下降是一种贪婪的方法，并且不知道更好。
-
这个选项是我最推荐的一个：模拟退火。 （恕我直言）模拟退火将具有 1 的所有优点，而不会增加额外的复杂性，同时比 2 更健壮。本质上，SA 只是状态之间的一种随机游走。 因此，除了成本和状态之外，你还必须定义一种在状态之间随机转换的方式。 SA 也不容易陷入局部最小值，同时始终如一地产生非常好的结果。 SA 唯一需要的调整是冷却计划——它决定了 SA 收敛的速度。 我发现 SA 的最大优点是它在概念上很简单，并且在经验上比我尝试过的大多数其他方法产生更好的结果。 有关 SA 的信息可以在 这里 找到，底部列出了大量的通用实现。
3b. （稍后添加的编辑）SA 和我上面列出的技术都是通用 AI 技术，并非真正专门针对游戏的 AI。 一般来说，算法越专业，它就越有可能表现得更好。 请参阅无免费午餐定理 2。 3 的另一个扩展是称为并行回火的东西，它通过帮助它避免局部最优值来显着提高 SA 的性能。 关于并行回火的一些原始论文已经相当过时了 3，但其他论文已经更新了4。
无论你最终选择什么方法，将你的问题分解为状态和成本函数都非常重要，正如我之前所说的那样。 作为经验法则，我建议从 20-50 个状态变量开始，因为你的状态搜索空间是这些变量数量的指数函数。
