设万维读者为首页 广告服务 技术服务 联系我们 关于万维
简体 繁体 手机版
分类广告
版主:诤友
万维读者网 > 教育学术 > 帖子
浅谈蒙特卡洛树搜索(MCTS)
送交者: gugeren 2016年03月20日00:33:13 于 [教育学术] 发送悄悄话

浅谈蒙特卡洛树搜索(MCTS)

1] 围棋软件AlphaGo的3个主要系统

最近打败世界围棋手李世石的围棋软件AlphaGo主要由以下3个系统组成:

1. 策略网络(Policy Network):落子选择机制,它着眼于每一步弈棋的下法。

2. 估值网络(Value Network):局面评估机制,它注重于对全局形势的判断。

3. 蒙特卡洛树搜索(Monte Carlo Tree Search,MCTS):实现围棋这样超高复杂博弈机制的一种随机算法。

前两个系统容易理解。蒙特卡洛树搜索则有些让人不好理解。本想看到内行的介绍文章,但这类文章一直没有出现。故不揣冒昧,先写一篇,以抛砖引玉。

2] 什么是搜索树和树搜索?

由于棋类活动的每一步一般可以有好几种走法,因此可以把这个思考过程描述成一棵“树”的形状,术语就称为“搜索树” [search tree],见图:

而发现这棵“树”中的每一步好棋,就称为“树搜索”(tree searching)。

简单的棋类,如“井字棋”、“五子棋”,可以把所有能走的全部棋步都找出来,然后把对手的回应棋步也全都找出来,然后找出第3步、第4步、……,并对每步都进行评估,这样就形成了比较正确的走法。这是人们下棋时思考的过程。想得越深、越广,就越容易赢棋。

电脑软件模仿人类下棋,也是采用这种方法;只是它把每个棋步都评分成数值,比较这些数值的大小。数值越大的棋步表明赢的希望越大,就成为软件走棋的依据。

但是对于中国象棋、国际象棋和围棋来说,这棵“树”就太大,根也太深了,写出这样算法的软件就比较难。

特别是围棋,由于它的棋盘上有361个点之多,因此把这些棋步全部找出来,是不现实的。

由此就引入了蒙特卡洛搜索。

3] 蒙特卡洛搜索树及其原理

蒙特卡洛树搜索,简单地说,就是只在全部可以走的棋步“树”中,随机地选取若干棋步,从中挑选出最好的那步棋走。等对方回应的棋步走出后,再继续随机地选取相应的棋步,重复这样的过程;而不是找出所有可能的棋步。

因为摩纳哥(Monaco)的蒙特卡洛是世界有名的赌城之一,而这样的搜索有些像赌博那样碰运气,因此得名。

有人举了一个生动的例子来描述蒙特卡洛搜索树。

在一个密封的筐里有100个苹果,人们每次拿出1个苹果,目的是从筐中挑出最大的苹果来。

人们最先想到的做法就是:随机拿出1个苹果,再随机拿出另1个苹果与它相比,从中挑出较大的那个苹果来;然后再从筐中拿出第3个苹果,把它与那个大的苹果相比,挑出大的那个……。这样重复以上的过程。

人们每次挑出的苹果都至少不比上次的小。拿出的苹果越多,就能找到越大的苹果。但是除非人们挑选完所有的100个苹果,他们无法肯定挑出了筐里最大的苹果,但是却能保证能挑出已经拿出来的苹果中最大的那个。

这个挑苹果的算法,就是蒙特卡罗树的算法:尽量选出好的,但不能保证是最好的。

由于蒙特卡洛树搜索仅随机选取了某几个棋步进行比较,因此,它走出的棋步也并非是最佳的棋步,但是却是比较好的棋步。对AlphaGo来说,至少是可以取胜的棋步;最坏的情形,大概是能保证它不会输的棋步。

具体反映到AlphaGo上,这就是为什么它有时会走出一些“弱手”而让9段高手们看不起的原因。但是高手们不了解的是,软件走出的那些“弱”的棋步其实并非不会取胜,只是为了减少计算,它可能选择了当时棋手们看来只是第二好、第三好,甚至第n好的棋步;只要保证它能赢棋,一步的好坏对它来说是无所谓的。

