一个Bot的诞生！（下）

预计阅读时间：10min

前言：哦，很遗憾，看完前半部分，并没有诞生一个Bot，因为前半部分都是在闲扯。我写这个东西的初衷是让大家看到有些算法其实并不是那么神秘，尤其是机器学习周边的一些算法，它们从一开始被冠以智能这顶高帽，让很多人望而却步。今天要介绍的是一个叫蒙特卡洛树搜索的算法，它跟之前我提到的一众启发式算法都有一个共同的特点就是泛用性极强但是运算量很高。考虑到我的小CPU算力有限，所以我的第一个demo选择了zhang88a提到的碰手小游戏。

蒙特卡洛树搜索与阿法狗

首先蒙特卡洛树搜索不是机器学习算法，但是它确实和机器学习有密切的关系。它最近最为成功的工程应用就是在AlphaGo/Zero上。作为最近最为人们津津乐道的人工智能系统，它包含了三个最主要的部分，一个是用来进行博弈树搜索的蒙特卡洛树搜索算法，一个是由残差卷机神经网络完成的对盘面进行先验评估的部分，还有一个对上述的神经网络进行强化学习的自我对弈的部分。 这里面蒙特卡洛树搜索（MCTS）和残差卷机神经网络（ResNet）相互补足，MCTS为系统提供了适用于博弈问题的框架，ResNet为MCTS解决了在围棋这种极端复杂的游戏中决策树难以探索到结束的问题。这个组合还有一个很棒的地方，就是ResNet可以事先训练好，在工作时直接当做一个完备的离线评估函数使用，而MCTS在线运行。对阿法狗来说很大一部分的运算其实在它参与比赛之前已经完成。

由于我们的重点是MCTS因此对ResNet这里就不展开介绍（而且其实我也不是很了解）。相信很多人都知道蒙特卡洛实验，或者有时候我们不知道什么是蒙特卡洛实验，但是潜意识里是有蒙特卡洛实验的思想的。蒙特卡洛实验的核心思想是用大量的实验结果来取代理论的概率分布情况。比如现在有个骰子，我想知道它是不是均匀的。用机械唯物主义的思想来说，只要知道这个骰子的所有参数就能知道它是不是均匀的，可是这是很蠢的，因为这么做的前提就无法达成。但是我们还有一个更加可行的方法，就是我投这个骰子很多很多次，看看是不是6种数字出现的次数差不多。这就是蒙特卡洛的思想，我相信即便没有任何概率论知识的人也是能想到这个方法的，频率会趋近于概率这样的思想就像先天就存在于我们脑海中的一样。这个思想衍生出来很多有用的算法，粒子滤波还有今天的主角MCTS就是这其中的典型。

蒙特卡洛树搜索的秘密

MCTS有一些让人头大的原理图和数学理论，我相信会劝退一些没有耐心的小伙伴，因此我只介绍它的思想方法。第一条思路是到我们的行动阶段时，不同的选择产生的胜率是不同的。这里的胜率是个很笼统的叫法，我们可以把这个东西看作我们行动结束后盘面上对我方优势大小的一个评估参数，显然不同的人或者算法对同样的局面判断出来我方的优势大小也不一样。基于第一条思路，轮到我们行动的时候，我们的任务是找到胜率最大的那一步。第二条思路是一个盘面的胜率多少可以用当前盘面开始进行很多次游戏之后统计胜利的频率来完成。这一条也很好理解，理论上来说就一个残局来说，我找一万组人来下这个残局，统计结果就能知道哪一方容易赢了。这个思路就是蒙特卡洛的思想。第三条思路是我们好像并没有一万组人给我们下各种残局来评估局势，所以我们起初需要一个下残局的策略。如果我们的Bot已经完成了，那么这一条很容易实现，然而我们这是在写Bot的过程中，这似乎是个悖论。所以一开始我们需要找一个稍显笨拙的策略，事实上在没有什么其他手段的时候我只能安排两个智障玩家对弈，就是说它们只会在合法的步骤里面随便选一种来行动，直到游戏结束。听起来很笨是不？还有第四个思路是虽然我有两个智障玩家帮我模拟对弈，但是它们虽然笨但是知道总结，当它下某一步赢了之后下次碰到这种一样的局面它会比较倾向于下同一步。这里会涉及一对矛盾，即使说如果我第一步走步骤1最后赢了，下次又走1也赢了，最后发现1的胜率不错这个智障玩家就会不停走这一步，其他步骤其实可能胜率更加高但是因为被探索的太少，因为偶尔多输了几次就被认为是较差的步骤。但是如果我们把每一步都试玩很多很多次，也不太好，因为会在真正的差的步骤里面消耗太多的算力，像围棋这种每一着都有上百种情况的游戏来说这么做更加不现实。第五个思路是我们需要找到一个策略来平衡前面说的矛盾，对胜率高的步骤我们要多探索，对于探索次数太少的也要增加探索的欲望。有了这个举措，我们的核心算法基本就布置完成了，在视觉上表现为一棵完整的博弈树只被有选择的探索了，有些分支被探索的多，有些被探索了数次之后因为老是导致输掉，就会减少探索的频率。这么做的目的就是保证了大部分的算力被用来搜索高胜率的步骤，同时一定程度上抑制了因为随机模拟带来的偶然性。

对于上面的这个过程唯一让人不放心的地方在于思路四，我们的MCTS对问题的解读到这里就为止了。而AlphaGo使用的神经网络完成的一件事是什么呢？其实就是用一个训练完成的神经网络帮助思路四里面这个笨拙的玩家，在神经网络对盘面的评估比较可靠的时候，这两个玩家模拟出来的对局质量会比随机行动来的高很多。这相当于大大提高了MCTS搜索时候的质量，相应的Bot的战力也会得到大幅度的提高。

一个小demo

现在我们要做的就是利用上面这些有些笼统的知识来设计一个小Bot,希望它能在碰手的小游戏中击败包括我的小伙伴超哥的人类玩家和zhang88a的Bot。当然很遗憾这个游戏是先手必胜的，而zhang88a的Bot已经把这个游戏穷举完了，所以在对方先手的情况下我是赢不了的。不过我们的Bot即便是后手也能轻松击败人类哦，比如我已经输给它n多次了。

平台依旧是matlab（毕竟只会这东西），主要就四个函数，一个用来跟用户交互的入口函数，一个用来根据盘面判决是结束游戏还是继续游戏的函数，一个指挥Bot行动的函数，一个根据不同的玩家行动更新盘面的函数。主要的部分在于第三个，考虑到这个游戏实在是简单，而且我急于求成，所以当时部署MCTS的时候一切从简，博弈树只向下展开一层。出于能力有限也没有训练用来改善效果的神经网络。

附上两张先后手被花式暴捶的羞耻画面。

有些人可能会觉得整个算法其实没有那么玄乎，确实这个算法对我来说是个非常朴实的东西，但是它的效果依旧让我眼前一亮，以至于我觉得单纯的利用它和i5的处理器就能胜任一些更加复杂的游戏，比如说五子棋。

最后

最后也没啥好说的了，要不就感谢一下zhang88a的合作？