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不同的地方就是

它多了一个α β 并且它多了一条剪枝语句

和多了一条更新这个β的这个语句