您好,欢迎来到 中国大学生在线

【重理工智库】Alpha Go 是如何领悟棋道的

2017年03月21日 14:24:46 来源: 重理工智库 作者: 字号:TT

导读:2016年,人工智能机器人Alpha Go一连击败多位世界顶尖围棋高手,使得“人工智能”话题热度持续。人工智能背后有很多专业性问题,本期特邀我校计算机科学与工程学院南海博士与大家共同探讨分析Alpha Go是如何理解围棋并赢得比赛的。

引言:阿尔法围棋(Alpha Go)是一款围棋人工智能程序,由谷歌(Google)旗下DeepMind公司的戴密斯·哈萨比斯、大卫·席尔瓦、黄士杰与他们的团队开发,国人也亲切地称之为“阿法狗”。其主要工作原理是“深度学习”。

2016年1月27日,谷歌研究者开发的名为“阿尔法围棋”(Alpha Go)的人工智能机器人,在没有任何让子的情况下,以5:0完胜欧洲围棋冠军、职业二段选手樊麾。

2016年3月9日到15日,Alpha Go挑战世界围棋冠军李世石,比赛采用中国围棋规则,最终以4比1的总比分取得了胜利。

2016年12月29日晚起到2017年1月4日晚,Alpha Go在弈城围棋网和野狐围棋网以“大师”(Master)为注册名,依次对战数十位人类顶尖高手,取得60胜0负的辉煌战绩。

十几年前,面对人工智能,围棋被认为是人类智慧的最后一座堡垒,时至2017年的今天,Alpha Go已经摒弃了人类千百年来的棋谱,靠洞中修炼、左右互搏练就出来一套聂卫平大师看来“不可思议”,“超出人类认知”的着法。在这篇文字里我们不关心Alpha Go背后眼花缭乱的专业技术,我们只关心,作为一台机器,Alpha Go究竟是如何理解围棋的,它的棋技是否真的已经得道?

1.    何为道

道,极致的宇宙世界观、世界规律与规则。老子中曾言:道可道非常道。得道,乃古代道家谓顺应自然﹑与天合一的境界。而围棋之道,是天道人道交合而成,每一颗棋子都有其价值,每一步都有其用意,哪怕此时的臭棋、恶手,只要善加利用,也有可能转化成好手、妙招。

2.    系统组成

我们还是先来了解一下Alpha Go的肉身。Alpha Go系统主要由几个部分组成:一、策略网络(Policy Network),给定当前局面,预测/采样下一步的走棋;二、快速走子(Fast rollout),目标和策略网络一样,但是在适当牺牲走棋质量的前提下,速度要比走棋网络快1000倍;三、估值网络(Value Network),给定当前局面,估计是白胜还是黑胜;四、蒙特卡洛树搜索(Monte Carlo Tree Search),把以上这三个部分连起来,形成一个完整的系统。其中策略网络和估值网络是核心,被看作是Alpha Go的两个不同神经网络“大脑”,用以提升棋力。

Alpha Go的双核大脑把棋盘当成19×19的图像,用卷积层构建棋盘局面的表达,进而减少搜索树的有效深度与宽度,用走棋网络进行抽样行动,用价值网络评估棋局。

下文着重介绍两个核心神经网络是如何工作的。

3第一个大脑:策略网络(Policy Netwo)

在下图中,黑棋先行,图上的数字表示Alpha Go认为黑棋可能在这一位置落子的概率。我们发现,其中有两个位置落子的概率比较大(图中绿色的位置),其他位置可能性比较小。职业棋手会根据几个最有可能的走法推演以后的变化,Alpha Go也是如此,它通过策略网络进行预测职业选手的走步有57%的准确率。

(图片来自网络)

Policy Network,即策略网络,是一种深度卷积神经网络的模型,它的输入是当前的棋局(19×19的棋盘,每个位置有黑,白,空3种状态),输出可能性最大(即最优)的着法,每个空位都有一个概率(可能性)。Policy Network先向职业选手学习,直接从围棋对战平台KGS(可以理解成外国的联众围棋游戏大厅)获得16万局6至9段人类选手的围棋对弈棋谱,总共有3000万个的局面,训练出来了一个具有13层策略网络的类似人类下棋行为的模型。学习的目的不仅仅是记住这个局面,而是预测相似的局面,进行举一反三。这种学习叫做“监督学习”(supervised learning)。以前的职业棋手的棋谱,就是它的老师(监督)。

深度学习(deep learning)是近几年兴起的模拟人脑的机器学习方法。Alpha Go通过深度学习训练得到的policy比以前其他的学习方法都更加准确。这就是Alpha Go强的原因之一。

