AlphaGo背后的搜索算法：蒙特卡罗树搜索

昨天（3月9日）下午，经过三个多小时的较量，韩国棋手李世石宣布向谷歌人工智能AplphaGo认输，意味着人工智能获得了这场人机世纪之战的第一场胜利。而此前AlphaGo已经以平等条件击败了欧洲围棋冠军樊麾。

有专家在赛后评论说，AlphaGo的胜利只能算是算法的胜利，因为人工智能目前只是一种算法程序，没有道德，也没有情感，更谈不上情感。

小编其实认为这并没有错，而且就算李世石最后输给了AlphaGo，这样不代表人类输给了机器人。因为这台打败了人类最高智能代表的机器，是由人类一手精心打造的，其内部的算法也是众多科学家一步一步改进得来的。

本文的主题，就是AlphaGo能够成功击败专业棋手的功臣之一：蒙特卡罗树搜索（Monte Carlo Tree Search）。

蒙特卡罗搜索树的贡献，从谷歌AlphaGo的官方网站上就可见一斑。

AlphaGo背后的搜索算法：蒙特卡罗树搜索

完美信息博弈

我们知道，围棋有着明确的游戏规则，其中不存在随机或运气成分（如掷骰子或洗牌）。这类游戏都可以归类为所谓的完美信息博弈（perfect information games）。在完美信息博弈中，每时点参与人采取一个行动，每个参与人在其决策的同时知道以前所有的行动。

因此，理论上我们是可以构建一个包含了所有可能结果的树，因为游戏中所有的一切都是有规则可循的（fully determined）。几乎所有的弈棋程序，都是依靠其强大、精确的计算能力，来预测好的下法。

为什么之前的弈棋程序没有征服围棋？

AlphaGo并不是第一个智能弈棋程序。1997年时，已有超级电脑深蓝战胜国际象棋棋王卡斯帕罗夫的先例。那么为什么深蓝没有乘胜追击，挑战围棋呢？这是因为IBM在比赛结束后就让深蓝退役了。O(∩_∩)O~

说正经的，这很大程度上与围棋的极大可能性和此前弈棋程序的算法限制有关。

我们知道，围棋棋盘横竖各有19条线，共有361个落子点，双方交替落子，这意味着围棋总共可能有10^171(1后面有171个零)种可能性。这超过了宇宙中的原子总数是10^80(1后面80个零)！

而传统AI一般采用的是暴力搜索方法（深蓝就是这样干的），就所有可能存在的下法构建一个树。这样自然根本无法应对围棋游戏啦。

什么是蒙特卡罗树搜索？

“蒙特卡洛树搜索”是一种启发式的搜索策略，能够基于对搜索空间的随机抽样来扩大搜索树，从而分析围棋这类游戏中每一步棋应该怎么走才能够创造最好机会。

一位名叫苏椰的知乎用户举了这样一个例子，以通俗的语言进行了解释：假如筐里有100个苹果，让我每次闭眼拿1个，挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个……我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。这个挑苹果的算法，就属于蒙特卡罗算法：尽量找好的，但不保证是最好的。

需要说明的是，蒙特卡罗树搜索并不是只有一种算法，而是一类算法。其中最流行的算法之一就是UCT（upper confidence bounds applied to trees）。

AlphaGo是第一个使用该算法的弈棋程序吗？

AlphaGo不是第一个使用蒙特卡罗树搜索的弈棋程序。

据senseis.xmp.net网站介绍，第一个使用UCT算法的围棋程序是MoGo。而且，MoGo在2008年的美国围棋公开赛上，第一次在19×19的全尺寸棋盘上击败了职业选手（当然与AlphaGo不同，这位职业选手让了9个子）。

AlphaGo是如何使用蒙特卡罗树搜索的？

虽然“蒙特卡洛树搜索”在此前一些弈棋程序中也有采用，在相对较小的棋盘中能够很好地发挥作用，但在正规的全尺寸棋盘上，这种方法的缺陷也体现出来了，因为涉及的搜索树实在太大了。

但AlphaGo采用了很聪明的策略，利用深度学习的方法降低搜索树的复杂性。因此“深度学习”和“蒙特卡洛树搜索”就成为它的两个关键因素。在每个模拟游戏中，AlphaGo都有两个大脑指引它进行搜索：价值网络（value network）和政策网络（policy network）。“政策网络”观察棋盘布局企图找到较好的下法，“价值网络”则预测这样下的话对方棋手赢棋的可能。结合这两个建议，AlphaGo最终决定怎样落子才是胜算最大的。

AlphaGo背后的搜索算法：蒙特卡罗树搜索