当前课程知识点：人工智能 > 第五章 对抗搜索 > 5.4 不完美的实时决策 > Video
那么我们知道虽然α-β剪枝能够提高这个效率
能将搜索的这个时间复杂度的指数减半
但是呢实际的博弈游戏当中每一位棋手它的时间
是有限的
那么假设每个棋手有一百秒的时间
那么假设智能体它的计算机计算能力呢
它每一秒钟呢可以拓展十的四次方个结点
也就是说可以搜索十的四次方个结点
那么一百秒时间里面 它最多只能拓展十的六次方
个结点
也就是说只能计算十的六次方个结点
那么这个对于一个普通的游戏来讲这个能力不够
的
也就是说不可能搜索到 即使用这个α-β剪枝算法
也不可能往前搜索到终止状态
也就是说它没有办法在这个100秒时间内
在有限的计算能力情况下
搜索到 往前推理到终止状态
从而计算出一个分值出来告诉它应该怎么样下棋
做不到 那么做不到的话 那么我们就要做一些不完
美的实时决策 也就是说不要追求完美
那么怎么样做呢 我们有两种方法
也就是说我们在两个方面进行改进
第一个就是对这个深度进行限制
也就是说不让它搜索到终止状态
也就是说也搜索不到终止状态
所以呢就给它一个深度限制
然后规定它往前看到第几层就一定要返回来
那么竟然有一个深度限制 不能搜索到终止状态
那么我们的这个简单的效能函数就没有用
那么我们就需要对这种非终止状态进行一个打分
那么这个打分呢就需要程序员来定义这个评估函
数
所以呢需要定义评估函数
那么利用这两种技术来实现这种不完美的实时决
策
从而使得这个博弈游戏呢有可能进行
所以我们来看到这个改进了的计算极小极大值的
一个方法
也就是说我们把它命名为启发式的极小极大值方
法
那么看到这个公式
也就是说因为我们定义了一个启发式的评估函数
来评估这个非终止状态的这个好坏
它的这个值 所以我们给它一个名字H-Minimax
然后呢它有两个参数 一个就是当前状态s
另外一个就是这个状态结点它所在的这个深度d
所以我们来看到 首先我们看一下这个当前状态结
点呢
它的这个深度是不是到达了深度限制
也就是说如果到达了呢 直接使用我们的启发式评
估函数对这个s进行评估
产生一个分值返回去作为这个结点的分值
如果不是 也就是说没有到达这个深度限制
并且这个结点为max结点 那么就跟前面一样的
我们就去计算它的所有儿子
这个儿子怎么产生的呢 就是当前状态执行某个动
作
这个动作当然是当前状态合法的动作 允许的动作
产生儿子
所有的儿子结点里面它的分值取一个最大值
这个是max最大值
那么它的儿子 计算它的儿子 它的这个Minimax值
的话
那么它的儿子的深度是比我当前这个深度要多一
层的
所以这个深度要进行改变d+1 第二个参数
也就是说这个是产生儿子 所以是儿子状态
这个是儿子状态的深度
然后呢当这个当前状态又没到达深度限制
并且它是一个min结点的时候 那么同样的道理
它是去求它所有儿子结点分值里面的最小值作为
它的值
那么它的儿子结点是怎么产生的呢
就是当前状态通过执行合法的动作产生一个儿子
状态
这个是儿子状态 所以第一个参数
然后第二个参数呢就是儿子状态的 儿子状态结点
的深度
就是d+1 因为当前状态是d 儿子就是d+1
所以呢去所有的儿子状态分值里面求一个最小值
那么这个就是我们的min结点的启发式极小极大值
的求法
那么关键这里一个难点就是如何来定义这个评估
函数
也就是说这个评估函数定义的好与坏
那么直接影响到你这个博弈智能体的效果的
也就是说评估函数肯定要和最终的输赢 最终的这
个效能函数呢 要是一样的
也就是说评估函数值大的 对应的这个状态
也就是说它对于max来讲 它取胜的概率就应该越
大
那么我们一般的话 对于这个一般来说这个评估函
数我们都定义成一些特征的加权和
那么比如说国际象棋 那么它的这个就是一个特征
的加权和
那么这些特征怎么样定义的
也就是说这些特征到底表示什么
这些权值到底有多大
那肯定是领域里面的专家 就是专家知识决定的
比如说这个对于国际象棋来讲第一个特征我就可
以定义成
这个白皇后的数字减去这个黑皇后的数字
就是两方这个皇后个数相差越大
那么也就是说我这个max这一方皇后个数越多
比你多那么就意味着取胜的概率比较大
所以这是第一个特征
那么像第二个特征 第n个特征怎么定义的
都是游戏领域里面的一些先验知识告诉你的
那么这些权重一个可以通过这个先验知识
还有可以通过这个不断的实验
另外可以通过我们的机器学习来学习得到
所以一般评估函数的话就是用这个特征的加权和
来表示
来求出这个状态的好与坏
那么这个是 这个评估函数的定义
那么来看一下这种加了这个深度限制的这种博弈
搜索
它和我们前面讲过的α-β搜素算法或者说Minimax
搜索算法呢
他其实上不同点在于这个终止状态的判断这条语
句呢
就变成了是否达到深度限制的判断
也就是说我们前面是 如果这个状态是终止状态
那立马用那个效能函数值返回它的这个效能值
那么现在就变成判断这个状态是不是到达了深度
限制
那么到达了我就用这个 我们定义的这个启发式评
估函数去求出当前这个状态的分值返回去的
所以就这里改变了
然后结点的这个效能值是用这个我们的启发式评
估函数值来代替
所以这个是它不同的地方就在于这一条语句
你改一下就行了 关键是要定义好这个评估函数
那么我们来看到国际象棋
b呢我们一般认为它是等于35
这什么意思呢 也就是说国际象棋里面它的平均分
支数是35
也就是说每一次轮到你下的时候大概你有35种不
同的下法 不同的选择
这个就是这个35的意思
也就是说我们这个分支个数的意思
那么我们前面讲过了 也就是说每个棋手假设给你
100秒
那么假设这个max在一秒里面可以运算十的四次方
个结点
所以100秒的时间它只能运算十的六次方个结点
那么十的六次方个结点 相当于它可以往前推到多
少层呢
我们国际象棋的b呢平均是35
那就是35的m次方等于10的六次方
我们就推出来这个m最多等于4
也就是说意味着你最多可以往前推到第四层你就
要返回来了 你就没有时间了
而你往前推到第四层就用启发式函数值返回来的
话
那么这个水平 这个国际象棋手的水平就相当于我
们的一个新手
就下的很差的
那么如果你能够提高你的效率 比如说我采用α-β剪
枝
使得这个层次可以翻倍可以往前看到第八层
那么你往前看到 往前推理到第八层
那么你就相当于一个国际象棋高手了
那么对于深蓝来讲 它是一个国际象棋打败了国际
象棋大师的
那么它可以往前推到第十二层
所以这个就是这个深度限制搜索
那么它使得这个博弈游戏呢可以实际的进行
尽管它实现的是不完美的决策 也就是说不是推到
了最终止层
但是它还一样的可以达到很高的水平
那么这个是深度限制搜索
那么我们来看一下这个博弈程序发展的现状
那么对于这个我们举了三个例子 像跳棋 国际象棋
围棋 按时间顺序来的
那么跳棋呢 在94年的时候就打败了人类冠军
所以这个人是比不上这个跳棋的 跳棋是我们的人
工智能下的最好
那么国际象棋的话呢是深蓝在97年就打败了这个
人类冠军的
那么围棋的话认为是 早些年都认为是不可能打败
人类的
因为围棋它的这个b这个分支数呢特别大
然后呢它又很复杂
所以呢在早些年都认为它不可能打败人类
那么在16年的时候呢这个AlphaGo呢
它以3612分超越3608分的柯杰成为新的世界第一
也就是说2016年的时候AlphaGo成功的打败了人
类冠军
也就是说它利用更先进的机器学习技术
利用最新的计算能力 计算资源
成功的实现了这个 打败人类世界冠军的这个目标
这个是这个博弈程序发展的现状
所以现在博弈人工智能发展的还是很快的
最后我们来看一下这一章的结论
也就是说博弈游戏呢 因为它很容易形式化
为什么呢 因为博弈游戏相对来说 相对其他的什么
体育游戏啊简单的多
也就是说它的游戏规则呢非常的确定
也就是说每一次的动作的结果它是非常的确定的
很容易形式化
也就是说它的状态也很容易描述 就是棋盘状态
然后呢这个输赢也很容易判断
所以呢它是比较容易形式化的
所以很容易形式化的话 就很容易由我们的计算机
来求解
这个问题形式化了之后呢 就很容易用搜索算法来
求解
所以呢使得这个博弈成为人工智能研究者非常感
兴趣的这个研究领域 一直以来都是非常感兴趣的
并且再说它取得了很多的突破
所以呢它也为人工智能的传播呢起了重大的贡献
也就是说引起了人们的兴趣
就像AlphaGo就掀起了人工智能热一样
那么这个是博弈游戏
那么我们在讲到博弈的时候我们讲到了极小极大
值算法
以及后面讲到的这个α-β剪枝算法
那么α-β剪枝算法的话可以计算出和极小极大值一
样的结果
也就是说它不会影响最终的结果
尽管它只搜索了部分的博弈树
那么尽管这个α-β算法能够使得这个搜索的层次加
深一倍
但是呢由于这个博弈时间的限制 我们还是需要这
个截断搜索
也就是应用这个启发式的评估函数来估计这个非
终止状态的这个效能值
那么这个是这一章的主要内容
-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卡尔曼滤波器
-结课测试
