Facebook 研究員解析演算法技術:AlphaGo 為什麼這麼厲害?

作者 | 發布日期 2016 年 03 月 14 日 11:15 | 分類 人工智慧 , 尖端科技 , 科技教育 follow us in feedly
google-alphago-logo

最近 AlphaGo 的世紀大戰引發關注,3 場比賽都打敗李世乭,它究竟厲害在哪裡?本篇內容來自 Facebook 人工智慧研究員田淵棟,他曾就職於 Google X 部門。



最近我仔細看了一下 AlphaGo 在《Nature》雜誌上發表的文章,寫一些分析給大家分享。

AlphaGo 這個系統主要由幾個部分組成:

  • 走棋網路(Policy Network),給定當前局面,預測 / 採樣下一步的走棋。
  • 快速走子(Fast rollout),目標和 1 一樣,但在適當犧牲走棋品質的條件下,速度要比 1 快 1,000 倍。
  • 估值網路(Value Network),給定當前局面,估計是白勝還是黑勝。
  • 蒙地卡羅樹狀搜尋(Monte Carlo Tree Search,MCTS),把以上這 3 個部分連起來,形成一個完整的系統。

我們的 DarkForest 和 AlphaGo 同樣是用 4 搭建的系統。DarkForest 較 AlphaGo 而言,在訓練時加強了 1,而少了 2 和 3,然後以開源軟體 Pachi 的缺省策略(default policy)部分替代了 2 的功能。以下介紹下各部分。

 

1. 走棋網路

走棋網路把當前局面做為輸入,預測 / 採樣下一步的走棋。它的預測不只給出最強的一手,而是對棋盤上所有可能的下一著給一個分數。棋盤上有 361 個點,它就給出 361 個數,好招的分數比壞招要高。DarkForest 在這部分有創新,透過在訓練時預測三步而非一步,提高了策略輸出的品質,和他們在使用增強學習進行自我對局後得到的走棋網路(RL network)的效果相當。當然,他們並沒有在最後的系統中使用增強學習後的網路,而是用了直接通過訓練學習到的網路(SL network),理由是 RL network 輸出的走棋缺乏變化,對搜尋不利。

雷鋒網配圖

有意思的是 AlphaGo 為了速度上的考慮,只用了寬度為 192 的網路,而並沒有使用最好的寬度為 384 的網路(見圖 a),所以要是 GPU 更快一點(或者更多一點),AlphaGo 肯定會變得更強的。

所謂的 0.1 秒走一步,就是純粹用這樣的網路,下出有最高置信度的合法著法。這種做法一點也沒有做搜索,但是大局觀非常強,不會陷入局部戰鬥中,說它建模了「棋感」一點也沒有錯。我們把 DarkForest 的走棋網路直接放上 KGS 就有 3d 的水準,讓所有人都驚嘆了一下。可以說,這一波圍棋 AI 的突破,主要得益於走棋網路的突破。這個在以前是不可想像的,以前用的是基於規則,或者基於局部形狀再加上簡單線性分類器訓練的走子生成法,需要慢慢調參數年,才有進步。

當然,只用走棋網路問題也很多,就我們在 DarkForest 上看到的來說,會不顧大小無謂爭劫,會無謂脫先,不顧局部死活,對殺出錯等。有點像高手不經認真思考的隨手棋。因為走棋網路沒有價值判斷功能,只是憑「直覺」在下棋,只有在加了搜尋之後,電腦才有價值判斷的能力。

 

2. 快速走子

那有了走棋網路,為什麼還要做快速走子呢?有兩個原因,首先走棋網路的運行速度是比較慢的,AlphaGo 說是 3 毫秒,我們這裡也差不多,而快速走子能做到幾微秒級別,差了 1,000 倍。所以在走棋網路沒有返回的時候讓 CPU 不閑著先搜尋起來是很重要的,等到網路返回更好的著法後,再更新對應的著法資訊。

其次,快速走子可以用來評估盤面。由於天文數字般的可能局面數,圍棋的搜尋是毫無希望走到底的,搜尋到一定程度就要對現有局面做個估分。在沒有估值網路的時候,不像國象可以透過算棋子的分數來對盤面做比較精確的估值,圍棋盤面的估計得要透過模擬走子來進行,從當前盤面一路走到底,不考慮岔路地算出勝負,然後把勝負值做為當前盤面價值的一個估計。這裡有個需要權衡的地方:在同等時間下,模擬走子的品質高,單次估值精度高但走子速度慢;類比走子速度快乃至使用隨機走子,雖然單次估值精度低,但可以多模擬幾次算平均值,效果未必不好。所以說,如果有一個品質高又速度快的走子策略,那對於棋力的提高是非常有幫助的。

