第三部分 游戏与推理：开发具有更接近人类水平的学习和推理能力的机器

09 学会玩游戏，智能究竟从何而来从

深度Q学习，从更好的猜测中学习猜测

DeepMind团队将强化学习，尤其是Q学习，与DNN相结合，创建了一个能够学习玩雅达利电子游戏的系统。该小组把他们的方法称作深度Q学习（deep Q-learning）。
深度Q学习是用ConvNets来替代Q表。按照DeepMind的说法，这个网络称为深度Q网络（deep Q-network, DQN）。

• DQN的输入是系统在某个给定时间的状态，此处被定义为当前的帧（当前屏幕的图像）加上之前的三帧（前三个时步的屏幕图像）。
• 给定输入状态，网络的输出是每个可能操作的估计值。可能的操作包括：向左移动球拍、向右移动球拍，以及无操作，即不移动球拍。
• 在每次迭代中系统将其状态输入DQN，并根据DQN的输出值选择一个动作。系统并不总是选择具有最高估计值的动作，强化学习需要在探索与坚持之间取得一个平衡。

• 系统执行其选择的动作，例如，将球拍向左移动一定距离，如果球碰巧击中其中一块砖，则可能会获得一次奖励。然后系统执行一个学习步骤，即通过反向传播更新DQN中的权重。

  
  用于《打砖块》游戏的深度Q网络示意图
  • 在强化学习中我们没有标签。一个来自游戏的给定的帧并不带有指示系统应采取某种动作的标签。在这种情况下，我们如何计算输出的误差呢？
  • 答案如下。回想一下，如果你是那个学习智能体，当前状态下某个动作的值是对你在选择某一动作并持续选择高价值动作的条件下，本片段结束后你将获得多少奖励的估计，那么，越接近这一片段的结尾，估值就越准确，因为在一个片段的结尾处，你能计算出你将获得的实际奖励！其中的诀窍是假设网络在当前迭代的输出比上一次迭代的输出更接近于正确值，然后，通过反向传播学习调整网络权重，从而使得当前与先前迭代输出之间的差异最小化。理查德·萨顿是这种方法的鼻祖之一，他把该方法称为：从猜测中学习猜测。我把它修改为：从更好的猜测中学习猜测。
  • 简而言之，强化学习不是将其输出与人类给定的标签进行匹配，而是假设后续迭代给出的值比前面迭代给出的值更好，网络学习的是使其输出在一次迭代到下一次迭代的过程中保持一致。这种学习方法被称为时序差分学习（temporal difference learning）。
  • 系统将其当前状态作为深度Q网络的输入，深度Q网络为每个可能的动作输出一个值，系统选择并执行一个动作，产生一个新的状态。然后，学习开始了：系统将其新状态输入网络，网络为每个动作输出一组新值。新值集与原值集之间的差异被认为是网络的“误差”，这个误差再经过反向传播来改变网络的权重。这些步骤在许多片段（游戏回合）中重复执行。

价值6.5亿美元的智能体

DeepMind的深度Q学习程序在超过一半的游戏中表现得比人类测试员更好，而且，在那些深度Q学习表现更好的游戏的一半中，程序的表现比人类的表现好2倍以上。在那些深度Q学习比人类表现好2倍以上的游戏的一半中，程序的表现比人类的表现要好5倍以上。令人惊诧的是，在《打砖块》中，深度Q网络程序的平均得分是人类的10倍以上。

西洋跳棋和国际象棋

塞缪尔的西洋跳棋程序是最早的机器学习程序之一，事实上，正是塞缪尔发明了“机器学习”这个词。
塞缪尔的西洋跳棋程序是基于搜索博弈树（game tree）的方法，该方法是迄今为止所有棋类游戏程序的基础，包括我在后面将要描述的AlphaGo。
按照惯例，博弈树的“根”应绘制在顶部，这与自然界中树的根不同，其展示了玩家行棋之前的初始棋盘。从根节点延伸出的分支指向第一个玩家（此处为黑子）所有可能的行棋方式，这里有7种可能的行棋方式，为简单起见，图9-4仅展示其中的3种。对于黑子这7种行棋方式中的每一种，白子都有7种可能的对应行棋方式（图中没有全部列出），以此类推。图9-4中每个棋盘展示了一种可能的棋子排列，被称为一盘棋局。

