大家好
欢迎回来
我们今天这一节还是介绍基于决策树和搜索的人工智能系统
我们再接着讲零和博弈当中的最大最小法
我们知道在完全信息的零和博弈游戏当中
玩家在可选的选项当中的进行选择的时候
应该要在决策树上选择自己优势最大化的一步下法
不光是棋也好牌也好
那么反过来也就是说
要选择令对手优势最小的那种方法
所以就有最大最小这么一个概念
但是我们在实际的博弈的过程当中
必须承认
作为一个回合制的游戏
当然你不能够假设说对方就一定比你笨
所以应该假设双方都很聪明
双方都要采取一个最优的策略
那么最优的策略
这样就使得我们这人工智能系统在进行选择的时候
在一步步往前看的时候
显然就是我要下的这一步
就应该是我的收益最大的这一步
那么下面再往前看的时候
也就是说对手要应对我们的时候
应该是使得我们自己收益最小的
所以这样的话
因为是回合
我下一步对手下一步再我下再对手下
所以这时候我们在决策树上进行计算的时候
就应该是我方的收益最大
然后我方的收益最小
再是我方收益最大
最后还是我方收益最小
这样就叫做最大最小这么一个过程
所以这种算法就叫做最大最小法
那么最大最小法的决策树
最大最小法我们可以叫做minimax这种方法
那么他这样的一个决策树就很有特点
那么这个特点就包括决策树
我们知道都是分层的是吧
那么最高这一层是我方收益
然后接下来就是对方下的时候
对方下的时候我方的收益
再下一层又颠倒过来
所以我们把这样的一个现象
就把决策树上每一个局面
它的评估值就分成最底下这一层
最底下就是已经下完了
或者说我终止搜索
因为在很多的情况下
一些棋它的局面特别的复杂
他的步数很多
如果是这样的话
那么我不可能一直搜索到最终的终局
我可能只会搜索到往前
比如说往前看十步
十步十层就是一个终局
那么最后那一步
就是一个终局的步骤
终局往上
可能就是对方下得
再往上就是我方下的了
那么就把我方下的收益叫做max结点
把对方下的收益叫做min结点
所以我们在整个的minimax决策树上
就有三种结点
我方下的收益就应该是max最大结点
然后对方下的我方的收益是min最小化收益
然后还有最后的终局
所以应该有max-min-max-min
然后最后一直到最终的一个终局
我们这样对于决策树来说
我们就需要首先把决策树上的所有的结点的
估值给它计算出来
那么这三类的结点估值都是什么样的情况呢
很显然对于终止结点就是最后的终局的结点而言
它的估值就相当于直接对局面的一个估值
我们在前面谈到不同的棋按照规则有不同的估值函数
比如说在我们的井字旗的游戏当中
我们有一个估值函数
就是在我方这个情况下
对于我方来说
我还有多少种可能能够构成三连
构成同一条线的横竖斜
如果有一种可能
那么估值就是一两种可能估值就是二
那么这样对于局面的一个估值
所以最下边的终止结点
那么他的决策树上的估值就直接等于这个局面的估值
就跟我们原来的估值函数是一样的
而对于这个max节点就是我要下这一步
那么显然我是应该选择最大化估值最大化收益的
那么这个就是选择它下一层的节点当中
最大的值作为我max结点的值
这个min结点就反过来
也就是他的下一层
它的子节点当中选择一个最小的值
作为min结点的值
所以我们可想而知
要构建出整个的决策树的所有的估值的话
应该是从最终的最下层的一个终止结点
开始对每一个局面进行估值
然后一步一步的往上给他推回去
如果是min
那么就是选择一个最小的作为min结点的估值
如果是max
那么就是在所有的子结点当中
选择一个最大的作为max节点的估值
这就是minimax的整个的算法的原理
所以我们说整个算法的过程也相当的明确
第一个
首先我们要把决策树给它构建出来
那么决策树就包括了每一个结点都是一个下棋的一个局面
一直构建到最后的终局结点为止
然后第二就是把所有的评估函数
我们原来有一个对于局面有一个评估函数
把它应用到最底层的叶结点当中
把它的所有的评估值就是终止结点这个评估值给算出来
算出来以后从底向上
一步一步的计算出每一个结点的minimax值来
最后我们建立起minimax决策树之后
我们要指导我们下一步棋
对吧
那么下一步棋最终就是从根结点里头
根结点显然就是一个max结点
也就是应该是我下这一步
那么max结点里头选一个它的最大分支
因为它是从它的子节点当中选一个最大的
作为他自己的估值
那么也就是他选一个导向最大的节点的路径去下这一步棋
作为它最终的行动的决策
然后我们来仔细的看一下整个的算法过程
首先第一步就是构建决策树
对于我们的井字棋游戏来说
显然我们要构建决策树
就从一个空棋盘开始
这棵决策树我们可以看到它是针对叉的
就是这个拿叉的棋手他应该怎么下
我们可以看到它的第一层所有的子节点
它的局面就是有九种情况
是吧
下在左上角
上中上右和中左中央中右
还有下左下中和下右
这九种情况
这是第一层
第二层就是对方下
对方下这个圈
挨着我下还是隔着下、在我的下方下
那么这个也会有一系列的局面出来
我们把整个的决策树给它构建出来
构建完了以后
我们从最底层的叶子节点开始估值
用我们的局面的估值函数
所以我们就可以得到说
最后应该是下不下去了
所以就有一个如果是负无穷的话
那么这个估值就表示我已经我肯定会输
那么如果是和棋就是零
如果我赢了
那么就是一个正无穷
所以下面有三种这样的情况
那么这样的估值一步步的在第二步我们在进行
决策树上的所有其他的内部结点的估值的求值
那么求minimax值主要的流程就是
第一个
如果说这个结点是一个终止结点的话
那么就刚才我们的方法就应用我们的局面的估值函数来进行求值
把所有的最底层的给它算好
那么一步一步的往上推
那么往上推
如果上一个结点是一个max结点
也就是我要下的话
那么就找到max结点的每一个子结点的值
它每个节点就是下面
它有几种下法
每一种想法就是它的一个子结点
每一种下法它都有一个评估值的时候
找到其中最大的子结点值作为max结点的估值
那么反过来
如果某一个结点它是一个min结点
那么我们就也一样找到min结点
它往下下的有几个局面
每个局面它的估值
因为如果是一个结点
它的子结点就是它的下一层结点的话
必然这些子结点的值评估值就已经是算好的
因为推到最后是最终的最下面那一层
是吧
最下面那一层我们已经在第一步
如果是终止结点已经用局面估值函数已经求出来了
所以如果这个结点是一个min结点的话
那么我们就找到min结点
他是子结点所有的值
然后求出其中最小的结点值
把它作为min结点本身的估值
所以这样min-max一直往回推
从最底层的终止结点往上推
一直推到最终的根结点
最后作为我们的行动的依据
那么具体来说
我们来看看其中的一部分
就对井字棋游戏当中的这一部分
我来看看这个算法的整个过程
那么首先我们已经构建起这一部分的
我们这个是往前看一步两步三步往前看三步
这样的情况下
我们构建了一个四层的这么一棵树
那么它有一个终止的结点
我们把终止的每个局面
它的估值都算出来
我们可以看到有的是3
有的是4
有的3
有的是1、2、1、1
然后我们由终止结点往上一层来算
上一层是max结点
max结点就把每一个终止结点里头的最大的
那部分给它挑出来作为它的值
这里头最左边左下就是一个3一个4
那显然它应该是4
那么这里有一个3一个1
那么它就是3
那么这里一个2一个1
那么它就是2
这是max结点
它的估值就算出来了
这个估值就说明说我们在这个节点当中是我们
下一步是我要去下叉的棋手要去下的时候
我们应该选一个更有利于我们的局面
那么再往上就是min结点
min结点应该是轮到对方下
对吧
那么对方下的时候就显然要选一个我方优势最小的
因为我们必须要承认对方跟我们一样聪明
他也会采取这样的类似的这种策略
那这种的估计是合理的
比如说一个是4
一个是3
那么在min节点当中就应该一个比较小的值就是3
那么一个2一个1的情况下
那么我们min结点就应该选1
然后再往上最上一层
它又是一个max结点
就是我方要下的时候
当我要看到这个局面
我方要下的时候应该要下到哪儿
那显然一个3一个1
我就应该这个值是一个3
是一个3
那么值在3的情况下已经一直往上推
已经跟结点已经计算完了
也就是说整个决策树上的所有的评估值已经都计算完成
接下来我们就要选择说我应该下哪一步
那么这个其实很清楚了
对吧
在根结点当中
它的估值是3
3是从哪来的
3是从我下在左上角这一步来的
所以我们的下一步应该下哪
所以叉棋手它就应该下在左上角
就V等于3这个步骤里头
所以我们这一节主要的给大家介绍了一个最大最小法
那么通过最大最小法
我们知道这个是一个对于完全信息零和博弈的情况下
一个比较经典的一个算法
那么通过最大最小法
可以在我们信息完全信息对等大家都平等的情况下
那么得到我方下棋的
我方决策的一个最优的策略