algorithm - 博弈树算法和渐进深化 : How to approximate an answer without reaching the leaf nodes?

Question

我刚看到麻省理工学院关于博弈树和 MinMax 算法的讲座，其中讨论了 Alpha Beta 剪枝和渐进深化。
https://www.youtube.com/watch?v=STjW3eH0Cik

因此，如果我理解正确的话，渐进式加深是指当您尝试在每个级别上近似回答并尝试根据移动的时间限制深入到叶节点时。在任何时候得到一些答案是很重要的。现在，在 36:22教授讨论了我们没有足够时间的情况，我们只走到第 (d-1) 层，其中 d 是树的深度。然后他还建议我们可以在每个级别都有一个临时答案，因为我们应该在任何时间点都有一些大概的答案。

我的问题是，如果不去叶节点，我们怎么能得到任何答案，因为只有在叶节点，我们才能断定谁能赢得比赛。想想这个井字游戏。在第 (d-1) 级，我们没有足够的信息来决定直到 (d-1) 的这个节点的这一系列 Action 是否会赢得我或输掉比赛。在更高的层次上说在 (d-3) 它更加模糊!当我们往下走时，一切皆有可能。不是吗？因此，如果算法决定计算到第 (d-1) 层，那么所有这些路径选项都是相等的!没有什么能保证赢，也没有什么能保证在第 (d-1) 级输，因为如果我理解正确的话，输赢只能在叶节点上计算。在纯 MinMax 算法中尤其如此。

那么，我们如何才能在第 (d-1) 级或第 (d-5) 级获得“近似答案”呢？

Answer 1

我会尽力解释清楚。
逐步深化的背景和重要性
我要你知道，在现实世界的游戏中，你用来决定的时间是有限的! (因为用户体验和其他关于人机交互的问题或关于你游戏中的问题/设计)。
你有一个游戏树并使用差异算法来优化遍历所有树。但存在三个问题:

• 你有时间限制!
• 您需要计算当前游戏树中的最佳解决方案，这是根据树的深度进行计算的时间!
• 您需要决定是否在不违反时间限制的情况下进入树中以获得更精确的答案。

所有问题的答案都是渐进加深的:在当前关卡计算答案并尝试通过树中的下一个关卡；但是如果你没有时间，你准备好在上一关得到一个答案，然后把它作为答案拿出来
回答你的问题
您可以想象树中的当前级别是游戏树中的“最终级别”(您假设)，但是如果您进入树中的下一个级别，您将获得最佳解决方案，然后如果您可以下一级:现在就去!但是你需要计算当前游戏树中的最佳答案，因为它是游戏树中的“最终级别”作为保险单，如果你没有在时间限制下完成下一级别的最佳答案计算。