最后的消遣
2012-7
上海科技教育出版社
马丁·加德纳
无
马丁·加德纳是美国著名的数学趣题大师，为《科学美国人》杂志撰写专栏文章几乎成了他的专利，从1956年到1986年，长达30年之久。《最后的消遣》是他第15本，也是最后一本集子，包括了平面宇宙，鸡蛋趣话，扭结拓扑学和有向图等各种有趣的问题，是这位已故的数学大师留给我们的最后一本数学财富。
序言第1章 小素数的强规律第2章 跳棋游戏，第一部分第3章 跳棋游戏，第二部分第4章 模数算术与赫默的邪恶女巫第5章 拉维尼娅寻找公寓及其他趣题第6章 斯科特·金的对称作品第7章 抛物线第8章 非欧几何第9章 选举的数学第10章 一个环面悖论与其他趣题第11章 最小斯坦纳树第12章 三值图，蛇鲨与薄俱魔进阶读物
早就有人指出，同一棋盘上可以同时进行互不相关的两盘跳棋比赛，其 一 在黑格上玩，另一盘在白格上下。一个王棋最多能跳过对方的几只王棋？答案是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）与约翰逊（David Joh on）。罗杰斯（John Roge ，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
无