更加厉害的是,Alpha Go学习完大部分职业棋手棋谱后,为了超越老师和自己,独孤求败的它只能和自己左右互搏,通过自己与自己对弈,找到更好的policy,这就是增强学习(reinforcement learning)的思想。比如我们已经有了一个策略网络p,先用p和p对弈,比如1万局,就得到了一万个新棋谱,加入到训练集当中,训练出p 1。然后再让p 1和p 1 对局,得到另外一万个新棋谱,这样可以训练出p2,如此往复,可以得到pn,pn也叫做“增强学习的策略网络”(reinforcement learning (RL) policy network)。它没有直接的监督信息,而是把模型放入特定环境中(下棋),通过和环境互相作用,环境对模型完成任务的效果给予反馈(赢棋还是输),从而使模型改变自己(更新参数),更好地完成任务(赢棋)。增强学习后,再让pn和p对局,在不用任何搜索的情况下赢棋的概率可达80%,效果拔群。

最后,Alpha Go还有一个mini的Policy Network,叫rollout。它是用在上面所说的模拟中,快速模拟的终局的。它的输入比正常Policy Network 小,它的模型小,耗时是2微秒,而一个policy要3毫秒。虽然它没有policy准确,但是它的速度较快。

总结一下policy。它是用来预测下一步“大概”该走哪里。它使用了深度学习,监督学习,增强学习等方法。它主要用于每次模拟中的bonus的先验(我大概该怎么走),和Value Network的学习。

4.第二个大脑:价值网络Value Network

Alpha Go的灵魂核心就在下面这个公式里。

V*(s) = Vp*(s) 约等于Vp(s)。

s是棋盘的状态,就是前面说的19*19,每个交叉3种状态。

V是对这个状态的评估,就是说黑赢的概率是多少。

V*是这个评估的真值。

p*是正解(产生正解的policy)

p是Alpha Go前面所说学到的最强的Policy Network。

如果模拟以后每步都是正解p*,其结果就是V*,这解释了等号。

如果你知道V*这个函数,在当前局面,你要对走下一步(围棋平均有250种可能性)后的状态s进行评估,选最大的V*走就行。围棋就完美解决了。但是,前面说了,V*不存在。同样p*也不存在(理论上存在,实际因为搜索空间太大,计算量太大找不到。在5×5的棋盘中下棋可以做到)。

Alpha Go天才般的用最强policy,p来近似正解p*,从而可以用p的模拟Vp来近似V*。即使Vp只是一个近似,但已经比现在的职业9段好了。想想她的p是从职业选手的着法学来的,就是你能想到的棋她都想到了。而且她还在不断使的p更准。Alpha Go模拟到终局,也极少出错。

围棋比其他棋类(比如象棋)复杂的原因主要在于两点:一个是棋局的搜索量大,棋类博弈问题实际是一个树搜索问题,树的平均广度、深度越大,搜索越难,需要的计算量越大。围棋平均广度是250,深度150,象棋平均广度是35,深度80。如果要遍历围棋博弈树,要搜索250的150次方,是不现实的。而更重要的原因前面讲了,是象棋有比较简单的手工可以做出的value函数。比如,吃王(将)得正无穷分,吃车得100分,等等。1997年打败当时国际象棋世界冠军的Deep Blue就是人手工设定的value。而围棋的value比象棋难太多了,手工是无法做到的,所以只能再次寄希望于深度学习了。

下面这幅图是Alpha Go用Value Network预测的走下一步赢的概率。空的地方都被蓝色标示了,越深说明Alpha Go赢的概率越高。这和我们学的棋理是相符的,在没有战斗时,靠边的1,2线地方和中间的概率都低,因为它们效率不高。而且大多数地方的概率都接近50%。所以说赢棋难,输棋也很难。这当然排除双方激烈战斗的情况。

(图片来自网络)

Value Network是通过Policy Network得到的。Alpha Go可以通过自己和自己下棋,双方都用最强的policy来模拟,直到终局,终局的V*(谁赢)就比较容易判断了。注意,这里的“模拟”是在线下学习的过程中模拟,而先前提到的模拟是Alpha Go在下棋(线上)中使用的。

Value Network也是一个监督的深度学习的模型。多次模拟的结果(谁赢)为它提供监督信息。它的模型结构和Policy Network相似,但是学习的目标有所不同。policy是预测下一步走哪里,value是走步后赢的概率。

