雷鋒網(wǎng)注：本文作者許鐵， 法國巴黎高師物理碩士 ，以色列理工大學(xué)（以色列85%科技創(chuàng)業(yè)人才的搖籃, 計算機(jī)科學(xué)享譽(yù)全球）計算神經(jīng)科學(xué)博士，巡洋艦科技有限公司創(chuàng)始人, 曾在香港浸會大學(xué)非線性科學(xué)中心工作一年。

阿爾法狗這個被大家熱議過很久的主題， 里面其實(shí)包含了非常深刻的機(jī)器學(xué)習(xí)智慧。 是一部學(xué)習(xí)機(jī)器學(xué)習(xí)甚至是人類決策的絕好教材。機(jī)器學(xué)習(xí)是Alphago取勝的關(guān)鍵，為什么它會發(fā)揮巨大作用，請看下文。

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

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

圖： 八皇后， 窮盡并知難而退就夠了，八個女人也不難安排

與之類似的方法稍作改進(jìn)可以很好的解決國際象棋的問題， 卻難以做到解決圍棋的問題， 為什么？ 因?yàn)楸娝苤?，圍棋的維度實(shí)在太大了， 每一次落子都有幾百（棋盤19*19大?。┓N可能， 設(shè)想假如一盤棋要在幾百步之后得出勝負(fù)，你有多少種可能性， 確實(shí)很難通過任何和窮舉法沾邊的算法解決掉。

這里就涉及如何有效的減少搜索空間，這個核心問題。這也是為什么一個下圍棋的問題需要用到機(jī)器學(xué)習(xí)的關(guān)鍵， 因?yàn)闄C(jī)器學(xué)習(xí)讓你通過有限數(shù)據(jù)推測所有其他可能（類似一個插值過程）。

要讓機(jī)器做這個事先看看人是怎么做的， 其實(shí)決策的核心就是如何減少搜索空間的問題。 雖然人生的可能在一定程度是無限的， 但大多數(shù)可能你連考慮都不會考慮， 比如去朝鮮移民或到孟加拉國賣香蕉。我們?nèi)祟愑糜薮?，聰明?合理，不合理這些詞匯描述各種選擇的優(yōu)劣， 并且大腦自動屏蔽大部分不合理的解釋。 你是如何得到這些答案的呢？第一個就是如何通過常年的試錯來計算每個行為的結(jié)果，所謂一朝被蛇咬，十年怕井繩。另一個就是看書，和高手對話直接學(xué)習(xí)它們的經(jīng)驗(yàn)。

反過來就是機(jī)器學(xué)習(xí)的原理，首先說試錯學(xué)習(xí)，或者根據(jù)某種行為最終導(dǎo)致的結(jié)果來調(diào)整行為策略的方法， 我們通常稱之為強(qiáng)化學(xué)習(xí)。

強(qiáng)化學(xué)習(xí)通常用如上框圖實(shí)現(xiàn)， 即agent會根據(jù)環(huán)境給與的reward調(diào)整action的一個反饋系統(tǒng)， 最終實(shí)現(xiàn)利益最大化， 難點(diǎn)在于agent的行為通常改變環(huán)境，而環(huán)境影響行為策略。

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

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

2.  每一步的策略只需考慮這一步的狀態(tài)

這允許機(jī)器學(xué)習(xí)用一個非常兇猛的簡化框架來解決這個問題，馬爾科夫決策過程。也即是說我們用一個離散的時間序列來表述狀態(tài)s，另一個離散的時間序列表述行為a，兩個時間序列有著深刻的耦合關(guān)系，下一刻的狀態(tài)s（t+1）取決于此刻行為 a（t）和狀態(tài) s（t），最終決定下一刻的行為 a（t+1） 兩者間的關(guān)系即策略P（a（t）|s（t）），由于是馬爾科夫鏈， 所以每一時刻的策略只與此刻狀態(tài)s（t）有關(guān)。  

