第二部分 我们是怎么走到这一步的 第二章 黄金年代（第3页）

在一个偏僻的寺院里，立着三根柱子，还有64个金环。每一个金环的尺寸都不同，并且金环都可以套在柱子上。最初，所有的金环按照上小下大的顺序，都套在最左边的柱子上，然后，僧侣们要利用这三根柱子，一个一个移动金环。他们的目标是把所有金环都移动到最右边的柱子上，移动的时候，僧侣们必须遵从两个原则：

1。一次只能把一个金环从一根柱子移动到另一根柱子上。

2。任何一个金环都不能位于比它小的金环之上。

要解决这个问题，僧侣们必须找到正确的移动顺序，使得所有的金环从左边柱子移动到右边柱子，并且遵循大金环不能放在小金环之上的规则。

按照传说，当僧侣们完成任务的时候，世界就会毁灭[1]。当然，我们很快就会知道，哪怕这个传说是真的，也无须为此担忧，因为宇宙在僧侣们移动完所有64个金环之前早就灭亡了。所以现实中的汉诺塔只会有极少的金环，如图3所示。

图3　汉诺塔

人工智能黄金年代的经典谜题，图a展示了汉诺塔的初始状态（所有的金环都在最左边的柱子上），图b展示了目标状态（所有的金环都被挪到最右边的柱子上），图c展示了错误的移动状态（大金环放在了小金环上面）。

那么，我们将如何着手解决汉诺塔这样的问题呢？答案是使用一种名叫搜索的技术。在这一点上，我得首先澄清，在人工智能领域使用“搜索”一词时，并非指打开谷歌或者百度对网站进行搜索。人工智能领域的搜索，是一种基本的问题解决技术，它涉及让系统全盘考虑所有进程。任何像下棋一样的程序都是基于搜索技术的，汽车上的卫星导航系统也是。它一次又一次地出现在诸多领域，是人工智能技术的基石之一。

所有类似汉诺塔的问题都有着相通的解决方案。在积木世界里，我们希望能够找到相应的步骤，把初始状态的物体转变为指定的目标状态。“状态”这个术语在人工智能领域指的是某个事物或者问题在某个特定时刻呈现的结构。

用搜索的方式来解决类似汉诺塔的问题，我们可以遵照以下步骤：

·首先，从初始状态开始，我们考虑每个可能的动作对初始状态的影响，执行每一步操作都会将初始状态转换为一个新的状态。

·如果其中某个新状态是我们的目标状态，那就意味着操作成功：这个问题的解决步骤就是从初始状态达到目标状态所执行的操作。

·否则，在每一个新状态上，继续考虑所有可能导致状态变更的操作，重复这样的过程，以此类推。

应用搜索的方法会得到一个树状的结构图，被称为搜索树，图4为我们展示了解决汉诺塔问题的搜索树的一小部分片段。

·最初，我们只能选择移动最小的金环，只有将它移动到中间或者最右边的柱子上。所以对应第一步，我们只有两种移动可能，以及两种不同的新状态。

·如果我们选择将最小的金环移动到中间柱子（初始状态左下方箭头对应的状态），那么我们随后可以执行三种操作：将最小的金环移动到最左侧或者最右侧的柱子，或者将第二个金环移动到最右侧柱子（不能将第二个金环移动到中间柱子，因为它会位于最小金环的上方，这就违背了移动规则）。

·以此类推。

图4　汉诺塔问题搜索树的一小部分片段

因为我们逐级逐级地在生成搜索树，这就意味着我们考虑到了所有的移动可能性，因此，如果这个问题确定是有解决方案的，我们就可以确保使用搜索的方法最终能够找到它（“最终”这个词在句中是至关重要的，至于为什么，很快就会揭晓）。

