蒙特卡洛树搜索MCTS

AlphaGo Zero跟AlphaGo的最大区别是抛弃人类棋谱的，完全通过自我对弈来学会下棋的，并且仅用40小时就到达了AlphaGo的棋力。

过程是这样，首先生成棋谱，然后将棋谱作为输入训练神经网络，训练好的神经网络用来预测落子和胜率。如下图：

在AlphaGo Zero中蒙特卡洛树搜索主要是用来生成棋谱的

MCTS算法是一种决策算法，每次模拟（simulation）分为4步：

第一、二步的流程（遍历、拓展节点）：

1.从状态S0开始，要在下面两个动作中进行选择（假设只有两个动作可选），选择的标准就是 值， 选择最大化 UCT 的节点作为下一个节点 。初始情况两个 ,按顺序选择S1

2.判断目前的结点S1(current node)是不是叶节点，这里叶节点是指其没有被展开（expansion）过。

3.接下来，按照流程图，需要判断结点S1被访问的系数是否为0。是0，则要进行Rollout。(Rollout其实就是在接下来的步骤中每一步都随机采取动作，直到停止点（围棋中的对局结束），得到一个最终的value。)==>假设Rollout最终值为20.

4.Backpropagation，即利用Rollout最终得到的value来更新路径上每个结点的T,N值。(之后把Rollout的结果删除：MCTS的想法就是要从出S0发不断的进行迭代，不断更新结点值，直到达到一定的迭代次数或者时间。)

5.如果没有达到一定的迭代次数或者时间，继续从根节点进行1-4

第三步rollout模拟:

例子说明见: 蒙特卡洛树搜索（MCTS）算法-计算过程 ，视频讲解见B站: 【MCTS】Youtube上迄今为止最好的蒙特卡罗树搜索讲解

相比极大极小法（minimax）。这个策略假定你的对手发挥了最好的博弈水平，然后以此调整策略来最大化你的收益。简单地说，给定状态，你想要找到一个能产生最大收益的 move ，假定你的对手想要最小化你的收益（最大化他自己的收益）。因此，名字叫作 极小化极大 。

极小化极大算法的最大劣势 是，需要扩展整个博弈树。对于分支因子较高的博弈（例如围棋或者国际象棋），这会导致庞大的博弈树从而失败。

UCT是一个让我们从已访问的节点中选择下一个节点来进行遍历的函数，也是MCTS的核心函数。

第一部分是 ​ ，也称作exploitation component

可以看做是子节点Vi的胜率估计（总收益/总次数=平均每次的收益）。但是不能只选择胜率高的下一步，因为这种贪婪方式的搜索会很快导致游戏结束，这往往会导致搜索不充分，错过最优解。

举个简单的例子。现在假设MCTS的UCT函数只用了探索成分，从根节点开始，我们对所有子节点进行了一次模拟，然后在下一步中只访问至少赢了一次的子节点。那么在第一次模拟中那些不幸未被选中的节点（实际中rollout策略函数通常是随机的）将会被立刻抛弃

，这个成分更倾向于那些想对较少被探索的节点N(Vi)小。

参数c是exploitation和exploration之间的折中系数。

终止条件(or)：

当MSCT程序结束时，最佳的移动通常是访问次数最多的那个节点，也是UCT最大的点。

深度学习入门：AlphaGo Zero蒙特卡洛树搜索

蒙特卡洛树搜索（MCTS）算法-计算过程

【MCTS】Youtube上迄今为止最好的蒙特卡罗树搜索讲解

python实现的基于蒙特卡洛树搜索(MCTS)与UCB的五子棋游戏

mctspy：蒙特卡洛树搜索算法的python实现

1、MCTS认证均只有一科考试科目，只要通过该科考试，即可取得MCTS资格，但开发技术的MCTS要求考生必须要先通过70-536:TS:Microsoft .NET FrameworkApplication Development Foundation，才可以拥有以通过一科考试的方式取得开发技术的MCTS认证的资格。参考资料主要以微软公司的TrainingKit系列和MOC系列，还有Sybex的学习指南为主，以易证宝资料最为考前强化练习。

2、mcts翻译过来就是微软认证技术专家，是微软认证体系中最基础的证书，其证书的等级相当于以前的MCP认证，并做为MCP认证的后继证书，持有MCTS代表对微软某个技术或某个产品具有充分的技术能力，可以执行搭建和管理(针对网管或系统管理人员) 或程序撰写能力(针对开发人员)。

3、报考条件：

学历：报考MCTS不限制考生的文凭，任何人都可以报考

能力：基本的计算机应用能力，微软公司建议考生最好相应的软件使用和技术应用的经验

应用方向：

方向：从系统管理，网络管理，应用开发到数据库都有

职位：企业（组织）IT管理、技术员，工程师助理

能力：具体的单项技术或者产品的基本应用技能，系统以及网络

?2016年，“阿尔法围棋”在围棋人机大战中击败了韩国九段棋手、世界冠军李世石，引发巨大关注。在今年的政府工作报告中提到，加强新一代人工智能研发应用，在医疗、养老、教育、文化、体育等多领域推进“互联网＋”。发展智能产业，拓展智能生活，运用新技术、新业态、新模式，大力改造提升传统产业。那么人工智能是否可以应用在化学领域，实现部分化学工作的自动化呢？最近，Segler等人在Nature上发表研究工作，展示了他们设计的软件程序在有机合成中的神奇应用，文章DOI: 10.1038/nature25978。同时，Nature发文对此进行了点评，文章DOI: 10.1038/d41586-018-03774-5。随着人工智能的发展，人类不禁感慨，人工智能的发展是否会让部分化学工作者失业呢？

