什么型号最适合优化实时策略游戏？

Question

最近一篇文章讨论了使用遗传算法来优化星际争霸II中的"构建顺序".

星际争霸的初始状态是预先确定的并且是不变的.和国际象棋一样,在比赛的早期阶段做出的决定对于球员在比赛中后期的表现能力具有长期影响.因此,各种开放可能性或"构建订单"正在经过深入的研究和审查.在上述文章的发行之前,计算机辅助的构建顺序创建可能并不像最近那样流行.

我的问题是...... 遗传算法真的是建模优化构建订单的最佳方法吗？

构建顺序是一系列操作.某些操作具有先决条件,例如"在创建构建C之前需要构建B,但您可以随时构建A".所以染色体可能看起来像AABAC.

我想知道遗传算法是否真的是解决这个问题的最佳方法.虽然我对这个领域并不太熟悉,但我很难将基因概念变成数据结构,这是一系列行动.这些不是独立的选择,可以像头和脚一样混合和匹配.那么复制和穿越这样的东西有什么价值呢？

我想任何国际象棋AI都会更合适,因为在任何给定时间的选择数组都可以在某种程度上被视为树状.

Answer 1

正如 TaslemGuy 指出的那样，遗传算法不能保证是最优的，尽管它们通常会给出良好的结果。

为了获得最佳结果，您必须搜索所有可能的操作组合，直到找到通过树状表示的最佳路径。然而，在《星际争霸》中做到这一点很困难，因为实现目标有很多不同的途径。在国际象棋中，您将棋子从 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来搜索可能性树。

编辑：

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