跟著阿爾法狗理解深度強化學習框架

作者： 許鐵

阿爾法狗這個被大家熱議過很久的主題， 裡面其實包含了非常深刻的機器學習智慧。 是一部學習機器學習甚至是人類決策的絕好教材。機器學習是Alphago取勝的關鍵，為什麼它會發揮巨大作用，請看下文。

了解一門科學技術最好的方法就是找出其核心論文， 讓我們看看阿法狗的核心論文是怎麼解讀這個問題的。 以及如果把你放在這樣一個位置， 會如何設計這盤遊戲。

如果大家了解棋牌類遊戲以及電腦與之對弈的歷史， 則會非常清楚老派程序員的套路， 那就會明白這類問題最簡單的辦法就是窮舉法， 比如歷史著名的八皇后問題， 你需要在國際象棋棋盤上擺放八個皇后，而使得她們各自不位於對方的縱線，橫線或對角線上， 你只需要按照一定的方法做一個循環，從第一排往下一排遍歷， 當你碰見擺不開的情形，就回到上一步最終重新擺，最後總可以把沒有問題的組合求出來。

與之類似的方法稍作改進可以很好的解決國際象棋的問題， 卻難以做到解決圍棋的問題， 為什麼？ 因為眾所周知的，圍棋的維度實在太大了， 每一次落子都有幾百（棋盤19*19大小）種可能， 設想假如一盤棋要在幾百步之後得出勝負，你有多少種可能性， 確實很難通過任何和窮舉法沾邊的演算法解決掉。

這裡就涉及如何有效的減少搜索空間，這個核心問題。這也是為什麼一個下圍棋的問題需要用到機器學習的關鍵， 因為機器學習讓你通過有限數據推測所有其他可能（類似一個插值過程）。

要讓機器做這個事先看看人是怎麼做的， 我們無時無刻不在決策也都面臨如何減少搜索空間的問題。 雖然人生的可能在一定程度是無限的， 但大多數可能你連考慮都不會考慮， 比如去朝鮮移民或到孟加拉國賣香蕉。我們人類用愚蠢，聰明， 合理，不合理這些辭彙描述各種選擇的優劣， 並且大腦自動屏蔽大部分不合理的解釋。 你是如何得到這些答案的呢？第一個就是如何通過常年的試錯來計算每個行為的結果，所謂一朝被蛇咬，十年怕井繩。另一個就是看書，和高手對話直接學習它們的經驗。

反過來就是機器學習的原理，首先說試錯學習，或者根據某種行為最終導致的結果來調整行為策略的方法， 我們通常稱之為強化學習。

而具體到圍棋上， 這個策略的核心是根據圍棋的特性：

1. 在每一步雙方信息完全已知

2. 每一步的策略只需考慮這一步的狀態

這允許機器學慣用一個非常兇猛的簡化框架來解決這個問題，馬爾科夫決策過程。也即是說我們用一個離散的時間序列來表述狀態s，另一個離散的時間序列表述行為a，兩個時間序列有著深刻的耦合關係，下一刻的狀態s（t+1）取決於此刻行為 a（t）和狀態 s（t），最終決定下一刻的行為 a（t+1） 兩者間的關係即策略P（a（t）|s（t）），由於是馬爾科夫鏈， 所以每一時刻的策略只與此刻狀態s（t）有關。 各種棋類就是最明顯的馬鏈。 由於未來存在不確定性， 策略本身也是一個概率分布函數的形式。最終我們要優化採取P（s|a）所得到的回報R（s）最大。馬爾科夫決策過程是在解決未來狀態不確定而行為和狀態又具有馬氏性時十分有利的方法。

解決馬爾科夫決策過程的一個簡單實用粗暴的演算法叫做蒙特卡洛樹搜索（MCTS）。

圖： 蒙特卡洛樹與它的四個步驟 ，選擇，擴張， 模擬估值和結果回傳，對應一個經典的強化學習框架

說到蒙特卡洛， 這是大名鼎鼎的隨機抽樣方法。所謂樹，大家一定可以想到決策樹，樹的節點是某一刻的狀態，而枝杈代表一個決策， 而這裡的蒙特卡洛樹， 即用隨機抽樣的方法生成整個決策樹的過程。

假設電腦現在的狀態是s（t）， 那麼你隨便扔個篩子走一步，然後電腦模擬的對手也扔個篩子隨便走一步，這樣下下去， 總有一刻會分出勝負， 這個時候你回顧勝利和失敗的人的歷史走棋軌跡，贏的走法在其整個決策樹上的每個狀態（枝葉）都加一分， 輸的走法每一步位置都減一分， 這個分數會影響下一次抽樣的概率 ， 使得容易贏的步子會有更大概率取到。 最終依次往複電腦和電腦玩無數次後， 就會選擇出特別容易贏的策略。 這個過程酷似進化選擇演算法， 就是讓那些有優勢的選擇有更高的繁殖子代概率， 從而最終勝出，體現了生物和環境的博弈。

註：這裡提個小問題, 馬爾科夫決策過程威力巨大， 而在現實決策里，你要去哪個大學上學，你要選哪個股票，都的策略選擇都很難只看當下，這個框架還能用多少呢？

