Chinook 西洋跳棋程序

Chinook 是由 Jonathan Schaeffer 及其同事开发的西洋跳棋（checkers）计算机程序 ^[1]。它最常被提到的两点是：它是首个在任何游戏中赢得人类世界冠军的计算机程序；完成后的版本无法被击败 ^[1]。

由来

Schaeffer 于 1989 年启动 Chinook 项目，最初目标很明确：赢得人类西洋跳棋世界冠军 ^[1]。这个程序在 1990 年获得争夺冠军的资格，并在 1992 年的冠军赛中落败 ^[1]。据《科学美国人》报道，在 1992 年与 Marion Tinsley 的比赛中，Chinook 曾两次击败对手，但计算机故障导致了一次弃权 ^[4]。CBC 报道称，Chinook 最初采用启发式（heuristic）方法，依据顶尖跳棋棋手总结的经验规则；到了 1990 年代中期，它有时仍会输棋 ^[3]。这说明早期的 Chinook 还不是后来那个无法被击败的完整系统。

主要特点

启发式方法用一些实用规则来挑选走法，不保证每一步都是最佳。Chinook 的早期版本正是这样下棋的 ^[3]。项目后期发生了变化：完成后的程序不再需要启发式，而是变成一个信息数据库，知道一局游戏中每种局面下的最佳走法 ^[1]。建立这些知识需要大量计算。每天平均使用 50 台计算机，峰值时超过 200 台，用来计算 Chinook 所需的知识 ^[1]。求解工作建立了一个数据库，涵盖棋盘上棋子不超过 10 枚时的全部 39 万亿种排列 ^[2]。对于这些局面，程序可以查表得到已证明的最佳走法，而不是靠估计。

比赛与结果

1994 年，Chinook 赢得人类世界冠军 ^[1]。它因此成为首个在任何游戏中赢得人类世界冠军的计算机程序，这一成就得到吉尼斯世界纪录（Guinness World Records）的认可 ^[1]。1994 年与 Tinsley 的复赛情况特殊：《科学美国人》称，Tinsley 在六局和棋后因健康问题退出 ^[4]。Chinook 一直保持不败，直到 1997 年退役 ^[1]。2001 年，Schaeffer 重新启动了这个项目 ^[1]。

在发展中的位置

Chinook 的意义不只是赢过一次冠军。它把人类竞技目标与长期求解工作结合起来：早期版本会输棋，后来完成版无法被击败，两者的差别就是从启发式棋手变成存储起来的完整知识 ^[3][1]。项目也展示了游戏求解的规模：许多计算机每天运行，最终得到覆盖棋子不超过 10 枚的全部排列的数据库 ^[1][2]。1994 年的冠军头衔和吉尼斯世界纪录的认可，使它成为计算机程序在游戏中赢得人类世界冠军的公开例子 ^[1]。2001 年的重启则是在退役之后继续推进项目 ^[1]。因此，Chinook 既是一个为比赛而建的程序，也是一个已求解局面的档案：它的早期版本依靠规则和经验，完成后的版本对覆盖到的局面则从数据库中给出最佳走法 ^[1][2]。