今天,引人注目的人机大战终于以4:1的悬殊比分,宣告了AlphaGo赢得了比赛,看起来计算机相当的强大,就围棋这个领域来讲,已经完全战胜了人类,那么我们不禁要问,计算机战胜人类的原理是什么?他们真的具备跟人类匹敌的智商吗?
大概在10多年前,我曾经写过一个中国象棋的AI项目,当时并没有利用分布式计算(那时也不懂),只是一个单机程序,大概能有6-7步的预测能力,经过不客观测试,能战胜我能接触到的所有象棋爱好者。当时人机博弈理论的基础就是Alpha-Beta搜索:
Alpha-Beta搜索实际上是从最简单的BFS搜索和之后的A*搜索发展来的,BFS其实就是最简单的穷举,每层都把所有的可能列出来,最后给一个结论,而A*搜索在这个基础上,多了一个选择函数,即在每层遍历时,给一个优先级,优先从看起来局部最优的方向入手遍历,比如我们在地图上设计寻路的机器人,可以设定NPC周围所有8个节点方向上,最指向最终目的地的方向的节点是看起来最优的,然后从这个节点优先遍历。
Alpha-Beta搜索,实际也借鉴了A*的思想,即每次都从局部看起来最优的结果给出下一步的判断。首先,我来解释一下什么是局部最优:
因为以目前计算机(尤其指单机)的计算能力,是无法遍历棋盘所有可能的,以围棋为例,19*19的棋盘上,一共有361个点,也就是执黑先行者有361个选择,之后执白有360个选择,于是361*360*359....,这是一个比天文数字还大的数字,所以我们根本不可能通过计算得到全局最优。
判断棋局的优劣
那么,我们怎么评价某一种走法看起来最优呢?这就需要根据不同的棋,设定规则了,以中国象棋为例:
规则1,我们规定,自己一方所有子能走的区域越大则越优,说俗点,别把自己给“闷死”了,比如 马走到边上。于是给定一个棋盘,我们可以计算:
V1= 马可走的区域+车可走的区域+兵可走的区域+帅可走的区域+....
V越大,则越优秀
但是,下过象棋的人都会觉得,规则1也太简单了吧,完全没考虑到车和兵在棋盘上的重要度完全不一样,不能按照一个权值系数算,另外,规则1完全没考虑到对对手的威胁性,于是,我们进行改进:
V2=系数A * (系数1*马可走的区域+系数2*车可走的区域+系数3*兵可走的区域...) + 系数B * (自己的马有可能吃掉对方的子的重要度+自己的车有可能吃掉对方的子的重要度+自己的兵可以吃掉对方的子的重要度...)
大家能明显的看到,V2比V1合理多了,不仅仅考虑到了自己的字别被“闷死”,还考虑到了对对方的威胁,那么这个公式还能不能改进呢?还能!我们知道,对对方的威胁,对帅的威胁是最高的,对车的威胁完全高于对兵的威胁,说俗一点,就是能吃掉对方的帅,绝不吃掉对方的车,能吃掉对方的车,绝不吃掉对方的兵。
于是,这个公式就V3就更复杂了,系数也越来越多,这里我们得出一个结论:
我们一定一个得到一个公式,它较公平的判断一个棋局,对某一方的优劣是什么,且这个优劣还是可以量化的!当然,对于围棋而言,这个公式更麻烦一些。
但这里我们忽略了一个问题:即最终的公式有N多的系数,我们需要一种办法来确定最优的系数组合。
Alpha-Beta搜索
当双方博弈时,当下一步该自己走时,只需要遍历所有的下一步可能,然后选择一个棋局对自己最优的方案即可,这个非常简单,但是,这仅仅代表计算机有预测一步的能力,按照这个逻辑设计出来的程序可能连小孩都打不过,要想战胜人,需要有提前预判N步的能力。那么怎么预测两步呢?
我们可以遍历所有的下一步的下一步的可能,因为下一步的下一步是对手下,所以我们只需要从所有可能中选择让对手最难受的一种可能即可。于是,按照这个思路,我们就产生了两个约束条件:
A:对自己最有利
B:让对手最难受
如果我们在搜索过程中,不断的以这两个约束条件去进行搜索,这就是Alpha-Beta搜索。两个约束条件更符合博弈的本质,即对自己最有利且不断限制对方。Alpha-Beta算法本身也很简单,可自行Google。
看起来AI下棋的原理不难,但其实真正的奥秘就是如何减少搜索的计算量。
核心:减少计算量
从之前的描述,我们可以看出,计算机算的越快,赢的概率越大,那么怎么算的更快呢?更好的硬件+分布式并行是一种思路,当然从算法上能减少计算量则更好!减少计算量的办法至少有这么几种:
1,其实每步下棋时,没有必要棋盘上所有点都考虑,而是可以优先考虑某些点,比如离目前棋子比较近的点,这样就能减少相当一部分工作量。
2,录入相当多的棋谱,这样可以避免搜索一直到叶子节点,如果匹配到棋谱的话,可以从之前很多步就提前返回。
3,赋予计算机一种神奇的能力,让他能够有预感,预感到某一步可能“有戏”,这样把这一步放到Alpha-Beta搜索队列的前面,优先搜索,这样避免把计算资源浪费在其他“没戏”的下一步上。
而3,也是根据AlphaGo公开出的资料中,最高深的一点,即所谓的CNN,应用在蒙特卡罗搜索MCTS中,从而把有限的计算能力计算值得计算的子节点。这一点在围棋中尤为重要(更尤其在初盘中盘,因为末盘的搜索量会急剧减少),能做好这一点才是让围棋AI能够战胜人类高手的关键。
那么按照公开资料,AlphaGo是根据CNN卷积神经网络来训练AI的,输入就是19*19的棋盘信息,输出就是一个value,量化的代表对谁有利,通过输入成千上万的高手棋谱,经过反复的自学习,确定神经网络的参数,最终可以实现给定任何一个棋局,判断其是否对自己有利,这样就可以在每次Alpha-Beta搜索计算前,把待搜索的布局排序,优先搜索那些对自己有利的布局,从而大大缩小计算量。
神经元网络大多都依赖梯度下降,即误差反传BP,举个通俗的例子,一个盲人登山,要寻找山的最高点,他所能做的,就是不断的往前或者往后迈,不断收集前后两步的高度差值,如果高度差很大,就反馈给大脑加大步伐,如果高度差越来越小,就反馈给大脑减小步伐,最终直到前后两步的高度差一样了,也就找到最高点了(其实是局部最高点)。这个比较好理解,但是为什么卷积的神经网络适合围棋这个场景,这里面是数学理论的推导依据还是先有模型不断经验测试的结果,只能靠进一步研读Google的资料来寻找答案了。
机器战胜人类了吗?
从上面的浅显分析可以看出,即使AlphaGo将来可以战胜柯洁大棋渣,其整个运算过程其实跟围棋艺术本身没任何关系,包括是最神秘的那个CNN里面的层级、参数关系,也很难说明他们跟人类的思考模式有相似的关系。我总感觉,这种AI只不过是用计算机的逻辑在某一个“固定的、可言传的”规则上计算能力超过了人类。
但我们现实生活中,“不固定的、不可言传”的事务比比皆是,怎么谈生意、怎么忽悠投资人、怎么跟领导汇报、怎么泡妞。。。这些都无法用固定规则来描述,换句话说,即使给出再大的计算能力,也很难给出上面这些事的“棋局优劣函数”,同时也无法找出一个CNN网络来评估训练这些事,因为他们的输出根本就是不是离散的。
所以,我觉得目前的AlphaGo距离真正的人类智商还相差太远,等什么时候,计算机能够做到察言观色、洞察秋毫,能够像电影“机器姬”迷惑人类时,才能算是真正的人工智能!