乔纳森·谢弗对完美跳棋游戏的探索已经结束。这位来自埃德蒙顿阿尔伯塔大学的 50 岁计算机科学家，在十多年前与历史上最伟大的跳棋冠军进行了一场火的考验后，就将人类棋手远远甩在了身后。
现在，在让数十台计算机日夜工作了 18 年——跳，跳，跳——之后，他说他已经破解了这款游戏——让我成为王！。“起始位置，假设双方都没有犯错，结果是平局，”他说。
谢弗的证明今天在《科学》杂志上进行了描述（并且可以在这里免费获取以供他人验证），这将使跳棋成为机器迄今为止破解的最复杂的游戏，其难度比堆叠棋子游戏“四子连线”高出一百万倍。
支持科学新闻报道
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您将帮助确保有关塑造我们当今世界的发现和想法的具有影响力的故事的未来。
“这是一个里程碑，”IBM 位于纽约州霍桑市的 T. J. Watson 研究中心的计算机科学家、国际象棋程序“深蓝”的共同发明者默里·坎贝尔说。“他扩展了最先进的水平。”
尽管技术限制禁止分析八乘八棋盘上可能出现的 500千兆亿种可能的排列组合中的每一种，但谢弗和他的团队还是确定了一些招法，这些招法保证了无论竞争多么激烈，游戏都将以平局结束。
像任何复杂的数学证明一样，这个结果将不得不经受严格的审查。但荷兰马斯特里赫特大学的计算机科学家雅普·范登·赫里克说，“它接近 100%”，他已经看到了细节。“他从未发表过任何不完全真实的东西。”
开局：如履薄冰
谢弗的奥德赛始于 20 世纪 80 年代后期。他编写了一个顶级的国际象棋程序，但 IBM 即将投入其远更庞大的资源到“深蓝”上。“我喜欢竞争，”他说，所以他将注意力转向了其他地方。“我天真地认为我可以破解跳棋游戏，”他回忆道。“你可以在一分钟内教会某人规则。”
1989 年，他带着 16 兆字节的计算机内存出发，很快发现跳棋和国际象棋一样，可能的局面太多，无法快速找到解决方案。因此，他改变了方向，发誓要推翻传奇跳棋冠军马里昂·廷斯利，后者自 1950 年以来在锦标赛中只输过三场比赛。
1992 年，谢弗的程序“奇努克”挑战了廷斯利，当时美国跳棋联合会和英国跳棋协会暂时拒绝批准人机对决，廷斯利辞去了世界冠军头衔。
据谢弗说，廷斯利非常出色，以至于他的对手们玩起了沉闷的游戏，希望能至少获得平局；“奇努克”显然为这位冠军重新带来了游戏的魔力。“它下出了大胆、激进的招法——它如履薄冰，”谢弗拟人化地说道。“它会做一些人们看到后会说，‘天哪，那个程序疯了吗？’的事情。”
该程序实际上击败了廷斯利两次，但计算机故障导致一次弃权，让人类以 3-2 领先，还剩两场比赛，这是一场 40 场比赛的最佳对决。谢弗让“奇努克”采取激进的策略试图挽回局面，结果导致计算机再次失利，并使其创造者输掉了比赛，谢弗在他的著作《领先一步》中回忆道。
在两年后的复赛中，廷斯利在六场平局后突然退出，理由是健康问题，这使得“奇努克”默认成为人机世界冠军。跳棋冠军被诊断出患有胰腺癌，不到一年后去世。
“奇努克”在 1996 年彻底击败了顶尖人类棋手，但谢弗对那些年的回忆却是苦乐参半的。“事后看来，也许当时对我来说，胜利比其他事情更重要。我有点痴迷，”他说。“我的妻子会说不止有点痴迷。”
残局：让我成为王！
在本世纪初，他认为计算机速度和内存的提高已使他实现破解游戏的目标触手可及。解决方案的第一个部分建立在廷斯利时代开始的工作之上。阿尔伯塔大学的研究人员详尽地检查了最后阶段的比赛，针对任何 10 个或更少棋子的排列组合，确定了 3.9 x 1013 个位置中的哪些位置是赢、输还是平局。
接下来，他们确定了 19 个代表性的开局序列，并搜索了后续招法，以找到最容易找到的与最终位置（赢、输或平局）的连接。为了节省时间，他们忽略了毫无意义的来回招法或那些不会将平局变成胜利的招法。
如果可能的招法序列像树一样分支，该小组发现主要分支之后的主要分支都导致平局。谢弗说，4 月 27 日，该程序追踪了最后的分支，完成了他 18 年的任务。他得到了他的王。
结果本身并不令人惊讶。“我们预计这应该是平局，因为在最高水平的比赛中，有很多比赛以平局结束，”赫里克说。
沃森的坎贝尔说，证明所做的，是突出了有条不紊地逐一检查结果的力量。最强大的国际象棋程序，如“深蓝”和“深弗里茨”，通过将快速的数字运算与从多年的人类对弈中获得的经验法则相结合，击败了世界冠军。
坎贝尔指出，跳棋破解器相对来说比较笨。“它所知道的只是这步棋赢了，或者这步棋没有赢，”他说。“它无法‘解释’它知道什么。”
出于这个原因，赫里克说，在研究人员弄清楚如何将结果转化为人类思维可以遵循的规则或程序之前，这些结果对棋手不会有太大帮助——这本身就是一个重大挑战。
下一步棋？
那么，下一个将被计算机攻克的游戏是什么呢？谢弗及其同事推测将是奥赛罗，一种八乘八的翻转棋子游戏。国际象棋提出了一个更强大的挑战，但研究人员“正处于思考”破解它的领域，赫里克称之为“一项巨大的成就”。
游戏的巨大白色鲸鱼仍然是亚洲的消遣围棋。尽管程序最近在九乘九的棋盘上变得可以与大师们竞争，但在完整的 19 乘 19 的游戏中，它们仍然是无力的。
谢弗是一位真正的游戏爱好者——他的两条狗分别名为“拼字游戏”和“拉密纸牌”——计划在下周的一场 500 手牌的比赛中，让他的扑克程序对抗两位顶尖牌手，这场比赛旨在最大限度地减少运气的成分。
自从专注于世界冠军赛以来，他已经走了很长一段路。无论未来的游戏如何，他都可以对当前的胜利感到满意。“十八年后，”他说，“我终于完成了。”