AlphaGo 研究筆記

本文作者:林快。來自雲書苑教育科技公司。致力於:一,光劍注音輸入法,二,快刀中文原創性比對系統開發工作, 都是「大數據深度學習的人工智慧」,在商業界的淺薄應用,希望跟同好交流心得。

谷歌旗下 DeepMind 公司研發的 AlphaGo ,戰勝了人類職業棋王選手,不為別的,谷歌就是要向世界證明人工智慧強大。2016 年 1 月 28 日,DeepMind 公司在國際權威期刊《Nature》發表論文 Mastering the game of Go with deep neural networks and tree search ,介紹了 AlphaGo 軟體的核心技術。這篇論文光作者就 20 個,明顯是下了血本,領軍的兩位,都是電腦圍棋界鼎鼎大名的大神。其中一位,是來自台灣師範大學的黃士傑,另一位 David Silver 是電腦圍棋和深度學習的頂尖專家,可說是兩位長期研究圍棋領域的高手。

本文是對 AlphaGo 軟體工作原理,淺薄的個人研究筆記,還有一點點筆者從事人工智慧開發的心得,拋磚引玉,望其他高手指正。當然,AlphaGo 研發團隊裡有來自台灣電腦圍棋軟體高手,相信不久,黃士傑本人也會解密一下這轟動全球的技術關鍵。

不多說廢話,這論文裡的技術是出乎意料的簡單,卻很強大。

 

一,系統核心關鍵:搜尋+大數據深度學習。

令人意想不到,幾乎完全沒用到圍棋領域的專業知識。

二,兩套能深度學習的子系統。

面對複雜的圍棋棋局,AlphaGo 不是用暴力式的搜尋比對,而是開發了兩套能深度學習的子系統,來解決搜尋量太大的問題。

「策略網路」(Policy Network)子系統負責下一步的落子選擇, 把理論上存在的平均 200 種可能性,縮小到得分最高的幾種選擇;「價值網路」(Value Network)子系統負責評估落子後的局面,與最終勝負的或然率關係,判斷當下局面是否處於優勢,贏面多大。第一個子系統減少計算的寬度——不需要計算所有落子的可能;第二個子系統減少計算的深度,不用徒勞地去嘗試算到底。AlphaGo 們用了許多真正專業棋局來訓練軟體產生一堆數據,這種方法稱為監督學習(Supervised Learning),然後更讓電腦跟電腦下棋,這種方法稱為強化學習(Reinforcement Learning),每次電腦跟電腦自己下棋都能讓軟體的棋力精進。

三,第一個子系統(Policy Network)它有兩種學習模式。

模式一:簡單模式。透過採集 KGS(一個圍棋對弈線上主機)上的對局資料來訓練系統。這可以理解為:讓系統學習「定式」,也就是在一個既定的局面下,人類會怎麼走,這種學習不牽扯到優劣判斷這個議題。

另一個模式是複雜模式,主要功能在自我強化學習,它透過電腦自己和自己大規模對局的勝負,來學習每一步走子的優劣。因為是自我對局,資料量是無限的。

第二個子系統(Value Network)作用在學習評估整體盤面的優劣,它也是透過大規模自我對局來進行訓練,若採用人類對局的數據,容易因資料量過少導致失敗。

四,在對弈時,兩套子系統是這樣協力工作的。

第一個子系統的簡單模式會判斷,在當前局面下有哪些走法值得考慮,其複雜模式,則是透過蒙地卡羅樹搜尋演算法 MCTS 展開各種走法,推敲各種走法的優劣,即所謂的「算棋」。在這個計算過程中,第二個子系統會協助第一個系統審勢度局,砍掉大量不值得深入考慮的分岔樹,大大提高電腦效率。與此同時,第二個子系統透過預知新局面的優劣,也能給出下一次建議。

五,如果擁有無限比對資源,MCTS理論上可以透過探索每一局的可能步驟,去計算最佳落子。

但暴力式比對所有走法的可能性,對圍棋來說變化太多了(大到比我們認知宇宙裡的粒子還多)。圍棋棋盤橫豎各有 19 條線,共有 361 個落子點,雙方交替落子,這意味著圍棋總共可能有 10 ^ 171(1 後面有 171 個零)種可能性。這超過了宇宙中的原子總數是 10 ^ 80(1 後面 80 個零)! 所以實際上沒辦法搜尋每一個可能的變種。MCTS 做法比其他方法好的原因,是在識別有利的變數,這樣可跳過一些不利的,從而提高效率。

