hi
大家好
欢迎回来
我们这一节再继续基于决策树和搜索的人工智能系统
那么我们前面已经介绍了一些基本的方法
而且这些方法也都很有效地应用在这些完全信息的零和博弈
也就是各种的这种棋类上面了
那么最终的发展
它是一个什么样的途径
我们今天就从国际象棋聊到围棋
看看在这种完全信息的零和博弈的游戏当中
基于决策树和搜索的这种人工智能它到底能够走多远
那么首先对于国际象棋而言
我们知道在打败了国际象棋世界冠军卡斯帕罗夫的算法
就是深蓝的算法
那么深蓝的算法可以说它已经达到了基于决策树和基于搜索的人工智能算法的一个顶峰
它综合了minimax以及AlphaBeta剪枝
那么在残局的阶段
它增加了搜索的深度
也就是它通过提高算力来增加往前搜索的深度
那么在开局阶段
因为开局的时候棋盘上基本上没有什么棋子
那么可能性相当的大
整个决策树非常的庞大
在这种情况下
如果你需要在有限的时间内能够得到一个很好的或者说比较好的解的话
那么就需要用到启发式的算法
所以在深蓝的算法当中
他在开局阶段利用了大量的人类对局的这种开局库
它从很多的大师的各种各样的开局当中去进行
选择去进行匹配和选择
那么在这种启发式的算法的帮助下
深蓝最终打败了国际象棋的世界冠军卡斯帕罗夫
那么从深蓝开始
人工智能也被人们重新的关注起来
那么我们知道这种完全信息的零和博弈的这种棋类当中
顶峰就是围棋
那么如果我们也同样把基于决策树和搜索的方法应用在围棋的人工智能上会怎么样
人们早就做了这种尝试
用AlphaBeta剪枝的方法
minimax这种决策树的方法用在围棋上
那么有一个叫GNU Go这么一个人工智能程序
它可以达到业余5到10级左右的这样的一个水平
那么在整个围棋人工智能的一个排行榜上
GNU Go他利用了AlphaBeta剪枝的这种算法
它的棋力往往被当作一个基准的分数来判断
那么经过各种各样的改良
各种各样的改进的这种基于决策树和搜索的
其他人工智能算法
一般都会比GNU Go来的更高一些
那么如果还要再继续进展
怎么办
因为AlphaBeta剪枝已经是确定算法
再加上启发这算法的这种情况下
你如果还不能够得到一个好结果的话
那么人们最终转去求助于统计学上的这种方法
统计学上方法有一种就称之为蒙特卡洛方法
它主要是通过随机采样的计算来得到一个近似的结果
它是一种比较通用性的一个计算方法
也就是说一种方法能够解决很多的问题
比如说像动画当中显示的这样
我们如果要求一个图形的面积
一个不规则图形的面积
当然我们知道如果是一个规则图形
如果是一个圆或者一个椭圆
或者说一个矩形
甚至一个直线的多边形
我们都可以有数学公式
直接计算出图形的面积
当如果这个图形是一个不规则的情况下
你怎么去计算它的面积
那么随机采样的方法就给了我们一个启发
那么它基本的方法是这样的
在一个正方形一个范围里头
然后里头有一个随机图形
那么这个随机图形是一个1/4圆
是一个红色的图形
那么我们在矩形上
正方形为已知已知面积
他面积等于1
那么上面的落上很大量的随机点
那么我们就通过判断这个随机点是落在图形内部
还是落在图形的外部
来看它们落在内部和总的点数的比例
就能够得到图形的面积和外面正方形面积之比
当然我们知道如果说你这个随机的点足够的多
足够的随机
那么越这个点越随机
这个点的数量越多的话
那么这个面积它就会越精确
当然这个图形动画其实通过求1/4圆的面积
实际上用这种方法在很多的例子算法例子当中
被用来求π的近似值
我们发现如果你落得这个点越多
对于求出来π的近似值就越精确
那么所以我们就在这个启发式算法
在AlphaBeta剪枝的算法的基础上
我们就有了一个更大的一个扩展的空间
也就是用随机采样
用统计的方法来近似于碰运气
当然所谓的碰运气也并不是完全的靠运气
而是通过大量的计算
慢慢的逼近一个最优的一个决策
那么具体怎么去做
我们来看看蒙特卡洛树的搜索的方法
那么它简称叫MCTS
那么它是一种在决策空间当中随机的采样
并且根据结果来构建原来特别大的决策树当中的一小部分
来寻找一个最优决策的一种方法
那么在这个方法当中
对于决策树的构建
它有一整套的流程
有选择扩张模拟然后反馈
那么这样就可以在决策树原本最原始
的就是它的特别庞大的情况下
我们可以用相对比较小的代价要注意
这个是相对比较小
你要考虑到决策树本身就相当的庞大
所谓的相对比较小
那么实际上你为了得到一个比较好的结果
你其实也需要做大量的计算
但是大量的计算对于我们整个的决策树而言
相比还是很小的
但是只要统计的采样它具有代表性
那么实际上我们可以用较小的代价能够得到
一个最优策略的一个近似结果
那么蒙特卡洛树搜索他的方法分为四个阶段
首先头两个阶段是选择和扩张
那么这是一个树的一个选择扩张的策略
那么它主要也是从这个根局面开始来进行随机的选择
并且随机的创建新的叶结点
就是头两个阶段
然后随机之后它再从一个非终止的一个状态
这还没有终止
这个状态的随机选择
然后不断的用随机的策略
不断的进行游戏
得到一个最终的一个价值评估
比如最终是赢了
好
那就说明说明了这个节点它有一个采样获得了胜利
那么当然这个随机它不仅仅是做一次
他可能会做很多次
比如说做一千次
那么一千次里头它可能随机一千次
当然相比起整个的可能的决策树而言
这一千次实在是太小
但是我们具有代表性的一千次
它的可能有比如说有800次都获得了胜利
那好
这个胜率就是80
然后再通过反向的传播就是一个反馈
把80的策略就一直反馈到这个根节点
这个指示我们在选择策略的时候
应该更加的偏向于他
这就是整个蒙特卡洛树搜索的一个基本的方法
那么我们来看一个例子
就是一个选择扩张模拟和最终反向传播反馈的一个过程
那么这是一个演示这是白棋下的
这里头统计出来的胜率是21盘赢了11盘
当然下一层就是黑棋的黑棋的胜率
对吧
那么接下来还是白棋的胜利
最终是黑棋胜
那么在整个的扩张的选择扩张的过程当中
它有一个随机的途径
然后到了最终一个最下层的节点
但是最下层节点还远没有到终结的状态
所以为最下层的节点进行一次扩张
这是一个白棋的状态
白棋状态这还没有进行
最终的到终局
所以他没有一个评估
那么所以我们还可以再继续
那么继续的情况下
在多次进行了一次的模拟
进行一次模拟从0局0胜率一直到最下面
做了一次之后
我们发现这一盘他输了
就是0/1
输了以后再把这个结果由决策树进行传播上去
传播最终传播到根节点
我们可以看到这个根节点里头
他的盘数采样数增加了1 就是22局
但是这个胜率还是只赢了11局
这个就是整个蒙特卡洛树搜索的一个例子
那么对于蒙特卡洛树搜索这个算法用在围棋当中
它取得了什么样的一个成就呢
那么在2006年叫做Mu Go这么一个程序
他是第一个使用蒙特卡洛树搜索的一个围棋程序
最终他取得的成绩是在9×9的棋盘
我们知道围棋的正式的棋盘是要比这个大得多
它在9×9的棋盘上首次击败了职业选手
那么接下来的在经过漫长的时间的发展
最终有一个叫做DeepZenGo
这个是在AlphaGo我们知道
AlphaGo是最终击败了人类的围棋的顶尖高手
是在AlphaGo之前一个最强的一个围棋人工智能程序
那么对于DeepZenGo来说
它可以达到跟职业棋手差距3到4子
这样的一个水平
这是在基于搜索
基于决策树搜索再加上蒙特卡洛树搜索的算法之后
人工智能围棋程序获得了最高的水平了
当然我们最终击败人类围棋顶尖高手是AlphaGo
AlphaGo人工智能算法它实际上也
是基于蒙特卡洛树搜索的算法的基础上
通过神经网络的方法来进行训练
得到了更好的树的选择扩张的策略以及更好的估值函数
那么最终的AlphaGo在数据和算力的两个资源的加持之下
最终战胜了人类的围棋的顶尖的冠军
那么最终的结果比较
棋力的比较大概是这样的
如果以GNU Go作为基准
他的棋力比如说是1800的话
那么DeepZenGo到了4200的水平
然后这里头四位是人类棋手
顶尖棋手最高的
那么还是由AlphaGo和AlphaGo Zero
那么到了AlphaGo Zero
40个block版本
它最终达到了一个最高的顶峰的这么一个水平
所以我们说在人工智能程序当中
实际上它并不是突然达到的一个高度
而是经过人类的各种算法的研究
一步一步的积累的这么一个结果
那么其中对在局基于决策树和搜索的这种
人工智能算法是一个非常一个很好的一个坚实的基础
在比如说在minimax和在AlphaBeta剪枝的基础上
再结合启发式的算法
再结合基于随机和统计的方法
蒙特卡洛树搜索这些方法
逐渐地使得基于决策树和搜索的人工智能系统
一步步的登上了一个智能的一个新的高峰