aps*_*nce 12 language-agnostic algorithm artificial-intelligence minimax alpha-beta-pruning
我花了一整天的时间试图在没有真正了解它的情况下实现minimax.现在,我想我理解minimax是如何工作的,但不是alpha-beta修剪.
这是我对极小极大的理解:
生成所有可能移动的列表,直到深度限制.
评估游戏区域对底部每个节点的有利程度.
对于每个节点(从底部开始),如果图层为最大,则该节点的得分是其子节点的最高得分.如果图层是min,则该节点的得分是其子项的最低得分.
如果您尝试最大分数,则执行分数最高的移动;如果您想要最小分数,则执行最低分数.
我对alpha-beta修剪的理解是,如果父层是min并且你的节点得分高于最低得分,那么你可以修剪它,因为它不会影响结果.
但是,我不明白的是,如果你能计算出一个节点的得分,你需要知道一个低于节点的层上所有节点的得分(根据我对minimax的理解).这意味着您将继续使用相同数量的CPU功率.
任何人都可以指出我错了什么？这个答案(Minimax为一个白痴解释)帮助我理解minimax,但我不知道alpha beta修剪会有多大帮助.
谢谢.
phk*_*ler 15
要了解Alpha-Beta,请考虑以下情况.这是白人转向,白人试图最大化得分,黑人试图最小化得分.
White评估移动A,B和C并找到最佳得分为20和C.现在考虑评估移动D时会发生什么:
如果白色选择移动D,我们需要考虑黑色的反向移动.在早期,我们发现黑色可以捕获白色女王,并且由于失去的女王,该子树获得的MIN得分为5.但是,我们还没有考虑所有黑人的反击.是否值得检查其余的？没有.
我们不在乎黑人是否可以得分低于5,因为白人移动"C"可以将得分保持在20分.黑人不会选择得分高于5的反击因为他试图最小化得分和已经找到了得分为5的移动.对于白色,只要D的MIN(5到目前为止)低于C(肯定是20),移动C优先于移动D. 因此,我们"修剪"那里的其余树,弹回一个级别并评估白色移动E,F,G,H ....到最后.
希望有所帮助.