AlphaGo 最後是選擇裝上 MCTS 的演算法模組,讓它嵌入不同功能去評估變種。最後馬力全開。

隨著使用模組的不同,AlphaGo能力變化和模擬結果。

AlphaGo 的能力變化與 MCTS 的使用有關。僅使用一種方法的時候,AlphaGo 跟民間圍棋高手差不多,但當混合使用上述方法,就到達人類職業棋手水平。最後,兩個子系統的結果,以平均加權,做出最終要輸出的決定。

六,在論文中有個有趣結論。

兩套子系統取平均結果,比依賴兩者各自得出的結果都要好很多。這應當是 AlphaGo 最擬人化的部分。這兩個系統的工作方式,一個判斷細部,一個縱覽全局。和人類很像 。但 AlphaGo 最終綜合兩套系統的方式相當簡單:讓兩者各自評估一下每種可能的優劣,然後取一個平均數。呵呵,這可絕不是人類的思維方式。

七,AlphaGo 採用圖像處理技術來學習盤面判斷。

也就是把圍棋棋盤當一張照片在處理。因此,記憶體裡並不是儲存一套套的棋譜資料,而是把所有棋譜都轉變為一個個函數。新增一個棋譜時,經過 13 個網路層,得到一個 19 × 19 維函數,如此一來可以知道,每個地方下子的機率有多少。換言之,輸入一個棋盤,輸出是一個函數。

八,論文還詳細講了一套工程最佳化的技術

分佈式計算,大量的雲主機去提高 MCTS 速度,但核心都是相同的演算法了。

深入 AlphaGo 核心

AlphaGo 透過兩套神經網路子系統合作來改進下棋。

這兩套系統是多層神經網路(13層),跟 Google 圖片搜尋引擎識別圖像的結構相似。它們從多層式開始啟發,去處理圍棋棋盤的定位,就像圖片分類器處理圖片一樣。經由過濾,13 個完全連接的神經網路層,產生它們搜尋到的局面判斷。這些層次能夠做分類和邏輯推理。

這些網路透過反覆訓練來檢查結果,然後校對調整參數,讓下次執行更好。這個處理方式有大量的隨機性元素, AlphaGo 開發者也無從得知軟體「思考」的結果,但可以確定的是,更多的訓練能讓它不斷進化。

第一步驟:啟動落子選擇器 (Move Picker)

進入落子選擇器之後,AlphaGo 開始執行第一個神經網路子系統,叫做「監督學習的策略網路(Policy Network)」,觀察棋盤佈局企圖找到最佳的下一步。事實上,它能預測計算出下一步棋的最佳機率,前一步猜測的,就是那個可行性得分最高的。

落子選擇器是怎麼看到棋盤的?標示數字處,代表最強人類選手可能的落點。

AlphaGo 採集了 KGS(網路圍棋對戰平台)上,超過百萬套人類對弈棋局落子,來產生龐大資料,這是 AlphaGo 模擬人的地方,目的是學習那些頂尖高手的下棋策略。經過大數據訓練後,AlphaGo 落子選擇器的預測正確性已達57%,幾乎等同職業棋手的實力。但系統的最終目標不是為了贏得勝利,而是要找到跟人類高手同樣的思考模式。

更快的落子

AlphaGo 為了提高效率更快落子,研發團隊採取了這樣的策略。AlphaGo 的落子選擇器首先執行「快速搜尋」版本。快速搜尋版本不比對 19 x 19 的棋盤,但會評估對手先前棋路和剛下的這一手,在兩者間產生一個更小的值,讓計算速度比之前快 1000 倍,實現了更佳的「搜尋結構」。

傳統上越強的搜尋,意味著耗時越久,為了比對到一個不錯的落子,「搜尋結構」需要逐一去檢查幾千種落子可能性才能輸出結果。但 AlphaGo 這樣兩套系統混合使用,讓這比對效率大大提高。

第二步驟:棋局評估器 (Position Evaluator)

