4.2 国际象棋世界冠军是一台计算机——那又怎样
现实生活是复杂的，所以AI一直在寻求简化（约束）来使测试新想法和新方法变得更容易。游戏一直被用于计划，因为游戏比现实生活简单得多（它们完全由一些规则定义），所以它们更容易自动化和理解。以计算机国际象棋为例，它是AI领域一个经典且悠久的话题。你可能想知道国际象棋和机器人有什么关系，但请耐心听我说：游戏是一个主题，它直接导致了2012年的重大突破，进而引发了当前的AI活动风暴。
自从第一台电子计算机可以用于编程以来，人们就认为实现计算机国际象棋是一种有趣的挑战。艾伦·图灵在这方面也做出了重大的独创性贡献[2]。国际象棋需要大量的思考才能下好，所以它似乎是一个很好的智力测试。写一个简单的程序来决定下一步走什么，实际上并不太难设计。事实上，这是一个很好的本科编程项目。
当然，这样的练习不会产生非常高水平的游戏，但这里所描述的基本搜索算法与世界冠军计算机国际象棋程序中使用的基本相同。至于规划，象棋程序的基本算法由一个生成器和一个评估器组成，如前所述。这些在方框4.1和方框4.2中进行了概述。
方框4.1 国际象棋是如何自动化的——走法树
这是最开始棋盘的情况，而走法是你从那里所做的各种合法的移动。图4.2显示了这个过程的图解，称为搜索树。为了便于说明，我将可能的走法限制为3种。从最开始的位置产生的三种棋盘变化被放置在第一级下面。这是计算机的走法。接下来是对手的回应，给出了第二级的九种可能的情况，然后计算机再走，依此类推[3]。这是运行中的生成器，其生成搜索树。
图4.2 一个两人游戏搜索树
棋盘的情况随着级别的增加而迅速增长。例如，如果我们在这棵树的每个位置上只有三种走法，那么在第10级，将有超过59 000种可能的棋局。如果在每个位置上只有五种走法，那么在第10级将有超过900万种可能的棋局！国际象棋平均每步大约有10到20种走法，因此树的增长速度是非常惊人的。这种类型的快速膨胀被称为指数级增长，或者，就产生的棋盘组合的数量而言，称为组合性爆炸[4]。
你在走法树上越往下走，顶部走法的含义就越明显，而最好的走法就是你所选择的那一步。众所周知，国际象棋大师需要进行大量的搜索，因此，如果计算机能够比大师们搜索得更深一些，那么它就应该能够击败他们——至少理论上是这样的。编写国际象棋程序很有趣，也很吸引人，需要多种编程技巧来保持过程效率高，且没有浪费宝贵的思考时间。许多有创造力的人通常在业余时间从事计算机国际象棋（和许多其他游戏）的工作。这个产业吸引人的一点是，衡量业绩很容易，因为真正重要的是游戏的结果。因此，人类象棋选手的排名系统也可以应用于计算机程序。1970年，举行了第一届计算机国际象棋锦标赛，从那以后，定期的锦标赛就成了相互测试程序的一种方式，从而衡量这方面的进展[5]。
经过多年的发展，计算机最终战胜了世界冠军。1997年，Garry Kasparov被深蓝（Deep Blue）击败。深蓝是一台装有IBM处理器的计算机，使用的是专门的国际象棋硬件，每秒可以探测2亿步棋。深蓝是由卡内基梅隆大学（Carnegie Mellon University）的Fenghsiung Hsu和他的同事们于1985年开发的一个名为“深思”（Deep Thought）的大学项目[6]。1988年，“深思”成了第一台国际象棋大师级水平的计算机。然后，在1989年，其发明者加入IBM，IBM接管了这个项目，并将其更名为深蓝。
方框4.2 评估可能的走法
当生成尽可能多的搜索树时（受可用时间和内存的限制），必须评估每个分支中最深层的所有位置。评估器根据情况来给它们打分——计算机是正分，对手是负分，中立情况是零分。这些在图4.2中标记为“估值”。接下来，对于每一个分支，如果该计算机走了，计算机会选择最佳值，或者如果该对手走了，则选择最差值，并将这个值传回到上面一级的棋盘（见图4.2）。这个过程称为备份（backing up），对所有级别的所有分支都会重复执行此过程，并且在顶部的当前位置会出现一个值，这就指明了要走哪一步。
在这种情况下，树的左分支比其他两个分支（其工作方式没有显示）要好。请注意，85是可以预期的最佳值，因为尽管有价值高达440的情况，但如果对手下得好，我们就不能期望达到这样的值，因为当轮到她时，她会避开这些情况，而选择一个数值较低的走法。这就是所谓的极大极小算法，它假设每个人都能尽可能地发挥出最佳水平，所以一个选手会试图将情形最大化，而对手则会试图将情形最小化。国际象棋是一种零和博弈，对一方有利的东西总是对另一方不利，一个数字可以反映游戏的状态并用于衡量进展。
当Kasparov被击败时，大众媒体打出了这样的标题：“计算机打败了冠军——接下来它们将接管世界”，或者“国际象棋的霸主地位给人类带来了厄运”。然而，这一切都没有发生，计算机击败世界冠军的事实对计算机的其他方面或该技术的应用没有任何影响。国际象棋仍然是一种非常受欢迎的游戏，计算技术也在继续快速发展。深蓝的胜利对IBM来说是一次伟大的公关活动，但对他们来说也仅此而已。之后，IBM解散了“深蓝”，不再继续进行计算机国际象棋的研究，而是回到了开发和销售更强大的处理器和软件系统的主要议程上来。