互动科普

AlphaGo = 蒙特卡罗树搜索 + 深度神经网络

那么既然同属“蛮力搜索”程序，为什么深蓝善于下国际象棋却对围棋一窍不通，而传统围棋程序只能达到业余高段位棋力？这些程序的区别就在于搜索策略、评估函数和汇总策略3个模块的具体实现方法不同。

深蓝时代的国际象棋程序得益于拥有一个强大的评估函数。当时人类国际象棋大师所拥有的知识已经足够精确，使得对盘面胜率的评估可以被直接描述成一个程序。这个强大的评估函数使得国际象棋程序在搜索状态空间时只需要考察较少步数的变化（比如深蓝“只需”考察平均十几步之内的变化）就可以得到比较可靠的胜率信息，这样就可以把程序需要的计算量控制在深蓝时代的硬件能力范围之内。

但围棋一直缺少这样强大的评估函数，所以国际象棋中使用的搜索策略组合对围棋就完全不适用了。直到2006年前后，发现了一种新的搜索策略组合，叫蒙特卡罗树搜索（MCTS）。前面提到，状态空间搜索都要搭配评估函数一同工作。蒙特卡罗树搜索作为一种搜索策略，对它的评估函数“搭档”只有可以判断盘终盘面胜负这个最低要求（因此也可以说蒙特卡罗树搜索根本不需要真正意义上的评估函数），这恰好弥补了围棋程序在评估函数上的缺陷。蒙特卡罗树搜索的这个特性是因为它采用一种更谨慎的汇总策略，可以更有效地从对未来盘面的低质量的评估结果中提取有用信息。要注意的是，今天的AlphaGo同样也是使用蒙特卡罗树搜索策略，所以和传统围棋程序一样都是基于蒙特卡罗树搜索的程序。

不过，评估函数上的固有缺陷仍然使得AlphaGo之前的蒙特卡罗树搜索程序不得不在状态空间搜索时把变化一直展开到盘终 (或者至少到棋局末期）。为此，蒙特卡罗树搜索采用一种比较激进的选择策略，以尽量排除掉意义不大的可能变化。AlphaGo之前的一流围棋程序大多直接借助围棋专业知识来编写这样的选择策略。随着选择策略变得越来越专业，基于蒙特卡罗树搜索的围棋程序的业余段位一路上涨，从几年前的业余初段提高到目前至少业余五段的棋力。

需要强调的是，即使在达到高段位棋力的程序中，目前用到的围棋专业知识仍然只是入门级的。如果（不经过搜索）直接基于这些根据知识编写的选择策略决定走子的话，程序棋力只会惨不忍睹。不过，尽管这个选择策略自身棋力不堪一击，但它只是整体“蛮力搜索”的一个模块，而使用这样基于入门级围棋知识编写的选择策略的“蛮力搜索”型程序却足以战胜围棋业余高手。

蒙特卡罗树搜索策略加围棋专业知识的组合，经过近10年的发展，已经可以击败绝大多数人类业余棋手，但仍然无法挑战职业棋手，直到AlphaGo横空出世。

AlphaGo完整继承了自深蓝时代沿袭下来的“蛮力搜索”算法框架，在状态空间搜索中使用的信息汇总策略也与传统蒙特卡罗树搜索围软件完全一样，而且在其选择策略中也同样使用大量手工编写的入门级围棋专业知识。在公众眼中“从天而降”的AlphaGo，其实是从一个大概具备一流开源围棋软件水平的传统蒙特卡罗树搜索程序改造升级而来。AlphaGo棋力的大幅上涨，本质上是因为成功向搜索中加入了更多的围棋领域知识。具体而言，AlphaGo大幅改进了状态空间搜索中的选择策略，而且还配备了一个有效的围棋盘面评估函数，这两个模块级别的改进带来了超出很多人预期的棋力提升。更有趣的是，这两方面的改进都是同一项技术带来的，这就是（深度）人工神经网络。

图 围棋程序的分类

（本文发表于《科学世界》2016年第4期）