13

我花了一整天的时间尝试实现极小极大，但并没有真正理解它。现在，我想我了解极小极大的工作原理，但不了解 alpha-beta 修剪。

这是我对极小极大的理解：

  1. 生成所有可能移动的列表，直到深度限制。

  2. 评估游戏场对底部每个节点的有利程度。

  3. 对于每个节点，（从底部开始），如果层为最大值，则该节点的分数是其子节点的最高分数。如果层是 min，则该节点的分数是其子节点的最低分数。

  4. 如果您尝试将其最大化，则执行得分最高的移动，或者如果您想要最小得分，则执行最低的移动。

我对 alpha-beta 剪枝的理解是，如果父层是 min 并且您的节点的分数高于最低分数，那么您可以对其进行剪枝，因为它不会影响结果。

但是，我不明白的是，如果您可以计算出一个节点的分数，您将需要知道低于该节点的层上所有节点的分数（以我对极小极大的理解）。这意味着您仍将使用相同数量的 CPU 功率。

谁能指出我做错了什么？这个答案（为白痴解释了 Minimax）帮助我理解了 minimax，但我不明白 alpha beta pruning 会有什么帮助。

谢谢你。

4

5 回答 5

17

要了解 Alpha-Beta，请考虑以下情况。轮到白方了，白方试图最大化分数，黑方试图最小化分数。

白棋评估 A、B 和 C 步，发现 C 步的最佳分数是 20。现在考虑评估 D 步时会发生什么：

如果白棋选择D，我们需要考虑黑棋的反击。早期，我们发现黑方可以捕获白皇后，并且由于失去皇后，该子树的 MIN 得分为 5。然而，我们并没有考虑到所有的黑人反击。其余的值得检查吗？不。

我们不关心黑方能否得到低于 5 的分数，因为白方走“C”可以将分数保持在 20。黑方不会选择分数高于 5 的反棋，因为他试图最小化分数并且已经找到了得分为 5 的棋步。对于白棋，只要 D 的 MIN（到目前为止为 5）低于 C 的最小值（肯定是 20），则 C 步优于 D 步。所以我们在那里“修剪”树的其余部分，弹出一个级别并评估白色移动 E，F，G，H .... 到最后。

希望有帮助。

于 2011-10-25T14:44:15.283 回答
3

您无需评估节点的整个子树即可确定其值。Alpha Beta Pruning 使用两个动态计算的边界 alpha 和 beta 来限制节点可以采用的值。

Alpha 是通过博弈树的另一条路径保证最大玩家（无论最小玩家做什么）的最小值。此值用于在最小化级别执行截止（修剪）。当最小玩家发现最小节点的得分必然小于 alpha 时，它不需要评估来自该节点的任何更多选择，因为最大玩家已经有了更好的移动（具有值 alpha 的移动）。

Beta 是保证最小玩家的最大值，用于在最大化级别执行截止。当最大玩家发现最大节点的分数必然大于 beta 时，它可以停止评估来自该节点的任何更多选择，因为最小玩家不会允许它走这条路，因为最小玩家已经有一条路径这保证了 beta 的值。

我已经详细解释了 Alpha Beta Pruning、它的伪代码和一些改进： http: //kartikkukreja.wordpress.com/2014/06/29/alphabetasearch/

于 2014-06-29T19:17:08.410 回答
1

（非常）对mimimax的简短解释：

  • 您（棋盘位置的评估者）可以选择下棋n。您尝试所有这些并将董事会职位交给（对手）评估员。

    • 对手评估新的棋盘位置（对他来说，对手方） - 通过做基本相同的事情，递归调用（他的对手）评估器，除非达到最大深度或其他一些条件并且调用静态评估器 - 和然后选择最大评估并将评估发送回给您。

  • 您选择具有这些评估最小值的移动。而那个评估是你在开始时必须评估的董事会的评估。

（非常）对α-β-剪枝的简短解释：

  • 您（棋盘位置的评估者）可以选择下棋n。您将所有这些都一一尝试，并将董事会位置提供给（对手）评估者 - 但您也传递您当前的评估（您的董事会）。

    • 对手评估新的棋盘位置（对他来说，对手方）并将评估发送回给您。但他是怎么做到的？他可以选择m下棋。他尝试了所有这些并将新的棋盘位置（一个一个）提供给（他的对手）评估者，然后选择最大的一个。
    • 关键步骤：如果他返回的任何评估值大于您给他的最小值，则可以肯定他最终会返回至少那么大的评估值（因为他想最大化）。而且您肯定会忽略该值（因为您想最小化），因此他停止了他尚未评估的板的任何工作。

  • 您选择具有这些评估最小值的移动。而那个评估是你在开始时必须评估的董事会的评估。

于 2011-10-25T15:08:48.907 回答
1

这是一个简短的答案——您可以知道一个节点的值，而无需计算其所有子节点的精确值。

一旦我们知道子节点不能比之前评估的兄弟节点更好，从父节点玩家的角度来看，我们就可以停止评估子子树。至少有这么糟糕。

于 2011-10-25T17:31:49.433 回答
1

我认为您的问题暗示了对评估功能的误解

如果您可以计算出一个节点的分数，您将需要知道比该节点低一层的所有节点的分数（以我对极小极大的理解）

我不完全确定你的意思，但听起来是错误的。评估函数(EF) 通常是一种非常快速的静态位置评估。这意味着它只需要查看一个位置并从中得出“结论”。（IOW，您并不总是将分支评估为n plys）

现在很多时候，评估确实是静态的，这意味着位置评估函数是完全确定的。这也是评估结果易于缓存的原因（因为每次评估位置时它们都是相同的）。

现在，例如国际象棋，通常与上述有相当多的明显/隐蔽偏差：

  • 一个位置可能会根据游戏环境进行不同的评估（例如，确切的位置是否在游戏中更早出现；发生了多少没有棋子移动/捕获的移动，过路和易位机会）。解决这个问题的最常见“技巧”是将状态实际合并到“位置” 1

  • 通常为游戏的不同阶段（开场、中间、结束）选择不同的 EF；这有一些设计影响（如何在更改 EF 时处理缓存的评估？当不同层的 EF 不同时如何进行 alpha/beta 修剪？）

老实说，我不知道常见的国际象棋引擎如何解决后者（我只是为我的玩具引擎避免了它）

我会参考在线资源，例如：

1就像“检查”/“僵局”条件一样，如果它们在评估函数之外没有特殊情况

于 2011-10-25T11:55:22.453 回答