五天前在穀歌總部舉辦的一場國際象棋比賽, DeepMind聯合創始人德米斯·哈薩比斯(左三)笑開了花
編者按:20年前的1997年, 超級電腦“深藍”在比賽中擊敗Garry Kasparov,
2017年12月5日, 穀歌DeepMind團隊一篇名為Mastering Chess and Shogi by Self-Play with aGeneral Reinforcement Learning Algorithm的學術論文悄然發表。
在論文中, 團隊證明在除了遊戲規則外沒有其他任何相應資料的情況下, 他們的程式AlphaZero能通過泛化強化學習演算法在4個小時內學會國際象棋、在2個小時內學會日本將棋、在8個小時內學會圍棋, 並擊敗相應領域的“世界冠軍”。 不少觀看了AlphaZero和國際象棋“冠軍”程式Stockfish對局記錄的網友紛紛表示:
這不是簡單的“毆打”, 這簡直是拆遷!
論文概要在摘要中, DeepMind團隊是這樣介紹AlphaZero的:
國際象棋是人工智慧史上研究最廣泛的領域, 這個龐大的項目基於複雜搜索技術的組合、特定領域的適應性調整以及數十年來經人類專家提煉所得的評估函數。
事實上, 電腦在象棋領域的研究歷史幾乎和電腦科學本身一樣古老, 巴貝奇、圖靈、香農、馮·諾依曼, 這些大師都曾為國際象棋的分析和下法設計過硬體、演算法和理論。 之後, 國際象棋也一度成為一代人工智慧領域研究人員心目中的重大挑戰, 為了讓機器能承受超越人類極限的計算任務,
然而, 到目前為止, 他們取得的成果還只限於這個狹窄的棋牌遊戲領域, 如果沒有其他人的大力投入, 它們無法被推廣到其他問題上。 而DeepMind的這個嘗試正是對這種局面的一個突破。
AlphaZero簡介
AlphaZero的目的是利用深度學習網路和蒙特卡洛樹搜索演算法進行自我對弈, 再依靠評分系統不斷訓練自己在棋局中佔據優勢, 最後戰勝對手。 它的設計主要圍繞以下幾方面:
用神經網路體系類比網格狀的棋盤, 其中輸入為棋子座標, 輸出為動作(棋子移動方式), 它們被構建為多個層。
DeepMind為AlphaZero提供了非常翔實的遊戲規則, 演算法能利用蒙特卡洛樹搜索類比任何規則允許的下法來結束棋局,
這些遊戲規則也用於對輸入層(即castling, 重複而無演進)和輸出層(棋子移動、叫吃和將棋drop)的編碼;
演算法會用合理下法的特定數量等比例降低搜索雜訊;
如果棋局有時長/步數限制, AlphaZero會在進行國際象棋比賽和將棋比賽時限制自己的最高步數來獲得一個計算到的結果;而圍棋則用Tromp-Taylor規則來評分。
正如摘要中提到的, 除了必要的遊戲規則外, 演算法沒有任何如視頻、棋譜、定式等遊戲相關的學習資料。
AlphaZero演算法原理
在論文中, DeepMind並沒有給出AlphaZero的具體模型設計, 只表示它是AlphaGo Zero演算法的通用版本, 兩者都不再借用傳統手工搜集整理的資料和遊戲的特定技巧玩法進行學習, 而是依靠DNN和“白板”強化學習演算法不斷自我對弈。
DNN
AlphaZero使用的深度神經網路包含一個參數θ:
(p, v) = fθ(s)
其中輸入s為棋子的座標,神經網路根據每個動作a輸出具有分量
pa = Pr(a|s)
的移動概率p的向量,而v則是根據座標s估計的預期結果z的標量值:
v ≈ E[z|s].
AlphaZero能在自學中學習移動概率計算和預期結果估計,並將其用來指導搜索。
蒙特卡洛樹搜索演算法
不同于利用遊戲專用資料的alpha-beta搜索,AlphaZero用的是蒙特卡洛樹搜索演算法(MCTS),它的每一次搜索都包含一系列從根節點到葉子節點最後貫穿整棵樹的自我對弈模擬。而每次類比會通過從每個狀態s中選擇一個低訪問次數、高移動概率、高價值動作a來繼續推進(衡量標準為s中a類比的葉子節點狀態平均值)。最後搜索返回的是一個表示移動概率分佈的向量π,它在比例上和貪婪性上都與訪問根節點的次數相關。
強化學習
DNN中的參數θ經隨機初始化後,AlphaZero會通過一種自我對弈的強化學習演算法來進行訓練。棋局中,蒙特卡洛樹搜索演算法會對應給出下棋雙方的下一步動作:at ∼ πt。棋局結束後,演算法根據遊戲規則對棋子位置sT計算表現評分z:-1為負;0為平;+1為勝。為了降低預測結果vt和評分z之間的誤差,同時使動作向量pt和搜索概率πt更接近,參數θ會做重新調整。具體來說,θ可由以下算式計算得出:
其中c為控制L2權重正則化水準的參數。調整後,更新的參數會用於之後的自我對弈棋局。
AlphaZero和AlphaGo Zero的區別
DeepMind也在論文中介紹了AlphaZero和AlphaGo Zero的一些不同點,它們主要表現在以下這幾個方面:
AlphaGo Zero只會考慮輸/贏兩種結果,因此它會不斷估計並優化勝率;而AlphaZero會估計和優化比賽結果,並考慮平局或其他潛在的情況。
由於無論怎麼調整棋局方位,圍棋的規則都不會發生變化,AlphaZero沿用了AlphaGo Zero的方法,會通過增加一些對稱資料強化訓練,並在蒙特卡洛樹搜索期間隨機調整棋盤角度進行評估。但考慮到國際象棋和將棋的規則是不對稱的,AlphaZero沒有增加訓練資料,在搜索時也不會改變棋盤位置。
AlphaGo Zero演算法提升自我的方式是不斷反覆運算,它會計算每一次訓練的表現,如果後一次比前一次更優,那後者會代替前者進行之後的自我對弈。而AlphaZero從頭到尾只有一個神經網路,它只通過更新參數來完成自我更新,省去了評分步驟,也不統計最佳狀態。
AlphaGo Zero通過貝葉斯優化調整搜索的超參數,而AlphaZero則重複使用相同的超參數,無需針對特定遊戲做改變。當然,這一點也有例外,就是AlphaZero為了保證搜索會把雜訊添加進之前的動作中,它與合理下法的數量成正比。
棋局表現在展示成果前,DeepMind先在論文中評價了圍棋、國際象棋、將棋對神經網路架構的適應性。他們指出,由於規則的高度對稱性、動作空間簡單、比賽結果只有輸和贏,圍棋是最適合神經網路訓練的。而國際象棋和將棋棋盤規則不對稱,棋子移動方式各異,尤其是將棋還允許被吃掉的棋子重返戰場,因此引入一些新的設計和思考十分必要。事實上,國際象棋和將棋都有平局的結果,尤其是國際象棋還把平局視為一種最優解,這都對AlphaZero提出了新的挑戰。
AlphaZero國際象棋、將棋、圍棋百場對局結果
在這次實驗中,AlphaZero的“世界冠軍”對手們分別是2016年TCEC冠軍、今年在51場比賽中保持不敗戰績的國際象棋AI程式Stockfish,2017年CSA世界冠軍、日本將棋AI程式Elmo,以及DeepMind上一篇論文的主角、只訓練了3天就超越AlphaGo(李世石版)的圍棋AI程式AG0 3(AlphaGo Zero3天訓練版)。
如上圖所示,AlphaZero在三個遊戲中都佔據優勢,以總成績28勝72平、90勝2平8負和60勝40負的戰績鎖定勝局。但我們也可以發現,執黑執白似乎對AlphaZero的表現有一定影響。執白棋時,它分別以25勝25平、43勝2平5負在國際象棋和將棋比賽中戰勝對手;而執黑棋時,它在將棋上以47勝3負大勝Elmo,但在國際象棋上則以3勝47平險勝。可能是因為“師出同門”,AlphaZero在圍棋上表現穩定,和AG0 3相比進步也很明顯。
訓練落子70萬步後,AlphaZero和其他“世界冠軍”的Elo評分對比
雖然對局結果中似乎出現了一些有關黑白棋公平性上的發現,但毫無疑問的一點是,AlphaZero利用這300場比賽證明了它的實力,而這一切是在除了比賽規則外沒有任何預備的訓練資料、訓練時間只壓縮在24小時內的情況下實現的。
上圖是論文中的一幅評分圖,暫且拋開評分可信度,通過對比資料我們可以發現,AlphaZero在訓練到30萬步時已經超越了Stockfish,此時用時約為4小時。而在將棋訓練中,AlphaZero僅用2小時、11萬步就超越了Elmo。在面對棋盤情況更複雜的圍棋時,演算法在16.5萬步時和戰勝李世石的AlphaGo打成平手(8小時),並在之後一路上升。
遺憾的是,雖然DeepMind展示了AlphaZero和AG0 3的對局成績,但是並沒有在論文中說明訓練了多長時間。
AlphaZero對國際象棋部分下法的評價
是RL還是TPU?雖然AlphaZero在技術上取得的成就毋庸置疑,但在相當一部分國際象棋愛好者和部分機器學習愛好者看來,這篇論文並沒有真正證明強化學習演算法和AlphaZero本身的優越性,而引起爭議的正是下面這幅圖。
隨著思考時間延長,AlphaZero和Stockfish、Elmo在Elo評分上的變化
據透露,DeepMind在訓練AlphaZero時用了5000個TPU和64個二代TPU,這也是他們把訓練時間壓縮在24小時內的最主要原因。其中二代TPU是穀歌今年5月發佈的新型深度學習晶片,把64個二代TPU連接起來後,它們的浮點性能可以達到驚人的11.5PFLOPS,遠超世界上前五百超級電腦的算力。
在論文中,團隊稱為了公平起見,AlphaZero和AG0 3使用的是一台帶有4個TPU的機器,而Stockfish和Elmo使用的是“足以發揮它們最大效果”的64個執行緒和1GB的雜湊表。在這樣的背景下,依靠蒙特卡洛樹搜索,AlphaZero每秒只需在國際象棋中搜索8萬次,在將棋中搜索4萬次,而Stockfish每秒需要的搜索次數高達7000萬次,Elmo也要3500萬次,它們用的是α-β搜索。
對此,DeepMind給出的結論是α-β搜索的內在優勢需要被重新考量,如上圖所示,思考時間延長後,AlphaZero較其他兩個程式在評分上有了更好的表現。
但是許多人對此提出了異議,AI思考時間越長做出的決策越準確的道理眾所周知,但它對算力的壓力也會隨時間增長,而Stockfish和Elmo的硬體設定和AlphaZero相比太差了。誠然,開發人員在設計它們的時候會考慮到硬體的承受能力,把資源佔用控制在可以接受的範圍內,這使它們在起跑線上就遠遠落後於AlphaZero,再加上可怕的搜索次數,因此一個情理之中的疑問是:如果Stockfish也基於4個TPU的算力設計,AlphaZero是否能超越它?
另外,一些人也對文中的Elo評分提出了異議,考慮到Stockfish並沒有國際象棋需要的opening book,所以這些評分很有可能是有問題的。
結語無論如何,AlphaZero在只有遊戲規則的前提下在一天內就擊敗了3類棋牌遊戲中的頂級“選手”,這本身就是一個非常了不起的成就。在這種情況下,比較演算法優劣或是爭論誰強誰弱的問題恐怕都不重要了,重要的是我們需要看到神經網路的力量。未來機器學習在遊戲“輸贏”定義上還有很長一條路要走,但與此同時,它將給我們的認知方式帶來前所未有的改變。
而是依靠DNN和“白板”強化學習演算法不斷自我對弈。DNN
AlphaZero使用的深度神經網路包含一個參數θ:
(p, v) = fθ(s)
其中輸入s為棋子的座標,神經網路根據每個動作a輸出具有分量
pa = Pr(a|s)
的移動概率p的向量,而v則是根據座標s估計的預期結果z的標量值:
v ≈ E[z|s].
AlphaZero能在自學中學習移動概率計算和預期結果估計,並將其用來指導搜索。
蒙特卡洛樹搜索演算法
不同于利用遊戲專用資料的alpha-beta搜索,AlphaZero用的是蒙特卡洛樹搜索演算法(MCTS),它的每一次搜索都包含一系列從根節點到葉子節點最後貫穿整棵樹的自我對弈模擬。而每次類比會通過從每個狀態s中選擇一個低訪問次數、高移動概率、高價值動作a來繼續推進(衡量標準為s中a類比的葉子節點狀態平均值)。最後搜索返回的是一個表示移動概率分佈的向量π,它在比例上和貪婪性上都與訪問根節點的次數相關。
強化學習
DNN中的參數θ經隨機初始化後,AlphaZero會通過一種自我對弈的強化學習演算法來進行訓練。棋局中,蒙特卡洛樹搜索演算法會對應給出下棋雙方的下一步動作:at ∼ πt。棋局結束後,演算法根據遊戲規則對棋子位置sT計算表現評分z:-1為負;0為平;+1為勝。為了降低預測結果vt和評分z之間的誤差,同時使動作向量pt和搜索概率πt更接近,參數θ會做重新調整。具體來說,θ可由以下算式計算得出:
其中c為控制L2權重正則化水準的參數。調整後,更新的參數會用於之後的自我對弈棋局。
AlphaZero和AlphaGo Zero的區別
DeepMind也在論文中介紹了AlphaZero和AlphaGo Zero的一些不同點,它們主要表現在以下這幾個方面:
AlphaGo Zero只會考慮輸/贏兩種結果,因此它會不斷估計並優化勝率;而AlphaZero會估計和優化比賽結果,並考慮平局或其他潛在的情況。
由於無論怎麼調整棋局方位,圍棋的規則都不會發生變化,AlphaZero沿用了AlphaGo Zero的方法,會通過增加一些對稱資料強化訓練,並在蒙特卡洛樹搜索期間隨機調整棋盤角度進行評估。但考慮到國際象棋和將棋的規則是不對稱的,AlphaZero沒有增加訓練資料,在搜索時也不會改變棋盤位置。
AlphaGo Zero演算法提升自我的方式是不斷反覆運算,它會計算每一次訓練的表現,如果後一次比前一次更優,那後者會代替前者進行之後的自我對弈。而AlphaZero從頭到尾只有一個神經網路,它只通過更新參數來完成自我更新,省去了評分步驟,也不統計最佳狀態。
AlphaGo Zero通過貝葉斯優化調整搜索的超參數,而AlphaZero則重複使用相同的超參數,無需針對特定遊戲做改變。當然,這一點也有例外,就是AlphaZero為了保證搜索會把雜訊添加進之前的動作中,它與合理下法的數量成正比。
棋局表現在展示成果前,DeepMind先在論文中評價了圍棋、國際象棋、將棋對神經網路架構的適應性。他們指出,由於規則的高度對稱性、動作空間簡單、比賽結果只有輸和贏,圍棋是最適合神經網路訓練的。而國際象棋和將棋棋盤規則不對稱,棋子移動方式各異,尤其是將棋還允許被吃掉的棋子重返戰場,因此引入一些新的設計和思考十分必要。事實上,國際象棋和將棋都有平局的結果,尤其是國際象棋還把平局視為一種最優解,這都對AlphaZero提出了新的挑戰。
AlphaZero國際象棋、將棋、圍棋百場對局結果
在這次實驗中,AlphaZero的“世界冠軍”對手們分別是2016年TCEC冠軍、今年在51場比賽中保持不敗戰績的國際象棋AI程式Stockfish,2017年CSA世界冠軍、日本將棋AI程式Elmo,以及DeepMind上一篇論文的主角、只訓練了3天就超越AlphaGo(李世石版)的圍棋AI程式AG0 3(AlphaGo Zero3天訓練版)。
如上圖所示,AlphaZero在三個遊戲中都佔據優勢,以總成績28勝72平、90勝2平8負和60勝40負的戰績鎖定勝局。但我們也可以發現,執黑執白似乎對AlphaZero的表現有一定影響。執白棋時,它分別以25勝25平、43勝2平5負在國際象棋和將棋比賽中戰勝對手;而執黑棋時,它在將棋上以47勝3負大勝Elmo,但在國際象棋上則以3勝47平險勝。可能是因為“師出同門”,AlphaZero在圍棋上表現穩定,和AG0 3相比進步也很明顯。
訓練落子70萬步後,AlphaZero和其他“世界冠軍”的Elo評分對比
雖然對局結果中似乎出現了一些有關黑白棋公平性上的發現,但毫無疑問的一點是,AlphaZero利用這300場比賽證明了它的實力,而這一切是在除了比賽規則外沒有任何預備的訓練資料、訓練時間只壓縮在24小時內的情況下實現的。
上圖是論文中的一幅評分圖,暫且拋開評分可信度,通過對比資料我們可以發現,AlphaZero在訓練到30萬步時已經超越了Stockfish,此時用時約為4小時。而在將棋訓練中,AlphaZero僅用2小時、11萬步就超越了Elmo。在面對棋盤情況更複雜的圍棋時,演算法在16.5萬步時和戰勝李世石的AlphaGo打成平手(8小時),並在之後一路上升。
遺憾的是,雖然DeepMind展示了AlphaZero和AG0 3的對局成績,但是並沒有在論文中說明訓練了多長時間。
AlphaZero對國際象棋部分下法的評價
是RL還是TPU?雖然AlphaZero在技術上取得的成就毋庸置疑,但在相當一部分國際象棋愛好者和部分機器學習愛好者看來,這篇論文並沒有真正證明強化學習演算法和AlphaZero本身的優越性,而引起爭議的正是下面這幅圖。
隨著思考時間延長,AlphaZero和Stockfish、Elmo在Elo評分上的變化
據透露,DeepMind在訓練AlphaZero時用了5000個TPU和64個二代TPU,這也是他們把訓練時間壓縮在24小時內的最主要原因。其中二代TPU是穀歌今年5月發佈的新型深度學習晶片,把64個二代TPU連接起來後,它們的浮點性能可以達到驚人的11.5PFLOPS,遠超世界上前五百超級電腦的算力。
在論文中,團隊稱為了公平起見,AlphaZero和AG0 3使用的是一台帶有4個TPU的機器,而Stockfish和Elmo使用的是“足以發揮它們最大效果”的64個執行緒和1GB的雜湊表。在這樣的背景下,依靠蒙特卡洛樹搜索,AlphaZero每秒只需在國際象棋中搜索8萬次,在將棋中搜索4萬次,而Stockfish每秒需要的搜索次數高達7000萬次,Elmo也要3500萬次,它們用的是α-β搜索。
對此,DeepMind給出的結論是α-β搜索的內在優勢需要被重新考量,如上圖所示,思考時間延長後,AlphaZero較其他兩個程式在評分上有了更好的表現。
但是許多人對此提出了異議,AI思考時間越長做出的決策越準確的道理眾所周知,但它對算力的壓力也會隨時間增長,而Stockfish和Elmo的硬體設定和AlphaZero相比太差了。誠然,開發人員在設計它們的時候會考慮到硬體的承受能力,把資源佔用控制在可以接受的範圍內,這使它們在起跑線上就遠遠落後於AlphaZero,再加上可怕的搜索次數,因此一個情理之中的疑問是:如果Stockfish也基於4個TPU的算力設計,AlphaZero是否能超越它?
另外,一些人也對文中的Elo評分提出了異議,考慮到Stockfish並沒有國際象棋需要的opening book,所以這些評分很有可能是有問題的。
結語無論如何,AlphaZero在只有遊戲規則的前提下在一天內就擊敗了3類棋牌遊戲中的頂級“選手”,這本身就是一個非常了不起的成就。在這種情況下,比較演算法優劣或是爭論誰強誰弱的問題恐怕都不重要了,重要的是我們需要看到神經網路的力量。未來機器學習在遊戲“輸贏”定義上還有很長一條路要走,但與此同時,它將給我們的認知方式帶來前所未有的改變。