人工智能会让化学家失业吗？人工智能会让化学家失业吗？

Scheme 1. 逆合成分析举例

合成化学是从简单的分子构建目标化合物的过程，是化学学科的重要分支，长期以来，合成化学家的理论知识和经验被认为是成功构建分子的关键。在上个世纪60年代，有机合成大师E. J. Corey提出了“逆合成分析”的概念，并因此获得1990年的诺贝尔化学奖。合成化学家在考虑分子合成时，都会使用“逆合成分析”的方法，思考一系列问题（Scheme 1），比如：

1）该分子的前体结构是什么，该由什么样的最初原料构建？

2）每一步的产率怎么样？

3）每一步的 *** 作可行性如何？

然而，这一切真的只有人类才能完成吗？在查询每一步反应时，通常化学家会通过网络数据库如Scifinder或Reaxys等检索，那么是否可以设计一个程序，往其中植入足够多化学反应的数据库，让程序来设计合成路线呢？自上个世纪60年代起，人类一直都在设法寻找这样的程序，然而该研究很难取得成功。

有两个最基本的因素，阻碍了该研究的成功。首先，电脑硬件无法应对这样的挑战；其次，软件程序无法完全理解化学文献的复杂性。有机化学反应是极为复杂的，比如对某个特定反应，只有当Z基团不存在时，X基团可以顺利地转化为Y基团；但当Z基团存在时，也可以通过改变温度、酸碱度、溶剂等条件实现相应的转化。这样复杂的过程，是软件程序难于理解的。

针对第二个问题，人类已经开发了许多不同的解决方法。一种方法是往程序中植入足够多的化学反应，包括反应的局限性和条件限制。这样的程序往往会产生很多类似的合成路线，对这些路线进行评估便可以产生最合理的路线。目前这样的思路已经取得了一定的成功，并且产生了具有一定竞争力的软件产品。

Segler等人采用了另一种方法，他们考虑不把研究者的经验注入电脑，而让程序自己学习设计路线。事实上，程序存贮和记忆的容量比人脑要大得多，能提供的可能性也更多。目前，这样的研究已经产生了惊人的效果。

在该工作中，作者设计了一个电脑程序，可以自主地从一个大的数据库中学习化学反应，并进行细致地筛选。并且，它只会筛选已经被多次成功应用的反应。当程序被要求设计合成路线时，它可以像人类一样进行逆合成分析，根据自己掌握的知识制定出最有希望的合成前体，并对合成路线的可行性进行分析。作者将三个人工神经网络和一个随机Monte Carlo tree search结合起来（作者称之为3N-MCTS），用来产生最有希望的合成路线。

比如对如下药物候选分子的合成，在过去的报道中需要如下六步合成路线（Asian J. Chem. 2015, 27, 2117-2124）。令人惊讶的是，作者利用他们开发的计算程序可以在5.4 s内发现该合成路线。

人工智能会让化学家失业吗？

Scheme 2. 软件程序设计的逆合成分析

值得一提的是，程序设计的合成路线不仅可以接受程序评分系统的考核，也可以接受训练有素的合成化学家的双盲实验审查。研究发现，对于test a, 化学家对于文献报道的路线和 3N-MCTS设计的路线没有明显的倾向性（Scheme 3a）；对于test b, 相对没有知规矩制约的heuristic BFS程序，化学家高度倾向于3N-MCTS程序设计的合成路线（Scheme 3b）。对于test a 的task 1, MCTS 提供的路线是通过Ohira-Bestmann试剂发生Seyferth-Gilbert 增碳反应，而化学家倾向于选择经由Grignard反应的合成路线。尽管MCTS 路线在理论上是可能的，但在 *** 作上不太方便。但接下来构建环系的方法则是一致的（Scheme 3c）。而对于test b，由于没有规矩的制约和范围的限制，heuristic BFS 产生了在逆合成分析中备受指责的错误（Scheme 3d）。因此，总体来说3N-MCTS产生的合成路线是较为合理的。

人工智能会让化学家失业吗？

Scheme 3. MCTS产生的路线与文献报道的路线、BFS产生的路线进行双盲实验比较

然而，这并不意味着程序给出的所有路线都是合理的，但化学家设计的合成路线也并不都是可行的。小编曾听不少学生抱怨，导师设计的合成路线是行不通的。因此，Segler等人报道的机器提出的路线不比人类提出的路线差，已经历史性地突破了。机器可以在短时间内分析众多的文献，在最短时间内提出可行的合成方案，这远远不是人类能比的。

那么人类不仅设想，如果人工智能继续发展下去，是否有一天会对合成化学家的工作岗位构成威胁呢？尽管软件无法处理特别复杂的、不常见的结构，但一些常规的合成问题会渐渐被AI取代。

总结：人工智能的发展，对很多化学家的工作岗位构成了威胁。然而，人工智能确实可以帮助化学家避免了许多重复的工作，让化学家把更多的精力放在思考高质量的问题上，比如该合成怎么样的分子、为什么要合成该分子，而不是把精力放在合成的具体细节上。目前来说，并不是所有化学家都能接受这一转变，然而历史的车轮滚滚向前，它不会随任何人的意志而改变，人工智能改变化学发展的日子终究要来。...

---