α-β剪枝算法

算法简介

1）前提条件

α-β剪枝算法是对极大极小算法的优化，当然前提条件也都是一样的，以五子棋为例：
（1）双方都按自己认为的最佳落子行棋；
（2）对给定的盘面用一个分值来评估，这个评估值永远是从一方（搜索程序）来评价的，我方有利时给一个正数，对方有利时给一个负数。

基于上述前提，以我方分值来评估，总结为：
之后的每一步，我方总是选择分值最大的，对方总是选择分值最小的（即负数最大）

2）具体分析

N：是当前节点的评估值
α：最大下限，即我方，初值取-∞
β：最小上限，即对方，初值取+∞
最终我们所能选择的节点即为：α ≤ N ≤ β

解释一下，说的绕一点就是，我方是在对方选择了分值最小的情况下选择最大的。
假设该我方落子，只看两步的情况下，考虑的应该是下一步对方下了对我最不利的地方时我所要下的对我方最有利的位置。
所以α是最大下限，β是最小上限。
但如果出现如下情况，则需要剪枝：


这里为什么出现了等于的情况后后面的也要剪掉，是因为我们知道此时的α已经取到了最好的情况，后面不会比这个更好。

图示分析

参考文章 http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html
不多说，直接上图：

口：此节点代表我方举动，也称为MAX节点
⚪：此节点代表对方举动，也称为MIN节点

最终结果即为第一张图。