当前课程知识点：人工智能 > 第五章 对抗搜索 > 5.1博弈及极小极大值概念 > Video
这一章讨论竞争环境当中的搜索问题
所谓的竞争环境呢 就是存在多个智能体
并且这个智能体它们之间是一种竞争关系
也就是它们的目标是有冲突的
那么在这种环境当中智能体需要考虑对手的每一
个响应
从而找出自己的行动方案
那么这种对抗搜索问题也称为博弈搜索问题
而前面讲到的搜索问题它所处的环境当中只有一
个智能体
是不需要考虑其他智能体的
而博弈搜索问题呢 它要针对对手的每一种可能的
反应呢
做出一种响应 搜索出一种策略
那么我们人工智能当中的博弈通常是指的是
确定的 完全可观察的环境中两个智能体轮流行动
的零和游戏
也就是说博弈游戏指的是下棋 类似于下棋的这种
游戏
也就是说这种游戏规则非常确定
并且它每做一个动作所产生的状态结果是确定的
而每一位棋手它都能够完全观察到棋盘状态
也就是说环境是完全可观察的
并且呢这个环境当中只有两个智能体
这两个智能体必须轮流下棋 必须轮流行动
最终这个棋呢 这个游戏呢 有输赢
也就是说这个是一个零和游戏
那么针对这种博弈游戏我们应该如何来搜索出一
个最优决策
我们首先看到这里有一个井字游戏的博弈搜索树
那么这个井字游戏的博弈搜索树
它的这个状态描述呢 用的就是棋盘状态
所以状态描述相对简单
那么初始状态的话就是棋盘上面没有任何的棋子
然后接下来就是我们的一个棋手
也就是说调用这个算法的棋手 我们把它取名叫
MAX
这个棋手 智能体 它下棋
那么它下的棋用这个X来表示
那么它在下第一个棋的时候它可以在这九个格子
上面的任意一个格子摆放
所以呢对于初始状态呢 它有九个后续状态
那么在这个MAX这个智能体下完这一步棋之后呢
我们的MIN 它的对手我们取名叫MIN
对手MIN就要下棋 轮到它来下棋
因为是两个智能体轮流下棋 轮流行动
那么它下的棋我们用小圆圈来表示
那么它对于MAX产生的每一种可能结点 这九个后
续状态
它都可以在剩下的八个格子里面摆放它的棋子
所以呢对这个MIN结点它可以产生八个后续结点
对于每一个MIN结点 这一层的每一个MIN结点
那么它摆放完它的棋子之后 又轮到我们的MAX智
能体
来摆放它的棋子 来下它的棋
那么它也可以在剩下的七个格子里摆放它的棋
所以呢对于这一层的MAX结点它的后续状态有七
个
也就是说它的分支数是七
那么它下完之后呢 又轮到我们的MIN来下
那么MIN可以在接下来的六个格子里面摆放它的棋
子
那么不断的这样轮流交替下去 直到到达终止状态
那么终止状态呢 是一种什么样的状态呢 对于博弈
游戏来讲
就是能分的出胜负的状态
或者是所有的棋盘格子上都摆满了棋子
任何一个棋手都没有办法再下棋了
那么这样子的状态就叫做终止状态
那么像这里一样 这就是一个终止状态
这个终止状态是我们的MIN结点 我们的MIN智能体
赢了
也就是说它摆放的棋子在同一列所以它赢了
那么这个状态是棋盘上摆满了棋子没有办法再进
行下去了
那么又分不出胜负 这是一个平局的终止状态
那么这个这个状态呢 是我们的MAX
它摆放的的棋子在同一条线上 同一个对角线上
所以是我们的MAX赢了
那么我们定义了一个效能函数
这个效能函数呢就是用来评估这个终止状态 给终
止状态打分的
哪么这个效能函数呢是针对调用这个搜索函数的
MAX智能体来定义的
所以这个效能值呢 大的时候意味着我们MAX赢了
小的时候意味着我们MAX输了
也就是说效能函数值越大MAX越有利
效能函数值越小MAX越不利
而它的对手MIN希望这个效能函数值越小越好
所以这个效能函数是针对MAX来定义的
那么有这种形式化之后呢 我们就把这个调用这个
搜索算法的智能体命名为MAX
也就是说它希望这个效能函数值越大越好
而它的对手命名为MIN它希望这个效能函数值越小
越好
那么这个就是我们的博弈搜索算法它的一个形式
化的一个例子
那么我们在博弈游戏中如何搜索到最佳行动方案
也就是说如何做出决策呢
我们有一种极小极大值算法 它的思想就是
选择具有最高极小极大值的动作来执行
也就是说呢我们的MAX智能体要做下棋的选择的
时候
要做动作选择的时候
它去调用这个搜索算法 去求出我做A这个动作的
时候我得到一个什么样的极小极大值
做A2这个动作的时候得到一个什么样的极小极大
值
做A3这个动作我得到一个什么样的极小极大值
那么我就选择一个能够使我具有最高极小极大值
的动作来执行
像这里假设它选择A1的时候它会得到三分
选择A2的时候会得到两分 选择A3的时候会得到两
分
那么当然它就会选择A1来执行 所以它就返回去
告诉智能体采用A1这个动作来玩这个游戏
这个就是我们的极小极大优化决策算法的思想
那么这个极小极大值是怎么算出来的呢
它是怎么定义的呢 我们来看一下
这个极小极大值呢它也是针对我们的MAX结点来
定义的
也就是MAX希望这个极小极大值越大越好
那么这个极小极大值的定义是这样一个定义
就是说某一个结点S它的这个极小极大值
等于什么呢 当这个结点对应的状态是一个终止状
态的时候
那么这个极小极大值就等于它的效能函数值
也就是说我们在问题的形式化的时候就定义了一
个效能函数值
那么这个效能函数可以给任何一个终止状态 打出
一个分数来的
那么如果当这个结点对应的状态是一个终止状态
的时候
就直接返回它这个效能函数值作为它的极小极大
值
那么如果这个状态不是终止状态
那么当这个结点是一个MAX结点的时候 它的值是
多少呢
它的值是从它的儿子结点里面找一个最大值作为
它的值
那么它的儿子结点是怎么产生的呢
就是MAX结点它能够执行什么样的动作
这些游戏规则规定的
也就是说当前这个状态下能够执行的动作里面
执行这些动作产生的所有后续状态里面 后续结点
里面
这些后续结点的这个值里面 找一个最大值作为我
的值
这个就是当这个结点为这个MAX结点的时候这个
极小极大值如何计算
就是从它所有的后续结点里面找一个最大值返回
来
那么当这个结点为MIN结点的时候呢
因为MIN结点它是希望效能函数值越小越好
所以呢它就从它的后续结点里面找一个最小值返
回来作为MIN结点的值 极小极大值
那么同样的也是它的后续结点也是 怎么产生的呢
当前这个状态可以执行的动作 所有动作
每个动作产生一个后续结点
那么每一个后续结点有一个极小极大值的
从这个所有后续结点的值里面选一个最小值
作为我们这个MIN结点的极小极大值
这个就是极小极大值的一个定义
那么来看一下怎么样来计算每一个结点的极小极
大值
像这个例子 这个很简单的一个例子
这个游戏呢就是MAX走一步MIN走一步
就可以到达终止状态的一个简单的示例游戏
那么大家看到像这些结点都是终止状态的
可以根据定义的效能函数值直接给出它的极小极
大值
所以它就是3、12、8、2、4、6、14、5、2
那么这三个结点呢是中间结点 不是终止状态
那么就要看它是什么结点
那么这个节点呢是MIN结点所以我们看到MIN结点
我们一般表示成这个尖尖 三角形的这个尖朝下
MIN结点也就是说它取最小值
这个MIN结点呢它的这个值怎么算出来的呢
我们刚才讲了 它是去求这个儿子结点里面的最小
值作为它的值
所以呢它有三个儿子 这三个儿子的值我们都已经
算出来了
因为这三个儿子都是终止状态
所以已经算出来了3、12、8
所以它取它所有的儿子结点里面的最小值 所以它
就是3
那么这个结点也是一个MIN结点同样的它取它所有
的儿子结点的值里面的最小值
所以它等于2
那么这个节点也是它取 它是一个MIN结点
所以它取它所有儿子结点里面的最小值 它是2
所以这三个结点的极小极大值也算出来了
那么这个值这个结点它的值怎么算呢
这个结点它是一个MAX结点 这个MAX结点大家看
到它是用正的三角形来表示的
就是这个三角形的尖是朝上的
那么MAX结点呢它的极小极大值是取它所有儿子
结点值里面的最大值
那么第一个儿子3 第二个儿子2 第三个儿子2
所以它得到一个最大值3 所以3就是它的极小极大
值
那么为什么MAX结点它的值要取最大值呢
因为我们知道这个效能函数是针对MAX来定义的
他希望值越大越好 而MIN呢希望这个值越小越好
所以MAX它肯定会选择这个值越大的这个行动 进
行行动
而MIN呢希望这个效能函数值越小越好
所以他就会选择这个能产生最小的效能函数值的
这个行动执行
所以这个就是我们的极小极大值如何计算
那么我们的这个极小极大决策算法呢
它的思想就是选择一个能返回最大值的行动方案
进行执行
那么像这里一样我们的MAX它在执行A1的时候能
得3分 在执行A2的时候能得两分
执行A3的时候能得两分 它推出来的
它通过搜索算法计算出来的
所以呢它一定会返回这个A1这个动作告诉智能体
去执行
因为A1它能够得的分更多
因为我们这个分值是针对MAX来定义的
而调用这个算法的智能体就是我们的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卡尔曼滤波器
-结课测试