这也解释了为什么AlphaGo仅在几个月前赢了2段棋手,而在几个月后却能以4:1赢了9段棋手李世石(第4盘中,李世石也只能说是险胜)。实际上,软件是根据对手的棋步来相应地走棋的。对手弱,它选择的棋步就会弱,而不是像人类棋手那样,根据自己的水平走出自己的最好走法。遇到9段高手,它也是如此。这显示出它“遇强则强,遇弱则弱”的特点。

蒙特卡洛算法由数学家乌拉姆(Stanisław M. Ulam,1909-1984)最早提出,再经科学天才冯·诺伊曼(John von Neumann,1903-1957)发展和完善。

乌拉姆曾利用这个蒙特卡罗方法计算裂变材料的中子扩散问题。

4] 题外话

因为AlphaGo是人写的,因此它肯定有弱点。就是说,它并非不可战胜的。

AlphaGo软件的估值网络,据报道可达13层之多;就是说,它可以看到13步棋步那么远。

而在开局阶段,由于AlphaGo软件采用的蒙特卡洛树搜索的那棵“树”太大,因此可能会牺牲掉一些搜索的深度,而达不到13层之多,以此来保证有足够的搜索的广度。

由此可以看出,AlphaGo的开局是比较弱的。其实这也是所有棋类对弈软件的普遍弱点。有关资料显示,AlphaGo这个“软弱的”开局阶段大概持续20手左右,以后随着棋盘上的棋子越来越多,它的棋力也会越来越强。

因此,人类棋手需要在开局阶段尽量找到能占优势的棋步,而不能寄希望在中盘甚至收官阶段来打败它;或者想把局面弄复杂些来打败软件。

从资料来看,平常的比赛时,AlphaGo经常打开一个5x5个局部棋盘的窗口;就是说,它一般能把这25个格子里的变化都研究得透透的了。这个水平,估计人类9段棋手是做不到的;他们可以根据经验来大致评估双方的棋势,而不能把每个点(目)的各种情况都算透了。

棋类对弈软件的全局观较差

有人可能会说,这次AlphaGo与李世石的比赛中,感到软件的全局观是不错的。其原因可能是,据说李的棋,局部计算较好,全局上面则较差。对比之下,反而是软件更强些。

想想也能明白,毕竟整个棋盘的全局的计算量巨大,而局部的计算量则较小。

棋类对弈软件没有主动进攻意识

棋类对弈软件主要根据对手的走法找出相应的棋步来应对。它们普遍缺乏主动地在某个局部挑起战争的意识。尤其在前段棋局时是如此。这也是由于主动挑战需要的计算量太大,应付局面则需要的计算量小多了。

作为软件的人类对手,就要利用软件的这个弱点,主动挑起战争。

这也是李世石感到软件在执黑时弱、执白时强的原因:先手时它不知道走什么好;而应战时则比较好走。

多展开几个局部的战争。让软件不知道应该把主要精力放在哪儿。

电脑软件大多是“一根筋”思路。它可以把事情计算得很深层,但是不善于应付多局面的事务。要至少展开2个以上的局部战争。

参考连接

https://www.zhihu.com/question/20254139

http://songshuhui.net/archives/94410


0%(0)
0%(0)
  我的理解这是个边际递减的应用 - 道还 03/20/16 (502)
标 题 (必选项):
内 容 (选填项):
实用资讯
北美最全的折扣机票网站
贝佳药业美国专利【骨精华】消关节痛、骨刺、五十肩【心血通】改善心绞痛
一周点击热帖 更多>>
一周回复热帖
历史上的今天:回复热帖
2015: Q/微信541520157毕业证 成绩单 回国证明
2015: 曲氏三言绝律第四谱
2014: 要教育子女些什么呢?
2014: 不尚贤,使民不争
2013: 对“NASA中国籍科学家姜波遭逮捕”事件
2013: 李扬:宇宙是设计制造的证据
2012: ZT: 暗物质和暗等量
2012: 少养专家多养猪,评张维迎的“国企是中
2011: 运动的光子应具有质量
2011: 广义相对论为超光速提供理论依据