《人工智能》(二): Alpha-Beta算法

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