各種棋類就是最明顯的馬鏈。 由于未來存在不確定性， 策略本身也是一個概率分布函數(shù)的形式。最終我們要優(yōu)化采取P（s|a）所得到的回報R（s）最大。馬爾科夫決策過程是在解決未來狀態(tài)不確定而狀態(tài)和行為又具有馬氏性時十分有利的方法。

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

 

 圖： 蒙特卡洛樹與它的四個步驟 ，選擇，擴(kuò)張， 模擬估值和結(jié)果回傳，對應(yīng)一個經(jīng)典的強(qiáng)化學(xué)習(xí)框架

說到蒙特卡洛， 這是大名鼎鼎的隨機(jī)抽樣方法。所謂樹，大家一定可以想到?jīng)Q策樹，樹的節(jié)點(diǎn)是某一刻的狀態(tài)，而枝杈代表一個決策， 而這里的蒙特卡洛樹， 即用隨機(jī)抽樣的方法生成整個決策樹的過程。

假設(shè)電腦現(xiàn)在的狀態(tài)是s（t）， 那么你隨便扔個篩子走一步，然后電腦模擬的對手也扔個篩子隨便走一步，這樣下下去， 總有一刻會分出勝負(fù)， 這個時候你回顧勝利和失敗的人的歷史走棋軌跡，贏的走法在其整個決策樹上的每個狀態(tài)（枝葉）都加一分， 輸?shù)淖叻恳徊轿恢枚紲p一分， 這個分?jǐn)?shù)會影響下一次抽樣的概率 ， 使得容易贏的步子會有更大概率取到。 最終依次往復(fù)電腦和電腦玩無數(shù)次后， 就會選擇出特別容易贏的策略。 這個過程酷似進(jìn)化選擇算法， 就是讓那些有優(yōu)勢的選擇有更高的繁殖子代概率， 從而最終勝出，體現(xiàn)了生物和環(huán)境的博弈。

注：這里提個小問題, 馬爾科夫決策過程威力巨大， 而在現(xiàn)實(shí)決策里，你要去哪個大學(xué)上學(xué)，你要選哪個股票，都的策略選擇都很難只看當(dāng)下，這個框架還能用多少呢？

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

注： 此處小心我們經(jīng)常會覺得直覺這個東西好像是天上掉下來的異稟，實(shí)則恰相反。直覺才是最需要學(xué)習(xí)的。

讓機(jī)器來做就是有監(jiān)督學(xué)習(xí)的回歸算法， 你要提取棋局的特征，算出對應(yīng)每一個走法出現(xiàn)的概率P(a(t)|s(t))，然而圍棋棋局的特征實(shí)在太復(fù)雜，如果你來一個線性回歸或KNN，一定會死的很慘。 這時候我們的深度學(xué)習(xí)開始派上用場。它可以自發(fā)的學(xué)習(xí)事物的表征。

圖，通過梯度回傳訓(xùn)練網(wǎng)絡(luò)連接

機(jī)器學(xué)習(xí)訓(xùn)練的目標(biāo)即使得數(shù)據(jù)被觀測到的概率最大，所謂Maximum Likelihood，對于神經(jīng)網(wǎng)絡(luò)，就是網(wǎng)絡(luò)連接參數(shù)的調(diào)整。

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

圖：策略網(wǎng)絡(luò)的思維，計算每種走法出現(xiàn)的概率

訓(xùn)練的最后一步是估值網(wǎng)絡(luò)，說說這里估值網(wǎng)絡(luò)是干什么的， 首先，在一個強(qiáng)化學(xué)習(xí)框架下， 你需要知道每個行為所對應(yīng)的確定回報，難點(diǎn)在于圍棋下完棋才有確定回報，想想圍棋步驟中的無限多可能性及得到結(jié)果可能的步數(shù)就令人生畏，此處深度學(xué)習(xí)算法的作用正是不需要走完就巧妙的估計出這一步對應(yīng)的贏利期望， 過程需要用一個深度網(wǎng)絡(luò)通過強(qiáng)化學(xué)習(xí)的框架來進(jìn)行。估值網(wǎng)絡(luò)的本質(zhì)在于建立現(xiàn)有行為和長遠(yuǎn)收益的聯(lián)系。 有人稱為看趨勢和全局觀。  訓(xùn)練這樣一個計算回報的網(wǎng)絡(luò)作用請往下看。