总结一下,Value Network预测下一次走步后赢的概率。是通过用最强policy来近似正解,模拟的结果来近似准确的形势判断V*。Value Network用监督的深度学习去学模拟的得到的结果。Value Network 主要用于模拟(在线下棋的时候)时计算Q值,也就是平均的形势判断。

最后,在线上下棋的时候,模拟其实是在蒙特卡罗树搜索(MCTS)下进行的,模拟的每一步是兼顾:模拟到现在平均的形势判断Value Network、快速rollout模拟到终局的形势判断、根据当前形势的选点policy,和惩罚过多的模拟同一个下法(鼓励探索)等方面。经过多次模拟,树会搜索得越来越广,越来越深。由于其回溯的机制,Q值变得越来越准确,之后的搜索会越来越强。因为每次的Q值,都是当前模拟认为的最优(排除鼓励探索,多次后会抵消),模拟最多的下法(树分支)就是整个模拟中累积认为最优的下法。

Alpha Go的基本框架见下图。线上下棋过程是图中红箭头。线下的准备工作(学习过程)是蓝箭头。线上下棋时,每次模拟要选下哪一步,不是简单的选择policy,而是要参考以前模拟的形势判断,包括:利用Value Network、快速模拟(小模拟)到终局、鼓励探索、policy先验(Q+u),它们比单纯的policy准确。最后选择模拟最多的,也就是平均最优的下法。而在线下,它要训练好policy模型、rollout模型和value模型。其中,policy,rollout可以从棋谱、和自己下棋中学习到。value可以从学习的policy下棋的模拟结果监督学到。从而完美解决value学不到的问题和policy和value互相嵌套的死结。

(图片来自网络)

5. Alpha Go是如何理解棋谱的

以上介绍了Alpha Go的系统结构,它是否领悟了棋道,关键在于它是如何理解围棋的,也就是围棋棋局的特征。因为围棋的极端复杂性,这些输入特征(棋子)的关系是非线性的。虽然理论上采用神经网络的算法可以处理非线性特征,但是计算量和对资源的消耗都太大。相反,如果有依据地增加一些新的特征的维度,使特征间的非线性关系不那么复杂,将使得模型变得更加简单、更加便于训练,优势还是很明显的。

那怎么增加更多的特征呢?这就需要利用部分围棋领域中的知识,比如围棋中的术语:气、目、空等概念都可以作为我们构造新特征的基础。在Alpha Go的Policy Network中就是采用了以下更多的特征:

(图片来自网络)

部分说明如下:

落子颜色(Stone color)

(图片来自网络)

落子颜色的三个平面中的1分别表示白棋、黑棋、空白位置。

轮次(Turn since)

(图片来自网络)

表示这个棋子距离当前局面的轮次,比如上一步对手走的就是1,上上一步自己走的就是2。因为围棋很多都是局部的战役,所以这个feature应该是有用的。

气(Liberties)

(图片来自网络)

表示棋子的气,即与它相邻的空白位置的数量。

打吃(Capture)/ 被打(Self-atari)

(图片来自网络)

表示对手被打吃/自己被打吃的数量,图中黑棋被打吃的数量为2。

征子(Ladder)

(图片来自网络)

图中白2征子有利,征子可以计算。

我们可以看到,Alpha Go的所谓的棋道,只有这么可怜的几条,例如气、打吃、征子都是围棋最基本的知识,谈不上技巧,连例如“七死八活”等基本死活棋都没有作为特征输入,更不用说“金鸡独立”、“老鼠偷油”等手劲,可见,从学习的输入特征来看,Alpha Go对围棋的理解只是停留在最基础的规则上面,“肤浅”得像个婴儿,可是,经过两个“大脑”的学习之后,这个婴儿竟然迅速自学成才,陡然成为一代宗师。

6.结束语

一代宗师Alpha Go,她的学习过程就是一部宗师的成长史:监督学习的Policy Network就像儿时跟随师父练习基本功,逐渐参透师父们的棋技;当师父的棋技全都吃透,没人能再教她的时候,增强学习Policy Network就像闭关修炼、左右互搏,独自研究新的棋路。可能失败,可能要重头再来,但这些都是通向可能的更大成功的基石。当各种棋风流派此消彼长,大师们坐坛论道、甚嚣尘上之时,她深深的脑海里那些千丝万缕的权重,也许就是他对围棋棋道的独特理解吧!

[责任编辑:刘宇宏]

围棋 人工智能 重理工

我要评论( 网友评论仅供其表达个人看法,并不表明本站同意其观点或证实其描述。)
用户名: 快速登录

全部评论0条)

关于我们 共建单位 联系方式