西洋跳棋的博弈树的一部分
一台高速计算机，则能在一个大得多的范围内执行这种前瞻。那为什么计算机无法对每一种可能进行分析，来判断如何行棋会最快地走向胜利？
西洋跳棋游戏的平均步数约为50步，这意味着图9-4中的博弈树可能会向下延伸50层，在每一层中，每个可能出现的棋局平均对应有6或7个分支，这意味着树中棋局的总数可能超过6⁵⁰，这是一个极其庞大的数字。假设有一台每秒可以计算10¹²个棋局的计算机，它将需要花费超过10¹⁹年才能分析完单个博弈树中的所有棋局。我们可以将这个数字与宇宙的年龄进行比较，后者的数量级仅为10¹⁰。显然，对博弈树进行完全搜索是不可行的。
幸运的是，即使计算机不做这种详尽的搜索，也有可能表现得很好。在每一回合中，塞缪尔的西洋跳棋游戏程序会在计算机的内存中创建如图9-4所示的那样一棵博弈树的一小部分。博弈树的根是玩家当前的棋局，而程序会利用其内置的跳棋规则，从当前的棋局中生成它能采取的所有合规的行棋方式，然后，在每种行棋方式对应的棋局上，程序再生成对手可能选择的所有合规的行棋方式，以此类推，这种程序最多可以做出4～5回合（或“层”）的前瞻。塞缪尔的程序使用了可变数量的层，具体选择哪种，取决于行棋动作。
该程序随后会对前瞻过程结束后出现的棋局进行评估。评估一个棋局意味着为其分配一个用于评价该棋局将有多大可能性会使得程序走向胜利的数值。塞缪尔的程序使用了能给棋局的各种特征进行评分的评估函数，如黑子在总数上的优势、黑子的国王数量、黑子中接近于“成为国王”的棋子数，总分是38分。这些特征是塞缪尔基于他对西洋跳棋的了解来选择的。一旦完成对底层每个棋局的评估，也就是前瞻过程结束后，程序就会使用一个被称为“极小化极大”（minimax）的经典算法，来对程序从当前棋局走出的下一步棋的所有可能性进行评估，然后选择其中评分最高的行棋方式。
我们应该很容易想到：当评估函数被用在游戏后期的棋局上时，评估会变得更加精准，因此，塞缪尔的程序的策略是：首先看到所有可能的行棋序列中的未来几步，然后将评估函数应用于几步后产生的棋局，再将获得的评估值通过极小化极大算法反向传播回博弈树的顶端，从而生成对当前棋局下所有可能行棋方式的评分。
该程序需要掌握的是：在给定的一个回合中，哪些棋局特征应该被包含在评估函数内，以及如何对这些特征进行加权来算出总分数。塞缪尔在他的系统中试验了几种学习方法，其中有个版本最有趣，系统会自己边玩边学！这种学习方法有点复杂，我就不在这里详述了，但其中的一些方面有着现代强化学习的影子。
尽管塞缪尔的西洋跳棋程序是人工智能历史上的一个重要里程碑，但我在这里讲述这段历史只是为了介绍其所包含的三个非常重要的概念：博弈树、评估函数和“自对弈学习”（learning by self-play）。

不智能的“智能赢家”深蓝

尽管塞缪尔的“棘手但可以被击败”的跳棋程序是了不起的，特别是在它那个时代，但它几乎没有动摇人们认为这种程序并不具备独特智能的想法。即便一台机器最终在1994年战胜了人类跳棋冠军，精通跳棋游戏的机器也从未被视为通用人工智能的代表，但这在国际象棋中则不同了。用哈萨比斯的话来说：“几十年来，顶尖的计算机科学家都相信，因为国际象棋被看作人类智力的典型印证，所以一个精通国际象棋的计算机游戏程序将会很快在其他方面全面超越人类。”包括艾伦·纽厄尔和赫伯特·西蒙这两位人工智能早期的开拓者在内的许多人，都曾公开表示过对国际象棋的赞扬。1958年，他们写道：“如果有人能够设计出成功的国际象棋机器，他可能已经触碰到了人类智力的核心。”
国际象棋比西洋跳棋明显要复杂得多。举个例子，在上文中我说过，在跳棋中，任何一个给定的棋局都有平均6种或7种可能的行棋方式。相比之下，国际象棋中任何一个给定的棋局平均有35种行棋方式，这使得国际象棋的博弈树要比跳棋巨大得多。几十年来，国际象棋程序一直在改进，与计算机硬件速度的提升保持步调一致。1997年，IBM凭借深蓝，在一个被广泛播出的电视节目中击败了国际象棋世界冠军加里·卡斯帕罗夫，获得了其在游戏比赛领域的第二个重大胜利。
深蓝使用了与塞缪尔的跳棋程序几乎相同的方法：在一个给定的回合中，以当前棋局为根创建部分博弈树，将评估函数应用于博弈树的最底层，然后使用极小化极大算法将值沿树向上传播并决定应该走哪步棋。塞缪尔的程序与深蓝之间的主要区别在于：深蓝在其博弈树中具有更深入的前瞻，更复杂的特别针对国际象棋的评估函数、手动编程的国际象棋知识，以及能够使其高速运行的专用并行硬件。此外，与塞缪尔的跳棋游戏程序不同，深蓝没有在任何核心部件上使用机器学习方法。
现在，人们通常认为，超人类的国际象棋游戏程序并不需要通用智能，而且从任何意义上来说，深蓝都不智能：除了下象棋之外，它什么都做不了，对于玩一局游戏且赢得这局游戏的意义，它也没有任何概念。我曾听一位演讲者打趣道：“深蓝确实打败了卡斯帕罗夫，但它从未从中获得任何乐趣。”
国际象棋作为一项具有挑战性的人类活动，有着相当长的历史，并且相当受欢迎。如今，国际象棋程序已经被人类棋手当作一种辅助训练工具，就像棒球运动员使用投球机进行练习一样。这是我们不断深化对智能这一概念的理解所产生的一个结果吗？并且得益于人工智能的进步，使我们更加确信这一点？还是说这只是印证了约翰·麦卡锡那句格言，“一旦它开始奏效，就没人再称它为人工智能了”？

