阿尔伯塔大学宣布西洋跳棋已被破解

什么叫做「破解」一个棋类游戏

西洋跳棋（checkers）是两人轮流走子、吃掉对方棋子的棋盘游戏。说一个游戏被「破解」，比说某个程序下得好要强得多：它意味着从开局开始，结果已经被确定地知道，而且存在一套策略，无论对手怎么走，都能保证这个结果。对西洋跳棋来说，答案是和棋。

宣布

2007年7月19日，阿尔伯塔大学（University of Alberta）宣布该校的计算机科学家破解了西洋跳棋。^[1] 校方发布的新闻稿说，结果当天发表在了《Science》杂志上，做出这一结果、名为 Chinook 的程序则在2007年4月下旬完成。^[1] 新闻稿说，这项工作耗时18年半，筛选了 500 billion billion（5×10²⁰）个跳棋局面。^[1]

证明是怎么做出来的

《Science》报道，Jonathan Schaeffer 从1989年开始着手破解西洋跳棋，证明由数百台计算机执行，历时近二十年。^[2] 其中一个核心部件，是收录棋盘上棋子不超过10枚时全部 39,000 billion（3.9×10¹³）种局面的数据库。^[2] 这类残局表之所以管用，是因为当剩下的棋子足够少时，每个局面的好坏都可以精确算出来并保存下来；下棋时程序只要查表就能知道局面优劣，不必再向前搜索，而更大局面的结论也可以由这些小局面拼出来。阿尔伯塔大学的新闻稿说，平均每天有50台计算机参与计算 Chinook 所需的知识，高峰时超过200台。^[1]《Scientific American》报道，Schaeffer 说程序在2007年4月27日追踪完了最后的分支，完成了这项18年的任务。^[4]

结果

新闻稿说，Chinook 可能被逼成平局，但永远不会被击败。^[1]《Science》报道说，如果两名棋手对弈西洋跳棋，双方都不走错，棋局必然以平局告终。^[2] CBC 引述《Science》的文章说，西洋跳棋现已被破解，双方完美走棋会导向平局，并称它是迄今被破解的最具挑战性的流行游戏。^[3]

意义

一个被破解、且答案为和棋的游戏，形状是特定的：先手不能强求胜利，后手也不能，因为双方最好的走法会互相抵消。^[2] 对一个程序来说，能下的最强结论是防守性的——它可以被逼平，但不会被击败，阿尔伯塔大学的新闻稿正是这样描述 Chinook 的。^[1] 这也意味着这个结果并没有把游戏从人手里拿走：只要人下得足够好，仍然可以和棋；程序排除掉的只是输棋这一种结局。

这项工作还展示了「穷尽式的计算答案」在实践中是什么样子。研究者不是去争论哪种计划更强，而是把局面逐一列举、逐一算清，代价是近二十年的时间和大批机器。^[2] 残局数据库、每天几十台计算机的持续计算、以及2007年4月追踪完的最后分支，都是这同一个结论的组成部分。^[1][4] 这次宣布把西洋跳棋放进了「结果不再有争议」的棋类之列，CBC 引述《Science》的说法，称它是到那时为止被破解的最具挑战性的流行游戏。^[3]