您可以在百度里搜索“数学之书：数学史上250个里程碑式的发现 艾草文学(www.321553.xyz)”查找最新章节！

　　※248.破解西洋跳棋

　　沙费尔（Jonathan Schaeffer，1957—）

　　2007年

　　法国艺术家波利（Louis-Léopold Boilly）大约在1803年的时候，完成这幅以全家一起玩西洋跳棋为背景的画作。2007年，计算机科学终于证明只要玩家不犯错的话，西洋跳棋最终一定会以平手的局面作收。

　　圈叉游戏（约公元前1300年），围棋（公元前548年），豆芽游戏（1967年）及破解艾瓦里游戏（2002年）

　　2007年，计算机科学家沙费尔和他的同事终于用计算机证明如果西洋跳棋玩家不犯错的话，最终一定会以平手局面作收。这代表西洋跳棋跟圈叉游戏一样，只要两位玩家都不犯错，游戏的结果一定是平手，没有胜方。

　　沙费尔的证明方式通过数以百计的计算机运算超过十八年的时间，使得西洋跳棋成为人类到目前为止破解过最复杂的游戏，这也表示理论上有可能设计出一台专门跟人类下西洋跳棋，而且永远不会落居下风的机器。

　　西洋跳棋的棋盘是8×8的方格，在16世纪时的欧洲相当流行，早期变形的版本则在现今伊拉克境内、古代吾珥城（City of Ur，约公元前3000年）的废墟中出土。西洋跳棋的棋子通常是黑、红两色的圆盘，棋子只能走斜线；两位玩家轮流下棋，只要跳过对手的棋子就能吃掉它。显而易见，由于西洋跳棋总共有5×10种可能走法，要证明西洋跳棋保证和局的困难度，远远超过证明圈叉游戏没有赢家这一回事。

　　西洋跳棋的研究团队总共考虑了39兆种棋盘上只剩十颗或更少棋子的布局，借以判定黑、红两色中哪一位会是最终赢家；研究团队也使用一种特殊的搜寻算法，研究棋局如何从原始状态“演变成”只剩下10颗棋子的决战阶段。顺利破解西洋跳棋的问题，代表人工智能这门经常与计算机复杂的问题解决策略有关的领域，总算跨越了一项非常重要的里程碑。

　　沙费尔在1994年用这套名为契努克（Chinook）的计算机程序挑战世界西洋跳棋的棋王汀斯雷（Marion Tinsley），结果计算机与人脑间的对抗不断以平手作收。八个月后汀斯雷因为癌症过世，有些人将他的死因归咎于沙费尔，因为来自契努克的挑战导致汀斯雷承受过大压力，也因此加速了他的死亡。 数学之书：数学史上250个里程碑式的发现