大家好
欢迎回来
那么我们这一节还继续
基于决策树和搜索的人工智能系统
那么在上一节的minmax值
minimax决策树的决策过程当中
我们得到了一个很好的全局的一个最优解
那么下面我们来看看针对这个minimax来如何
进行一个所谓的叫做AlphaBeta剪枝
那么什么叫AlphaBeta剪枝
我们首先观察minimax值的方法
那么这个方法显然为了求出最大和最小值
每个结点的max结点的最大值以及min结点的最小值的话
那么它需要把整个的局面树
也就是决策树所有的局面全都要进行计算出来
那么这样对于一些局面复杂的问题
就需要很大的空间
很大的内存空间以及很长的计算时间
当然我们说对于井字棋这样很简单的这种棋来讲并没有所谓
但是你一旦扩大到像黑白棋8X8
国际象棋甚至中国象棋
这些更复杂的棋类的时候
那么整个的决策树就会变得非常的大
而且我们其实观察到有一部分的结点
它实际上跟最后的结果是没有关系的
而且并不需要去把这个结点他的下边的局面再
进行展开和计算它下面的这些子节点的所有的这些估值
如果这些节点没有必要的结点不计算的话
那么就可以大量的节省对于这些局面保存的
内存空间以及算法的搜索时间
所以这种不计算就很形象地称之为
在决策树上把一些子结点删掉的做法就称之为剪枝
那么这种剪枝叫做AlphaBeta剪枝
是一个什么样的过程
它的剪枝的过程会很显然能够加速minimax的搜索的过程
我们就想到说给每一个结点给它保存
除了局面的估值之外
还保存一个结点估值可能取值得的一个上下界
为什么呢
因为我们在整个计算估值的过程当中
可以按照一个顺序来进行计算
我们原来是要知道一个结点
比如说min结点
他的所有的这个子结点当中求出一个最小值
但是我们会发现
实际上如果说我们从左到右这么挨个计算
当我前面已经有一个比较小的值的话
那么后边出现的值比前面的值要来得大
很显然我后边的大的值
它下边的这些所有的局面其实是可以不用去展开和计算的
那么这个就是叫做AlphaBeta剪枝的结果
那么所谓的上下界就是当前这个结点
如果是一个max结点的话
那么他需要维护更新一个所谓的下界
就是Alpha值
我们把这个下界称之为Alpha值
也就是当你计算一个max结点的估值的时候
这个下界就指明了说这个估值不应该小于这个值
而相反min结点他会维护更新一个
上界也是所谓的Beta值
那么这个的意义就是说我在计算min结点的子节点的估值过程当中
如果说某一些子节点它的估值很明显
它要超过上界了
那说明他在整个的选取过程当中一定不会被取到
因为前面会有已经有比他更小的
显然不会被取到
所以超过Beta的子结点
就不需要再去展开这个局面
并且计算下边的这些估值
所以整个原理称之为AlphaBeta剪枝
那么再详细的来讲
比如说我们对于max结点而言
他进行子结点搜索的时候
比如说我们这里头这个树当中
四方形的矩形称之为就是max结点
圆形称之为就是min结点
那么我们在计算max结点的估值的时候
我们首先显然是从下往上从左往右这样一个顺序
当我这个已经有一个结点
它的min值是3
那就说明max结点它最小应该是3
如果说的下一个结点它的估值不超过2的话
那么这些就不再是有计算的必要
为什么它不超过2
因为它的下面max是8
然后又出现了一个2
那么显然min结点应该是取最小的
那么后边你如果比2要大
显然都不需要进行计算
所以这时候就被剪枝了
所以我们说只要你当前的Alpha就是下限设为3的话
你一旦碰到它有可能是小于等于2的情况
那么整个的后边都可以不用计算
这就叫做Alpha剪枝
那么Beta剪枝是相对于min结点而言的
min结点他在搜索子节点的时候也是同样的过程
我们这个圆是一个min结点
那么它的下面是一个max结点
他得到了一个4的一个估值
那么也就是说min节点当中
它的上限就是4
如果后边如果超过4的话
那么就也不需要进行计算了
对吧
那么后面我们看到这个min是8
那么就说明这个结点至少是8
因为这个是一个max结点
至少是8
那么一旦出现这个8
那么后边全都不需要计算
就可以给它剪掉
所以这个叫做Beta剪枝
那么这样的话
AlphaBeta剪枝改进的整个过程算法
对于minimax整个的改进的算法是这样的
首先也是构建决策树
但是它并不需要像minmax这个方法一样把
整个决策树全都构建出来
他可以开始构建边计算估值
当然如果碰到了这个叶结点
就是最底层的终结结点的话
那么就把局面估值函数直接应用于叶结点
把它的估值给计算出来
然后做所谓的深度优先
什么叫深度优先
其实一般来讲在一棵决策树上
因为要进行搜索的时候
它尽量的往左下角走
从下往上从左往右
就按照这样的一个顺序来进行
那么按照这个顺序
你就可以逐步的传递和更新我们的下限值上限值以及结点的估值
那么对于max结点来讲
它更重要是更新下限就是Alpha值
对于min结点来讲
它就应该逐步的更新
它的上限就是Beta值
那么在这样整个的推的过程当中
就是会遇到很有可能我们不能说必然
很有可能会遇到被剪枝的情况
那么只要整个过程出现大量的剪枝的话
那么可想而知
我们整个的决策树就不需要被完整地建立起来
我们只需要决策树的一部分
也同样能够得到最优的决策
那么最后我们也是到根结点为止
去选择一个评估值最大的一个分支
作为我们行动的一个决策
那么我们还是以井字棋作为例子来看看剪枝的整个过程
首先我们看到这个是一个完整的一个决策树就是一个局面
它每个节点都是一个局面
如果是一个纯粹的minimax值的方法的话
那么显然我们要把整个决策树展开
然后计算出所有的结点的估值
然后一层一层的往上推
然后到一直推到根结点
我们就能够得到行动的决策应该是下哪一步
那么在AlphaBeta剪枝的方法当中
我们实际上就有一个顺序
这个树就是由下往上由左往右这么一个顺序
那么这个顺序里头在这可以看出来
我们先首先只要计算这五个局面
这五个局面的值
其中到了叶结点一个3一个1
那么max结点显然就是3
那么max的节点是3
那就意味着它上面的min结点
他的上限3
min结点的上限就是3
那么这个上限为止
我们再来往下看
我们一看这个计算了一个4
那么这个4这是一个max结点
说明它这个max节点当中它不会小过4
max结点它的最终的估值它不应该小过4
它有一个下限
那么一旦不小过4
那就说明3和4当中
3和可能4或者以及比4还要大
那么显然这个已经没有计算的必要了
它不会被选到
所以最终min结点应该是选择3
所以这里就被剪枝
那么再继续往下
这里有一个2一个1
那么max节点它就是2
2的情况下
就说明这个min结点
他的这个值它不会比2来得更大
它有一个上限
那么这样有一个3还有一个2以及还可能比2还小的情况
说明后边的这些都不需要再计算了
因为永远不可能再选到他
因为3永远都会比他来得大
所以最终我们肯定会选择比他来得大的3
所以我们最后在不需要计算所有的整个的决策树的情况下
我们就得到了最终得到的根结点的估值是等于3
而且3来自于他左边这个节点
最后我们也是同样的通过minimax法加上AlphaBeta剪枝的方法
在减少了很大的计算量的情况下
我们也同样得到了一个最优的决策
那么这就是一个剪枝的其中的一种方法
当然在minimax的基础上
其实有很多其他的这种更精细的这种剪枝的方法
那么AlphaBeta剪枝是用的最多的
也是最为经典的一种方法
他在很多的这种完全信息零和博弈的这种游戏当中
或者说博弈的决策当中被广泛的应用
这个也是我们人工智能系统在基于决策树和
基于搜索这么一个算法的前提下
人们逐渐发展的更加精细更加高效的算法
那么后面我们还会在逐渐的看到
是不是还有更多的方法来去进行改进
使得人工智能系统更加的高效更加的智能