AlphaGo 的第二個步驟,相對於落子選擇器,這裡要解決另一個問題,這步驟「棋局評估器」在論文中叫做「價值網路(Value Network)」。在給定棋子位置情況下,預測每一個棋手贏棋的可能,透過整體局面判斷來輔助落子選擇器。這判斷僅僅是大概的,但能有效提高搜尋速度。透過分類潛在局面的「好」與「壞」,AlphaGo 可以決定是否需要深入搜尋。如果棋局評估器比對,結果發現這數字太低,那麼該程式就跳過並忽略這方向上的可能性比對。

棋局評估器是怎麼看這個棋盤的?深藍色表示下一步有利於贏棋的位置。

棋局評估器也通過百萬套的棋局做訓練。DeepMind 團隊複製了兩套相同的 AlphaGo 落子選擇器,精心挑選隨機樣本讓電腦自己對弈,因此產生了大量棋局資料。這批棋局資料價值連城,可用來大規模訓練局面評估器。這種落子選擇器模擬各種可能性,從任意棋盤局面推斷雙方贏棋機率。如果單靠人類的棋局資料,難以達到這種級別的訓練。

搜尋樹的增刪

論文裡列出了幾個版本的落子選擇,再加上局面評估器,AlphaGo 可以很有效率的搜尋可能走法和步驟。搜尋方法就是蒙地卡羅樹搜尋演算法。但因為加上兩套子系統混合,因此能夠更具有智慧的猜測用哪個變種去搜尋,需要多深去搜尋。

搜尋樹

什麼是機器深度學習?

「深度學習」是指多層的人工神經網路,和訓練它的方法。第一層神經網路會把大量數字作為輸入,通過非線性方法取得權重,再產生另一批數據作為輸出。這就像生物神經大腦的工作原理一樣,通過合適的數量,多層組織結合在一起,形成神經網路「大腦」進行精確複雜的處理,也像照片識別的原理。

人工神經網路的研究,在幾十年前就出現了,但直到網路普及化後,才產生更多應用。在早期,研究先驅們能蒐集的數據樣本太少,而即便想依靠這些少量資料取得初階訓練效果,也都遠遠超過當時電腦所能處理的範圍。大量的「訓練」是學習的重要途徑,人們逐漸發現數據背後的價值,於是最近幾年,一些能獲取大數據資源的團隊,便開始採集大量內容來實現人工神經網路,透過「大數據」技術進行高效訓練。

深度學習不是簡單地搜尋比對以前的棋,而是把曾經看過的所有局面,融會貫通形成資料。以後電腦再遇到了,無論是整體還是局部,軟體都能分析得到最好的作法。

什麼是蒙地卡羅樹搜尋演算法?

「蒙地卡羅樹搜尋演算法」(Monte Carlo Tree Search 簡稱 MCTS)並不是一個演算法,而是一類隨機演算法的統稱。這類方法特點是,可在隨機採樣中計算得到近似結果,隨著採樣增多,得到正確結果的機率逐漸加大。但在獲得全部統計結果之前,無法肯定當下就是真實的結果。

舉個例子:一籃有 1000 個蘋果,想挑出最大蘋果。於是這樣挑選:先隨便拿起一個,再隨機拿另一個跟這個比,手上留下比較大的,再隨機拿下一個……每拿一次,手上的蘋果都至少比上次的大。拿的次數越多,挑的蘋果就越大。這個挑蘋果的方式,就屬於蒙地卡羅演算法:盡量找大的,但不保證一次就能挑中最大的。

而蒙地卡羅樹搜尋演算法這種啟發式的搜尋策略,能夠基於對搜尋,隨機抽樣來擴大搜尋樹,從而分析圍棋這類遊戲中,每一步棋該怎麼走才能夠創造最好機會。特別要說明的是,蒙地卡羅樹搜尋演算法其中比較流行的是一種叫 upper confidence bounds applied to trees 方法,簡稱 UTC 。

本文作者 Facebook 專頁

參考來源

– AlphaGo 首頁 http://goo.gl/960rvo

– Nature 論文原文 http://goo.gl/qcA0mg

– Nature 報導 http://goo.gl/AJUZKH

– Dan Maas 對論文的簡要結論 http://goo.gl/kNg3ST

 

 

廣告

AlphaGo 研究筆記 有 “ 1 則迴響 ”

  1. 引用通告: 真實範例:人工智慧寫作機器人—九把劍,從0開始的養成日記(上) | 雲書苑人工智慧學院

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s