如何当一个AlphaGo?
本文作者徐皓禕,创客,加泰罗尼亚理工人工智能研究生,已出版《自己动手做交互系统》。联系邮箱:[email protected]。
多年以来,开发能够与人类对弈围棋并获得全胜的人工智能系统一直是困扰业界的一大难题。在 AlphaGo 诞生之前,人们一度认为十多年后我们才有足够技术解决这一难题。
那么,AlphaGo 是怎么将旷世难题变得有希望被解决的?
大数据的诅咒
围棋问题之所以难,难在它的复杂程度远大于其它棋类游戏。国际象棋也好,西洋跳棋也罢,可能出现的棋局总和都跟围棋不在一个数量级。在排列组合比较有限的游戏中,计算机几乎能够“算无遗策”,但要解决围棋问题,算尽每一步的方法变得不切实际。
影响研究者算法的一个很重要的因素在于单位数据的信息量。打个比方,如果我们想从人群中认出某个人,我们可能需要掌握身高,性别,头发颜色等特征信息。我们所用到特征的数量,也就是数据的“维度”。
AI 在处理实际问题时所用的数据会包含多个特征:以图片为例,如果我们将每个像素值当作特征,那么图片信息的维度就是图片长度乘以宽度。因此,一份数据包含成千上万维度的信息并不鲜见。要看清围棋盘上的局势,就要求AI能够处理高维度的数据。
一般来说,机器进行学习的能力高低,很大程度取决于它对信息识别与分类的准确程度。相对而言,低维信息总是比较容易分类——在最理想的情况下, 我们可以找到一条线或一个平面将信息一分为二。但是对高维度数据,我们很难想象要怎么做同样的事情。而围棋,偏偏就是数据维度极高的游戏。
(图片来自:Go Game Guru)
在向机器提供学习材料进行训练时,提供待处理数据就好比喂人吃饭——儿童、一般成年人和超级大胃王的饭量各不相同,超过各自的上限会吃撑了,而吃得太少便会乏力。同理,不同的算法也需要不同数量的学习资料,数据过多会影响准确性,数据过少则会训练不充分。
要成为能判断围棋盘上局势的 AI,AlphaGo 选择了成为超级大胃王的道路,利用一种名为深度神经网络的架构,来“消化”用传统方法无从下手的数据集。这个大胃王所需要耗费的计算资源与训练时间多得令人咂舌——最终版本的 AlphaGo 使用 40 个搜索线程,48 个 CPU 与 8 个 GPU。而分布式版本则利用多台电脑,使用 40 个搜索线程,1202 个 CPU 与 176 个 GPU。
吃棋谱的黑箱子
吃得下高维数据,也要能从中汲取营养。科学家一般会将待解决的问题转化成数据建模,让机器进行摸索。如果机器有朝一日能利用某个数据模型准确描述实际情况,那么学习就算是成功了。
(图片来自:The Situational Intelligence Blog)
而所谓的“深度神经网络”,正是一种厉害的数学模型。它脱胎于对大脑神经运行方式的模拟,利用一层一层的“人工神经元”来计算输入数据和输出数据之间的复杂关系。这种架构能由浅入深地处理从局部到整体的信息,在更高层次上做出理解和归纳。
试想有一个箱子能够“学习”将不同的小球按颜色分类——你把小球放进箱子里,它就告诉你这个小球是什么颜色。一开始这个箱子可能很蠢,不能准确分类颜色。这时,人们需要手动或自动调整箱子的内部机关,同时放进一个又一个的小球让它分辨,并检查它得出的结果。如果所得结果和真实结果有差异,箱子内部的机关需要进一步调整;如果没有差异,便不再调整它。
在无数次判断小球的试炼后,箱子最终会成为一个完美的分类器。它不见得知道自己是在将小球按颜色分类,但它能够输出正确的分类结果。
本质上,AlphaGo 系统就是一连串的箱子。每一个这样的箱子都是一类比较自动的分类器,名曰“卷积网络”。经过合适的训练和参数调整,它们无需过多人工操作就能自动执行信息特征提取与归纳,利用现有的信息给出较为准确的答案。
AlphaGo 动用了 13 层卷积网络进行训练——训练内容自然也不是吃小球,而是吃棋谱。通过输入 3000 万张尺寸 19X19、来自不同比赛的棋谱,AlphaGo 得以学会识别每一步棋的状况,不仅学习小范围内的对战策略,也可在宏观上把握整体局势。
由于卷积网络中包含上万神经元,在 AlphaGo 内部进行的数据处理很难像图像识别一样可视化并给人直观反馈。换句话说,连论文作者只能推测它的决策方法:卷积网络输入层的各个节点可能正与棋盘上的每个可落子的点一一对应。
在 AlphaGo 这只“黑箱”内所发生的事倒并不是不可知的,只是分析和计算的工程量实在太多。要解释清楚这些神经网络内部所发生的事,除了工程师外,还得更多的数学家也来帮忙。
两张网一棵树,吃饱棋谱吐棋着
在AlphaGo“吃”的是棋谱,那“吐”出的是什么呢?
是棋着。
围棋是一子接一子的整体游戏,每落一子都会影响棋手最终获胜的几率。要寻求胜利,棋手就必须考虑每一回合落子的位置。有时候,一颗棋子能为棋手争得眼前的优势,却对远期目标不利,因此,棋手也需要考虑大局。
这两种需要考虑的点,换成 AlphaGo 这口箱子需要计算的数据便是“策略”(Policy)与“值函数”(Value Function)。
AlphaGo 吃下棋谱后,会记录每一回合中可以落子的点,并标注落子的概率——某点的概率数值越高,表明职业棋手越可能在该点落子,反之亦然。而对值函数的计算,则是在衡量当前状况与远期目标后,对所有选择做出的预测结果和优劣判断。
(图片来自:KWBU)
最初,研究者基于卷积网络给 AlphaGo 创建了“策略网络”。在开始阶段使用监督学习的套路,旨在教它吃啥吐啥——令网络做出与它所学习的棋局相同的预测。在学习的过程中,网络会自动调整自己的参数,尽可能地模仿人类棋手做出决策。在这个阶段,策略网络的学习重点是尽力模仿,而非在比赛中得胜。
随后,研究者再利用强化学习令系统自我对弈,通过得胜获得奖励,失败接受惩罚的方式,进一步调整策略网参数,实现自我优化。得益于计算机令人害怕的弈棋速度,AlphaGo 的策略网络在这一阶段进步十分明显,比较只使用监督学习训练出网络,胜算足足增加了 80%。
在优化的策略网络基础上,研究者又使用相同的网络结构训练“值网络”。在经过大量训练后,这口“黑箱”用自己的方法得到了能够准确计算策略与值函数的模型,并用训练好的神经网络分类器准确识别不同状况,以做出最优选择。可以说,通过卷积网络得到的模型,和职业棋手的作风已经有了七八分相似。
但有再好用的卷积网络,AlphaGo 也不可能将整盘棋所有可能出现的情况全部枚举出来做计算,原因很简单——没那么多时间。
怎么办?要在有限的时间里吐出最可能致胜的棋着,AlphaGo 还需要在两张网上种一棵树:蒙特卡洛树。
这个带有异域风情的名字全名叫“蒙特卡洛树搜索”。它是一种经典的棋类算法, 用于只需枚举当前和未来几个回合出现的情况,而将其他多余的分支放弃掉。
设想现在这一回合,AlphaGo 使用策略网络,在众多可能落子的点中选择出了概率数值最高的落子位置,同时在选定的点中用值函数网络计算长远利用。在通过这一步骤寻找最有利的落子位置时,AlphaGo 可能会向后推算几步,在枚举可能性的树状图上产生新的分枝。蒙特卡洛树搜索算法可以比较各个分支,并把较好的结果保留下来。等到下一回合,策略网络再做决策。如此循环往复直到游戏结束。 这两张网络一棵树结合起来,才使 AlphaGo 既具备了与专业棋手相当的比赛经验,也具备了提升临场发挥的素质。
他山之石,可以攻玉
凭借这样一副“好肠胃”,AlphaGo 已成为第一个5局击败职业围棋选手的智能系统,但是其潜力并不仅限于围棋。之前许多棘手而复杂决策任务,或许也可以利用 AlphaGo 搭建的卷积网络模型找到突破口。在深度学习的帮助下,机器能从一个笨小孩摇身变成学习天才。也许在未来,困扰专家的问题不再是如何更好地拟合数据,而是为机器寻找最好的学习资料——到那天,人类作为老师可能已经没有什么内容能教给机器了。机器唯有通过与机器对战,才能提升自己的知识水平。
参考资料
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Driessche, G. V., . . . Hassabis, D. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), 484489.
Elements of Reinforcement Learning
http://www.dcine.com/2016/01/28/alphago/
http://jeffbradberry.com/posts/2015/09/introtomontecarlotreesearch/
http://cs231n.github.io/neuralnetworks1/
题图来自:电影《吴清源》