什么模型最适合实时策略游戏的优化?

正如塔斯勒姆盖所指出的,遗传算法并不能保证是最优的,尽管它们通常会给出很好的结果。

一个象棋引擎可以查看棋盘的许多不同方面(例如,它有多少棋子,对手有多少棋子),以指导它的搜索。它可以忽略大多数可用的操作,如果它知道这些操作比其他操作更糟糕的话。

对于构建订单创建者来说,只有时间才是真正重要的。建造另一架无人机是为了更快地获取矿物,还是为了更快地启动产卵池?不像下棋那么简单。

这类决定很早就发生了,所以在你决定更好的决定之前,你必须搜索每一个选择,这需要 长的 如果我自己编写一个构建顺序优化器,我可能会尝试制定一个启发式方法来估计当前状态有多好(接近目标状态),就像象棋引擎所做的那样:

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需要调整。

Best-first search 或者也许 IDDFS 在可能性之树中寻找。

:

我最近发现 paper depth-first search 具有 branch and bound 以及基于技术树(例如,虫子需要产卵池)和收集所需矿物所需时间来估计达到目标所需的最小努力量的启发式方法。

嗯,这是个很好的问题。也许《星际争霸》中的前几步确实可以按照几乎任何顺序进行,因为与敌人的接触并不像在国际象棋中那样直接,因此记住前几步的顺序并不像知道前几步中包含了哪些动作那样重要。但这一联系似乎暗示着另一种情况,这意味着“基因”确实不太适合被交换,除非我在编码中遗漏了一些狡猾的东西。

然而,我所说的“糟糕的选择”是指它相对于更合适的方法来说是低效的;这并不是说它在不到一秒钟的时间内仍然不能产生98%的最佳结果。在这样的情况下,计算机的强大力量是有用的,通常更重要的是你已经正确地建模了搜索空间,而不是使用了最有效的算法。

遗传算法可以是,也可以有时不是,最优或非最优解。基于遗传算法的复杂性,有多少变异,组合的形式,以及如何对遗传算法的染色体进行解释。

所以,根据你的人工智能是如何实现的,遗传算法可能是最好的。

例如,神经网络经常被遗传算法优化。

查找“遗传编程”,它是类似的,但使用树结构而不是字符行,这允许更复杂的交互,更好地繁殖。对于更复杂的事情,他们通常做得更好。

this 和 this

这种遗传算法只优化了游戏中一个非常特殊的部分的策略:游戏的前几个构建动作的顺序。它还有一个非常明确的目标:尽快拥有尽可能多的蟑螂。

• 各单位建设时间 建筑
• 允许的单位和建筑物
• 幼虫再生率。

这是一个相对有限的,定义相对明确的问题,搜索空间很大。因此,它非常适合于遗传算法(以及其他一些优化算法)。一个完整的基因是以第七只蟑螂为终点的一组特定的建造顺序。据我所知,你可以“玩”这个特定的基因,看看它完成的有多快,所以你有一个非常明确的健身测试。

以这种方式使用的遗传算法是一个很好的工具,可以为星际争霸游戏的第一阶段找到一个更优的建造顺序。由于其随机性,它也善于发现一个令人惊讶的策略,这可能是作者的另一个目标。

使用遗传算法 这个