1977年，肯·汤普森（Ken Thompson）向顶级棋手展示了所有4枚棋子的残局数据库。其中一个数据库演示了，在K + Q对抗K + R中棋局变化万千，他们不能获胜。随后，根据K + R + B对抗K + R（Benko所称的“令人头痛的残局”），系统改变了规则，规定在75步内决出胜负，后来改为100步。由于最长的获胜步数为59步，因此最后又改回50步。这也扩展到了其他残局，如K + B + B对抗K + N，实践证明，这个残局需要77步才能决出胜负。

几百年来，人们认为残局K+Q对抗K+R（KQKR）最终是强势的一方获胜，虽然这并不容易，但是人们确定可以通过精心布置在50步内决出胜负。1977年，Ken Thompson参加了世界计算机国际象棋锦标赛，用KQKR数据库，挑战了出席的顶尖国际象棋大师。

国际大师Lawrence Day（来自加拿大）和Hans Berliner（1969年世界国际象棋锦标赛获胜者Chess Champion）并没有在50步内作为强势的一方获胜，这让他们惊恐和尴尬。此后轮到世界国际象棋锦标赛候选人——多年来《纽约时报》的国际象棋专栏的大师罗伯特·伯恩（Robert Byrne），结果他也没有获胜。

如果在棋盘上没有兵存在，国际象棋的规则允许50步内结束一盘残局。决出胜负最多需要31步。残局棋谱提供的常见启发式是：保持国王和车在一起，然后避免任何可能捉双以及穿串国王和车。相比之下，Ken Thompson数据库的下法偶尔会分开国王和车。它知道人类还不知道的道理吗？很简单，根本就没有，只要分开国王和车的下法是最长的存活下法，那么Ken Thompson就会使用这种下法。

加州伯克利大学国际象棋超级大师沃尔特·肖恩·布朗（Walter Shawn Browne）（1949—2015）是美国六次国际象棋冠军（1974年、1975年、1977年、1980年、1981年 和 1983年）。1972年，Bobby Fischer打败冰岛雷克雅未克的鲍里斯·斯帕斯基（Boris Spassky），赢得了世界冠军。在Fischer缺席的情况下，Walter Shawn Browne（见图C.0）是在20世纪70年代美国优秀的国际象棋棋手。在Bobby Fischer离开了伊拉斯姆斯高中后不到10年，Walter Shawn Browne也从这所学校退学了，他在许多棋盘游戏中（包括拼字游戏和西洋双陆棋）中表现出色，20多年来，他的主要收入均来源于扑克游戏。

1977年，在世界计算机国际象棋锦标赛的几个月后，善于计算的Browne接受了Ken Thompson数据库的挑战，下注100美元。这个挑战进行的速度是在2.5小时内要走40步（这是当时国际象棋比赛的标准）。就像他前面的其他人一样，Browne无法在50步内取胜。贝尔实验室和Browne之间通过电话来传达如何走子。

图C.0　Walter Shawn Browne

Browne是个竞争对手，也是个赌徒，一周之后，他要求重新对抗数据库，赌注“要么加倍，要么一笔勾销”。虽然布朗从来没有上大学，但是他也知道如何分析和学习。他研究了程序的下法，并寻找模式。虽然学习如何无失误下法（在50步内取胜）是一项具有挑战性的任务（由于决出胜负的最多步数为31步），但是学习如何在所有变化中进行最佳下法，并以最小的移动步数（31）取胜，对人类而言是一项艰巨的任务。在图C.1中，Browne是白方，有皇后；Belle是黑方。棋局从白方被将军开始。与最佳下法匹配的移动步数显示在括号中。

如图C.1所示，Browne确实赢了这个赌注，在第50步中抓住了车（这是通往胜利的道路）。根据最佳下法计算，他的下法实际上多花费了19步。

图C.1

Walter Browne在与计算机程序Belle（第二场比赛）进行残局KQ vs. KR的比赛中获胜。

最初，在Warren Stenberg和Edward Conway发表在《国际象棋之音》（1979年4-5月刊）上的文章中，出现了Browne与Belle比赛的记录，然后这个记录出现在D. Kopec（1990）的《人机国际象棋历史》中，以及在纽约A. Kent 和J.G. Williams的《计算机科学与技术百科全书》中（Marcel Dekker，Vol.26，Supp 11，pp.241-243）。

Browne后来告诉我（1990），与一些说他不“幸运”的报告相反，事实上，他已经分析、计算、准备和记忆了最后的24步，这与他在家的分析完全一致。他还提醒我，多年以后，他在另一盘理论残局——国王和两只相对抗的国王和马，他并没有在50步内获胜，这场比赛下了125步。国际象棋的规则还没有改变以适应这样的5枚棋子的残局。后来，我们从Thompson的数据库中了解到，这个残局需要66步无失误的落子才可以获胜（见表C.1）。

作为这个故事的补充，我们应该提到一本书，这本书的作者为“欧几里得（Euclid）”，由E. Freeborough编辑，于1895年由Trubner＆Company、Trench、Kegan Paul出版，题目为《Analysis of the Chess Ending King and Queen Against King and Rook》。这本书的分析与Thompson数据库的分析非常相似，得出的结论是：取胜所需的最多步数为31步。这本冗长绝版的书具有144页分析和191幅图，我们引用了其中一句话：“人们普遍认为，皇后对抗车，皇后的胜利可能没有实际困难……这是虚幻的，因此应该放弃了。”（第Ⅳ-Ⅴ页）

显然，“欧几里得（Euclid）”写的书在国际象棋和计算机国际象棋世界上都被忽视了！（Kopec，1990）

本文摘自人民邮电出版社异步社区《人工智能 第2版》

《人工智能（第2版）》

[美] 史蒂芬·卢奇（Stephen Lucci） 著

点击封面购买纸书

美国经典入门教材，被誉为人工智能领域百科全书。人工智能领域近十年来最前沿教程，更加适合本科生使用。

本书基于人工智能的理论基础， 向读者展示全面、新颖、丰富多彩且易于理解的人工智能知识体系。本书给出诸多的示例、应用程序、全彩图片和人物轶事，以激发读者的阅读和学习兴趣；还引入了机器人和机器学习的相关高级课程，包括神经网络、遗传算法、自然语言处理、规划和复杂的棋盘博弈等。