当前课程知识点：人工智能 > 第五章 对抗搜索 > 5.3.1剪枝的概念 > 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搜索到当前结点为止的
所有可供选择路径上面的一种最好的选择的值
所以这个就是α β的意思 那么有这个记录之后
就可以判断什么时候应该发生剪枝
-1.1 人工智能概念
-第一章 绪论--1.1 人工智能概念
-1.2 什么是理性智能体
--1.2理性智能体
-第一章 绪论--1.2 什么是理性智能体
-2.1.1问题求解智能体
-第二章 无信息搜索策略--2.1.1问题求解智能体
-2.1.2问题形式化
--Video
-2.1.3 树搜索算法
--Video
-第二章 无信息搜索策略--2.1.2问题形式化
-2.1.4树搜索算法的实现
--Video
-2.2.1搜索策略
--Video
-第二章 无信息搜索策略--2.1.3树搜索算法
-2.2.2宽度优先搜索
--Video
-2.2.3一致代价搜索
--Video
-第二章 无信息搜索策略--2.1.4树搜索算法的实现
-2.3.1深度优先搜索
--Video
-2.3.2有限深度搜索
--Video
-2.3.3迭代深入搜索
--Video
-第二章 无信息搜索策略--2.2.2宽度优先搜索
-2.3.4迭代深入深度搜索性能分析
--Video
-2.4无信息搜索策略小结
--Video
-第二章 无信息搜索策略--2.2.3一致代价搜索
-第二章 无信息搜索策略--2.3.1深度优先搜索
-第二章 无信息搜索策略--2.3.2有限深度搜索
-第二章 无信息搜索策略--2.3.3迭代深入搜索
-第二章 无信息搜索策略--2.3.4迭代深入深度搜索性能分析
-第二章 无信息搜索策略--2.4无信息搜索策略小结
-3.1贪婪搜索算法
--Video
-3.2.1A星搜索算法
--Video
-第三章 有信息搜索策略--3.2.1A星搜索算法
-3.2.2A星搜索算法的最优性
--Video
-3.2.3可采纳的启发式函数
--Video
-第三章 有信息搜索策略--3.2.2A星搜索算法的最优性
-3.3爬山搜索算法
--Video
-3.4模拟退火搜索算法
--Video
-第三章 有信息搜索策略--3.2.3可采纳的启发式函数
-3.5遗传算法
--Video
-第三章 有信息搜索策略--3.3爬山搜索算法
-第三章 有信息搜索策略--3.5遗传算法
-4.1.1什么是约束满足问题
--Video
-第四章 约束满足问题--4.1.1什么是约束满足问
-4.1.2约束满足问题的标准搜索形式化
--Video
-4.2.1回溯搜索算法
--Video
-第四章 约束满足问题--4.1.2约束满足问题的标准搜索形式化
-4.2.2回溯搜索的变量赋值顺序策略
--Video
-4.2.3回溯搜索的前向检查及约束传播
--Video
-第四章 约束满足问题--4.2.1回溯搜索算法
-4.2.4 AC-3弧相容算法
--Video
-4.3约束满足问题的局部搜索方法
--Video
-第四章 约束满足问题--4.2.2回溯搜索的变量赋值顺序策略
-第四章 约束满足问题--4.2.3回溯搜索的前向检
-第四章 约束满足问题--4.3约束满足问题的局部搜索方法
-5.1博弈及极小极大值概念
--Video
-5.2极小极大值决策算法
--Video
-第五章 对抗搜索--5.2极小极大值决策算法
-5.3.1剪枝的概念
--Video
-5.3.2 alpha-beta算法
--Video
-5.3.3 alpha-beta剪枝示例
--Video
-5.4 不完美的实时决策
--Video
-第五章 对抗搜索--5.3.3 alpha-beta剪枝示例
-第五章 对抗搜索--5.4 不完美的实时决策
-6.1不确定性量化
--Video
-第六章 不确定性推理--6.1不确定性量化
-6.2使用完全联合分布进行推理
--Video
-6.3贝叶斯规则及其应用
--Video
-6.4贝叶斯网络推理
--Video
-第六章 不确定性推理--6.2使用完全联合分布进行推理
-6.5隐马尔可夫模型
--Video
-6.6卡尔曼滤波器
--6.6
-第六章 不确定性推理--6.4贝叶斯网络推理
-第六章 不确定性推理--6.3贝叶斯规则及其应用
-第六章 不确定性推理--6.6卡尔曼滤波器
-结课测试
