大家好
欢迎回来
我们这一段还继续基于决策树和搜索的智能系统
我们在介绍完博弈树之后
我们来看看在博弈树上
我们要怎么做
才能够最终赢得博弈的胜利
其实这就是一个对于局面以及局面所采取的动作
如何进行判断
使得自己更加的有利
这个依据就是第一是当前的局面是什么样的
然后接下来我就走哪一步棋
对于我来讲最为有利
比如说左边他在两个叉两个圈的情况下
我这个叉应该下在什么地方
他是不是下在右上角比较合适
还是下在其他的地方
那么右边这也一样
一个叉在中央
一个圈在顶上
那么接下来这个叉应该怎么下
它才能够是最有利的
所以这个是一个选择的过程
我们在人工智能当中就提出一个所谓的
叫做估值函数
那么这里头就出现了一个数学概念
叫做函数
但也不必特别的着急
因为函数这个概念其实简单来讲
就是我对于一个局面来说
给它打多少分
一个局面打一个分
不同的局面有可能会有不同的分数
也有可能会有相同的分数
总之估值函数就是对每一个局面给出一个估值
也就是打了一个分
当然我们最终其实要追求的就是终局
在下棋下完了以后
到的终局是一个分数最高的
但是这个分是对于一方而言
比如说对于叉而言有一个估值函数
那么我就希望通过从最开始的一个局面
一直到最后采取一系列的动作
它有一系列的局面的变化
最终应该变化到
对于我来说分数最高的终局
那么这样我就赢了
对不对
所以这是一个估值函数
当然对于其他的棋类来说
这个估值其实还有更加复杂的一些因素
比如说在象棋当中
无论是中国象棋和国际象棋
它的这个子是有分类的
不像我们的井字棋
或者在围棋当中
一方只有一种棋子
比如说井字棋里面我叉都是叉圈都是圈
它没有分成红色绿色或者其他的什么的叉
但是在象棋当中
我们知道他的棋子是有分类的
比如像兵士相马炮车后是吧
那么中国象棋和国际象棋其实有相似的地方
也有不同的地方
但是总之每一种棋子它有自己扮演的角色
因为这个象棋它其实都是对于人类社会当中
一个阶层结构的一个模拟
所以它有各自有自己的能力的范围
我们知道在国际象棋当中
比如说后它就是最厉害的
它的走法的规则以及它能够所攻击到的范围都是非常的大
所以在这种就有所谓的叫做静态的子力以及数量的一个分配
虽然子力很强
比如说后的子力非常的强
但是它只有一个
这个兵它虽然子力非常的弱
但是它的数量很多
这是一个评估表
另外复杂的棋里边还有棋盘的特征
所谓的棋盘特征就是棋盘上的不同的位置
在下棋的不同的阶段
不同的时间阶段里头
实际上这个位置的它的价值是不一样的
再比如说我们这个表就展示了中国象棋
中国象棋它有活动的范围
有包括中央的部分
有边线的部分
有角落的部分
那么这些棋子它们的价值体现是什么样子的
还有子力在开局阶段
在中局阶段和残局阶段
它的子力也有所不同
比如说炮在开局阶段
它的价值可能是五
那么到了残局阶段的时候
如果剩下一个炮
它的子力价值就会增加
因为它的作用就会更加的显露出来
那么而这些子力的判断以及数量
还有棋盘的特征
这些实际上都是人们在设计棋类游戏的时候
设计规则的时候
有一些会设计规则的时候就已经定好了
有一些是在我们在长期的玩的过程当中
发展的过程当中
人们逐渐的发现了这个规律
总之或者是人制定的或者人的经验的反映
当然如果是像围棋这样
那么跟象棋情况其实是大不相同的
首先围棋的棋盘特别的大
其次围棋它只有一种棋子
所以很难通过的棋子的子力
因为都是一样的棋子
也很难通过数量以及棋盘的特征
因为它棋盘本身边除了中间除了角之外
其实没有什么特别
很明显的特征
因为它的数量整个棋盘很大了
那么而且在不同的局势下
你同一个子其实下在哪儿
他的价值是变化非常的大
有的时候你下的是一步废棋
有的时候关键的一个部位
你下去的话可能能够决定整个局势的输赢
所以对于围棋的估值函数来说
它是特别的复杂的
我们还是回过头来看井字棋
我们其实可以给井字棋做一个估值函数
我们考虑的整个的过程可以这么想
既然井字棋的最终的输赢是以
连成横竖或者斜的这种直线的话
那么我们估值就冲着什么估值
就是冲着它有可能完成横竖斜
这样的数量就可能性
如果可能性越大
那么它的估值就越高
当然这当中还得减去对方的可能性
所以它估值最高
就是对方无路无路可走
我们己方还有很多的可能
这才是最高
其实也符合零和游戏的特征
我们估值函数最具体的就是我们叉这一方
当然估值函数是双方是不一样的
我这一方比如说叉它还存在着可能性的
行列和斜的线数
它有几种可能构成横的竖的和斜的
有几种可能减去对方的可能
那么这就是局势的估值
我们再来看两个例子
就是左边这个我们可以看到这是有两个叉和一个圈
那么它们都在最上方
我们来看这个玩家叉
它的可能性有多少
玩家叉在将来的过程当中有可能连成直线的
就是两条下面空着的横线
然后还有它占据了这个角
有两条斜线
然后还有占据角的两条竖线
所以2+2+2它一共有6
它有六种线数
那么对方有几种这个圈
我们看这个圈
它占据了上行的中间
所以它除了两个空的横线可以占据
然后再加上竖线中央的这根竖线
所以它有三种可能
所以整个的局面对于玩家叉来讲
它的估值就是6减去对方的3就等于3
这是一个3的估值
那么右边这个例子
右边这个例子我们也同样是两个叉和一个圈
但是这个叉由右上角移到了中央
这个对于叉这一方来讲
它其实还是一样的
他有两个横线
两个竖线和两条斜线
所以它还是6
但是对方这个圈就少的多了
它只有最右边的竖线和最底下的横有可能
因为中央这个竖线被堵住了
斜线也被堵上了
所以它只有右边的控制的竖线和最底下的控制的横线
只有这两种可能
所以右边这个棋盘
它对于玩家叉的估值就是6-2等于4
我们可以看到很显然估值就变高了
那么变高就意味着我们在采取动作的时候
尽量就要如果有两个可以选择的话
我们就尽量要采取一个动作
能够到右边估值更高的局面上来
所以整个就是我们的选择的策略
我们如果根据估值函数进行选择最优策略的话
当我们从第一个这个局面就是一个叉一个圈
现在叉要下下一步的时候
我应该是下在右上角还是下在中央
我们刚才通过这个估值函数
我们可以看到
如果下在右上角的话
那么它这个局面的估值是3
如果下在中央这个局面估值是4
所以我们就倾向于选择最佳的行动
就是下在中央
使得下一个状态它的估值能够最大
人工智能下棋的基本的原理就是这样
我们首先建立一棵博弈树
博弈树有局面
有行动
然后衍生出更多的局面
再有对方的行动
再衍生出更多的局面
然后第二阶段就是对于每个局面有一个估值
函数来进行评估
给它进行打分
那么打分的情况下
第三步就选择策略
策略就是让每一步都能够最后得到终局的时候
局面的估值打分是最高的
所以基本上就是人工智能下这种完全信息的零和博弈的棋
他的整个的基本原理
当然我们这个也可以进行进一步的改进
第一个可以进行多步的搜索这种策略
什么是多步
我们刚才说到的下一步能够估值最高
其实它实际上是一种贪心算法
对吧
那么我就只顾到下一步眼前最高
当然我们也知道
你眼前的最高
也并不意味着最后你就能够一定能赢
有一些时候贪心策略是可以奏效的
但是你只要稍微复杂一些的这种博弈的游戏
他就不是这样的
你可能先要眼前收益的不会那么的多
但是最后能够导致你赢
所以这样就要进一步的提高搜索的深度
也就是说我要往前看
要看更多步
比如说我从刚才我们井字棋当中的一步扩展到
假设对方还会下什么
这是第二步
在对方的下这些的情况下
我还要再选什么
这三部你往前看的越多
你胜算的把握应该就会越大
当然如果多到最后你能够一直计算到终局
你选择的策略一直到终局
你能够导致你最后终局的打分是最高的
能够保证你赢的话
当然就没有问题了
但是通常来说
我们可以看到博弈树它的可能性
节点可能的局面的增长可以说是爆炸性的
通常来说
计算机的性能
它的硬件的性能很可能达不到那么多
所以我们只能退而求其次说往前看多少步
但是尽量多步当然你也不能说太多步了
然后如果太多步可能就会出现什么样的状况
人类棋手下了一步之后
他可能要等上一个小时
等你搜上一百步
然后才能够下下一步
这个是当然不可接受的
所以只能够是一个折中
一个是往前看的步数有一个限制
第二个策略可以说在不变深度的情况下
我可以在横向的去剪枝去配合
有一些明显不合理的步数下法
我们就可以不用去考虑它
而去追求深度更加的深
那么这个剪枝也能够提高效率
这就好像我们在冬天的时候为了
一棵树不会横向的长得特别的宽
我们在冬天的时候都会把树的树枝给它剪掉
那么这个树将来会就会长得又高又直
深度就会比较好
这个其实也是模拟自然的一种策略
当然如果还有再进一步的改进
这就是完全不一样了
第一是改进估值函数本身
你如果有一个特别好的估值函数
那么你可能胜算就会特别大
就会有更小的树的数量
以及你可以在同等的搜索的算力的情况下
你们能够搜索的更深
或者说剪枝你能够剪得更多
这就是在于估值函数自己的评估
但是估值函数的设计特别的复杂
如果是由人来设计的话
一般就要借助于棋类大师他的经验
或者说你去穷尽古今中外所有的高级的棋手他所下的棋谱
在这一步下一步它大概会怎么下
然后大家归纳出来的经验
你就下在边上
中间还是角哪个会好的话
那么对于这个局面的估值会有一个很复杂的
一个方式来进行评估
那么随着估值函数构件的越来越完善
那么人工智能就会越来越聪明
但是我们知道这个是由人所赋予这个算法赋予它智能的
当然我们也可以通过不同的棋类来添加不同的估值的规则
这些规则包括一些启发制的规则
有一些棋谱
有一些下棋的口诀
都可以把它变成搜索当中的一个辅助的一部分
当然最后最终的解决方案可能还是现在目前
基于仿生算法
基于神经网络
这些方法不是由人去告诉人工智能你应该怎么下
而是让人工智能自己从庞大的下棋的数量的
实践过程当中
自己去总结出来自己去学的策略
而我们知道这样的一个策略
它很有可能跟人类千百年来积累起来的经验很有可能不一样
我们在后边在介绍到AlphaGO的时候
还会给大家详细的介绍这一点