為了達到這個目標,神經網路的模型就顯得太慢,還是要用傳統的局部特徵匹配(local pattern matching)加線性回歸(logistic regression)的方法,這辦法雖然不新但非常好使,幾乎所有的廣告推薦、競價排名、新聞排序,用的都是它。與更為傳統的基於規則的方案相比,它在吸納了眾多高手對局之後就具備了用梯度下降法自動調參的能力,所以性能提高起來會更快更省心。AlphaGo 用這個辦法達到 2 微秒的走子速度和 24.2% 的走子準確率。24.2% 的意思是說,它的最好預測和圍棋高手的下子有 0.242 的概率是重合的,相比之下,走棋網路在 GPU 上用 2 毫秒能達到 57% 的準確率。這裡,我們就看到了走子速度和精度的權衡。

雷鋒網配圖

和訓練深度學習模型不同,快速走子用到了局部特徵匹配,自然需要一些圍棋的領域知識來選擇局部特徵。對此 AlphaGo 只提供了局部特徵的數目(見上圖),而沒有說明特徵的具體細節。我最近也實驗了他們的辦法,達到了 25.1% 的準確率和 4-5 微秒的走子速度,然而全系統整合下來並沒有複現他們的水準。感覺上 24.2% 並不能完全概括他們快速走子的棋力,因為只要走錯關鍵的一步,局面判斷就完全錯誤了;而下圖更能體現他們快速走子對盤面形勢估計的精確度,要能達到他們像下圖這樣的水準,比簡單地匹配 24.2% 要做更多的工作,而他們並未在文章中強調這一點。

雷鋒網配圖

在 AlphaGo 有了快速走子之後,不需要走棋網路和估值網路,不借助任何深度學習和 GPU 的幫助,不使用增強學習,在單機上就已經達到了 3d 的水準(見下圖倒數第二行),這是相當厲害的了。任何使用傳統方法在單機上達到這個水準的圍棋程式,都需要花費數年的時間。在 AlphaGo 之前,Aja Huang 曾經自己寫過非常不錯的圍棋程式,在這方面相信是有很多積累的。

 

3. 估值網路

雷鋒網配圖

AlphaGo 的估值網路可以說是錦上添花的部分,從圖 b 和 Extended Table 7 來看,沒有它 AlphaGo 也不會變得太弱,至少還是會在 7d-8d 的水準。少了估值網路,等級分少了 480 分,但是少了走棋網路,等級分就會少掉 800 至 1,000 分。特別有意思的是,如果只用估值網路來評估局面(2177),那其效果還不及只用快速走子(2416),只有將兩個合起來才有更大的提高。我的猜測是,估值網路和快速走子對盤面估計是互補的,在棋局一開始時,大家下得比較和氣,估值網路會比較重要;但在有複雜的死活或是對殺時,透過快速走子來估計盤面就變得更重要了。考慮到估值網路是整個系統中最難訓練的部分(需要 3 千萬局自我對局),我猜測它是最晚做出來並且最有可能能進一步提高的。

關於估值網路訓練資料的生成,值得注意的是文章中的附錄小字部分。與走棋網路不同,每一盤棋只取一個樣本來訓練以避免過擬合,不然對同一對局而言輸入稍有不同而輸出都相同,對訓練是非常不利的。這就是為什麼需要 3 千萬局,而非 3 千萬個盤面的原因。對於每局自我對局,取樣本是很有講究的,先用 SL network 保證走棋的多樣性,然後隨機走子,取盤面,然後用更精確的 RL network 走到底以得到最正確的勝負估計。當然這樣做的效果比用單一網路相比好多少,我不好說。

一個讓我吃驚的地方是,他們完全沒有做任何局部死活 / 對殺分析,純粹是用暴力訓練法訓練出一個相當不錯的估值網路。這在一定程度上說明深度卷積網路(DCNN)有自動將問題分解成子問題,並分別解決的能力。

