博弈程序的当前发展水平

有人也许会说博弈对于人工智能就像格兰披治国际汽车大奖赛对于汽车工业一样：当前发展最高水平的博弈游戏程序运行在令人眩目地快速、难以置信地良好调谐的机器上，结合了非常先进的工程技术，然而它们对于购物没有多大用途。尽管很多研究人员认为博弈多少和主流的人工智能无关，它还是不断地产生令人激动的和坚实的概念新潮流，并被广泛的领域所采纳。

国际象棋：1957年，赫伯特·西蒙预测10年之内计算机可以击败人类的世界冠军。40年后，深蓝（Deep Blue）程序在6局比赛的表演赛中击败了加里·卡斯帕罗夫（Garry Kasparov）。西蒙预测错了，但仅在时间上差了4倍的因子而已。卡斯帕罗夫写到：

决定性的比赛是第二局，它在我记忆中留下了伤痕……我们看到了远远超出我们最疯狂想像的事情，计算机能够预见它的决策中的长期棋局序列。机器拒绝走一步有决定性短期优势的棋——显示了非常类似于人类的对危险的感觉。（卡斯帕罗夫，1997）

深蓝是由IBM的Murray Campbell，Feng-Hsiung Hsu和Joseph Hoane（参见Campbell等人，2002）在深思（Deep Thought）的基础上开发的，深思是Campbell和Hsu早先在卡内基梅隆大学开发的。获胜的机器是一台并行计算机，它有30个IBM RS/6000处理器来运行“软件搜索”，480个定制的VLSI国际象棋处理器执行生成行棋的功能（包括行棋的排序）、树的最后几层的“硬件搜索”以及叶节点的评价。深蓝平均每秒搜索 12.6 亿个节点，峰值时可以每秒搜索 33 亿个节点。每步棋它生成多至 300亿个棋局，常规搜索深度是14步。机器的核心算法是使用调换表的标准迭代深入α -β搜索，但是它成功的关键看来是它对于有足够兴趣的强制或被动的行棋路线具备产生超越搜索深度的扩展的能力。在某些情况下搜索可以到达40层的深度。评价函数使用了超过8000个特征，许多特征用来描述非常独特的棋子模式。使用了一本有4000个棋局的“开局手册”以及一个存有70万个大师级比赛棋谱的数据库，可以从中提取综合的建议。系统同时还使用了一个大型残局数据库保存已解决的棋局，其中包含了5个棋子的全部棋局和6个棋子的很多棋局。这个数据库的效果是实际扩展了有效搜索深度，允许深蓝在某些情况下表现完美，甚至当它距离将死对手还有很多步棋的时候。

深蓝的成功加强了一个人们广泛支持的信念：计算机的博弈水平的进步主要源自更强有力的硬件——这也是 IBM 所倡导的。但另一方面，深蓝的缔造者们还指出搜索扩展和评价函数也至关重要（参见Campbell等人，2002）。此外，我们知道最近的一些算法改进使在标准个人计算机上运行的程序能赢得1992年以来的每届世界计算机国际象棋冠军赛，并且经常可以战胜那些能多搜索1000倍节点的大型并行机对手。一个剪枝启发式的变种可以把有效分支因子降低到3以下（相比之下，实际分支因子大约是 35）。这里最重要的是空招数启发式，通过使用让对手在游戏开始时连走两步棋的一个浅层搜索，能对棋局值生成一个很好的下界。这个下界常常允许α -β剪枝节省完全深度搜索的开销。同样重要的技术是无效剪枝，它可以帮助提前决策哪些行棋招数会引起后继节点中的β截断。

深蓝的团队拒绝了和卡斯帕罗夫再次比赛的机会。而最近的主要赛事是在2002年程序FRITZ挑战世界冠军弗拉德米尔·克拉姆尼克（Vladimir Kramnik）。这场8局的比赛最终战成平局。比赛的条件对人更有利，使用的硬件是一台普通的个人电脑而不是超级计算机。不过克拉姆尼克评论说“现在很明显顶级的程序和世界冠军几乎可以平起平坐了。”

西洋跳棋：从1952开始，IBM的阿瑟·萨缪尔（Arthur Samuel）利用业余时间开发了一个会通过自己大量下棋学习评价函数的西洋跳棋程序。我们将在第二十一章详细描述其思想。萨缪尔的程序开始是个新手，不过仅通过几天的自我下棋学习已经能改进自己，超过了萨缪尔本人的水平（虽然他不是个厉害的棋手）。在1962年它利用对方自己犯的错误击败了“蒙目西洋跳棋”冠军Robert Nealy。许多人觉得这意味着计算机在下西洋跳棋方面胜过了人，不过实际情况并不是这样的。当然，考虑到萨缪尔使用的计算设备（IBM704）只有可以存储 1 万字的主存，长期存储用的是磁带，而且只有一个0.000001-GHz的处理器，这次胜利仍然是一个伟大的成果。