围棋，规则简单却能产生无穷的复杂性

围棋已有两千多年的历史，被公认为所有棋类游戏中最难的。
深蓝能够从任一棋局开始进行大量前瞻，然后使用其评估函数来给未来的每一步棋分配一个值，这个值预示了一个特定棋局是否将获胜。然而，围棋程序无法使用这一策略，主要原因有如下两个。

• 首先，围棋的博弈树的规模要比国际象棋大得多。一个国际象棋棋手在一个给定棋局中平均有35种可能的行棋方式，而一个围棋棋手平均有250种这样的行棋方式。因此，即便使用专用的硬件，对围棋的博弈树进行“深蓝式”的暴力搜索也是不可行的。
• 其次，还没有人能够为围棋棋局创建一个良好的评估函数。也就是说，没有人有能力构建一个有效的公式来分析围棋中的一个棋局局势并预测哪一方将获胜。最优秀的人类围棋棋手依赖于他们对于局势的掌控以及难以言喻的直觉。人工智能研究人员尚未弄清楚如何将直觉编码到一个评估函数中。

AlphaGo对战李世石：精妙，精妙，精妙

AlphaGo的胜利甚至比深蓝的胜利意义更重大：人工智能克服了比国际象棋更大的挑战，而且是以一种令人印象更加深刻的方式完成的。与深蓝不同的是，AlphaGo通过自对弈的强化学习方法来提升它的能力。
哈萨比斯指出：“顶级围棋棋手区别于常人的东西是他们的直觉，我们在AlphaGo中所做的就是将这种所谓的直觉引入神经网络中。”

从随机选择到倾向选择，AlphaGo这样工作

