了解StarCraft 2的深度优先分支和界限实现

Question

问题是我发现很难理解DFBB是如何工作的，这种情况下的参数和输出应该是什么。

我正在为游戏StarCraft 2创建一个AI，它将处理游戏中的构建顺序(为人族团队)。我计划遵循链接中描述的方法(见下文)，该方法遵循了我所要做的非常相似的事情。总结一下我计划做的事情：

一个不同类型的建筑物，需要建立的清单将给我。建筑要花费矿产和天然气(这是游戏中的货币)，一些建筑是有先决条件的(这意味着在可能建造之前需要建造其他建筑)，它们需要一定的时间来建造。

在文章中，他们使用了Depth-First Branch，并确定了最佳构建顺序，这意味着以最快的方式构建该列表中的建筑。这是他们的伪代码：

​

​

其中状态S由S=(当前游戏时间、可用资源、正在进行但未完成的动作、工人收入数据)表示。文章描述了S‘是如何派生的，它是通过三个函数来完成的，所以我理解了位。

正如前面提到的，我正在努力理解在它们所描述的伪代码中，起始状态S，目标G，时间限制t和界限b应该用什么来表示。

我只知道三件事:需要建造的建筑物列表，我目前拥有的消耗品(矿物和天然气)，资源(即我已经在游戏中拥有的建筑物)。然后，这应该以某种方式应用于算法，但还不清楚函数的输入应该是什么。输出应该是一个按正确顺序排序的列表，所以如果我在哪里按照它们进来的顺序建造建筑物，那么它应该都能解决问题，这应该是它可以完成的最佳时间。

例如，我应该遍历建筑物列表，并在每个元素上运行DFBB，目标是查看建筑物是否可以建造。但是，在这种情况下，时间限制应该是什么，界限是什么意思？这仅仅是成本问题吗？

请解释如何在列表上运行此函数，以便找到构建它的最佳路径。这篇文章很容易阅读，但我需要一些帮助来理解它是如何工作的，以及如何将它应用于我的问题。

文章链接：https://ai.dmi.unibas.ch/research/reading_group/churchill-buro-aiide2011.pdf

Answer 1

开始状态S是游戏开始时的初始状态。我相信你们有100个迷你车和指挥中心还有12个？SCV，这就是你的开始。

这里的目标是你想要的建筑列表。满足的条件是都在目标中构建，也在S中。

时间限制是指您愿意花费多少时间来获得结果。如果你将它设置为5秒，它可能会给你一个次优的解决方案，但它会在5秒内完成。如果算法完成搜索，它将更早地返回。如果你不在意，就把它省略掉，但要确保你把解决方案写到了一个文件中，以防发生什么事情。

界限b是游戏中构建一切的时间限制。您最初将其设置为无限大或某个明显的值(例如10分钟？)。当你找到一个解决方案时，b会更新，所以你找到的每个新的解决方案都必须比前一个解决方案更快(在游戏中)。

一些笔记。确保可能的操作(步骤9中的子节点)包括不做任何事情(等待更多资源)和构建SCV。

另一件可能缺少的事情是SCV移动速度的正确建模。这些单位需要搬到一个地方来建造一些东西，而且他们也需要时间来重新开始开采。