很少有其他人试图做得更好，直到Jonathan Schaeffer和他的同事们开发出在常规个人微机上运行的使用α -β搜索的Chinook。Chinook使用了一个提前计算好的存有4440亿个不多于8个棋子的棋局数据库，使它的残局走棋没有缺陷。Chinook在1990年美国公开赛取得第二名，从而获得了向世界冠军挑战的权利。接着它遇上了麻烦，Marion Tinsley。Tinsley博士是40多年的世界冠军，在所有比赛中总共只输过3盘。第1次与Chinook的对弈中，Tinsley遭受了他的职业生涯的第4盘和第5盘失败，不过还是以20.5比18.5的分数赢了整个比赛。1994年8月的世界冠军赛中，Tinsley和Chinook继续对垒，不过Tinsley因健康原因退出了比赛。于是Chinook成为了正式的世界冠军。

Schaeffer相信，如果有足够的计算能力，残局数据库可以扩大到那种程度，其中前向搜索从初始棋局总能到达已解决的棋局，即西洋跳棋可以完全得到解决。（Chinook 可以提前 5 步宣布胜利。）这种彻底的分析对于 3 × 3 的井字棋可以手工完成，而对于 Qubic 游戏（4×4×4 的井字棋）、五子棋（Go-Moku，五子连珠）和九人莫里斯游戏（Nine-Men’s Morris）（Gasser，1998）的分析也已经由计算机完成。Ken Thompson和Lewis Stiller的卓越工作（1992年）解决了所有5个棋子和一些6个棋子的国际象棋残局，并且把这些解放在因特网上供大家使用。Stiller 发现了一种需要 262 步棋的强制将军的情况；这有些出乎意料，因为在国际象棋规则中要求在50步以内发生某些“进展”。

奥赛罗（Othello），也称为翻转棋（Reversi），可能作为一种计算机游戏比作为棋盘游戏更流行。它有比国际象棋更小的搜索空间，通常有5到15个合法行棋，不过评价的专门技术要从零做起。在1997年，Logistello程序（Buro，2002）以6比0击败了人类世界冠军Takeshi Murakami。目前一般都承认人类在翻转棋上无法与计算机较量。

西洋双陆棋（backgammon）：第6.5节解释了为什么引入掷骰子的不确定性使得深度搜索成为昂贵的奢侈品。大多数双陆棋的研究工作致力于改进评价函数。Gerry Tesauro（1992年）把萨缪尔的强化学习方法与神经元网络技术（第二十章）相结合，开发了一个非凡精确的评价函数用于进行二、三步深度的搜索。经过上百万次的自我训练比赛，Tesauro的程序TD-GAMMON稳定地排名在世界前三名棋手之列。这个程序对游戏的开放招数的观念，在某种意义上根本改变了公认的智慧。

围棋是亚洲最流行的棋盘游戏，至少需要和国际象棋一样多的专业训练。由于棋盘是19×19的，所以分支因子初始为361，对于常规的搜索算法来说这太令人生畏了。直到1997年还根本没有一个有竞争力的围棋程序，不过现在有些程序可以经常下出好棋了。大多数最好的程序把模式识别技术（当出现一定的棋子布局模式时就考虑下某些棋）和有限搜索（决定在局部某些棋子是否可以吃掉）结合起来。目前最强的程序可能包括Chen Zhixing的手谈（Goemate）和Michael Reiss的Go4++，大概相当于10级水平（较弱的业余棋手）。围棋仍是一个可能从通过使用更复杂的推理方法加强研究而获益的领域。成功也许来自寻找一些方法，把围棋分解成很多松散连接的“子游戏”，对它们分别进行局部推理，再把这些推理路线整合到一起。这样的技术对于一般的智能系统也有巨大的意义。

桥牌是一种不完整信息的游戏：一个牌手的牌其他牌手是看不到的。桥牌也是多人游戏，有四个人参加而不是两人，尽管牌手们每两人一队组成对抗的双方。正如我们在第 6.5 节中所见，桥牌中的最优打法包括信息搜集、交流、欺骗和仔细权衡概率等因素。赢得 1997 年计算机桥牌赛冠军的 Bridge BaronTM程序（Smith等人，1998）采用了许多这些技术。尽管它出牌不是最优的，Bridge Baron是少数几个成功地运用复杂的分层规划（参见第十二章）的博弈系统，它包含了诸如飞牌和挤牌这样的为桥牌选手所熟悉的高级思想。

GIB程序（Ginsberg，1999）所向披靡地赢得了2000年的冠军。GIB使用“观察的平均”的方法，做了两个重要的修改。首先，避免检查每个选择对于每种可能的未知牌的排列——可能多至1亿种——的可行程度，它只检查100个排列的随机样本。其次，GIB使用了基于解释的一般化来计算和缓存各种情形的标准类中最优打法的通用规则。这使得它可以准确地解决每副牌。GIB的战术精确性弥补了它在对信息推理方面的不足。它参加了1998年的人类标准桥牌世界冠军赛（只涉及主打）（计算机发牌，每个牌手主打相同的牌，考验牌手的功力——译者注），在35名选手中取得了第12名，这大大出乎很多人类专家的意料。