最后的消遣/科学美国人趣味数学集锦

作者简介

内容简介

早就有人指出，同一棋盘上可以同时进行互不相关的两盘跳棋比赛，其 一 在黑格上玩，另一盘在白格上下。 一个王棋*多能跳过对方的几只王棋？答案是9只，排列成3x3的正方 形。 两只王棋通常能击败一只王棋？这是众所周知的。并非为人熟知的是3 只 王棋也能击败对方的2只王棋，即便它们处在双角隅的位置。一般来说，3只 王 棋战胜2只王棋的*好办法是迫使对方交换吃子？从而变成两对一的局势。 给盲人使用的棋盘与棋子都已投放市场。为了使棋子就位，方格是凹的 。 双方的棋子，一方的呈圆形，另一方的则呈方形。 有位名叫施瓦茨的读者提请我注意，在4x4微型棋盘上，2只王棋无法击 败对方在双角隅游走的一只王棋。为了实施人们熟知的战术，棋盘的大小至 少 应为6x6。施瓦茨还发现？在3只王棋与2只占角王棋对抗时，如果是在标准 的8x8棋盘上，前者可以稳*胜券，然而在*大的棋盘上，双方将打成平局 。 时任美国**跳棋协会名誉秘书的基希(Ike Kisch)写信告诉我，在10x 10棋盘上玩的“波兰跳棋”现已*名为“**跳棋”。按照基希的说法，波 兰跳棋 这个名称起源于法国，时间大约在1750年左右，其时有一位波兰绅士引进了 100个方格的棋盘。后来它在法国流行起来，并迅速传播到其他**，尤其 在俄 罗斯与荷兰*加*人欢迎。 对熟悉计算机复杂性的读者来说，现已证明，扩大到2nx2n棋盘上的跳 棋，同扩大的围棋一样，都具有“P空间难度”。这就意味着，类似于象棋 或围棋 的其他棋类游戏在扩大到nxn棋盘时？可以用与之等价的跳棋对局来模拟， 其 时棋盘的尺寸将是n的一个多项式函数。跳棋有P空间难度的证明，是由以色 列学者弗兰克尔作出的，他的合作者是美国贝尔实验室的加里(Michael Garey)与约翰逊(D**id Johnson)。 罗杰斯(John Rogers，1829-1904年)是早年美国的一位有名的雕塑家， 他 的作品“巴黎的石膏像”已成为当地一景，为他赢得了他那个时代的“三维 空间 的罗克韦尔(Norman Rockwell)”美名。他*为人称道的作品是“农场里的 跳棋 手”。仅在美国就售出了5000件这一作品的复制品。1979年，罗杰斯纪念协 会 曾经制造并出售了这一艺术作品的青铜复制件，在全世界限售650件(见图 3.2)。图中，那位年轻的棋手正得意洋洋地指着他的致胜一步。罗杰斯原先 制作 的“巴黎石膏像”的许多复制品经常出现在古董商店与展览会上，通常是在 有 破损的情况下，根据其品相，售价从500美元到超过1000美元。 人工智能的学科创建者们曾经由于预言失灵而声名狼藉，当时他们曾扬 言，**象棋的计算机程序将击败所有的象棋大师而夺得世界**。类似地 ， 过分乐观的预言在跳棋界也不乏先例。例如兰德公司的贝尔曼曾发表过一篇 论文《论动态规划在象棋与跳棋中决定*优策略时的应用》(见《美国科学 院会 议录》第53卷，1965年2月，第244—247页)。他在论文中写道：“在有了* 大 型的电子计算机之后……看来可以十拿九稳地预言：10年之内？跳棋将成为 一 种**可以事先决定的游戏。” 从贝尔曼的轻率预言出口之时算起，30多年过去了，尽管跳棋程序改进 得 **之快，然而跳棋仍然远远不能认为已能被事先决定。当我在1996年撰写 本文时，已有好几个性能很好的跳棋程序可以用钱买到，其中***的程序 名 为CHINOOK，研发者是加拿大阿尔伯特省埃德蒙顿市阿尔伯特大学的三位计 算机科学家谢弗(Jonathan Schaeffer)、莱克(Bobert Lake)、卢(Paul Lu) ，协作 者还有两位跳棋专家布赖恩特(Martin Bryant)和特雷洛尔(Norman Treloar)。 在1996年谢弗、莱克、卢、布赖恩特四人合写的《CHINHIK——人机对话世 界 跳棋**》一书中，故事被作了戏剧性的渲染。另一本由谢弗执笔编写的关 于 CHINOOK的非技术书，也已被斯普林格出版社列入1997年的出版计划。 1990年，廷斯利在表演赛中同CHINOOK程序**进行了交锋，他赢了一 局，平13局，一局未输。1992年，他同该程序在伦敦正式交锋。廷斯利赢4 局， 输2局，平33局。输的这两局只是廷斯利长达42年的跳棋生涯中输掉的第6 局与第7局！ 1994年，再次进行了交锋。CHINOOK程序已经过大大改进，增加了几十 种新的秘密的开局“妙着”，它有能力搜索博弈树的所有分支，深度达到21 步 以上。交战情况是，前六局都打成平局。后来，廷斯利退出了比赛，他说要 到医 院去检查身体。他被确诊为患上癌症，在1995年去世。终其一生，他是一位 打 不败的世界**。他的退出使CHINOOK获得了世界跳棋**的称号，但问题 依然悬而未决：廷斯利与CHINOOK，究竟谁是*好的跳棋手？ 由于同跳棋大师拉弗蒂(Don Lafferty)打成平手，CHINOOK程序保住了 它 的**称号。1995年，双方再次较量，程序仍是赢家，双方的交战结果是： 程序 胜一局，平31局，一局未失。 目前的人类世界**是金(Ron King)。迄今为止，他尚未同CHINOOK进 行过正式交锋。不过谢弗与其助手们满怀信心地认为，廷斯利死后，世上已 经 没有任何棋手能打得过CHIN00K了。目前，世界上*拔尖的四位**高手排 名如下：CHINOOK 2712分，金2632分，朗2631分，拉弗蒂2625分。 CHINOOK程序几乎天天都在改进，它的编写者们真心希望“解决”一切 问 题，直到它能下出**的棋局。 P40-43