五局三胜，奖金100万美元 - 一场高风险的决战。 2016年3月9日至15日，排名第二的围棋手Lee Sidol接手了名为AlphaGo的计算机程序。
AlphaGo决定性击败了Sidol并超越了4-1系列赛。该计划由谷歌的DeepMind设计，催生了人工智能的许多其他发展，包括AlphaGo Zero。这些突破被广泛认为是人工智能（AGI）的垫脚石。
在本文中，我将向您介绍AlphaGo中心的算法 - 蒙特卡罗树搜索（MCTS）。该算法有一个主要目的 - 给定游戏状态，选择最有希望的移动。
为了给你一些AlphaGo背后的背景，我们首先简要介绍一下游戏AI程序的历史。然后，我们将看到AlphaGo的组件，游戏树概念，一些树搜索算法，最后深入研究MCTS算法的工作原理。
目录
游戏AI - 摘要
AlphaGo计划的组成部分
游戏树概念
树搜索算法
1.不知情的搜索
2.最佳搜索
3. Minimax
蒙特卡洛树搜索
1.树遍历和节点扩展
一个。 UCB1（上置信区）
湾推出
2.通过示例完成演练
游戏AI - 摘要
人工智能是一个庞大而复杂的领域。但在人工智能正式成为公认的工作机构之前，计算机科学的早期开拓者编写了游戏程序，以测试计算机是否可以解决人类智能水平任务
为了让您了解游戏人工智能从何处开始以及到目前为止的旅程，我将以下主要历史发展放在一起：
A. S. Douglas编写了第一个在1952年成功掌握游戏的软件。游戏？井字棋！这是他在剑桥大学博士论文的一部分
几年后，亚瑟·塞缪尔（Arthur Samuel）是第一个使用强化学习的人，通过与自己对抗来玩Checkers
1992年，Gerald Tesauro设计了一个名为TD-Gammon的现在流行的节目，在世界级的水平上玩步步高
几十年来，国际象棋被视为“人工智能的最终挑战”。 IBM的Deep Blue是第一款展示超人国际象棋功能的软件。该系统在1997年击败了国际象棋大卫加里卡斯帕罗夫（Garry Kasparov）
最受欢迎的棋盘游戏AI里程碑之一是在2016年的Go游戏中达成的。 9-dan职业围棋选手Lee Sedol在与谷歌DeepMind的AlphaGo软件比赛中输掉了五场比赛，该比赛采用深度强化学习方法
值得注意的最近视频游戏AI的里程碑包括由Google DeepMind开发的算法，用于以超人类技能水平从经典的Atari 2600视频游戏机上玩几款游戏
去年，OpenAI构建了流行的OpenAI Five系统，该系统掌握了DOTA的复杂策略游戏
而这只是略读表面！还有很多其他AI程序超出预期的例子。但这应该让你对我们今天的立场有一个很好的了解。
AlphaGo的组件
Alpha Go的核心部分包括：
蒙特卡洛树搜索：AI使用MCTS选择下一步行动
残留CNN（卷积神经网络）：AI使用这些网络评估新位置
强化学习：通过使用当前最佳代理来对抗自身来训练AI
在本博客中，我们将仅关注蒙特卡罗树搜索的工作。这有助于AlphaGo和AlphaGo Zero在有限的时间段内巧妙地探索并达到有趣/良好状态，从而帮助AI达到人类水平的性能。
它的应用程序超越了游戏。从理论上讲，MCTS可以应用于任何可以用{状态，动作}对和用于预测结果的模拟来描述的域。不要担心，如果现在听起来太复杂，我们将在本文中细分所有这些概念。
游戏树概念
游戏树是可以代表游戏的最知名的数据结构。这个概念实际上非常简单。
游戏树的每个节点代表游戏中的特定状态。在执行移动时，会从节点转换到其子节点。命名法与决策树非常相似，其中终端节点被称为叶节点。
例如，在上面的树中，每次移动相当于将十字架放在不同的位置。这分支到各种其他状态，其中在每个位置放置零以产生新状态。此过程一直持续到达到叶节点，其中胜负结果变得清晰。
树搜索算法
我们设计这些算法背后的主要目标是找到最佳路径以赢得游戏。换句话说，查找/搜索遍历树的方法，该树找到获得胜利的最佳节点。
大多数AI问题可以被视为搜索问题，可以通过找到最佳计划，路径，模型或功能来解决。
树搜索算法可以看作是构建搜索树：
根是表示搜索开始的状态的节点
边缘表示代理从一个状态转到另一个状态所采取的操作
节点代表状态
树分支出来，因为通常可以在给定状态下采取几种不同的动作。树搜索算法根据探索的分支和顺序而不同。
我们来讨论一些树搜索算法。
不知情的搜索
顾名思义，不知情的搜索算法搜索状态空间而没有关于目标的任何进一步信息。这些被认为是基本的计算机科学算法，而不是AI的一部分。属于此类搜索的两种基本算法是深度优先搜索（DFS）和广度优先搜索（BFS）。您可以在此博客文章中阅读有关它们的更多信息。
最佳搜索
最佳优先搜索（BFS）方法通过扩展根据特定规则选择的最有希望的节点来探索图。这种搜索的定义特征是，与DFS或BFS（盲目检查/扩展单元格而不知道任何内容）不同，BFS使用评估函数（有时称为“启发式”）来确定哪个节点最有希望，然后检查此节点。
例如，A *算法保留了一个“开放”节点的列表，这些节点位于一个被探索的节点旁边。请注意，尚未探索这些开放节点。对于每个开放节点，估计其距目标的距离。选择新节点以基于最低成本基础进行探索，其中成本是距原始节点的距离加上到目标的距离的估计。
极小
对于单人游戏，可以使用简单的不知情或知情搜索算法来找到最佳游戏状态的路径。对于有其他玩家需要考虑的双人对抗游戏，我们该怎么做？两个球员的行动都相互依赖。
对于这些游戏，我们依靠对抗性搜索。这包括两个（或更多）对抗性玩家的行为。基本的对抗
性搜索算法称为Minimax。
该算法已成功用于播放经典的完美信息双人棋盘游戏，如Checkers和Chess。事实上，它是（重新）发明的，专门用于建立国际象棋游戏计划。
Minimax算法的核心循环在玩家1和玩家2之间交替，非常像国际象棋中的白人和黑人玩家。这些被称为最小玩家和最大玩家。为每个玩家探索所有可能的动作。
对于每个结果状态，还探索了其他玩家的所有可能移动。这种情况一直持续到所有可能的移动组合都已经尝试到游戏结束的程度（获胜，失败或平局）。整个游戏树是通过这个过程生成的，从根节点到叶子：
探索每个节点以找到给出最大值或分数的移动。
蒙特卡洛树搜索
像tic-tac-toe，checkers和chess这样的游戏可以使用minimax算法来解决。但是，当每个州都有大量潜在的行动时，事情会变得有点棘手。这是因为minimax探索了所有可用的节点。在有限的时间内解决像Go这样的复杂游戏会变得非常困难。
Go具有大约300的分支因子，即，从每个状态可以进行大约300次动作，而国际象棋通常有大约30种动作可供选择。此外，围绕对手的Go的位置性质使得很难正确地估计给定板状态的值。有关Go规则的更多信息，请参阅此链接。
还有其他一些具有复杂规则的游戏，minimax无法解决这些问题。这些包括具有不完全信息的战舰扑克和诸如步步高和垄断的非确定性游戏。 2007年发明的蒙特卡洛树搜索提供了一种可能的解决方案。
基本的MCTS算法很简单：根据模拟播出的结果，逐个节点地构建搜索树。该过程可以分解为以下步骤：
选择
从根节点R开始选择好的子节点，其表示导致更好的总体结果（获胜）的状态。
扩张
如果L不是终端节点（即它不结束游戏），则创建一个或多个子节点并选择一个。
模拟（推出）
从C运行模拟播放，直到达到结果。
反向传播
使用模拟结果更新当前移动序列。
树遍历和节点扩展
在我们深入研究并理解树遍历和节点扩展之前，让我们熟悉一些术语。
UCB价值
UCB1或节点的置信上限由以下公式给出：
见链接中的插图
哪里，
Vi是此节点下所有节点的平均奖励/值
N是父节点被访问的次数，和
ni是子节点i被访问的次数
推出
首次展示是什么意思？在我们到达叶节点之前，我们会在每个步骤中随机选择一个动作并模拟此动作以在游戏结束时获得平均奖励。
循环永远：
如果Si是终端状态：
返回值（Si）
Ai =随机（available_actions（Si））
Si =模拟（Si，Ai）
此循环将一直运行，直到达到终端状态。
蒙特卡罗树搜索的流程图
树遍历和节点扩展
你从S0开始，这是初始状态。如果当前节点不是叶节点，我们计算UCB1的值并选择最大化UCB值的节点。我们一直这样做，直到到达叶节点。
接下来，我们询问此叶节点被采样了多少次。如果之前从未采样过，我们只需进行推广（而不是扩展）。但是，如果之前已对其进行了采样，那么我们会在树中为每个可用操作（我们在此处调用扩展）添加一个新节点（状态）。
您当前的节点现在是这个新创建的节点。然后我们从这一步骤开始推广。
以示例完成演练
让我们对算法进行全面的演练，以真正理解这一概念并以清晰的方式理解它。
迭代1：
我们从初始状态S0开始。在这里，我们有动作a1和a2，它们导致状态s1和s2具有总分t和访问次数n。但是我们如何在2个子节点之间进行选择呢？
初始状态
这是我们计算两个子节点的UCB值并采用哪个节点最大化该值的位置。由于尚未访问任何节点，因此第二项对于两者都是无限的。因此，我们将采取第一个节点
我们现在处于叶节点，我们需要检查是否已访问过它。事实证明，我们没有。在这种情况下，在算法的基础上，我们一直向下滚动到终端状态。假设此卷展栏的值为20
从S1推出
现在是第4阶段，或者是反向传播阶段。叶节点（20）的值一直反向传播到根节点。所以现在，对于节点S1和S0，t = 20并且n = 1
Post Backpropogation
这是第一次迭代的结束
MCTS的工作方式是我们运行它一定数量的迭代或直到我们没有时间。这将告诉我们每一步应采取的最佳行动是什么，以获得最大回报。
迭代2：
我们回到初始状态并询问下一个要访问的子节点。再次，我们计算UCB值，S1为20 + 2 * sqrt（ln（1）/ 1）= 20，S2为无穷大。由于S2具有更高的值，我们将选择该节点
将在S2处完成推出以获得值10，该值将被反向传播到根节点。根节点的值现在为30
来自S2的反向传播
迭代3：
在下图中，S1具有更高的UCB1值，因此应在此处进行扩展：
现在在S1，我们处于与初始状态完全相同的位置，两个节点的UCB1值都是无限的。我们从S3进行部署，最终在叶节点处获得值0
迭代4：
我们再次必须在S1和S2之间做出选择。 S1的UCB值为11.48和S2为12.10：
我们将在S2进行扩展步骤，因为那是我们新的当前节点。在扩展时，创建了2个新节点--S5和S6。由于这些是2个新状态，因此将执行推出直到叶节点获取值并返回反向
这是该算法的要点。只要需要（或计算可能），我们就可以执行更多迭代。基本思想是随着迭代次数的增加，每个节点的值估计变得更加准确。
结束笔记
Deepmind的AlphaGo和AlphaGo Zero程序远比本文范围之外的其他各个方面复杂得多。但是，蒙特卡罗树搜索算法仍然是它的核心。 MCTS在使Go等复杂游戏在有限的时间内更容易破解方面发挥着主要作用。 MCTS的一些开源实现链接如下：
在Python中实现
用C ++实现
我希望强化学习能在2019年取得很大的进展。看到很多复杂的游戏很快被机器破解也就不足为奇了。这是学习强化学习的好时机！
我很乐意在下面的评论部分听到您对本文和此算法的想法和建议。你以前用过这个算法吗？如果没有，你想试试哪个游戏？
最初于2019年1月23日在www.analyticsvidhya.com上发布。