Minimax的α-β剪枝
我花了一整天的时间来实现minimax，而没有真正理解它。现在，我想我明白了minimax是如何工作的，而不是α-beta剪枝。
这是我对minimax的理解：
- 生成所有可能的移动的列表，直到深度限制。
- 评估游戏场对底部的每个节点有多有利。
- 对于每个节点(从底部开始)，如果层是最大的，则该节点的得分是其子节点的最高得分。如果该层是最小的，则该节点的得分是其子节点的最低得分。
- 如果您想要最大的分数，则执行得分最高的移动，如果您想要最低的分数，则执行最低的移动。
我对alpha-beta剪枝的理解是，如果父层是min，并且您的节点的得分比最小值高，那么您可以修剪它，因为它不会影响结果。
然而，我不明白的是，如果你能计算出一个节点的分数，你将需要知道一个层上所有节点的得分低于这个节点(在我对minimax的理解中)。这意味着你仍将使用同样数量的CPU能量。
有人能指出我出了什么错吗？这个答案( Minimax为一个白痴解释 )帮助我理解了minimax，但我不明白αβ剪枝会有什么帮助。
谢谢。
回答 4
Stack Overflow用户
发布于 2011-10-25 14:44:15
要理解Alpha-Beta，请考虑以下情况。这是白色的转变，白色是试图最大化的得分，黑色是试图最小化得分。
White评估移动A、B和C，发现C的最佳得分是20。现在考虑一下评估移动D时会发生什么：
如果白色选择移动D，我们需要考虑黑色的反移动。早期，我们发现黑色可以捕获白色皇后，而该子树的最小得分为5分，因为失去了女王。然而，我们并没有考虑所有黑人的反击。其他的值得检查吗？不是的。
我们不在乎黑人是否能得到低于5分的分数，因为白人移动"C“可以将分数保持在20分。布莱克不会选择一个得分高于5分的反移动，因为他正在尝试MINimize得分，并且已经发现移动得分为5分。对于白色，移动C优先于移动D，只要D( 5到目前为止)的最小值低于C(当然是20 )。所以我们“修剪”剩下的树，弹出一个水平，评估白色移动E，F，G，H.直到最后。
希望这能有所帮助。
Stack Overflow用户
发布于 2014-06-29 19:17:08
您不需要计算节点的整个子树来决定它的值。Alpha Beta剪枝使用两个动态计算的界限alpha和beta来绑定节点可以使用的值。
Alpha是通过游戏树的另一条路径保证最大玩家通过另一条路径的最小值(不管最小玩家做什么)。此值用于在最小级别执行袖口(剪枝)。当min发现一个min节点的得分一定小于alpha时，它不需要评估来自该节点的任何更多的选择，因为max player已经有了更好的移动(值为alpha的移动)。
Beta是min得到保证的最大值，用于在最大化级别上执行裁剪。当max player发现最大节点的得分必然大于beta时，它可以停止评估来自该节点的任何更多选择，因为min将不允许它选择这条路径，因为min已经有一条保证值为beta的路径。
我写了一个详细的解释阿尔法贝塔剪枝，它的伪代码和几个改进：http://kartikkukreja.wordpress.com/2014/06/29/alphabetasearch/
Stack Overflow用户
发布于 2011-10-25 15:08:48
(非常) mimimax的简短解释
- 您(董事会职位的评估人员)可以选择播放
n移动。你尝试他们所有的，并给予董事会的立场(对手)评估。
- The opponent evaluates the new board positions (for him, the opponent side) - by doing essentially the same thing, recursively calling (his opponent) evaluator, unless the maximum depth or some other condition has been reached and a static evaluator is called - and then selects the **maximum** evaluation and sends the evaluations back to you.
- 您可以选择具有这些计算值的最小的移动。这个评估是你在一开始就必须评估的董事会的评估。
(非常)对α-β的简短解释-剪枝
- 您(董事会职位的评估人员)可以选择播放
n移动。你试着所有的一个一个，并把董事会的位置给(对手)评估者-但你也传递你当前的评估(你的董事会)。
- The opponent evaluates the new board position (for him, the opponent side) and sends the evaluation back to you. But how does he do that? He has the choice of playing `m` moves. He tries all of them and gives the new board positions (one by one) to (his opponent) evaluator and then chooses the maximum one.
- **Crucial step**: If any of those evaluations that he gets back, is bigger than the minimum you gave him, it is certain that he will eventually return an evaluation value at least that large (because he wants to **maximize**). And you are sure to ignore that value (because you want to **minimize**), so he stops any more work for boards he hasn't yet evaluated.
- 您可以选择具有这些计算值的最小的移动。这个评估是你在一开始就必须评估的董事会的评估。
https://stackoverflow.com/questions/7888754
复制相似问题
腾讯云开发者
