一尘不染

用于Minimax的Alpha-Beta修剪

algorithm

我花了整整一天的时间来尝试实施minimax而不真正了解它。现在,我想我了解minimax的工作原理,但不了解alpha-beta修剪。

这是我对minimax的理解:

  1. 生成所有可能动作的列表,直到深度限制为止。

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

  3. 对于每个节点(从底部开始),如果层数最大,则该节点的分数是其子节点中的最高分数。如果层是最小值,则该节点的分数是其子节点中最低的分数。

  4. 如果试图使分数最高,则执行得分最高的移动;如果希望分数最低,则执行最低的移动。

我对alpha-beta修剪的理解是,如果父层为min,并且您的节点的得分高于最小得分,则可以对其进行修剪,因为这不会影响结果。

但是,我不了解的是,如果您可以算出一个节点的分数,则需要知道低于该节点的层上所有节点的分数(以我对minimax的理解)。这意味着您仍将使用相同数量的CPU能力。

有人可以指出我出了什么问题吗?这个答案帮助我理解了minimax,但是我不知道alpha
beta修剪将如何提供帮助。

谢谢。


阅读 257

收藏
2020-07-28

共1个答案

一尘不染

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

怀特评估A,B和C的动作,发现C的最佳得分为20。现在考虑评估D时会发生什么:

如果白色选择了D步,我们需要考虑黑色的反步。早期,我们发现黑色可以捕获白色女王,而子树由于丢失了女王而获得的最低分是5。但是,我们尚未考虑所有黑人的反动。是否值得检查其余部分?没有。

我们不在乎黑人是否可以得到低于5的分数,因为白人将“
C”移动到可以使得分保持在20。黑人不会选择得分高于5的反击,因为他正试图最小化得分,并且已经发现得分为5的举动。对于白色,一旦D的MIN(到目前为止为5)低于C(肯定为20),则C优于D。因此,我们在那里修剪树的其余部分,弹出一个级别并评估白色移动E,F,G,H
....到最后。

希望有帮助。

2020-07-28