AlphaGo再進化,AlphaZero輕取國際象棋冠軍程式

Photo Credit: David Lapetina, CC BY-SA 3.0
你為什麼需要這則新聞

從戰勝人類世界冠軍的AlphaGo,到無須人類知識自學下棋的AlphaGo Zero,現在DeepMind團隊已發展出可應用到國際象棋及日本將棋的AlphaZero,更擊敗了這兩領域的冠軍程式。

AlphaGo, AlphaGo Zero, Alpha Zero

2016年3月,Google棋下的人工智能公司DeepMind,派出使用深度學習技術的程式AlphaGo跟韓國圍棋九段棋士李世乭對奕,並在5局中以4勝1負之成績擊敗對方,成為圍棋史上首次有電腦程式擊敗人類世界冠軍。

去年底開始,AlphaGo的新版本以Master之名秘密在網上跟棋手對奕,未嘗一敗,最終由AlphaGo重要推手的黃士傑博士揭露身分。這個更強大的AlphaGo Master亦於今年5月跟世界排名第一的九段棋手柯潔對奕,結果以3比0勝出。

今年10月,DeepMind在期刊《自然》發表研究,宣布AlphaGo已被新版本超越。以往AlphaGo需要先從人類的棋譜學習下棋,但新版的AlphaGo Zero只需要從基本規則出發,跟自己對奕,三天就達到擊敗李世乭版本的AlphaGo Lee水平,21天後已超越擊敗柯潔的AlphaGo Master,40天內擊敗所有其他版本的AlphaGo,成為最佳棋手。

本星期二(12月5日)DeepMind研究團隊在論文預印本存庫arXiv貼出論文,宣布他們的移除了AlphaGo Zero專門為圍棋而設的限制,AlphaZero採用跟AlphaGo Zero類似的強化學習(reinforcement larning)技術,但其演算法不僅應用在圍棋之上,更可以用來學習國際象際和將棋,無需任何領域知識(domain knowledge),只需要知道遊戲規則。

更多限制的棋

1997年,IBM的「深藍」(Deep Blue)已在國際象棋上擊敗了當時的世界冠軍卡斯帕洛夫(Garry Kasparov),事隔20年,現時電腦程式的棋力已遠勝人類,2016年的世界冠軍為Stockfish。

從運算複雜度而言,將棋比國際象棋更難︰使用更大的棋盤,而且捕捉到對方的棋後可以放在棋盤上任何位置,以致棋局變化更大。目前最強的將棋程式Elmo,也是近來才擊敗人類世界冠軍。

無類是國際象棋抑或將棋,這類下棋程式得力於大規模搜索、大量啟發法(heuristic),以及特定用於國際象棋或將棋的設計。

研究團隊指出,圍棋適合以神經網絡處理,因為其規則不受平移影響,並能對應棋盤上的鄰點去定義「自由度」,也是旋轉及鏡射對稱,方便處理數據。此外下子規則簡單——可以放在棋盤上任何位置——結果亦是簡單的勝或負,容易用來訓練神經網絡。

相比之下,國際象棋和將棋較不適合AlphaGo的神經網絡架構,因為規則受位置影響、不對稱,亦包含長距離的互動。下棋時,並非所有位置都可以合法走動,而且有機會出現和局,亦有人相信最優解是和局。

後浪推前浪

團隊將AlphaZero的演算法分別應用到國際象棋、將棋和圍棋三種遊戲上,使用相同設定但各自獨立訓練。不過2小時,AlphaZero走了11萬步棋後,就在將棋上超越了Elmo。在國際象棋方面,AlphaZero也僅需要4小時,走了30萬步棋便超越Stockfish。至於AlphaGo的強項圍棋,AlphaZero用了8小時(16.5萬步棋)去超越擊敗李世乭的AlphaGo Lee。

他們又把完成訓練的AlphaZero跟Stockfish、Elmo及訓練了三天的AlphaGo Zero對奕,Stockfish及Elmo均以最強水平應戰,使用64線程及1GB大小的散列表(hash table);AlphaZero及AlphaGo Zero都用4個張量處理器(TPU)。

AlphaZero分別跟三個程式對奕100局,執黑棋白棋各佔一半。國際象棋中先行的白方AlphaZero跟Stockfish勝和各半,黑方AlphaZero成績則為3勝47和,勝出率28%但未嘗一敗。跟Elmo的將棋比賽中,先行的AlphaGo成績為47勝三負,後手的AlphaGo則43勝2和5負,總計勝出率高達9成。至於跟AlphaGo Zero的圍棋比賽,AlphaZero執白棋先行時成績為31勝19負,執黑棋時則29勝21負,雙方差距較小但仍明顯佔優,整體勝出率為6成。

更有效率

除了對賽成績外,團隊亦分析了AlphaZero所用的「蒙地卡羅樹搜尋法」(MCTS)表現,並跟Stockfish和Elmo的alpha-beta剪枝法比較。整體而言,AlphaZero搜尋的步數遠低於其餘兩個程式,相差近千倍︰在國際象棋比賽中,AlphaZero每秒搜尋了8萬個位置,Stockfish數字為7,000萬;在將棋比賽中,AlphaZero每秒搜尋4萬個位置,Elmo數字為3,500萬。團隊認為AlphaZero的MCTS隨考慮時間增長的效率,比起alpha-beta搜尋法優勝,質疑長久以來認為此方法在有關領域較優勝的信念。

最後,團隊又檢視了國際險棋中人類棋手最常用的開局方式——在網上數據庫用上10萬次的開局走法——發現當中每一款都由AlphaZero在自行對奕訓練期間,獨立發現並頻繁使用。在每一款開局走法中,AlphaZero亦擊敗了Stockfish,顯示它掌握了廣泛的下棋技巧。

論文總結指出,比起下圍棋的AlphaGo,AlphaZero是個應用更廣泛的強化學習演算法,能夠在數小時內取得驚人成果,更有效尋搜位置,而且只需要遊戲規則,不依賴其他特定的領域知識。而且在沒有特別修改下,AlphaZero可以應用到更複雜的將棋和國際象棋,並於數小時內超越原本最強的程式。

解決現實難題?

DeepMind行政總裁Demis Hassabis曾表示,AlphaGo Zero的未來版本可以協助解決多項科學難題,由設計新藥到發現新物料等。今次AlphaZero明顯應用更廣泛,不過要達至上述目標,相信尚有一大段距離。

牛津大學的電腦科學教授Michael Wooldridge提醒,DeepMind團隊今次的結果符合他們過往表現,令人印象深刻,但三款遊戲都相對「封閉」,規則較為有限而且可知。如要在現實世界應用,需要處理未知的情況,遠遠複雜得多。他認為當DeepMind開始轉向較為「開放」的問題時,人工智能領域的發展會變得更有趣。

相關文章︰

資料來源︰

或許你會想看
更多『新聞』文章 更多『科技』文章 更多『Kayue』文章
Loader