浅谈蒙特卡洛树搜索（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