公式：  訓(xùn)練要解決的問題， 求得狀態(tài)S下采取策略p最終收益的期望

圖： 估值網(wǎng)絡(luò)的效果圖，數(shù)字即回報

那么問題來了， 蒙特卡洛樹和深度學(xué)習(xí)兩者如何天衣無縫的結(jié)合起來呢？ 這就是整個Alphago設(shè)計最巧妙的地方 ： 首先，你應(yīng)該還記得MCTS的框架， 首先MCTS可以拆解為4步：第一selection，在已有的選項(xiàng)（經(jīng)歷過的）中進(jìn)行抽樣選擇， 第二expansion， 走到一個沒有先前從未經(jīng)歷的局面上，探索新行為，即生成新的枝杈， 第三Evaluation，得到新行為的回報，第四，回傳，把回報的結(jié)果反向傳遞給策略。深度學(xué)習(xí)的結(jié)果可以被非常完美的嵌入到蒙特卡洛搜索的步驟里， 首先在expansion的步驟，我們不用從零開始隨機(jī)的生成一個前所未有的狀態(tài)，而是用根據(jù)前人經(jīng)驗(yàn)訓(xùn)練的策略網(wǎng)絡(luò)直接生成新狀態(tài)， 海量了減小了無用的搜索。 然后， 在Evaluation的步驟上， 我們可以不需要跑完整個比賽，而是通過深度學(xué)習(xí)的結(jié)果直接算出這個新姿勢可能的長期回報（此處即估值網(wǎng)絡(luò)的巨大作用，所謂步步看清n久之后的影響），這個計算出的回報，會在最終游戲完成的時候與真正實(shí)踐的結(jié)果相結(jié)合完成學(xué)習(xí)的步驟。

 

圖 ：深度學(xué)習(xí)如何嵌入蒙特卡洛樹搜索

與戰(zhàn)勝國際象棋大師的深藍(lán)不同， 在Alphago的情形下機(jī)器學(xué)習(xí)發(fā)揮了巨大的作用，因?yàn)锳lphago的策略和智能主要是在不?？雌遄V和左右互搏中進(jìn)化出來的，對于圍棋這樣規(guī)則非常復(fù)雜的東西，設(shè)計一套必勝規(guī)則幾無可能，也只有機(jī)器學(xué)習(xí)（強(qiáng)化學(xué)習(xí)）的進(jìn)化和自我改進(jìn)思想才是最終取勝之法器。也是為什么Alphago的技術(shù)對其它人工智能非常有啟發(fā)。  

從整個上面的解析看來， 其實(shí)訓(xùn)練Alphago的算法思路并非十分復(fù)雜，用一句話總結(jié)， 就是在巨人的肩膀上迅速試錯。 這也是各種人生決策的最好辦法吧。 你說你要活獨(dú)一無二的人生不模擬任何人，你估計是個撞南墻的傻X，你說你要就看著最牛逼的精英跟著走， 你可能一輩子重復(fù)別人的生活。而牛X的人， 顯然是站在巨人的肩膀上，邊描摹那三千萬精英的步法，并深度總結(jié)其規(guī)律， 然后在變化自己的動作花樣。 然而我們?nèi)祟悰]有那么多時間完simulation，也沒有那么多GPU進(jìn)行并行運(yùn)算， 所以我們其實(shí)在找的是低搜索成本的近似解，謂之次優(yōu)解。

歡迎關(guān)注巡洋艦機(jī)器學(xué)習(xí)對抗復(fù)雜系統(tǒng)系列后續(xù)--一個強(qiáng)化學(xué)習(xí)在電網(wǎng)設(shè)計中的實(shí)例

雷鋒網(wǎng)注：本文由許鐵-混沌巡洋艦授權(quán)雷鋒網(wǎng)發(fā)布，如需轉(zhuǎn)載請聯(lián)系微信號562763765。

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。