那么，解决汉诺塔问题需要移动的最少次数是多少呢？也就是说，从初始状态到目标状态，最少需要移动多少次？对于三个金环而言，答案很简单，是7次。你不可能找到少于7次的解决方案了。当然，也有很多方案可以用超过七步的方式解决问题（实际上是有无穷多方案），但它们不是最优的，因为我们想用最少的步骤、在最短的时间内解决问题。现在，考虑到我们所描述的搜索过程是详细无遗漏的——考虑到了每一步搜索树的所有可能性——搜索技术不光能保证寻找到解决方案，也能保证寻找到最优解决方案。

这就意味着，穷举搜索的方式不仅能保证在问题可解的时候寻找到问题的解，还能保证寻找到问题的最优解。另外，作为计算机的算法，穷举搜索非常简单——编写一个程序来实现它非常容易。

不过，哪怕我们只是粗略研究图4所示的片段都能够看出来，如刚才所描述的那样，采用穷举搜索的方式来解决问题是个相当愚蠢的过程。比如，仔细看看搜索树最左边的分支，仅仅移动两步以后，问题又返回到了初始状态，这是在无谓地浪费精力。如果是你来研究解决汉诺塔问题，可能会在寻找解决方案的时候犯一两次类似的错误，不过你会很快发现问题所在，并且学会避免做一些徒劳的移动。然而，一台简单执行穷举搜索的计算机却无法做到：它只能穷举出所有移动下的所有新状态，哪怕某些穷举步骤就是在浪费时间，它也会走回头路，回到已经被确认过失败的状态。

除了太多重复和低效率以外，穷举搜索还有一个根本的问题。如果你做过一些实验，会发现在大部分状态下，汉诺塔问题都有三种移动的可能性，即分支因子为3。不同的问题对应着不同的分支因子。比如，围棋的分支因子为250，这就意味着在游戏给定的任意状态下，每个玩家约有250种落子的可能性，当然，这只是平均值。所以，我们来看看搜索树随着分支因子能增长到多大——对确定了分支因子数的搜索树，在不同层级有多少种状态。以围棋为例[24]：

·搜索树的第一级有250种状态，因为在游戏棋盘的初始状态下，可以有250种新出现的状态。

·第二级搜索树有250×250=62500种状态，因为我们必须考虑到250种落子选择后，每一种状态都有250种可能出现的新状态。

·第三级搜索树有62500×250，大约有1560多万种状态。

·以此类推，第四级搜索树就会有大约39亿种状态。

到此为止吧，在我撰写这篇文章的时候，一台普通的台式机已经没有足够的内存来存储四级围棋搜索树的状态了。而通常一局围棋游戏要走大概200步，在围棋搜索树中存储200步走棋的搜索树状态数目，那是一个大到你我都无法想象的天文数字，它比我们宇宙中所有原子的数目还大几百个数量级。无论对传统计算机技术做出怎样的改进，它们都无法完成这样可怕的搜索树。

搜索树这种迅速、荒唐的增长速度导致了无法想象的问题，我们称之为组合爆炸，它是人工智能所面临的最重要的实际问题，因为搜索技术在人工智能领域使用得非常广泛[25]。如果你能够寻找到一个快速并且万无一失的办法解决搜索树的难题——发明一种方法，既能达成穷举搜索的目标，又无须占用这么恐怖的资源——恭喜你，你将青史留名，并且让许多人工智能目前所面临的困难迎刃而解。可我不得不遗憾地说，你做不到。我们没办法回避组合爆炸的问题，只能想办法处理它。

在人工智能发展初期，组合爆炸被认为是根本性问题，麦卡锡将其确定为1956年人工智能暑期学校的重要研究课题之一。人们的关注点主要集中在提高搜索效率上，对此，有几种不同的解决方案。

深度搜索的主要优点在于不用存储整个搜索树，只需要存储当前正在处理的分支即可。但它有一个很大的缺陷：如果选择了错误的分支进行探索，可能会在错误的路上越走越远，永远找不到解决方案。所以，要想使用深度优先搜索，首先我们得确认哪个分支最值得搜索。这时候，我们就需要启发式搜索来帮忙了。

