Alpha-Beta算法
Paste_Image.png
用于Min-Max的剪枝，一些搜索是没有必要的，故此可以剪除（cut-off）那些没有必要搜索,即对搜索进行剪枝（prune)。Alpha-Beta算法是一种有效而常用的剪枝算法.
Alpha-Beta算法是在Min-Max方法基础上的一个改进.它维护一个搜索窗口（search window）:[α, β].其中
α Alpha is the maximum lower bound of possible solutions
当前对抗者能确保达到的最大的结点值，在进一步的搜索中,将竭力提高α这个下限.
ps.可能的最小值
β Beta is the minimum upper bound of possible solutions
表示在搜索进行到当前状态,在对手逼迫下,当前对抗者所达到的最小的博弈值.如果α > β,那么就没有必要再搜索这个结点及其子结点了.
ps. 可能的最大值
初始状态是根节点
Paste_Image.png
而后顺着根节点一直向下延展，直到某一个子节点
Paste_Image.png
其中第四层是对抗者的节点-min节点，试图获取子节点的最小值，所以β＝3
Paste_Image.png
下一步我们查看第四层节点的另外一个孩子
Paste_Image.png
发现是17，由于17>3，所以不会受任何影响。现在我们已经知道了第四层min节点的所有child，所以我们上溯到第三层，第三层是一个max节点，max节点总是取子节点的最大值，而第四层左子节点的最大值是3，因此第三层节点的最小可能值就是3了
Paste_Image.png
而后父节点把属性传给子节点，如下，由于不是子节点，我们继续查找它的子节点，此时是2
Paste_Image.png
2会影响父节点的上限，因此此时变成如下情况
Paste_Image.png
此时α>β了，因此该节点被裁剪掉
Paste_Image.png
回头看我们第三层节点，α＝3，比2更大，因此不用管。而后我们继续向上迭代，第二层为min节点，取所有子节点的最小值，而左侧子节点的下限是3，所以其父节点的上限变为3，如图所示
Paste_Image.png
而后我们继续向下扩充，画出它的左子树，直到根节点，如图所示
Paste_Image.png
发现一个叶子节点为15，向上更新，此时我们更新父节点为它实际的值（为何？节点都不全?应该把节点算全了才能向上更新吧？）
Paste_Image.png
这样，我们就得出了一颗左子树，而后我们继续向上更新即可。
最后来张大图
Paste_Image.png
网友评论