喬納森·謝弗對完美跳棋遊戲的探索已經結束。這位來自埃德蒙頓阿爾伯塔大學的 50 歲計算機科學家，在十多年前與歷史上最偉大的跳棋冠軍進行了一場火的考驗後，就將人類棋手遠遠甩在了身後。
現在，在讓數十臺計算機日夜工作了 18 年——跳，跳，跳——之後，他說他已經破解了這款遊戲——讓我成為王！。“起始位置，假設雙方都沒有犯錯，結果是平局，”他說。
謝弗的證明今天在《科學》雜誌上進行了描述（並且可以在這裡免費獲取以供他人驗證），這將使跳棋成為機器迄今為止破解的最複雜的遊戲，其難度比堆疊棋子游戲“四子連線”高出一百萬倍。
支援科學新聞報道
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道 訂閱。透過購買訂閱，您將幫助確保有關塑造我們當今世界的發現和想法的具有影響力的故事的未來。
“這是一個里程碑，”IBM 位於紐約州霍桑市的 T. J. Watson 研究中心的計算機科學家、國際象棋程式“深藍”的共同發明者默裡·坎貝爾說。“他擴充套件了最先進的水平。”
儘管技術限制禁止分析八乘八棋盤上可能出現的 500千兆億種可能的排列組合中的每一種，但謝弗和他的團隊還是確定了一些招法，這些招法保證了無論競爭多麼激烈，遊戲都將以平局結束。
像任何複雜的數學證明一樣，這個結果將不得不經受嚴格的審查。但荷蘭馬斯特裡赫特大學的計算機科學家雅普·範登·赫裡克說，“它接近 100%”，他已經看到了細節。“他從未發表過任何不完全真實的東西。”
開局：如履薄冰
謝弗的奧德賽始於 20 世紀 80 年代後期。他編寫了一個頂級的國際象棋程式，但 IBM 即將投入其遠更龐大的資源到“深藍”上。“我喜歡競爭，”他說，所以他將注意力轉向了其他地方。“我天真地認為我可以破解跳棋遊戲，”他回憶道。“你可以在一分鐘內教會某人規則。”
1989 年，他帶著 16 兆位元組的計算機記憶體出發，很快發現跳棋和國際象棋一樣，可能的局面太多，無法快速找到解決方案。因此，他改變了方向，發誓要推翻傳奇跳棋冠軍馬里昂·廷斯利，後者自 1950 年以來在錦標賽中只輸過三場比賽。
1992 年，謝弗的程式“奇努克”挑戰了廷斯利，當時美國跳棋聯合會和英國跳棋協會暫時拒絕批准人機對決，廷斯利辭去了世界冠軍頭銜。
據謝弗說，廷斯利非常出色，以至於他的對手們玩起了沉悶的遊戲，希望能至少獲得平局；“奇努克”顯然為這位冠軍重新帶來了遊戲的魔力。“它下出了大膽、激進的招法——它如履薄冰，”謝弗擬人化地說道。“它會做一些人們看到後會說，‘天哪，那個程式瘋了嗎？’的事情。”
該程式實際上擊敗了廷斯利兩次，但計算機故障導致一次棄權，讓人類以 3-2 領先，還剩兩場比賽，這是一場 40 場比賽的最佳對決。謝弗讓“奇努克”採取激進的策略試圖挽回局面，結果導致計算機再次失利，並使其創造者輸掉了比賽，謝弗在他的著作《領先一步》中回憶道。
在兩年後的複賽中，廷斯利在六場平局後突然退出，理由是健康問題，這使得“奇努克”預設成為人機世界冠軍。跳棋冠軍被診斷出患有胰腺癌，不到一年後去世。
“奇努克”在 1996 年徹底擊敗了頂尖人類棋手，但謝弗對那些年的回憶卻是苦樂參半的。“事後看來，也許當時對我來說，勝利比其他事情更重要。我有點痴迷，”他說。“我的妻子會說不止有點痴迷。”
殘局：讓我成為王！
在本世紀初，他認為計算機速度和記憶體的提高已使他實現破解遊戲的目標觸手可及。解決方案的第一個部分建立在廷斯利時代開始的工作之上。阿爾伯塔大學的研究人員詳盡地檢查了最後階段的比賽，針對任何 10 個或更少棋子的排列組合，確定了 3.9 x 1013 個位置中的哪些位置是贏、輸還是平局。
接下來，他們確定了 19 個代表性的開局序列，並搜尋了後續招法，以找到最容易找到的與最終位置（贏、輸或平局）的連線。為了節省時間，他們忽略了毫無意義的來回招法或那些不會將平局變成勝利的招法。
如果可能的招法序列像樹一樣分支，該小組發現主要分支之後的主要分支都導致平局。謝弗說，4 月 27 日，該程式追蹤了最後的分支，完成了他 18 年的任務。他得到了他的王。
結果本身並不令人驚訝。“我們預計這應該是平局，因為在最高水平的比賽中，有很多比賽以平局結束，”赫裡克說。
沃森的坎貝爾說，證明所做的，是突出了有條不紊地逐一檢查結果的力量。最強大的國際象棋程式，如“深藍”和“深弗裡茨”，透過將快速的數字運算與從多年的人類對弈中獲得的經驗法則相結合，擊敗了世界冠軍。
坎貝爾指出，跳棋破解器相對來說比較笨。“它所知道的只是這步棋贏了，或者這步棋沒有贏，”他說。“它無法‘解釋’它知道什麼。”
出於這個原因，赫裡克說，在研究人員弄清楚如何將結果轉化為人類思維可以遵循的規則或程式之前，這些結果對棋手不會有太大幫助——這本身就是一個重大挑戰。
下一步棋？
那麼，下一個將被計算機攻克的遊戲是什麼呢？謝弗及其同事推測將是奧賽羅，一種八乘八的翻轉棋子游戲。國際象棋提出了一個更強大的挑戰，但研究人員“正處於思考”破解它的領域，赫裡克稱之為“一項巨大的成就”。
遊戲的巨大白色鯨魚仍然是亞洲的消遣圍棋。儘管程式最近在九乘九的棋盤上變得可以與大師們競爭，但在完整的 19 乘 19 的遊戲中，它們仍然是無力的。
謝弗是一位真正的遊戲愛好者——他的兩條狗分別名為“拼字遊戲”和“拉密紙牌”——計劃在下週的一場 500 手牌的比賽中，讓他的撲克程式對抗兩位頂尖牌手，這場比賽旨在最大限度地減少運氣的成分。
自從專注於世界冠軍賽以來，他已經走了很長一段路。無論未來的遊戲如何，他都可以對當前的勝利感到滿意。“十八年後，”他說，“我終於完成了。”