启发式搜索的概念就是使用所谓的“经验法则”来指导搜索的重点。通常我们也无法寻找到直指正确搜索路径的启发式方法，但我们往往可以在感兴趣的问题上找到启发式搜索方向。当然，我们也明白，有些情况下，启发式搜索的运行情况并不那么尽如人意。

启发式搜索是一个自然而然产生的概念，多年来它被重新定义了很多次，所以争论到底是谁发明了它已经毫无意义。但是，我们可以确定，第一个应用在人工智能程序的启发式搜索来自一个玩跳棋游戏的程序[26]，由IBM的亚瑟·塞缪尔（AithurSamuel）于20世纪50年代中期创造。塞缪尔编写的跳棋程序，在许多方面为人工智能领域开辟了新天地。首先，以棋盘为人工智能技术的试验场，这一传统就是塞缪尔的跳棋程序开创的。即使在今天，这也是一种常见的技巧，虽然也有不少人提出反对意见。其次，正如我们所提到的，也是即将展开详细讨论的一点，该程序是基于启发式搜索编写的。最后，我们会在之后详细讨论，塞缪尔的跳棋程序是第一个真正意义上的机器学习程序：他的程序自学了怎么玩跳棋。

塞缪尔跳棋程序的关键点在于给棋盘的各个位置赋予不同的权重，用以评估对选手而言位置“好”的程度：从直觉来说，某些“好”的位置可能让某位选手更容易取得胜利，而一些“坏”的位置则会导致失败。为此，塞缪尔用一系列特征值来计算棋盘上的点位价值。例如，某些比较关键的位置，能够让你形成连跳，这样的连跳越多，就意味着你在棋盘上的形势越占上风。然后，程序将不同的评估参数整合起来，给出棋盘位置的一个综合评估价值分数，形成一个量化的评估标准。再根据启发式搜索方法来选择最佳的棋盘移动路径。

在实践中，要考虑比简单的启发式算法更复杂的情况：因为跳棋是一种对抗游戏，你必须考虑到对手可能如何行动。塞缪尔的跳棋程序会认为你的对手会做出对你最不利的举动。这种“最坏情况推理”的方法（即假设对手的行为会使得自己的得分最大化，让你的得分最小化）称为极大极小值搜索，是对抗性游戏的基本概念。

大部分早期的启发式搜索算法，包括塞缪尔的程序，都使用了某种特别的启发方式——“尝试—实践—判断”。20世纪60年代末，美国SRI人工智能研究中心的尼尔斯·尼尔森（NilsNilsson）和他的同事取得了突破，他们开发出名为A*的技术，作为我们之前讨论过的SHAKEY项目的一部分。A*定义了一些简单的规则，让我们可以确定哪些启发是“有益的”。在A*之前，启发式搜索不过是一个猜谜游戏；而在A*之后，它是一个数学上很容易理解的过程[27]。A*现在被视为计算机科学中的基础算法之一，并且在实践中得到了广泛的应用。其实，我们在生活中经常会遇见使用A*算法的程序，比如车载卫星导航系统等。尽管A*很惊艳，但它仍然依赖于使用特定的启发式搜索：好的启发能很快地找到解决方案，而差的启发就没什么价值。对如何为特定问题找到更优秀的启发，A*本身并没有给出答案。

人工智能遇上了复杂性障碍

我们在上一章讲过，计算机的出现源自艾伦·图灵想解决一个彼时数学界的世纪难题。图灵发明计算机可能算是计算机科学史上最大的讽刺之一，因为他的本意是证明有些事情计算机永远也办不到。

在图灵的研究成果问世后的几十年里，探索计算机能做和不能做的事情的范围形成世界各地数学系的小分支的研究方向。这项工作的重点在于把那些固有的不可判定问题（无法用计算机解决的问题）和可判定问题（能够用计算机解决的问题）区分开来。从那时起，人们发现了十分有意思的现象——不可判定的问题存在层次结构：即存在某些问题，不仅不可判定，还是高阶不可判定的（这对某些研究特定领域的数学家而言很棘手）。