三、闭着眼睛瞎蒙

1983年圣诞节期间，时年9岁的法国男孩雷米●库仑（Rémi Coulom）从父亲那里得到了一件让他欣喜若狂的节日礼物：一台可编程游戏机。

可以想象，在电脑还没有走进千家万户的当时，一台智能游戏机对于一个不到十岁的男孩会产生怎样的诱惑。不过小雷米并没有满足于玩机器本身自带的游戏，没过多久他就开始尝试通过编程来开发自己喜爱的游戏。仅仅用了不到一年的时间，他便成功地写出了第一款智能游戏。从此以后，他的这一爱好更加一发而不可收。到18岁时，他已经开发出了难度极高的能与国际象棋选手对弈的人工智能软件。

在网络尚不发达的当时，写出一款人工智能游戏可不是一件容易的事。由于找不到可供参考的源代码，对于每一种算法，雷米只能自己一行一行地用代码去实现。因此，他的国际象棋软件的表现并不是很理想。

不过，国际象棋软件却成为他进入棋类编程的切入点。1997年，也就是“深蓝”打败卡斯帕罗夫那年，雷米参加了在巴黎举办的世界电脑国际象棋冠军赛。这次活动让他有幸结识了这一领域里的很多牛人。也正是由于这个原因，后来在进入研究生院学习时，他选择了以电脑编程为自己的主攻方向。

拿到博士学位之后，雷米在法国里尔第三大学（Université de Lille 3）任教。其间他曾指导一名硕士生做关于围棋电脑人机对弈问题的毕业论文。硕士生在做完论文后就离开转而攻读博士学位去了，可雷米自己却深深地陷入了这个问题之中。

雷米觉得靠当前的蛮力搜索法是很难在这个领域里取得突破性进展的。必须想出一种算法，尽可能多地把一些昏招除去，才有可能把电脑从无穷无尽的搜索中解放出来。有一次他和同事讨论这个问题，同事觉得也许可以尝试一下用概率统计学的方法来指导机器下棋。

雷米顿觉眼前一亮。很多逐一列举法无能为力的难题都可以用统计学的方法来解决。现成的例子就有人口普查问题，总统选举的预测问题。这些问题与围棋人机对弈问题有着类似的难度：不可能把真实情况一一列举出来。解决的方法也很简单：取一小部分有代表性的样本，用这些样本来估算整个系统的特征。

雷米的同事并没能给出用概率统计学解决围棋对弈问题的具体方法。不过在得到这个灵感之后，雷米便一头钻了进去。不久，他将电脑蛮力搜索与概率统计学结合在一起，发明了一种全新的算法：蒙特卡罗树搜索（Monte Carlo Tree Search，简写MCTS）方法。使用这个算法，他写出了全新一代电脑围棋软件。

什么是蒙特卡罗树搜索？听上去很高深抽象，其实它的基本原理非常简单。具体的做法就是：闭着眼睛瞎蒙！

啊，电脑这么不负责任吗？其实这是没有办法的办法。我们人类在很多情况下也必须借助这种不靠谱的方法来决策。假如我们在森林里迷了路，分不清东南西北，手上既没有地图也没有指南针，电话不巧也没电了。在这种情况下，除了认定几个不知正确与否的方向听天由命地向外冲之外，谁还能想出更高明的办法？

相比之下，电脑的瞎蒙其实是非常科学的。让我们依旧以5x5围棋盘来举例说明。

还是假定黑子第一手下在B-1，现在轮到电脑走白子。

由于电脑没有人类拥有的无与伦比的直觉，所以它必须把每一种落子的可能性都试一遍，然后从推导出的结果来决定这步棋好不好。假定它从A-0开始，A-1，A-2……一直试到E-4。

咦，这和前面的蛮力搜索不是完全一样吗？

不一样，在蛮力搜索时，电脑必须把接下来有可能产生的每一种落子都列举清楚。而在进行蒙特卡罗树搜索时，它只需闭着眼睛随便选取一定数量的走法，然后根据这些走法所产生的结果来评估落子的优劣。

说得再具体一些。假定现在电脑想要知道在E-4落子是不是一步好棋。如果是蛮力搜索法，那么电脑会把接下来黑子的23种下法，再接下来白子的22种下法……一直到把棋盘摆满的所有下法都一一列举出来加以评估。稍有数学常识的人都会知道这样得出的会是一个天文数字，姑且假定有一亿种。

蒙特卡罗树搜索的基本思路就是：在评估当前的落子时，不必把接下来的一亿种可能性全都列举出来，而只需从中随机挑选一部分，比如说一万种下法来进行比较。

这里的一亿、一万只是为了举例方便。实际数字会比它们大得多得多。

只需随机挑选一万种？那万一把能够出奇制胜的妙招漏掉，或者把蠢得不能再蠢的昏招包含在里面，那不是要对整个形势做出错误的判断了吗？

答案是即使漏掉了个把妙招或者包含进了个把昏招也没关系。

是不是太不负责任了呢？

完全没有。还拿这个5x5的棋盘来举例：假设一个水平正常的人和一个臭棋篓子来比赛，水平正常的人执黑，先走了B-1，而臭棋篓子接下来走了E-4。突然，臭棋篓子想起自己得去和女朋友约会了，于是他对正在旁边观阵的围棋大师说，接下来的棋你帮我下吧。结果是，围棋大师在十分不利的情况下依然战胜了水平正常的人。

尽管臭棋篓子开了个臭局，然而在围棋大师接手之后，白方反而取得了胜利。原因就在于围棋大师后来走出了几步谁也没想到的妙招。

然而这个结果是不能用来评估臭棋篓子开局的好坏的。

要想正确判断E-4这步棋是不是高明之举，最好的办法是找两个水平普通、实力相当的人接着下完这盘棋。为了排除诸如发挥失常等偶然因素，最好能多找些水平类似的选手来捉对厮杀。最后再用这些选手比赛的总结果，来衡量E-4这手棋水平的高低。

让实力相当的双方在正常发挥的情况下下完这盘棋，然后根据比赛结果来判断当前这手棋下得好不好，这便是蒙特卡罗树搜索的核心思想。

由于是选择是完全随机的，因而无法排除这些落子里不包含绝处逢生或大意失荆州棋招的可能性。

不过即使有也没关系，因为棋盘上的落子，绝大多数都属于平庸的普通下法，极妙和极蠢的走法均属于凤毛麟角之类。从一亿种下法中随机选取一万种，即使真的选到这二者，其数量也不可能多。由于蒙特卡罗树搜索看的是整体统计结果，因而这里的偏差不会对总结果造成影响。

下面就是蒙特卡罗树搜索算法的实例。为了画图方便，这里把随机样本从一万改为十。

比如说电脑想比较到底是下E-4好还是C-2好。它知道不管选哪个，接下来的走法都是成千上亿，不可能全部列举。于是电脑就从以E-4开始的棋局中随机挑了10局，又从以C-2开始的棋局中随机挑了10局，看看哪种走法自己赢的局数多。

结果它发现，从E-4开始下，10局棋自己只赢了1局；而从C-2开始下，10局棋自己赢了8局。所以电脑认为：C-2比E-4好。

这样一个算法，把电脑的围棋能力提高了好几个数量级。

待续

阶梯讲师原创作品•谢谢阅读