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年的美国围棋公开赛上,第一次在19x19的全尺寸棋盘上击败了职业选手(当然与AlphaGo不同,这位职业选手让了9个子)。

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

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

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

AlphaGo背后的搜索算法:蒙特卡罗树搜索-数据分析网

能用Python实现这种树搜索法吗?

当然可以,而且一个使用UCT算法实现的Python弈棋程序只有400行代码左右哦!想要下载试玩的话,就看本期另外一篇推送吧。

参考资料:

https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/

http://senseis.xmp.net/?MonteCarlo

http://senseis.xmp.net/?UCT

http://tech.huanqiu.com/news/2016-03/8668752.html

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

http://googleresearch.blogspot.com/2016/01/alphago-mastering-ancient-game-of-go.html

http://www.dcine.com/2016/01/28/alphago/