当前课程知识点：人工智能 > 第五章 对抗搜索 > 5.3.2 alpha-beta算法 > Video
那么我们来看一下这个α-β算法
那么α-β算法 它名字也叫做α-β搜索
那么它的输入就是当轮到这个智能体max下棋的时
候它就调用这个算法
然后把它当前的棋盘状态作为输入
然后这个搜索算法就会返回一个动作让这个max去
执行
所以这个输入就是这个当前的棋盘状态
函数呢 它的语句就是去计算这个当前状态
因为是max结点 这个结点它的分值是多少
也就是说它能够得多少分就是这个极小极大值分
然后呢这个计算分值呢 是调用这个Max-value
计算max结点的这个函数
那么他有三个参数 和前面的极小极大值算法不一
样的
它第一个参数就是我们的这个当前的棋盘状态
第二个参数就是我们的α 第三个参数就是我们的β
那么一开始的话 搜索刚刚开始的时候这个α呢
就是给它一个初值就是给它一个很小的数
因为这个α将来是要取最大值的
因为值越大对于max来说就越好 因为α存储的是
max到当前为止他找到的一个最好的路径的分值
那么这个正无穷就是β的初始化值
也就是说给它一个很大的数
因为β的话将来是要取一个最小值
也就是说β是给min存储了一个最好的分值
所以呢它初始化是给它一个很大的正数给它初始
化
然后呢就调用计算max结点的函数去计算出来这个
当前这个棋盘状态它的分值是多少
然后计算出来这个分值之后呢 就看一下它是哪条
路
也就是说它是哪一个后续状态产生的这个分值
也就是说它是哪一种行动导致的这个后续状态得
到的这个分
那么找到之后就把这个动作返回去让这个max去执
行
那么这个思路跟前面的极小极大值算法是一样的
所以关键就是去计算这些结点的值 效能值 它的分
值
那么我们首先看到对于max结点来讲它是怎么样计
算这个 它的这个分值的
它有三个参数 第一个参数就是max结点对应的棋
盘状态
第二个参数就是我们的α 也就是说到当前为止它搜
索过的路径 一个最好的一种分值
那么这个β就是给min存储的一个最好的这个分值
那么这个它返回的也是这个max结点的一个效能值
或者说叫做极小极大值 也就是说一个分值
那么所以它的这个输入参数是三个 它有三个
第一个参数就是调用它的这个max结点的状态
然后这个α就是我们说的
就是到当前为止 搜索到当前状态为止的
所有的选择路径上面的一种最好的选择所对应的
这个分值
就是我们的α 也就是说它是给我们max存储的
max存储的好的就是越大越好
那么β的话就是搜索到当前状态为止
给min 对于min来讲它的一个最好的一种路径选择
所对应的这个 它的得分
那么这个β当然是越小越好 因为它是min
它是希望越小越好的
那么这个是这三个参数的意思
那么首先我们看一下第一条语句
也就是说当前这个状态是一个终止状态
那毫无疑问的就是立马返回去把这个状态对应的
这个效能函数值返回去作为它的一个分值
那么这是终止状态
也就是说这个终止状态的话 它是不会去更新这个
α、β 也不存在什么剪枝的
就是说他这一条语句它就回去了
那么只有当这个状态它不是一个终止状态
那么就意味着它是有选择路劲的 它下面是有儿子
的
那么有儿子 其实是每一个儿子就意味着它的一种
选择路径
那么我们来看一下这个max结点的分值计算方法和
前面讲过的一样
它就是要去求它的所有的后续结点分值里面的一
个最大值
所以呢我们设一个局部变量v 用来存储
到时候用来存储当前这个max结点的这个分值
所以给它初始化为一个很小的数 因为它要取最大
值的
所以呢 然后就开始遍历它的每一个儿子（后续）
所以呢for each for a s
就是这个 它的这个当前状态max当前状态的这个
后续s
每一个s都要来做这个事情 首先算出这个s的分值
来
因为我们知道这个max的后续是min
所以要算这个s的分值要去调用MIN-VALUE去计算
等下后面我们看到MIN-VALUE怎么计算的
然后调用这个函数去计算它的儿子的分值
然后计算出来之后呢就看一下那个儿子最大
把最大的这个儿子分值放到这个v里面去
就是不断的去比较这个v和这个儿子哪个更大
把更大的存储到v里面去
这个到时候就是求所有儿子里面的一个最大值
但是每一个儿子的时候 算出来之后呢
它要去判断一下是不是要发生剪枝
也就是说它看一下 到当前这个儿子为止
这个v值 也就是说我们这个max能够得到的分值
是不是会大于等于我的β
这个β就是我们的这个 给min结点存储的一个最好
的分值
也就是说这个max是不是要比我min存储的最好分
值要更大
那么也就意味着什么呢
意味着这个max结点对于min来讲是一个更差的一
个选择
所以呢这个min呢 就会回避这个max
为什么这么讲呢
你想一下调用这个max的函数除了我们这个初始会
调用的话
随着搜索的进行还有谁会调用它呢
就是它的父亲结点会去调用它
因为它的父亲结点要计算每一个儿子的分值
而这个max个父亲结点是谁啊 是min
min结点的话它有很多个儿子 很多个max儿子
如果它发现这个儿子的分值更大
比我原来找到的那种选择更大
也就是说意味着这个儿子更差
那么它的父亲结点就会避免max这条路的
所以呢它就根本就不会去遍历这个max下面的其他
的子分支了
所以就会直接的把这个v返回去
就是相当于把这个max这个分支它压根就不考虑了
所以其他的max下面的儿子压根就没有用了
所以把其他的儿子就剪枝掉了 就直接回去了
这一句就回去了 把这个v回去 就作为max的一个
值
尽管这个v根本就不是它的实际值
但是因为这个max这个分支对于我的min来讲
它根本不会走这个分支 所以直接让它回去
就这个意思
否则的话 也就是说否则的话就是不发生剪枝
不发生剪枝的话 那对于max来讲它就要看一下
我选择的这个儿子 这个分支 是不是一个更好的一
种选择
所以它要去判断 要去判断它原来存储的那个α值更
大还是当前的v更大
反正这个α要存储一个 最好的一种 对max来讲的
最好的一种选择
所以它要更新这个α的
所以这里面就是和min-max算法不同的两个 加了
两条语句
第一条就实现剪枝 第二条就实现记录α的功能
等一下这个后面我们会看到一个实际的例子 大家
就明白这个什么意思了
所以大家一定要记住这里的剪枝是针对它的父亲
结点而言的
而这里的α是针对的当前max结点而言 它这个儿子
就是它的分支选择
所以它要看一下这个分支选择是不是一个最好的
选择
所以要更新这个α 是这个意思
那么所有的儿子 如果都没有发生剪枝的话
那么这个for循环就全部结束
然后找到一个最大值作为这个max结点的值返回去
这个就是我们计算 这个max结点值的一个函数
那么同样的的道理 计算这个min结点的这个函数
它也是一样的
那么它也是有三个参数
第一个参数就是这个min结点对应的这个状态
第二个参数就是α 第三个参数就是我们的β
那么它返回的也是这个min结点的这个效能值的
那么它这个三个参数的意思就是一样的
那么同样的道理 它也是首先看一下这个min结点对
应的状态是不是一个终止状态
如果是一个终止状态 很简单的
那么利用这个效能函数呢 得到它这个状态的分值
直接返回去了
因为这个状态是一个终止状态的话 就意味着这个
min结点它是没有儿子
也就是说它不是一个需要选择 需要作出选择的结
点
也就是说它就不需要去更新α更新β之类的
不需要做这些事情
那么如果不是一种终止状态的话
意味着它是一个 这个结点是一个分支结点
它有这个 多个这个选择
所以呢我们就要来计算它的这个值
那么我们计算它的值同样的要定义一个局部变量v
这个局部变量v的话用来存储这个min结点的分值
那么因为我min结点它是 求的是它的儿子分值的最
小值
所以初始化的时候给它初始化为一个很大的正数
那么同样的道理它要遍历它的这个所有儿子
那么for each s in当前的min结点状态的后续状态s
都要做这些事情 首先计算出来这个儿子的这个分
值
这个儿子的分值 因为min结点的儿子是max
所以去调用Max-value去计算它儿子的分值
计算出来之后呢 然后比较一下这个儿子这个值 和
当前存储的这个v哪个更小
反正把最小的放到这个v里面存储起来
那么这个和前面的min-max是一样的
那么每去计算一个儿子的值的时候 他要判断一下
是不是要发生剪枝
那么这个剪枝它怎么判断呢
那么首先看一下这个v 这个儿子的值是不是要比我
这个α的值还要更小
那么这个什么意思呢 因为我的min结点的话它是要
取最小值的
那么如果你当前都已经比我的α更小
那么意味着将来这个min结点这个值肯定比α更小
那么比α更小 那就意味着什么呢
因为min结点的父亲结点是max结点
那么意味着它的父亲走这条路就更差
那么它的max 它的父亲结点max就不会去走这个
当前这个min结点
所以当前这个min结点它压根就没有意义
所以立马就发生剪枝 立马就回去了 把这个v值返
回去
作为它的一个 这个值
因为这个值没有用所以准不准确没有关系
就是发生剪枝了 就回去了
因为我的max压根就不会选择这个分支走下去
所以呢它 它对于将来的值是没有影响的
如果不是的话那就往下走 那就去看一下
这个儿子是不是对于我们的min来讲是一种更好的
选择
那么是对于当前这个结点来讲 这个儿子是不是一
个更好的选择
所以就要去更新我们的β 也就是说更新我们的 给
我们的min结点更新这个β
看一下这个原来存储的那个β值和我当前这个v值
哪个更小
小的放起来 说明是一种更好的选择 是这个意思
对于min结点来讲是一种更好的选择
如果这个所有的儿子都没有发生剪枝的话呢
那么它这个整个循环结束之后呢
这个v里面就存储的是它所有儿子里面的最小值
所以就把这个最小值作为这个min结点的分值返回
去了
那么这个就是我们的这个计算min结点的这个函数
所以他跟前面min-max不同的地方就是
它多了一个α β 并且它多了一条剪枝语句
和多了一条更新这个β的这个语句
-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卡尔曼滤波器
-结课测试
