3

我刚刚看到了关于游戏树和 MinMax 算法的 MIT 讲座，其中讨论了 Alpha Beta 修剪和渐进深化。
https://www.youtube.com/watch?v=STjW3eH0Cik

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

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

那么我们将如何在第（d-1）级或说第（d-5）级获得“近似答案”？

4

1 回答 1

4

我会尽力解释清楚。
渐进式深化的背景和要点
我需要你知道，在现实世界的游戏中，你用来决定的时间是有限的！（因为用户体验和其他关于人机交互或游戏中的问题/设计的问题）。
您有一个博弈树，并使用差异算法来优化遍历所有树。但是存在三个问题：

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

所有问题的答案都是渐进式深化：在当前级别计算答案并尝试通过树中的下一个级别；但是如果你没有时间你准备好在上一个级别中有一个答案并将其作为答案 你可以想象
你的问题的答案你
的树中的当前级别是游戏树中的“最终级别”（你假设） ，但是如果你进入树中的下一个级别，你将获得最佳解决方案，那么如果你可以进入下一个级别：现在就去！但是你需要计算当前游戏树中的最佳答案，因为如果你没有在时间限制下完成下一层最佳答案的计算，它是游戏树中的“最后一层”作为保险单。

于 2017-11-04T00:06:43.583 回答