五子棋AI算法一 我对AlphaGo的看法

最近Google宣布他们的围棋AI以5:0的战绩打败欧洲围棋三冠王。我一直对人工智能比较感兴趣,正好趁年前空闲的几天用JS写了一个五子棋的AI。其实很久以前就用自创的算法写过一个JAVA版的五子棋AI,不过棋力很不理想。这次用的是JS写的,所以无论任何平台上只要能打开网页的都可以玩。

google爆出这个新闻之后,很多人觉得这是不是意味着电脑智商已经在人类之上了,围棋已经没有意义了之类的。甚至觉得这是不是电脑统治人类的开端。对这些想法我只能呵呵了。

Alphago其实没有人类的“智商”!

智商包括很多维度比如认知能力、学习能力、记忆力、创造力、逻辑思维能力等,而人类智商最大的特点在于创造力,或者说想象力。现在的AI并不具备创造力,但是具备一定的学习能力。
不过这个学习能力也仅仅是很片面的一个领域内的,比如AlphaGo只会学习围棋,不会学习如何写作如何修车等。所以它只具备人类通过深度学习算法赋予它的一点点很初级很优先的学习能力。这个学习能力和几岁的小孩都没法比。

Alphago 基本上是以深度神经网络结合蒙特卡罗算法实现的,他可以通过不断和高手对弈或者和自己对弈来提高棋力。无论是深度神经网络还是蒙特卡罗搜索,都是现成的理论,没有在AI领域有本质上的突破。
而Alphago能赢欧洲的围棋冠军,靠的是一群大牛程序员和一大批专业棋手以及那个超强计算能力的大型计算机。

围棋也不会失去意义

首先,虽然Alphago战胜了专业二段水平,但是围棋其实是一个亚洲的游戏,高手都在中日韩三国。业界公认樊麾和顶级的李世石九段是有巨大的实例差距的,而且和Alphago的对决中樊麾发挥的非常不好。所以Alphago在和樊麾对战的时候,棋力应该是专业二段左右,和李世石九段差距甚远。当然电脑的进步是神速的,而且Alphago肯定会研究李世石之前的棋谱来找对策,所以有一定的机会能赢,但是即使赢了,也不会赢得很轻松。个人比较倾向于现阶段Alphago会输,但是几年或者十几年之后,电脑最终会以极大优势横扫围棋界,这个时间点的到来比很多人预期的要快。

即使电脑完虐人类,围棋也不会失去意义。就像汽车不会让博尔特失去意义,深蓝不会让国际象棋失去意义一样。这段新闻过了之后,围棋还是围棋,电脑还是电脑。只不过可能小朋友能借助AI在网上虐一下高手而已。

Alphago的意义

围棋是一个唯一人类可以狂虐电脑的棋类游戏,甚至业余高手都可以狂虐电脑,之前最顶尖的电脑也不过业余5段水平,而全国业余五段数以万计,并且业余五段和业余六段以及专业段位有天壤之别。
主要原因有如下两点:

  • 围棋非常难进行局势评价。国际象棋对当前局势的评价函数比较简单,根据每个子的权重加一下就可以了(当然实际上没这么简单),而围棋这种牵一发动全身,需要纵观全局的游戏很难对当前局势设计一个好的评估函数。而且实际上并不存在一个简单的函数能对围棋的局势进行评估。
  • 围棋所需计算量极大,唯一的每一步平均有200+的变数,基本都会下满棋盘,相比之下 国际象棋每一步的平均变数不超过50,一般几十步就会结束游戏。

所以围棋的博弈树极其庞大,而且非常难对当前的局势进行评分。相比之下象棋这种游戏就简单太多了。所以传统的基于对博弈树进行搜索和评估的算法在围棋上是行不通的。而Alphago得出现,让这个问题的求解看到了希望。很多人觉得电脑下不赢人的原因是认为围棋需要靠大局观才能赢,而alphago证明了这种大局观也不过是一个数学问题而已,完全可以考计算机来解决。

如果说Alphago的意义,那就是它攻下了人类在棋类游戏的最后一块阵地,现在全世界的人都相信,电脑已经统治了所有棋类游戏。或者说,在所有的完备信息的零和博弈游戏中,电脑已经完胜人类。

下面说下完备信息零和博弈游戏的定义,关键就是两个点:

  • 完备信息,也就是博弈双方完全知道对方的所有信息,从第一步到最后一步,所有的走法,整个棋盘看的清清楚楚,也不存在随机性。相比之下,四国军棋就不在这个范围内,因为看不到对手的棋,德州扑克也不再这个范围内,因为看不到对手的牌,而且下一次发出的牌是随机的。
  • 零和博弈,也就是双方的收益之和为0。电脑优势则玩家必然劣势,不存在双方都是优势或者双方都是劣势的情况。

围棋和象棋都是典型的这类游戏,我们要讲的五子棋也是。

我们要讲的五子棋算法是用JS实现的,源码在github上,大家可以先看一下,跟电脑对战几盘感受下电脑的棋力:

下一章开始讲五子棋AI的几个关键算法实现,分别是

  • 极小化极大值搜索
  • Alpha-Beta 剪枝
  • 启发式评估函数
  • 迭代加深
  • 算杀