导入

什么是Alpha-Beta剪枝，Alpha-Beta剪枝到底有什么用呢？
甲乙两人正在玩报数计分游戏，甲乙两人可以报1~2的数字，当其中一人在报完数后计分板累计数字和为4则胜利。假设有一块计分板，计分板的初始值为0。假设甲先报数3，计分板更新为3；乙接着报数3，计分板更新为6，则乙胜利。将这场游戏的所有情况画成下图：

由于在树的顶端局势才刚刚成立我们很难知道一个选择对后来的结果产生什么样的影响，所以在博弈树中我们一般从上往上看这些结果是由什么选择造成的。
假设我们是甲，那么我们不会让乙轻易的得到4，于是我们在3rd时（左下橙色区域），我们不会出1而是出2

那么乙如果知道我们选择出1那么他上一步（2nd）则不会选择1而是会选择出2……

现将对甲有利的情况全部改为1，对乙有利的情况改为-1
则方框的意思是，当走这一条路时，若为1则甲必胜，如果是-1则乙必胜。最顶上的1表示甲一定必胜。

知道博弈树有什么用处后，我们来看看如何进行Alpha-Beta剪枝，将博弈树中对自己不利的条件都减掉，减小树都规模，减少搜索时间。

Alpha-Beta剪枝解题

解题顺序：左子树 -> 根 ->右子树
【例题1】一个简单例子：

可以意象为你正在比赛，方框里的数字越大则表明你胜算越大
我们先遍历左子树（右下粉红色部分），若对手选择左边的路则你的胜算≤4；若选择右边的路则你的胜算≤3，那么对手肯定选择右边。

回到根，此时结果是你的胜算≤3。

我们继续看右子树：如果对手选择右边，则你的结果≤-1，和之前结果相比你的胜算更小了，那么剩下的子树都不需要看了，于是右边剪枝。

完整解题思路

  • 初始化β为+∞，α为-∞
  • 从上至下Max，Min层交替
  • Max层：只改变α，为max(自己这一层的α，下一层的α，下一层β)
  • Min层：只改变β，为min(自己这一层的β，下一层的α，下一层β)
  • α和β是传递的，左中右顺序
  • 当α≥β时剪枝

【例题2】

首先初始化，然后我们到了最左子树，由于这是叶子，所以没有α、β值，直接数字和β（Min层）值比较。
β=min(+∞，10，5)=5

然后回溯到中子树，α=max(-∞,5,-∞)=5

左子树完成到右子树。首先将αβ传递下去（橙色），然后再判断αβ是否需要更改（紫色）。更改完后再传上去中子数，更改α。继续传递上去（紫色①）。

左边遍历完后继续右边（墨绿色），并传递αβ下去（墨绿色①②）。
然后继续β=min(7，12，8)，则不需要更改β；然后回溯（墨绿色③）。
回溯更新完α值，我们发现α=β（当α≥β时剪枝），即右边被剪枝（不用看）。
出现了我们的第一个剪枝

然后回溯（天蓝色），β=min(7,7,7)不需要改变，继续回溯到顶。

此时左边遍历完，然后右边。（淡紫色）

下面的如此类推就不详细解释了。
顺序指南淡橙色 -> 薄荷绿 -> 天蓝(传递) -> 玫红色

这样就剪枝完毕了，如果还有什么疑问欢迎评论或者私信大家来一起讨论讨论喔。(｡･∀･)ﾉﾞ

注意：
记得向下传递，向上更新。

参考视频：
https://www.bilibili.com/video/BV1Bf4y11758/?spm_id_from=333.337.search-card.all.click
https://www.bilibili.com/video/BV1nU4y1V788/?spm_id_from=333.337.search-card.all.click