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）