gpt4 book ai didi

algorithm - Minimax 的 Alpha-beta 剪枝

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:24:20 26 4
gpt4 key购买 nike

我花了一整天的时间在没有真正理解的情况下尝试实现 minimax。现在,我想我了解 minimax 的工作原理,但不了解 alpha-beta 剪枝。

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

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

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

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

  4. 如果您想获得最高分数,请执行得分最高的 Action ;如果您想要最低分数,请执行最低分数。

我对alpha-beta剪枝的理解是,如果parent layer是min,你的node的score比minimum score高,那你就可以prune了,不会影响结果。

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

谁能指出我错在哪里?这个答案 ( Minimax explained for an idiot ) 帮助我理解了 minimax,但我不明白 alpha beta 修剪会有什么帮助。

谢谢。

最佳答案

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

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

如果白棋选择D,我们需要考虑黑棋的反棋。早期,我们发现黑色可以捕获白色皇后,并且由于丢失皇后,该子树的 MIN 得分为 5。然而,我们并没有考虑所有的黑人反击。是否值得检查其余部分?没有。

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

希望对您有所帮助。

关于algorithm - Minimax 的 Alpha-beta 剪枝,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7888754/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com