以蒙特卡洛樹為代表的強化學習在圍棋這樣走法的可能性超多的情況下，只能部分的減少搜索空間，使得電腦達到一個高級業餘選手的水平， 而如果我們要進一步減少搜索空間 ，需要怎麼辦呢? 此時我們可以再回去想剛提到的人類減少搜索空間的一個重要方法是學習高手經驗， 對，沒錯，背棋譜，看的多了，就有一種犀利的直覺走出一個妙招。轉化為數學語言， 就是通過看棋譜，取得一個在某種局面下任意策略和最終贏率的對應關係，即使這個局面你從未見過。

註： 此處小心我們經常會覺得直覺這個東西好像是天上掉下來的異稟，實則恰相反。直覺才是最需要學習的。

讓機器來做就是有監督學習的回歸演算法， 你要提取棋局的特徵，算出對應每一個走法出現的概率P(a(t)|s(t))，然而圍棋棋局的特徵實在太複雜，如果你來一個線性回歸或KNN，一定會死的很慘。 這時候我們的深度學習開始派上用場。它可以自發的學習事物的表徵。

深度學習的過程正如同我們見識一個東西多了，自發的開始具有舉一反三能力，因之可以稱為把直覺加入了策略選擇，這時候你可以通過有限的經驗把握無限。 在訓練過程中，Alphago不停的根據現有的局面預測專家可能會出的招， 在經過三千萬組數據的訓練後，深度學習可以達到55.7%的預測率，這個概率說明人類的意圖也並不難被猜中，也是為什麼人會說和Alphago下棋如同和無數高手過招。 當然，這還不是訓練的終結， 此處的神經網路只在描摹高手的動作， 而之後我們要讓他能夠贏，好比在實踐中理解和優化高手的招術，這就是訓練的第二步，用強化學習方法， 訓練網路連接係數， 具體方法即讓現有的策略網路和隨機選出一個之前的策略網路進行左右互搏，然後把勝負結果回傳到每一步的策略上，進行梯度訓練。經過這個過程， 策略網路可以秒掉一些中級愛好者水平的演算法和自己之前在描摹各種高手時候的狀態。

訓練的最後一步是估值網路，說說這裡估值網路是幹什麼的， 首先，在一個強化學習框架下， 你需要知道每個行為所對應的確定回報，難點在於圍棋下完棋才有確定回報，想想圍棋步驟中的無限多可能性及得到結果可能的步數就令人生畏，此處深度學習演算法的作用正是不需要走完就巧妙的估計出這一步對應的贏利期望， 過程需要用一個深度網路通過強化學習的框架來進行。估值網路的本質在於建立現有行為和長遠收益的聯繫。 有人稱為看趨勢和全局觀。

訓練這樣一個計算回報的網路作用請往下看。

公式： 訓練要解決的問題， 求得狀態S下採取策略p最終收益的期望

圖： 估值網路的效果圖

那麼問題來了， 蒙特卡洛樹和深度學習兩者如何天衣無縫的結合起來呢？ 這就是整個Alphago設計最巧妙的地方 ： 首先，你應該還記得MCTS的框架， 首先MCTS可以拆解為4步：第一selection，在已有的選項（經歷過的）中進行抽樣選擇， 第二expansion， 走到一個沒有先前從未經歷的局面上，探索新行為，即生成新的枝杈， 第三Evaluation，得到新行為的回報，第四，回傳，把回報的結果反向傳遞給策略。深度學習的結果可以被非常完美的嵌入到蒙特卡洛搜索的步驟里， 首先在expansion的步驟，我們不用從零開始隨機的生成一個前所未有的狀態，而是用根據前人經驗訓練的策略網路直接生成新狀態， 海量了減小了無用的搜索。 然後， 在Evaluation的步驟上， 我們可以不需要跑完整個比賽，而是通過深度學習的結果直接算出這個新姿勢可能的回報（此處即估值網路的作用），這個計算出的回報，會在最終遊戲完成的時候與真正的結果相結合完成學習的步驟。

圖 ：深度學習如何嵌入蒙特卡洛樹搜索

與戰勝國際象棋大師的深藍不同， 在Alphago的情形下機器學習發揮了巨大的作用，因為Alphago的策略和智能主要是在不停看棋譜和左右互搏中進化出來的，對於圍棋這樣規則非常複雜的東西，設計一套必勝規則幾無可能，也只有機器學習（強化學習）的進化和自我改進思想才是最終取勝之法器。也是為什麼Alphago的技術對其它人工智慧非常有啟發。

從整個上面的解析看來， 其實訓練Alphago的演算法思路並非十分複雜，用一句話總結， 就是在巨人的肩膀上迅速試錯。 這也是各種人生決策的最好辦法吧。 你說你要活獨一無二的人生不模擬任何人，你估計是個撞南牆的傻X，你說你要就看著最牛逼的精英跟著走， 你可能一輩子重複別人的生活。而牛X的人， 顯然是站在巨人的肩膀上，邊描摹那三千萬精英的步法，並深度總結其規律， 然後在變化自己的動作花樣。 然而我們人類沒有那麼多時間完simulation，也沒有那麼多GPU進行並行運算， 所以我們其實在找的是低搜索成本的近似解，謂之次優解。

歡迎關注巡洋艦機器學習對抗複雜系統系列後續--一個強化學習在電網設計中的實例