计算机博弈的发展历史

1.3　计算机博弈的发展历史

第1.2节所引述的Claude Shannon关于计算机博弈论文是计算机博弈的早期经典论文之一，也标志着计算机围棋的起源。从该论文的发表算起，计算机博弈研究已经经历了六十年的发展，在此期间取得了举世瞩目的巨大成就。纵观计算机博弈六十年的发展历史，根据其所研究的核心博弈项目及其数学模型的不同，我们可以大致地把计算机博弈分成两大阶段：传统计算机博弈阶段和现代计算机博弈阶段。不同的阶段有不同的博弈项目作为核心研究对象，使用不同的数学模型和计算方法，研究成果也具有不同的意义，对相关领域也产生不同的影响。我们在本节主要讨论传统计算机博弈，现代计算机博弈的内容将在第5章讨论。

在传统计算机博弈阶段，计算机博弈的核心研究对象是国际象棋。第1.2节所引述的关于计算机博弈意义的论述，就是Claude Shannon以国际象棋为具体研究对象所阐述的。除此之外，在同一篇论文里，他也描述了传统计算机博弈的一些基本理论和方法，其中包括博弈树模型、极小极大搜索算法、局面评估函数和静止搜索算法等。在以国际象棋为核心的传统计算机博弈发展过程中，研究人员又设计了一系列新的搜索算法及其相关技术来提高计算机博弈搜索算法的效率，其中包括α-β剪枝算法、负侦查搜索算法和置换表技术。我们将在第2.1节、第2.3～2.9节分别讨论博弈树模型、局面评估函数、极小极大搜索算法、负极大搜索算法、α-β剪枝算法、负侦查搜索算法、静止搜索算法和置换表技术。

随着传统计算机博弈理论与方法的发展，以及计算机硬件和软件水平的提高，研究人员也不断构建计算机博弈程序，并在与人类博弈选手的比赛中取得了瞩目的成绩。以下是传统计算机博弈阶段的主要里程碑。

①1950年，Claude Shannon发表了关于计算机国际象棋的文章Programming a Computer for Playing Chess。

②1951年，Alan Turing在论文中开发了第一个完整的计算机国际象棋程序。

③1956年，John McCarthy发明了α-β剪枝搜索算法。

④1967年，Richard Greenblatt等人所开发的计算机国际象棋程序第一次在正式比赛中战胜了人类选手。

⑤1981年，计算机国际象棋程序Cray Blitz第一次在正式比赛中战胜大师级选手，并成为第一个具有大师及评分的程序。

⑥1982年，Ken Thompson的计算机国际象棋程序——Belle赢得美国国际象棋大师称号。

⑦1988年，Hans Berliner和Carl Ebeling开发的计算机国际象棋程序——HiTech战胜了国际象棋特级大师。

⑧1994年，Gerald Tesauro使用TD（λ）增强型学习算法开发了十五子棋戏（backgammon）大师级的程序。

⑨1997年，计算机国际象棋程序——Deep Blue第一次在六盘棋的比赛中战胜了当时的世界冠军Garry Kasparov。

⑩2007年，加拿大阿尔伯塔大学Jonathan Schaeffer等人在数学上证明了西洋跳棋（checkers）的可解性。