什么模型最适合优化实时战略游戏？

最近有一篇文章广为流传，讨论了使用遗传算法来优化《星际争霸II》中的“建造顺序”。

星际争霸比赛的初始状态是预先确定的，并且是恒定的。就像国际象棋一样，在比赛的早期阶段做出的决定，会对玩家在中后期游戏中的表现产生长期影响。因此，各种开局可能性或“建造顺序”受到大量研究和审查。在上述文章流传之前，计算机辅助的建造顺序创建可能不像最近那样流行。

我的问题是… 遗传算法真的是建模优化建造顺序的最佳方法吗？

建造顺序是一系列动作。有些动作有先决条件，例如“在创建建筑 C 之前，您需要建筑 B，但您可以随时拥有建筑 A。” 所以染色体可能看起来像 AABAC。

我想知道遗传算法是否真的是解决这个问题的最佳方法。虽然我对这个领域不太熟悉，但我很难将基因的概念硬塞进一个作为动作序列的数据结构中。这些不是可以像头和脚一样混合搭配的独立选择。那么，像繁殖和交叉这样的事情有什么价值呢？

我认为任何国际象棋AI使用的东西都会更合适，因为任何给定时间的选择数组都可以被视为树状结构。

回答：

正如 @人名指出的那样，遗传算法不能保证是最优的，即使它们通常会给出好的结果。

为了获得最佳结果，您必须搜索每种可能的动作组合，直到找到通过树状表示的最佳路径。然而，在星际争霸中做到这一点是困难的，因为有太多不同的路径可以达到目标。在国际象棋中，你将一个兵从 e2 移动到 e4，然后对手移动。在星际争霸中，你可以在瞬间 x 或 x+1 或 x+10 或… 移动一个单位

国际象棋引擎可以查看棋盘的许多不同方面（例如，它有多少棋子，对手有多少棋子），以指导它的搜索。如果它知道某些动作比其他动作差，它可以忽略大多数可用的动作。

对于建造顺序创建者来说，只有时间才是真正重要的。建造更多的农民来更快地获得矿物更好，还是立即开始建造基地更好？不像国际象棋那样简单明了。

这些类型的决定发生得很早，因此您必须搜索每个替代方案的结论，然后才能决定哪个更好，这将花费很长时间。如果我自己要编写一个建造顺序优化器，我可能会尝试制定一个启发式方法来估计当前状态有多好（接近目标状态），就像国际象棋引擎所做的那样：

Score = a*(Buildings_and_units_done/Buildings_and_units_required) - b*Time_elapsed - c*Minerals - d*Gas + e*Drone_count - f*Supply_left

这试图使分数与完成百分比以及星际争霸常识联系起来（保持低资源，建造农民，不要建造超过你需要的补给）。当然，变量 a 到 f 需要调整。

在您获得了一个可以在某种程度上估计情况价值的启发式方法之后，我将使用最佳优先搜索或者 IDDFS 来搜索可能性的树。

编辑：

我最近发现了一篇论文，实际上描述了星际争霸中的建造顺序优化，甚至是实时的。作者使用带有分支定界的深度优先搜索以及基于科技树（例如，小狗需要基地）和收集所需矿物所需的时间来估计达到目标所需的最小努力量的启发式方法。

学技术