Turochamp
| Turochamp | |
|---|---|
 | |
| 类型 | 电脑象棋 |
| 开发商 | 艾伦·图灵、戴维·高恩·钱珀瑙恩 |
| 模式 | 单人 |
Turochamp是艾伦·图灵和戴维·高恩·钱珀瑙恩于1948年开发的国际象棋程序，作为计算机科学和机器学习研究的一部分而创建。Turochamp会以低难度方式与人类棋手对弈，期间它会计算所有潜在的棋步，对手所有可能采取的走棋，以及它认为相当重要的后几步棋。接着，它会为每个状况分配点值，并选择最高点值的状况来移动。
Turochamp是已知最早进入开发阶段的电脑游戏，但由于算法过于复杂，当时的早期电脑（如自动计算机）无法运行，因此图灵和钱珀瑙恩从未完成。身在曼彻斯特的图灵试图将程序转换为1951年费兰提1型可执行代码，却未能如愿。1952年夏天，图灵以此程序与计算机科学家艾力克·格连尼对弈，并逐步手动执行它。可惜的是，到了1954年图灵辞世之时，程序仍无法在电脑上实际运行。钱珀瑙恩没有继续这个项目，也没有保留原始的程序设计。虽然程序从未在电脑上运行，但它是首个国际象棋程序的候选者；同一时期还有数个国际象棋程序被开发或提出，包括图灵尝试在费兰提1型上运行但未成功的另一程序。1951年，首个国际象棋程序成功运行。它直接受到Turochamp启发，也是为费兰提1型而开发，但只能解决“两步杀”残局。2012年，Turochamp再现于艾伦·图灵百年纪念会议之中，国际象棋特级大师加里·基莫维奇·卡斯帕罗夫与其对弈，并在会议上作主题演讲。
玩法
[编辑]
Turochamp会把玩家的棋步视为输入，并输出棋步作回应，借此模拟与玩家的国际象棋棋局[1][2][3]。程序算法使用启发法来决定最佳走棋，计算它所有潜在下子，然后依次计算对方所有可能的应对，以及相当重要的后几步棋，如吃掉没有保护的棋子、反吃、以低价值棋子交换对手高价值棋子等[1][2][3]。然后，程序会为每个结果状态分配点值，并按照极小化极大算法，选择最高点值的结果来移动[1][2][3]。点值高低根据数个标准来决定，包括每个棋子的移动能力和安全性，己方被将死的可能性，玩家棋子的价值（如果被吃掉），以及其他几项因素[4]。不同走棋有不同点值：例如，吃掉皇后得10分，而吃掉兵只得1分，另外根据棋盘的布局，国王被将军得1分或半分[4]。按照钱珀瑙恩的说法，程序算法主要围绕是否吃子而设计[1][4]；而据图灵所指，由此产生的游戏玩法产生了低水平国际象棋棋局，认为此与他自称的平均游戏等级水平相称[1][4]。
历史
[编辑]艾伦·图灵是英国数学家、计算机科学家、逻辑学家、密码分析家、哲学家、数理生物学家[5]。图灵对理论计算机科学的发展有很大影响，他透过图灵机对算法和运算的概念定形，而此机器可以说是通用电脑的模型[6][7][8]。图灵被广泛认为是理论计算机科学和人工智能之父[9]。自1941年起，图灵在布莱切利园从事战时密码分析，期间他开始与同事讨论机器能够下棋或执行其他“智能”任务的可能性，以及电脑利用启发法或算法搜索所有潜在解决方案来解决问题的构想[10][11]。图灵部分密码分析工作在炸弹机上进行，而它便是透过搜索解决方案可能性的运算模型来完成[11]。二战期间，他继续与同事讨论这个想法，又在1944年与经济统计学家戴维·高恩·钱珀瑙恩探讨[10][12]。到了1945年，图灵确信一台能够执行一般计算的机器，理论上能够克隆人脑能做的任何事情，包括下棋[10][12]。
二战结束后，图灵在国家物理实验室工作，并设计了自动计算机，属首批存储过程式电脑的设计。1946年，他为国家物理实验室撰写了题为《电子计算机计划》的报告，描述了他打算把自动计算机应用在数个项目上，其中一项是下棋程序。次年，他在伦敦数学学会演讲，并提出了一个想法：编程下棋的机器可以自我学习并借此获得经验。1948年，他再为国家物理实验室撰写报告，题为《智能机械》，当中提及了模仿国际象棋的形式。[13]
1948年夏末，图灵与当时的剑桥大学国王学院同僚钱珀瑙恩发明了一套理论规则系统，为国际象棋棋局决定下一步棋[1]。他们设计了一个程序来实行遵循这些规则的算法，但它过于复杂，无法在自动计算机或当时任何电脑上运行[1]。二人把程序命名为“Turochamp”，源于他们姓氏的组合，但它有时会被错误地报道为“Turbochamp”[13][14]。钱珀瑙恩指出，其妻与绰号“造纸机”的程序进行了一场模拟游戏，结果落败[13][15]。身处曼彻斯特的图灵尝试把程序转换为1951年费兰提1型可执行代码，惟代码过于复杂而未能成功[14]。作家杰克·科普兰著有数本关于图灵的书籍；据他所说，图灵并不担心程序无法运行，因为他相信电脑的运算速度和精密程度很快就会提高，使之成为可能[16]。1952年夏天，图灵以此程序与计算机科学家艾力克·格连尼对弈，并逐步手动执行它[14]。这场棋局获记录下来，程序每下一步都须花费30分钟来评估，最终它在29步内败阵[14]。虽然这场棋局证明该程序可以与人类进行一场完整的比赛，但到了1954年图灵辞世之时，它仍无法在电脑上实际运行[14]。
影响
[编辑]虽然Turochamp从未在电脑上运行，但它是首个国际象棋程序的候选者[13][17][18][19]。大约在同一时间也有数个国际象棋程序被开发或提出，例如克劳德·香农的1950年文章《为电脑设计下棋程序》、康拉德·楚泽在1941年至1945年间以他提出的编程语言Plankalkül所开发的国际象棋程序、唐纳德·米奇和尚恩·怀利合作开发的“Machiavelli”，其中图灵也尝试在费兰提1型上运行后者，但结果正如Turochamp一样失败[13][17][18][19]。1951年11月，费兰提员工迪特里希·普林茨受到图灵开发Turochamp的事迹所启发，因而为费兰提1型开发了首个可运行的国际象棋计算机程序，而且它能够解决“两步杀”残局[1]。
图灵和钱珀瑙恩编写的原始代码和算法没有被保留下来。1980年，钱珀瑙恩描述了Turochamp的运作模式，但他始终无法回忆起游戏规则所有细节[1][16]。2012年，国际象棋特级大师、前国际象棋世界冠军加里·基莫维奇·卡斯帕罗夫与另一位棋手佛雷德利·弗里德尔根据游戏算法的描述，开发了全新版本的Turochamp，并把它视为娱乐象征[20]。他们开发的最初版本无法重现图灵和格连尼的棋局，因此二人咨询了数字电脑象棋专家以及和图灵同时代的人，包括1983年国际象棋电脑“Belle”及UNIX操作系统的开发者肯·汤普逊[20]。直到两人咨询了唐纳德·米奇，他们才找到程序出现偏差的合理解释，米奇也明言图灵并不关心如何准确地计算出Turochamp的最佳走棋[20]。考虑到这一点，他们能够证明从棋局的第一步开始，图灵就错误地偏离了看似次优的下子，而没有计算出它们的点值[20]。卡斯帕罗夫在2012年6月22日至25日举办的艾伦·图灵百年纪念会议之中与Turochamp对弈，他用了16步便胜出棋局[20]。后来，卡斯帕罗夫赞扬该程序在历史上的地位，以及图灵在没有电脑的情况下编写算法的这项“杰出成就”[21]。
另见
[编辑]参考资料
[编辑]- ^ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 Copeland 2004，第563-564页.
- ^ 2.0 2.1 2.2 DAVID CHAMPERNOWNE (1912-2000). ICGA Journal. 2000-12-01, 23 (4): 262 [2022-08-21]. doi:10.3233/ICG-2000-23419. （原始内容存档于2022-08-21） （英语）.
- ^ 3.0 3.1 3.2 Cochlin, Daniel. Kasparov versus Turing. University of Manchester. 2012-06-26 [2022-08-20]. （原始内容存档于2022-05-31） （英语）.
- ^ 4.0 4.1 4.2 4.3 Levy & Newborn 2009，第35页.
- ^ Turing, Alan Mathison
. Who's Who. 2007-12-01 [2022-08-21]. doi:10.1093/ww/9780199540884.013.U243891. （原始内容存档于2022-08-22） （英语）.
- ^ Newman, Maxwell Herman Alexander. Alan Mathison Turing, 1912-1954. Biographical Memoirs of Fellows of the Royal Society. 1955-11-01, 1: 253–263 [2022-08-21]. doi:10.1098/rsbm.1955.0019. （原始内容存档于2022-08-21） （英语）.
- ^ Gray, Paul. Computer Scientist: ALAN TURING. Time. 1999-03-29 [2022-08-21]. （原始内容存档于2021-10-16） （英语）.
- ^ Sipser 2006，第37页.
- ^ Cooper & Leeuwen 2013，第481-485页.
- ^ 10.0 10.1 10.2 Hodges, Andrew. Alan Turing. Stanford Encyclopedia of Philosophy. 2013-09-30 [2022-08-21]. （原始内容存档于2022-08-01） （英语）.
- ^ 11.0 11.1 Copeland, Jack; Proudfoot, Diane. Alan Turing, Founder of the Modern Computer. The Rutherford Journal. 2012, 1 (4) [2022-08-21]. ISSN 1177-1380. （原始内容存档于2022-01-24） （英语）.
- ^ 12.0 12.1 Hodges 2014，第488页.
- ^ 13.0 13.1 13.2 13.3 13.4 Cooper & Leeuwen 2013，第644-650页.
- ^ 14.0 14.1 14.2 14.3 14.4 Clark, Liat; Steadman, Ian. Remembering Alan Turing: from codebreaking to AI, Turing made the world what it is today. Wired. 2017-06-07 [2022-08-21]. （原始内容存档于2022-06-19） （英语）.
- ^ Kasparov, Garry; Friedel, Frederic. Reconstructing Turing's "paper machine". ICGA Journal. 2018, 40 (2): 105–112 [2022-08-21]. ISSN 1389-6911. （原始内容存档于2022-08-21） （英语）.
- ^ 16.0 16.1 Oppy & Trakakis 2011，第13-14页.
- ^ 17.0 17.1 Dasgupta 2014，第193页.
- ^ 18.0 18.1 Turing 2015，Chapter 9.
- ^ 19.0 19.1 Atkinson 1998，第39页.
- ^ 20.0 20.1 20.2 20.3 20.4 Friedel, Frederic. Reconstructing Turing's "Paper Machine". ChaseBase. 2017-09-23 [2022-08-21]. （原始内容存档于2022-06-21） （英语）.
- ^ Parnell, Brid-Aine. Chess algorithm written by Alan Turing goes up against Kasparov. The Register. 2012-06-26 [2022-08-21]. （原始内容存档于2022-08-08） （英语）.
- 文献
- Hodges, Andrew. Alan Turing: The Enigma. Princeton University Press. 2014. ISBN 978-1-4008-6512-3 （英语）.
- Cooper, S. Barry; Leeuwen, Jan van (编). Alan Turing: His Work and Impact. Elsevier. 2013. ISBN 978-0-12-386980-7 （英语）.
- Oppy, Graham; Trakakis, Nick. The Antipodean Philosopher. Lexington Books. 2011. ISBN 978-0-7391-6655-0 （英语）.
- Atkinson, George W. Chess and Machine Intuition. Intellect Books. 1998. ISBN 978-1-871516-44-9 （英语）.
- Copeland, B. Jack. The Essential Turing. Oxford University Press. 2004. ISBN 978-0-19-825079-1 （英语）.
- Levy, David; Newborn, Monty. How Computers Play Chess. Ishi Press. 2009. ISBN 978-4-87187-801-2 （英语）.
- Sipser, Michael. Introduction to the Theory of Computation. PWS Publishing. 2006. ISBN 978-0-534-95097-2 （英语）.
- Dasgupta, Subrata. It Began with Babbage: The Genesis of Computer Science. Oxford University Press. 2014. ISBN 978-0-19-930941-2 （英语）.
- Turing, Dermot. Prof: Alan Turing Decoded. The History Press. 2015. ISBN 978-0-7509-6524-8 （英语）.
外部链接
[编辑]- 加里·基莫维奇·卡斯帕罗夫与Turochamp对弈之视频 （页面存档备份，存于互联网档案馆）（英文）
- 艾伦·图灵与艾力克·格连尼对弈（1952年），“图灵测试” （页面存档备份，存于互联网档案馆）（英文）
- 加里·基莫维奇·卡斯帕罗夫与Turochamp对弈（2012年） （页面存档备份，存于互联网档案馆）（英文）
- GitHub上的PyTuroChamp页面 — Turochamp开源代码（Python）