本文首发于 VG247 的合作刊物 USgamer。一些内容，例如这篇文章，在 USgamer 关闭后已迁移到 VG247 供后代使用 - 但尚未经过 VG247 团队的编辑或进一步审查。
1990 年，当世界排名第一的 Marion Tinsley 在一系列表演赛中与 Jonathan Schaeffer 教授的跳棋程序 Chinook 进行跳棋比赛时，他宣称：“我感觉自己又回到了少年时代。”
事实上，廷斯利当时已经 63 岁了，他被广泛认为是有史以来最伟大的跳棋棋手。然而，这种幸福的状态并非没有缺点。一方面，这意味着廷斯利想要打出一盘好跳棋是非常困难的。
“关于廷斯利，你首先要知道的是，廷斯利更像是机器，而不是人类，”谢弗在我们通过 Skype 聊天时向我解释道。 “他几乎是完美的。你会想到计算机的完美，但你不会想到人类的完美。从 1950 年到 1992 年我们再次与他交手，这 42 年里他总共输掉了 3 场比赛。 42 年来，他输掉了 3 场比赛。其中有 2 场比赛是在明显平局的情况下犯下的小错误。42 年来，只有一场记录表明他实际上被击败了。
“所以他几乎是完美的。很快，当他开始进步时，你知道，从未输过一场比赛，他得到了一个绰号：可怕的汀斯利。”谢弗皱起眉头。 “他不喜欢这个名字，但关键是与他比赛是一次可怕的经历。你永远不会赢。人们害怕他，每当人们坐下来和他比赛时，他们都不会为了赢而比赛.他们只会打平局。然后，当廷斯利在 1990 年对阵奇努克队时，他来到这里，我们打了 14 场比赛。他以 13 场平局以一对一的比分击败了我们。他说，‘当我年轻的时候，跳棋很令人兴奋。我们会尝试有趣的事情。我们会尝试危险的路线和冒险的事情。我们会做任何事情来尝试赢得比赛，这很有趣。但随着我年龄的增长，它变得无聊，因为没有人尝试打我。' Chinook 并不尊重 Tinsley。没有，对吧？程序会做出响亮、大胆的动作。它会走在悬崖边缘，挑战 Tinsley 向他冲锋。Tinsley 说跳棋又变得有趣了，因为它玩的游戏就像这是他十几岁的时候玩的。他真的非常喜欢和电脑对战。”
让玛丽恩·汀斯利再次感觉像个青少年是一项不错的成就，但这并不是谢弗最伟大的成就。 17 年后，他领导了一个小团队，继续解决跳棋问题。也就是说，如果两个“完美”棋手都没有犯任何错误，他将能够准确地确认两个“完美”棋手之间进行的任何跳棋游戏的结果是什么。如果廷斯利扮演廷斯利，并且他们都度过了美好的一天怎么办？跳棋的最优游戏如何结束？这是一个令人着迷的前景。数百年来，人们一直在玩各种跳棋。一旦你达到了一定的——尽管是极端的——熟练程度，这一切都本质上是被操纵的吗？不是由设计师操纵，而是由数学操纵——由宇宙操纵？
今天，谢弗担任阿尔伯塔大学理学院院长，当我们通过 Skype 聊天时，他显得精力充沛。由于意外或故意，教授将笔记本电脑的摄像头稍微向天空倾斜，因此在他的头顶上方，我看到艾伯塔省校园窗框的干净金属扫面，衬托着明亮的白云。谢弗本人低头凝视，就像一位好斗的牧师在进行严格的布道。他一半是诺姆·乔姆斯基，一半是诺曼·梅勒，一半是詹姆斯·凯恩，他首先承认，当他还是个小男孩时，他根本不关心跳棋。相反，他关心国际象棋。
“这就是让我感兴趣的原因，”他解释道。 “我是一个下棋的年轻人。我相当不错，我梦想成为世界冠军。最终你会意识到：嘿，我不会成功。因为我对计算感兴趣，我开始听到很多关于计算机国际象棋比赛的信息。那是 20 世纪 70 年代。我知道如何编程，我对国际象棋很感兴趣，所以我想，‘这应该不会太难吧？我可以编写一个程序让我成为世界冠军， 正确的？'所以这就是我的动机。有点自负。”
Schaeffer 于 1979 年开始编写国际象棋程序，并在长达十年的时间里一直保持着竞争力。 1986年，他的程序在世界国际象棋锦标赛——世界计算机象棋锦标赛上获得并列第一名。 1989 年，他帮助组织了在埃德蒙顿举行的下一次活动，但他的代码中的错误导致了失败。更糟糕的是，对于一个研究残局的学生来说，他童年国际象棋希望的轨迹似乎即将重演。 “这是不祥之兆，因为我的一些朋友组建了一个名为深蓝的团队，”他笑着说。 “我意识到，一个人，比如我，兼职开发一个国际象棋程序，永远无法与 IBM 即将推出的 Deep Blue 项目相媲美。”
不过，作为一名研究人员，谢弗的工作是撰写论文，因此他并没有完全离开这个领域，而是改变了方向。 “我意识到用跳棋解决同样的问题比用国际象棋更高效，”他说。
这是国际象棋棋手所期望的那种精明的战术举动。 “重点是跳棋面临着相同的研究挑战，但它更简单，”谢弗解释道。 “因为你只有两种，而不是六种不同的棋子类型。你不是在 64 个不同的方格上玩，而是只有 32 个。跳棋中没有像易车和过路这样的一大堆特殊规则，而是没有。它允许我摆脱许多复杂情况和特殊情况，专注于解决有趣的问题。”
对于谢弗来说，一直有一个非常有趣的问题：“如何构建一个超人的游戏程序？”他叹了一口气。 “构建一个游戏程序很容易，就像教人类如何玩国际象棋或跳棋等游戏很容易一样。只需进行一点训练，你就可以玩任何游戏，对吧？我们是通用目的问题 -求解器。但是你如何让它成为超人？这几乎就像收益递减法则。如果你是一个弱棋手，那么不需要做很多工作就能成为一个好的棋手。它需要很多要变得非常优秀，需要做更多的工作，然后需要付出更多的努力才能成为特级大师。我很好奇：计算机程序需要什么？从优秀到非常好再到伟大，需要付出什么努力？完美的？ ”
经过一番努力后，谢弗带着奇努克回到了赛道上。正是这个项目让廷斯利在 1990 年感到非常高兴——表演赛之后很快就开始了锦标赛比赛。
“我们通过正常渠道获得了参??加人类世界锦标赛的权利，”他说。 “你知道，深蓝在 1997 年与卡斯帕罗夫比赛，但它并没有获得与卡斯帕罗夫比赛的权利。IBM 投入了大量资金，卡斯帕罗夫同意支付这笔钱。我们参加了人类锦标赛，我们赢得了比赛有权与世界冠军玛丽昂·廷斯利一起参加世界锦标赛。” 1992年，奇努克在伦敦对阵廷斯利，以微弱优势落败。然而，1994 年的波士顿，廷斯利在六场比赛全部平局后辞职，称自己身体状况不佳，无法参加比赛。奇努克因弃权而获胜。九个月后，廷斯利去世了。
对于西洋跳棋界来说，这是一段悲伤的时光，但奇努克并不打算退休。如果说有什么不同的话，那就是谢弗现在更加雄心勃勃了。当你可以击败游戏本身时，为什么还要玩跳棋来获胜呢？ “我一直想解决跳棋问题，”谢弗承认。 “当我早年开始关注这款游戏时，我的想法是最终解决它。”他笑了。 “我当时很天真。”
请记住，解决游戏意味着能够从两个完美玩家之间的任何比赛中的任何位置确定最终结果。在这种情况下，“完美”意味着两个玩家都没有犯任何错误——每一步都被证明是最佳的。谢弗的目标是所谓的“弱”解决方案。换句话说，他正在寻求从开始到结束至少产生一个完整的理想动作序列。创建一种可以完成此类任务的算法意味着要玩很多跳棋，或者至少让计算机来玩跳棋，因为它会寻找那些完美的动作。
这就是这个过程开始变得棘手的地方。 “首先，跳棋是一项多大的游戏？”谢弗问道。 “因为，显然，对于像井字棋这样的游戏，你可以完美地玩它，并且可以快速解决游戏。这并不难。为什么跳棋那么难？”
事实证明，由于数字非常大，所以难度要大得多：5 x 10 到 20。那就是 5000 亿——一个 5 后面跟着 20 个零。
“这就是跳棋中的位置数量，人们很难理解这个数字有多大，”谢弗笑着说。 “所以假设你把太平洋排空了。没有水。太干了。现在，我给你一个勺子，一个茶匙，你可以把茶匙装满水，走到空荡荡的太平洋，然后把那茶匙水倒进去。如果你这样做5000亿次，你就会填满太平洋。所以它有多大。”
1989 年，谢弗宣布他要解决跳棋问题，这意味着要找到一种方法来驾驭这 5000 亿亿美元的棋局，寻找完美的走法。 “当我开始认真研究这个问题时，它比以前通过计算完美解决的任何问题都要大一百万倍，”他承认。 “这对我来说真的很愚蠢，但当你年轻而天真时，一切看起来都是可行的——所以你就这么做了。”
即便如此，5000亿也还是太大了。谢弗和他的团队必须发明解决问题的方法，试图降低这个数字。该项目成功的关键是使用了一些已被证明在国际象棋中稍微有效但在跳棋中可以非常有效地使用的东西。首先，谢弗将扭转比赛的局面。
“为了解决这个游戏，我实际上是从游戏结束时开始的，”他解释道。 “所以当跳棋开始时，棋盘上有 24 个棋子。我们每个人都吃掉一些棋子，最终你可能会在棋盘上只剩下一个棋子。我从那里开始。假设棋盘上只有一个棋子：我的棋子，一个白色的棋子。棋子。棋盘上只有 32 个方格。实际上，我可以有一个国王或一个跳棋，所以实际上有 64 种可能性。我可以建立一个包含所有 64 种可能性的数据库，所有这些可能性都是胜利我，因为我是唯一拥有一颗棋子的人。如果我改变颜色，那 64 种可能性对你来说都是胜利。所以现在，我有一个数据库，上面写着：每当我在棋盘上找到一颗棋子时，我不需要做任何计算。我只需在我的数据库中查找它，它就会告诉我这对我来说是胜利还是对你来说是胜利。对吗？
“现在把棋盘上的棋子备份到两颗。一颗给我，一颗给你。我可以想出将这些棋子放在棋盘上的所有方法。如果我吃掉了一颗棋子，我就剩下一颗棋子，我就可以了。”然后可以进入我的数据库。现在我可以移动到三块，因为当我失去一块时，我还剩下两块，我已经得到了我的答案——你赢了还是我赢了数据库。最终，我建立了这个数据库，直到棋盘上有十个棋子。这是数万亿个位置，超出了任何人可以理解的范围。这是完美的信息。如果你给我任何棋盘上有十个棋子的棋子位置，我立即进入数据库，它会告诉我：赢、输或平局。无需思考，你就完成了。”
有了残局数据库，谢弗又回到跳棋的起点。 “棋盘上有 24 个棋子，我们会进行搜索，然后当我们只剩下 10 个棋子时我们就会停止，因为我们可以在数据库中查找最终结果。这使我们能够解决 5000 亿的问题十亿，并把它缩小一百万倍，让我去解决。它变成了我真正可以解决的问题。”
即便如此，还是花了相当长的时间。从 1989 年开始，Schaeffer 的程序在大约 200 台计算机上持续运行，直到 1996 年，Schaeffer 不得不短暂停止，因为他需要执行的下一次计算需要比当前 32 位标准更强大的机器。三年后，随着 64 位处理器的普及，他再次开始计算，一直持续到 2007 年。从开始到结束，一共花了 18 年，其中有三年的停机时间。
2007 年春天，团队怀疑计算即将结束。 “我知道末日即将来临，”谢弗回忆道，“但我无法预测计算机何时会停止。程序的工作方式是将所有必须完成的工作分成几部分。有些部分很小，有些非常大。你永远不知道某件事会花一分钟还是一天。你永远无法判断。”
“如果你给我任何棋盘上有十个棋子的棋子位置，我会立即进入数据库，它会告诉我：赢、输或平局。无需思考，你就完成了。”
然而，四月的一个下午，谢弗有一种奇怪的感觉。他当时正在加州出差，和女儿一起开车沿着海岸行驶。 “当时是周末五点左右，我突然有一个冲动。我说，‘我们需要找个酒店。我需要检查一下电脑。’”我们到了一家酒店。我立即走进房间并登录。和以前一样，我做的第一件事就是检查 Chinook 目录，看看发生了什么，我立即发现所有计算机都停止了运行。
“我很生气，”他笑着说。 “当时我们正在运行 50 到 100 台计算机，当所有计算机都停止运行时，可能是出现了问题——可能是停电——需要一段时间才能将它们全部重新启动。当你谈论的是计算必须完美，你不能冒险引入错误。因此，如果它在计算过程中失败，你必须摆脱它并从头开始。
“所以我想，‘天哪，我需要一个小时才能把这一切解决好。’”我决定查看一下损坏情况。我打开了日志文件，查看了它的末尾。它的末尾只有一个字。”
这个词是田田！
田田！谢弗很久以前就将其编程到系统中，但承认他从未真正期望看到它。这意味着计算已经停止，因为没有更多的工作要做。这意味着跳棋已经解决了。
“真正让我害怕的是，Tada! 上的日期戳是下午 5 点 17 分，”他笑着说。 “当你调整时差时，当时是 5.18。所以我在计算完成后几秒钟内就登录了。不知何故，我只是知道计算即将结束。更奇怪的是，我的研究助理，他做了很多工作“这个项目，他同时登录。计算结束后不到一分钟，我们俩就登录了，并且互相交谈。我得出的结论是，互联网具有某种通灵能力。非常奇怪。”
结果如何？平局。 “跳棋比赛中双方完美发挥会导致平局，”谢弗说。 “两个完美的球员总是会打平。如果你有一个不完美的球员犯了错误，那么那个人就会输。”
当然，关键就在于“完美”这个词。这意味着虽然谢弗解决了跳棋问题，但他并没有毁掉我们大多数人的跳棋。如果你和我明天玩西洋跳棋，平局几乎不会是唯一可能的结果。我肯定会犯错误。你也可能会犯一些错误。比赛仍然令人愉快地难以预测，我们会玩得很开心。 （你可以带奶油蛋卷。）
对我来说，谢弗的最终成就就像发现了跳棋遗传密码中埋藏的东西——埋藏得很深的东西。人类玩这个游戏已经有数百年了，现在谢弗透露，一直以来，在某种程度上，它一直在等待着陷入不可避免的僵局。当然，要确定这一点，唯一的方法就是以人类从未采用过的方式玩游戏。廷斯利可能更像是机器而不是人类，一旦你达到了他的水平，他甚至可能怀疑西洋跳棋本质上是一种关于绘画的游戏，但他永远无法像奇努克那样证明这一点。他以不同的方式玩游戏。他的光辉是另一种光辉。
“这与鸟儿飞翔是一样的，”谢弗说。 “我们都知道鸟类是如何飞行的。它们就是这样进化的，而且它们的飞行能力非常好。当你获得技术并将其引入混合中时，你可以模仿鸟类飞行的方式，但技术有一定的优势。如果你要建造机翼，你可以用金属建造它们，你可以建造喷气发动机。
“计算机和智能也是一样的，由于硬件不同，能做好的事情和容易做的事情是有很大不同的。人类很擅长学习、推理之类的事情，而计算机的学习能力普遍较弱。”和推理。另一方面，他们非常擅长做偏微分方程或解决数十亿次重复的问题或记住千兆字节的数据。人类在这方面很弱。你不会记住百科全书。如果我给你一个任务，要求你做十亿次，你却不会做。”
跳棋并不是唯一一个以这种方式探索其遗传学的游戏。不是由一个长镜头。 “有很多游戏都已经解决了，”谢弗说。 “其中大多数都是无趣的——它们不是你或我会玩的那种游戏。还有一些我们希望解决的游戏。国际象棋。国际象棋是巨大的。除非有新技术，否则国际象棋将无法得到解决.用目前的技术不可能解决围棋问题。但是国际象棋、西洋跳棋、围棋：它们都是可以解决的。有些游戏带有运气成分，你无法构建一个总是会赢的程序，因为涉及到运气，例如掷骰子，但在其他地方……”
最后，谢弗和跳棋怎么样？他的计划似乎让廷斯利的比赛重新焕发了生机。奇努克的最终解决方案是否影响了谢弗自己对愤怒和称王的享受？他还在打球吗，还是知道埋藏在基因深处的抽牌毁了他的乐趣？
“哦，我从来没有玩过跳棋，”谢弗笑着说。 “我不是跳棋选手，我是国际象棋选手，记得吗？”
如果你有兴趣，你可以在线对战 Chinook。
留言