当前课程知识点：人工智能 > 第五章 对抗搜索 > 5.2极小极大值决策算法 > Video
所以看到这个极小极大决策算法
那么它这个函数名就命名为MINIMAX-DECISION
函数这个算法的输入呢就是当前的状态 也就是当
前的棋盘状态
因为轮到它下了 然后它的返回值就是返回一个动
作告诉这个智能体应该如何下这一步棋
那大家看到它的主体很简单的就两条语句
第一条就是因我们的调用算法的智能体是我们的
MAX
我们的MAX 所以呢当前这个状态对应的结点就是
MAX结点
所以呢它就去计算 这个MAX结点 它的这个值
也就是说极小极大值 计算这个值
所以它调用的是这个MAX-VALUE这个函数去计算
这个MAX结点的值
计算出来之后呢得到一个MAX的这个值
就像刚才这样一样得到这个值3
然后呢它就去看一下是这个状态的哪一个后续
对应着这个值 也就是说是哪一个后续结点对应着
这个值
我们看一下是这个后续结点对应这个值
那么这个后续结点是哪一个动作产生的呢
它就把这个动作 产生这个最大值的动作
返回去让智能体去执行
就像这里一样 那么是哪一个后续结点具有3呢
一看这个 是哪个动作产生了这个后续结点 是A1
所以它就把这个A1返回去让智能体去执行
所以这个程序就是这个意思
那么我们这个当前这个状态的这个值
这个MAX值是怎么计算出来的呢
然后我们来看到这里 然后它就要调用这个函数
调用计算这个MAX结点的极小极大值函数来计算
那么要计算这个MAX结点的极小极大值
它的返回值就是算出来一个效用值 就是这个
MAX结点的一个效能值 极小极大值
那么首先我们判断一下这个状态是不是一个终止
状态
如果是终止状态的话直接把它的效能函数值返回
去作为它的值 很简单的
如果不是的话 那么我们根据定义
这个结点是一个MAX结点那就要去
求它所有后续结点里面的一个最大值返回去
作为它的一个值
那么我们就定义一个临时变量v
用来储存这个值 这个max结点的效能值 极小极大
值
那么一开始给它初始化为负无穷 为什么呢
因为我们要求所有后续结点里面的最大值
所以呢它给它初始化为负无穷
然后呢就是进行for循环 就是去它所有的后续结点
也就是说它的所有的后续结点 这个就是后续的意
思
它的每一个后续结点去比较是不是比当前储存的
这个值更大
更大那么就存进来
所以整个儿子节点都比较完之后
这个v里面肯定储存的是一个所有后续结点里面的
一个最大值的
所以呢对于当前这个状态的每一个后续s
他都去看一下v里面储存的值和你这个后续的这个
值那个更大
更大的放到这个v里面去
那么这个后续s它这个值是怎么算出来的呢
因为我们max结点的后续是min结点
所以呢它的这个后续s的值的计算就要去调用另外
一个函数
另外一个函数是用来计算min结点的极小极大值
也就是说用来计算min结点的效能值的
所以呢对于它的每一个儿子
计算它的值的 效能值的时候要去调用MIN-VALUE
来计算
然后呢这个for循环结束完了之后
这个v里面就储存了所有的后续结点里面的最大值
然后这个最大值就是我们的max节点的效能函数值
也就是极小极大值 所以把他返回去
这个就是刚才的极小极大值的定义的一种实现
那么这个min结点它的效能值 它的极小极大值怎么
计算呢
它的这个函数在这里
同样这个min结点它的这个值的计算 它的输入就是
这个min结点对应的状态
然后它返回的就是这个值 它的极小极大值 或者称
为这个效能值
那么同样的首先判断一下这个状态是不是一个终
止状态
如果是的话呢 那么这个状态它是根据我们效能函
数定义
是有一个直接的值的直接返回去就行了
那么如果不是的话呢 那么它就要去找
它所有的儿子节点里面 从儿子结点的值里面找一
个最小值
作为这个极小结点的效能值的 这个是我们的定义
决定的
所以既然是要找最小 那么我们就用一个 定义一个
临时变量v
来存储这个最小值 那么这个v的初始化 用一个正
无穷来初始化
就是用一个很大值来初始化因为它要求最小值
同样的我们就去对于它的每一个儿子 都要比较 找
一遍
也就是说当前这个极小结点它的所有后续结点s
我们看一下这个s 这个节点的值和我们存储的这个
v值哪个更小
更小的话 放到这个v里面去
那么整个for循环结束之后呢
它这个v里面储存的就是所有的后续结点里面
值最小的那个值放到这里面 一个最小值放在这里
面
那么我们知道这个MIN结点的后续结点是MAX结点
所以要计算这个MIN结点的后续结点的值呢
要去调用MAX-VALUE来计算它的值
所以呢 这里面它递归的调用这个MAX-VALUE来
计算它的儿子结点的值
比较完了之后 这个for循环结束之后呢
这个v里面就储存了所有的MIN结点的后续结点里
面
具有一个最小值的后续结点的值返回去
作为这个MIN结点的效能值
那么这个就是这个极小极大决策算法的一个伪代
码
这个程序相当的简洁的 那么它理解起来也并不难
就是通过计算每个结点的效能值
也就是说一路往下走 走到这个终止状态的时候
得到这个终止状态的效能值 再一层一层返回去
得到调用这个算法的MAX结点的效能值
然后通过这个MAX的效能值呢 来选择一个
是哪一个动作得到的这个效能值
把这个动作返回去 让智能体去执行
那么这种算法其实是它的思想是什么
它的思想就是把对手MIN也想象成是一个不会犯错
误的对手
也就是说呢 如果我做A1这种行动
那么我的对手呢 是会做A11这种行动
还是会做A12这种行动还是会做A13这种行动呢
那么对手MIN它是不会犯错误的
它一定会选择使得你效能函数值最小的这个动作
来执行的
也就是说这个效能函数值越小对MIN越好的
所以MIN它一定会选择A11来执行
也就是说如果你执行 你选择A1的话 它就会选择
A11
也就是说意味着你只能得3分 你一定只能得3分
那么一样的道理如果你选择A2的话
那么MIN在这种情况下 它做这个动作A21
MAX你只能得两分 它做这个动作MAX得四分
它做这个动作MAX得6分
那么MIN结点它肯定希望MAX结点得分越少越好
所以它一定选择A21来执行
所以呢 就会使得你只能得两分
使得你这个执行A2的话只能得两分
那么同样的道理这个也是一样的
如果你选择A3进行执行动作的话
MIN的话 它选择A31你会得14分 选择A32你会得5
分
选择A33你会得两分 那么它一定会选择A33来执
行
使得你只能得两分
所以呢我们这个算法 他将对手假设成不会犯错误
的
也就是说对手也是一个在做最优决策的对手
在这种情况下它做出的决策
所以它就选择A1进行执行 因为A1会使它得到可能
的最高分3分
所以这种极小极大的决策算法在对手不会犯错误
的情况下 它能够得到一个最优的决策
也就是说它做出的这个决策不会比其他决策差的
但是如果对手不是一个完美对手
对手会犯错误的话 可能我们的算法呢就不是一个
最优的算法
就是它可能做出的决策会比其他方法更差 得到的
分更少
这个就是极小极大决策算法它的思想
就是在对手不犯错误的情况下
他选择能够得分最高的行动执行
那么来看一下这个极小极大算法的四大属性 也就
是说它的性质
首先看一下它有没有完备性
也就是说在有解的情况下它能不能找到解
那么只要搜索树是有限的 也就是说这个游戏是在
有限的步骤内能够完成的
并且这个分支数也是有限的
这种情况下 那么你一定能计算出这个结点的效能
值来
一定能够找到一个能够使得它得到这个效能值的
动作来执行的
也就是说能够计算出来的这些值
那么最优性的话怎么能够保证呢
我们刚才讲了我们的极小极大算法呢
它是把对手假想成是一个不会犯错误的对手
也就是说对手也是在做最优决策
这种情况下我搜索出的策略是最优的
它能够得到一个最大的效能值 所以它是最优的
那么对于时间复杂度来讲呢
那么我们最坏的情况下就是
整个的这个搜索树都要搜索一遍才能计算出来这
个值
所以呢它是 时间复杂度呢就是b的m次方
这个m就是我们这个搜索树的最深的层
这个b就是分支数
那么空间复杂度的话 我们采用的就是深度优先搜
索
也就是说我们在计算这个结点的效能值的时候呢
它是从最底层 也就是说要从一条路径下面的最底
层开始慢慢的回溯回去的
算出这个结点的值 所以它的空间复杂度呢是b乘以
m和我们的深度优先搜索是一样的
因为它在计算这个搜索的时候 在计算这个结点的
值的时候
采用的是这个深度优先的搜索
他是从最顶层要往前搜索一条路
往前搜索到这个终止状态的时候再返回去
返回去算出每一个结点的值来的
-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卡尔曼滤波器
-结课测试
