Video在线视频

那么极小极大值搜索 也就是Minimax搜索算法

需要检查 需要计算的游戏结点数目呢

是随着这个推理层或者是搜索深度

呈指数级增长的

那么我们知道博弈游戏呢它是有时间限制的

每个棋手有时间限制

那么在有限的时间里面

那么你如果需要往前推理往前搜索很多层的话

搜索到终止状态的话

那么你要搜索这么多个结点的话

可能时间上就来不及

那么有一种方法就是一种剪枝的方法

这种剪枝思想呢 就可以消除部分的搜索树

也就是说只搜索 只计算部分的博弈树

那么这种技术呢 称为 在我们的博弈算法里面呢

就称为α-β剪枝

那么这α-β剪枝 这个α、β到底是一种什么样的概念

我们后面会讲 不用着急

也就是说我们通过这个α-β剪枝呢

就可以只遍历博弈树中的一部分结点

也就是说不需要遍历这个博弈搜索树中的

每一个结点

它就可以计算出正确的这个Minimax值

极小极大值 从而 也不会影响最终的这个搜索结果

和最终的这个游戏的招数

那么我们来看一下这一个例子

这个例子就是一个α-β剪枝的一个例子

为什么它可以实现剪枝

大家看到这里 这里我们的max

就是我们调用这个算法的这个智能体max

也就是说它在选择下棋的招数的时候

首先看我第一种下棋招数会产生一个儿子

那么这个儿子呢会返回一个分值3给它

因为它第一个儿子是一个MIN

MIN的话它下面有三个儿子是 3 12 8

我们根据这个求分值的公式我们知道

MIN的话是取它儿子的最小值 所以它等于3

那么MAX呢是取它儿子的最大值

那么它知道有一个儿子给它三分

那么它取最大值的话 这个最大值肯定会大于等于3

其中因为有一个树枝已经给了它3了

然后它就会去看第二条路径

第二个动作会给它多少分

那么第二个动作的话呢 它第二个儿子

它去算它的分值 第二个儿子同样也是一个MIN结点

MIN结点它也是 这个分值怎么计算呢

它去看它儿子的最小值

那么首先它搜索这个 第一个儿子

第一个儿子计算出来等于两分

那么我们的MIN结点我们就知道了

我最终的分值会小于等于二

因为MIN的话它是求它儿子的最小值

所以这个时候我知道我已经小于等于2了

也就是说这个儿子的分值已经小于等于2了

那么MAX它就会想了

这条路我走下去我最终得到的分呢是会小于等于2

而这条路（第一条路）走下去我会得三分

也就是说这条路压根就没有用了

我不会走这条路 因为这条路的分值会小于等于2

不管你这个分支 这个结点多少分

也不管你这个结点多少分

我这个结点的分值最终肯定是小于等于2的

所以呢它就不用去计算这两个结点

也就是说它这两个结点就不用搜索不用计算

直接裁剪掉去看第三个儿子

所以呢看下第三个儿子 同样第三个儿子是MIN结点

然后呢第三个儿子的第一个儿子是14

我知道我最终的分值是小于等于14

因为MIN是求最小值的 所以呢 再看

然后第二个儿子是5分 那5和14取最小值是5

就知道我最终的分值是小于等于5的

因为还有儿子没有出来 但是有一个儿子已经5分了

然后在看第三个儿子是两分

那么这三个儿子全部出来了

我知道我最终取一个最小值得2分

所以呢执行第三个动作得到这个儿子是2分

执行第二个动作得到儿子的分值是小于等于2

执行第一个动作它得到3分

那么取一个MAX 大家想一下一个3分

一个小于等于2 一个是2

那么它肯定是得三分

所以这个MAX的分值得3分

所以呢它这个α-β搜索算法呢

它就知道它得三分然后就会选这个动作去执行

所以我剪掉的这个两个分支不会影响最终的结果

也就是说这个3分还是3分 还是选择这个动作执行

也就是说我们用这个公式来看一下

同样也是可以证明剪掉的这两个分支的这个分值

不会影响我们根节点最终计算出来的值

大家看到这个根节点的Minimax分值

它是等于它三个儿子的最大值

因为它是一个MAX结点

然后三个儿子呢是MIN结点

所以三个儿子分值的计算呢是它儿子的最小值

那么第一个MIN结点它三个儿子的分值

那么第一个MIN结点它三个儿子的分值

我们都需要知道的是3 12 8 全部搜索出来

所以呢知道它得三分

然后第二个儿子呢它第一个分支出来等于2的时候

我就不需要计算下去了 也就是说它x y尽管不知道

我先放到这里我就不管它 我就放到这

然后第三个儿子呢 14 5 2 那么取最小值它等于2

所以呢最后呢就等于这个

也就是它在3和这个式子以及2之间取一个最大值

那么大家想一下这个取一个最大值会是多少呢

肯定等于3 为什么 一个是3 一个是2

一个是会小于等于2的一个值

那么在这三种值之间取最大值肯定只能是3

因为这个min（2，x，y）一定是小于等于2的

在2 x y之间求一个最小值

这个最小值一定是小于等于2的

因为我已经知道有一个2了

不管x y是等于多少 这个求最小值一定小于等于2

如果你x y比2更小 那这个值肯定是小于2的

x y比二更大 那就是等于2

所以呢你最大这个值就是2

那么我们的max在3和这个值之间

进行取最大的话就只能等于3

所以这个就是α-β剪枝的思想

也就是说它剪除掉的这些分支呢

是不会影响最终的结果的

那么我们来看一下这个α-β剪枝里面的α代表什么

β又是代表着什么

也就是说为了实现这个剪枝

我们需要给这个max记录下来一个

搜索到现在为止的所有的选择路径上面

发现的这个最好的一种选择方案的值

也就是说它的这个Minimax值

那么max最好的值就是一个最大值

记录下这个α之后 它就知道什么时候应该发生剪枝

比如说像这个图里面 这个是一个max

那么他可能有好多条路

那么它发现它搜索到这个点的时候呢

他目前为止找到的一个最好的一条行动方案

它给它的值是α

也就是说它往这边走 这样下棋它可以得到α分

那么假设它现在搜索到这里来了

搜索到这里来了之后呢 这个max结点呢

它可以选择这样走 这样走 这样走

一旦它发现这条路走下去它只能得v分

那么只能得v分的话

如果它发现这个v分比我往这条路走的α分还更小

那么就意味着更差 那么它肯定不会选择这样走的

所以呢这条路径这个分支就可以删掉去

就可以减掉去 就不用去计算 也不用去往下搜索了

所以这个就是这个α的这个作用

那么类似的这个β是给min记录的

也就是说这个min结点 像这种min结点

min结点下面它也有很多的分支 选择

它可以选择走这个 选择走这个 选择走这个

那么它也是给它min结点记录搜索到当前结点为止

所有的可供选择的路径上面它最好的一种方案

它的这个值 最好的值

那么min的话最好的值就是最小的值

所以呢这个β就是一个最小的值

那么一旦它发现这个min

哪个分支路线上面这个结点这个分支点

给它的值 可能返回来的值会比这个β更大的话

那么它也会把这个分支就不用去计算它了

也不用去搜索它了 就直接把它减掉

所以这个就是为什么叫做α-β剪枝

就是因为它设置了两个变量

用来记录max和min搜索到当前结点为止的

所有可供选择路径上面的一种最好的选择的值

所以这个就是α β的意思 那么有这个记录之后

就可以判断什么时候应该发生剪枝