Minimax的Alpha-beta修剪-Java 学习之路

我花了一整天的时间试图在没有真正了解它的情况下实现minimax . 现在，我想我理解minimax是如何工作的，但不是alpha-beta修剪 .

这是我对minimax的理解：

生成所有可能移动的列表，直到深度限制 .
评估底部每个节点的游戏区域有多优惠 .
对于每个节点（从底部开始），如果图层为最大，则该节点的得分是其子节点的最高得分 . 如果图层是min，则该节点的得分是其子项的最低得分 .
如果您尝试最大分数，则执行分数最高的移动;如果您想要最小分数，则执行最低分数 .

我对alpha-beta修剪的理解是，如果父层是min并且你的节点得分高于最低得分，那么你可以修剪它，因为它不会影响结果 .

但是，我不明白的是，如果你能计算出一个节点的分数，你需要知道一个低于节点的层上所有节点的分数（根据我对minimax的理解） . 这意味着您仍将使用相同数量的CPU功率 .

任何人都可以指出我错了什么？这个答案（Minimax explained for an idiot）帮助我理解了极小极大，但我不知道alpha beta修剪会有多大帮助 .

谢谢 .

5 回答

3

要了解Alpha-Beta，请考虑以下情况 . 这是白人转，白人试图最大化得分，黑人试图最小化得分 .

White评估移动A，B和C并找到最佳得分为20，然后考虑在评估移动D时会发生什么：

如果白色选择移动D，我们需要考虑黑色的反向移动 . 在早期，我们发现黑色可以捕获白色女王，并且由于失去的女王，该子树获得的MIN得分为5 . 但是，我们并没有考虑所有黑人的反击 . 是否值得检查其余的？没有 .

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

希望有所帮助 .

回复于 2024-04-25T21:59:35+08:00
1

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

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

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

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

回复于 2024-04-25T21:59:35+08:00
15
（非常） mimimax 的简短说明：
- 您（董事会职位的评估员）可以选择播放 n 动作 . 你尝试了所有这些，并给（对手）评估员提供了董事会职位 .
- 对手评估新的棋盘位置（对于他，对手方） - 通过基本相同的事情，递归地调用（他的对手）评估者，除非达到最大深度或其他条件并且调用静态评估者 - 然后选择 maximum 评估并将评估结果发回给您 .
- 您选择具有这些评估的 minimum 的移动 . 而评估是对您在开始时必须评估的董事会的评估 .
（非常） α-β-pruning 的简短说明：
- 你（董事会职位的评估员）可以选择播放 n 动作 . 你尝试所有这些 one by one 并给（对手）评估员提供董事会职位 - 但你也传递你当前的评估（你的董事会） .
- 对手评估新的棋盘位置（对他而言，对手方）并将评估结果发回给你 . 但是他是怎么做到的？他可以选择玩 m 动作 . 他尝试了所有这些并将新的董事会职位（一个接一个）交给（他的对手）评估员，然后选择最大的一个 .
- Crucial step ：如果有的话那些他回来的评价，大于你给他的最低评价，可以肯定的是，他最终会返回至少那么大的评 Value （因为他想要 maximize ） . 并且你肯定会忽略这个值（因为你想 minimize ），所以他停止了他尚未评估的板子的更多工作 .
- 您选择具有这些评估的 minimum 的移动 . 而评估是对您在开始时必须评估的董事会的评估 .
回复于 2024-04-25T21:59:35+08:00
1

这是一个简短的答案 - 您可以在不计算其所有子项的精确值的情况下了解节点的值 .

一旦我们知道从父节点播放器的角度来看，子节点不能比先前评估的兄弟节点更好，我们就可以停止评估子子树 . 这至少是坏事 .

回复于 2024-04-25T21:59:35+08:00
1
我认为你的问题暗示了对评估功能的误解

如果你能计算出一个节点的分数，你需要知道一个低于节点的层上所有节点的分数（根据我对minimax的理解）

我不完全确定你的意思，但听起来不对 . 评估函数（EF）通常是非常快速的静态位置评估 . 这意味着它只需要查看单个位置并从中获得'verdict' . （IOW，你并不总是评估一个分支到n层）

现在很多次，评估确实是静态的，这意味着位置评估功能是完全确定的 . This is also the reason why the evaluation results are easily cacheable （因为每次评估一个位置时它们都是相同的） .

现在，例如国际象棋，通常有相当多的公开/隐蔽偏离上述：
- 可能会根据游戏背景对位置进行不同的评估（例如，在游戏过程中确切的位置是否确实发生过;没有进行典当移动/捕获的移动次数，传球和投掷机会） . 最常见的解决方法是将该状态实际纳入'position' 1
- 通常为游戏的不同阶段（开放，中间，结束）选择不同的EF;这有一些设计影响（如何在更改EF时处理缓存评估？当不同层的EF不同时，如何进行alpha / beta修剪？）
说实话，我不知道国际象棋引擎如何解决后者（我只是为我的玩具引擎避免使用它）

我会参考在线资源，例如：
1就像“检查”/“僵局”条件一样，如果它们在评估函数之外并不是特殊的套装
回复于 2024-04-25T21:59:35+08:00

Minimax的Alpha-beta修剪

5 回答

相关问题