现在已经有多个不同版本的AlphaGo了，为了区分它们，DeepMind开始以它们击败的人类围棋冠军的名字来给程序命名，比如AlphaGo Fan和AlphaGo Lee。AlphaGo Fan和AlphaGo Lee都使用了深度Q学习、“蒙特卡洛树搜索”（Monte Carlo tree search）、监督学习等方法与围棋专业知识进行融合。
在AlphaGo战胜李世石一年之后，DeepMind开发了一个新版本的程序，比AlphaGo更简单也更高级，这个新版本被称为AlphaGo Zero。与之前的版本不同的是：除了围棋规则之外，AlphaGo Zero对围棋的知识是从“零”开始的。在AlphaGo Lee与AlphaGo Zero的100场对弈中，AlphaGo Zero取得了完胜。此外，DeepMind采用了同样的方法（尽管具有不同的网络和不同的内置游戏规则）来让程序学习下国际象棋和将棋（也称为日本象棋），其作者将这些方法的集合称为AlphaZero。接下来，我将描述AlphaGo Zero的工作原理，但为简单起见，我将此版本简称为AlphaGo。
“直觉”这个词有一种神秘的光环，如果你觉得AlphaGo也有直觉，那么这种直觉源自它对深度Q学习和蒙特卡洛树搜索这些方法的巧妙结合。在科学和数学领域，蒙特卡洛指的是一系列计算机算法，即所谓的“蒙特卡洛方法”（Monte Carlo method），这一方法最初用在曼哈顿计划中来帮助设计原子弹。这个名字来源于一个想法：就像蒙特卡洛赌场那标志性的快速旋转的轮盘一样，一定程度的随机性可被用在计算机上来解决复杂的数学问题。
蒙特卡洛树搜索是专门为计算机游戏程序设计的蒙特卡洛方法的一个版本。与深蓝的评估函数的工作原理类似，蒙特卡洛树搜索用于为一个给定棋局的每一种可能的行棋方式来分配分数。可是，正如我在上面所解释的那样，在博弈树中使用大量的前瞻操作对围棋来说是不可行的，并且还没有人能为围棋中的棋局提出一个良好的评估函数。因此，蒙特卡洛树搜索的工作原理肯定有所不同。
如果黑子有足够多的时间，它可以对博弈树进行一次全面的搜索：前瞻所有的可能序列，然后选择一种最有可能令黑子获胜的行棋方式。可是，进行这样详尽的前瞻是不可行的，正如我之前提到的：即使是使用自宇宙诞生至今这么长的时间，都不够在围棋中进行一次完整的搜索。使用蒙特卡洛树搜索，黑子只前瞻每一种行棋方式可能产生的棋局序列中极小的一部分，并对这些棋局序列的输赢次数进行统计，然后，根据这个结果来为每种可能的行棋方式打分。受轮盘赌启发的随机性被用来决定如何前瞻。
AlphaGo在应用蒙特卡洛树搜索时就不用通过查看棋局局势来猜测哪种行棋方式最可能通往胜利，而只根据走子演算收集的关于给定行棋方式最终指向胜利或失败的统计数据，来判断下一步的最佳行棋策略。程序执行的走子演算越多，其统计数据就越有参考价值。和之前一样，该程序需要平衡“效用”（在走子演算期间选择得分最高的行棋方式）和“探索”（偶尔选择程序尚未有太多统计数据的得分较低的行棋方式）。AlphaGo的蒙特卡洛树搜索在每轮中会执行近2 000次走子演算。
从走子演算中生成足够多的统计数据需要花费大量时间，特别是对于存在大量可能行棋方式的围棋来说，更是如此。DeepMind团队意识到他们或许可以使用一个深度卷积神经网络来对蒙特卡洛树搜索进行补充，以提升它们的系统能力。以当前棋局作为输入，AlphaGo使用一个训练过的ConvNets来为当前棋局中所有可能的行棋方式分配一个粗略值，然后蒙特卡洛树搜索使用这些值来启动它的搜索，也就是说蒙特卡洛树搜索不用再随机选择初始行棋方式，而是根据ConvNets的输出值来判断哪一初始行棋方式是最优的。想象一下，你是正在注视着一个棋局的AlphaGo，在你开始为当前棋局执行蒙特卡洛树搜索的走子演算时，ConvNets会在你的耳边悄悄告诉你，当前棋局中的哪一步走法是最好的。
反过来，蒙特卡洛树搜索的结果又能反馈到对该ConvNets的训练中。设想一个经过一次蒙特卡洛树搜索的AlphaGo，搜索的结果是分配给它的所有可能行棋方式的新概率——基于执行走子演算期间所有可能行棋方式导致胜利或失败的概率，这些新概率现在通过反向传播来校正ConvNets的输出。随着对弈的进行，会产生一个又一个新的棋局，然后上述过程不断重复。从原则上说，ConvNets将会通过这一学习过程学会辨识局势，就像围棋大师一样。最终，ConvNets将在AlphaGo中发挥直觉的作用，这种直觉的实际效果会进一步被蒙特卡洛树搜索改进。

《AI 3.0》读书笔记
《AI 3.0》读书笔记 序1
《AI 3.0》读书笔记 序2
《AI 3.0》读书笔记 序3
《AI 3.0》读书笔记 译者序
《AI 3.0》读书笔记 第一部分 若想对未来下注，先要厘清人工智能为何仍然无法超越人类智能01
《AI 3.0》读书笔记 第一部分 若想对未来下注，先要厘清人工智能为何仍然无法超越人类智能02
《AI 3.0》读书笔记 第一部分 若想对未来下注，先要厘清人工智能为何仍然无法超越人类智能03
《AI 3.0》读书笔记 第二部分 视觉识别：始终是“看”起来容易“做”起来难 04 何人，何物，何时，何地，为何
《Ai 3.0》读书笔记 第二部分 视觉识别：始终是“看”起来容易“做”起来难 05 ConvNets和ImageNet，现代人工智能的基石
《AI 3.0》读书笔记 第二部分 视觉识别：始终是“看”起来容易“做”起来难 06　难以避免的长尾效应
《AI 3.0》读书笔记 第二部分 视觉识别：始终是“看”起来容易“做”起来难 07 确保价值观一致，构建值得信赖、有道德的人工智能
《AI 3.0》第三部分 游戏与推理：开发具有更接近人类水平的学习和推理能力的机器
《AI 3.0》第三部分 08 强化学习，最重要的是学会给机器人奖励