另外,我猜測他們在取訓練樣本時,判定最終勝負用的是中國規則。所以說 3 月和李世乭對局的時候也要求用中國規則,不然如果換成別的規則,就需要重新訓練估值網路(雖然我估計結果差距不會太大)。至於為什麼一開始就用的中國規則,我的猜測是程式設計非常方便(我在寫 DarkForest 的時候也是這樣覺得的)。

 

4. 蒙地卡羅樹狀搜尋

這部分基本用的是傳統方法,沒有太多可以評論的,他們用的是帶先驗的 UCT,即先考慮 DCNN 認為比較好的著法,然後等到每個著法探索次數多了,選擇更相信探索得來的勝率值。而 DarkForest 則直接選了 DCNN 推薦的前 3 或是前 5 的著法進行搜索。我初步試驗下來效果差不多,當然他們的辦法更靈活些,在允許使用大量搜尋次數的情況下,他們的辦法可以找到一些 DCNN 認為不好但卻對局面至關重要的著法。

一個有趣的地方是在每次搜索到葉子節點時,沒有立即展開葉子節點,而是等到訪問次數到達一定數目(40)才展開,這樣避免產生太多的分支,分散搜尋的注意力,也能節省 GPU 的寶貴資源,同時在展開時,對葉節點的盤面估值會更準確些。除此之外,他們也用了一些技巧,以在搜尋一開始時,避免多個執行緒同時搜尋一路變化,這部分我們在 DarkForest 中也注意到了,並且做了改進。

 

5. 總結

總的來說,這整篇文章是一個系統性的工作,而不是一兩個小點有了突破就能達到的勝利。在成功背後,是作者們,特別是兩位第一作者 David Silver 和 Aja Huang,在博士階段及畢業以後 5 年以上的積累,非一朝一夕所能完成的。他們能做出 AlphaGo 並享有現在的榮譽,是實至名歸的。

從以上分析也可以看出,與之前的圍棋系統相比,AlphaGo 較少依賴圍棋的領域知識,但還遠未達到通用系統的程度。職業棋手可以在看過了寥寥幾局之後明白對手的風格並採取相應策略,一位資深遊戲玩家也可以在玩一個新遊戲幾次後很快上手,但到目前為止,人工智慧系統要達到人類水準,還是需要大量樣本的訓練的。可以說,沒有千年來眾多棋手在圍棋上的積累,就沒有圍棋 AI 的今天。

在 AlphaGo 中,增強學習(Reinforcement Learning)所扮演的角色並沒有想像中那麼大。在理想情況下,我們希望人工智慧系統能在對局中動態地適應環境和對手的招式並且找到辦法反制之,但是在 AlphaGo 中增強學習更多地是用於提供更多品質更好的樣本,給有監督學習(Supervised Learning)以訓練出更好的模型。在這方面增強學習還有很長的路要走。

另外,據他們的文章所言,AlphaGo 整個系統在單機上已具有了職業水準,若是 Google 願意開幾萬台機器和李世乭對決(這對它來說再容易不過了,改個參數就行),相信比賽會非常精彩。

下面是根據讀者提問做的一些更新。

問題 1「Alphago 的 MCTS 做 rollout 的時候,除了使用快速走子,還用了搜尋樹的已有部分,看起來像是 AMAF / RAVE 反過來:AMAF 是把快速走子的資訊傳導到樹的其他無關部分,Alphago 是把樹的其他無關部分拿來增強快速走子。我懷疑這是不是它棋力比其他 DCNN+MCTS 強的原因之一。」

這個辦法在解死活題的文章中出現過,會在一定程度上提高搜索效率,但是提高多少還不知道。

問題 2「rollout 的走法品質變好可能會導致棋力下降。」

這裡要分兩種情況,tree policy 和 default policy。在 AlphaGo 的文章裡面已經說過了,tree policy 的分布不能太尖,不然在搜尋時太過重視一些看起來的好著,可能使得棋力下降。但是除了這種原因,一般來說 tree policy 變好棋力還是會變強的。

default policy 這邊,即(半)隨機走子到最後然後判分,就很複雜了,品質變好未必對局面能估得更准。default policy 需要保證的是每塊棋的死活大體正確,不要把死的棋下成活的或者反之,而對大局觀的要求反而沒有那麼高。雙方完全可以配合著把每塊棋下完,然後轉戰另一塊,而不是說搶在對方前去別處佔先手。

(本文由 雷鋒網 授權轉載) 

發表迴響