Minimax的Alpha-beta修剪

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

这是我对minimax的理解:

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

  • 评估底部每个节点的游戏区域有多优惠 .

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

  • 如果您尝试最大分数,则执行分数最高的移动;如果您想要最小分数,则执行最低分数 .

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

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

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

谢谢 .

回答(5)

2 years ago

要了解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 ....到最后 .

希望有所帮助 .

2 years ago

您无需评估节点的整个子树来确定其值 . 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/

2 years ago

(非常) mimimax 的简短说明:

  • 您(董事会职位的评估员)可以选择播放 n 动作 . 你尝试了所有这些,并给(对手)评估员提供了董事会职位 .

  • 对手评估新的棋盘位置(对于他,对手方) - 通过基本相同的事情,递归地调用(他的对手)评估者,除非达到最大深度或其他条件并且调用静态评估者 - 然后选择 maximum 评估并将评估结果发回给您 .

  • 您选择具有这些评估的 minimum 的移动 . 而评估是对您在开始时必须评估的董事会的评估 .


(非常) α-β-pruning 的简短说明:

  • 你(董事会职位的评估员)可以选择播放 n 动作 . 你尝试所有这些 one by one 并给(对手)评估员提供董事会职位 - 但你也传递你当前的评估(你的董事会) .

  • 对手评估新的棋盘位置(对他而言,对手方)并将评估结果发回给你 . 但是他是怎么做到的?他可以选择玩 m 动作 . 他尝试了所有这些并将新的董事会职位(一个接一个)交给(他的对手)评估员,然后选择最大的一个 .

  • Crucial step :如果有的话那些他回来的评价,大于你给他的最低评价,可以肯定的是,他最终会返回至少那么大的评 Value (因为他想要 maximize ) . 并且你肯定会忽略这个值(因为你想 minimize ),所以他停止了他尚未评估的板子的更多工作 .

  • 您选择具有这些评估的 minimum 的移动 . 而评估是对您在开始时必须评估的董事会的评估 .

2 years ago

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

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

2 years ago

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

如果你能计算出一个节点的分数,你需要知道一个低于节点的层上所有节点的分数(根据我对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就像“检查”/“僵局”条件一样,如果它们在评估函数之外并不是特殊的套装