AlphaGo基本原理：演算法每個部分其實都是已有技術

繼AlphaGo於2015年8月以5-0戰勝三屆歐洲冠軍樊麾、2016年3月以4-1擊敗世界頂級棋手李世石後，今年1月，AlphGo的升級版本Master橫掃各路高手，取得60比0的驚人戰績。20 年前IBM深藍（Deep Blue）電腦擊敗國際象棋冠軍卡斯帕羅夫的情景還歷歷在目，短短2年時間，人工智慧在圍棋領域又創造了人機對抗歷史上的新里程碑。

根據穀歌DeepMind團隊發表的論文，

我們可以窺探到AlphaGo的基本設計思路。任何完全資訊博弈都無非是一種搜索。搜索的複雜度取決於搜索空間的寬度（每步的選擇多寡）和深度（博弈的步數）。對於圍棋，寬度約為250，深度約為150。AlphaGo用價值網路（value network）消減深度，用策略網路（policy network）消減寬度，從而極大地縮小了搜索範圍。

所謂價值網路， 是用一個“價值”數來評估當前的棋局。如果我們把棋局上所有棋子的位置總和稱為一個“狀態”，每個狀態可能允許若干不同的後續狀態。

所有可能狀態的前後次 序關係就構成了所謂的搜尋樹。一個暴力的搜索演算法會遍歷這個搜尋樹的每一個子樹。但是，其實有些狀態是較容易判斷輸贏的，也就是評估其“價值”。我們把這 些狀態用價值表示，就可以據此省略了對它所有後續狀態的探索，即利用價值網路削減搜索深度。

所謂策略，是指在給定棋局，評估每一種應對可能的勝率，

從而根據當前盤面狀態來選擇走棋策略。在數學上，就是估計一個在各個合法位置上下子獲勝的可能的概率分佈。因為有些下法的獲勝概率很低，可忽略，所以用策略評估就可以消減搜尋樹的寬度。

更 通俗地說，所謂“價值”就是能看懂棋局，一眼就能判斷某給定棋局是不是能贏，這是個偏宏觀的評估。所謂的“策略”，是指在每一步博弈時，各種選擇的取捨， 這是個偏微觀的評估。

AlphaGo利用模擬棋手、強化自我的方法，在宏觀（價值評估）和微觀（策略評估）兩個方面提高了探索的效率。

在具體演算法上，AlphaGo用深度卷積神經網路（CNN）來訓練價值網路和策略網路。棋盤規模是（19×19），棋盤每個位置編碼48種經驗特徵。把這些特徵輸入模型進行訓練，經過層層卷積，更多隱含特徵會被利用。

基於類似的卷積神經網路結構，AlphaGo先做策略學習（學習如何下子），再做價值學習（學習評估局面）。

策略學習也分為兩步。第一步是有監督學習，即“打譜”，學習既往的人類棋譜。第二步是強化學習，即“左右互搏”，通過程式的自我博弈來發現能提高勝率的策略（見圖1）。

先說“打譜”（有監督學習）。AlphaGo學習了KGS網站上3000萬個落子位置。它先隨機選擇落子位置，利用既往的棋譜來“訓練”，試圖預測人類最可能在什麼位置落子。如果僅用落子歷史和位置資訊，AlphaGo 的預測成功率是55.7%。如果加上其他特徵，預測成功率可以進一步提高到57%。在數學上，打譜是用一種梯度下降演算法訓練模型。給定一個棋局和一個落子 方式，為了計算人類棋手會有多大概率採用這種下法，AlphaGo用一個13層的卷積網路來訓練這個概率的評估。這也是神經網路應用的經典做法，即基於梯 度下降來逼近一個函數的學習，這裡函數就是棋手如何落子的概率。

再說“左右互搏”（強化學習）。這是在打譜的基礎上，讓不同下法的程式之間相互博弈。強化學習的策略網路和有監督學習（打譜）的網路結構一樣，也同樣利用梯度下降的學習方法。區別在於用一個“回報”（贏棋是1，輸棋是-1）來獎勵那些會導致最終獲勝的策略。

價值網路的學習和策略網路類似，也用類似結構的卷積神經網路。區別在於網路的輸出不是一個落子的概率分佈，而是一個可能獲勝的數值（即“價值”）。這個訓練是一種回歸（regression），即調整網路的權重來逼近每一種棋局真實的輸贏預測。

如 果只是簡單地讓程式之間自由博弈，可能會導致過擬合：對訓練的資料（棋譜）效果很好，但是對於沒見過的棋局效果欠佳。這是因為一盤棋內不同的棋局之間是有 依賴關係的，而價值函數並不考慮這些關係。解決方法是用來自不同對弈過程的棋局的落子位置進行訓練，避免來自同一棋局的狀態之間的“資訊污染”（相關 性）。

有了策略網路和價值網路，就可以進行策略的搜索了。AlphaGo使用了“蒙特卡洛樹搜索”（MCTS）演算法。所謂搜索，就是給定一個棋局，確定下一步的落子位置。這分為“往下搜”和“往回看”兩個環節。在“往下搜”的環節，對給定的棋局，程式選擇最可能獲勝的落子位置，然後如此類推，直到搜尋樹上能分出結果的“葉子”節點。在“往回看”的環節，一個棋局各種不同的演化可能性被綜合評估，用於更新搜尋樹對棋局的評估。

為了提高訓練效率，AlphaGo利用圖形處理器（GPU）運行深度學習演算法（訓練價值網路和策略網路），利用CPU運行樹搜索演算法。因為GPU適合做大輸送量、低邏輯判斷的工作，適合深度學習這種資料量大而邏輯簡單的演算法。中央處理器（CPU）則恰恰相反，適合蒙特卡洛樹搜索這種邏輯複雜的演算法。

本文摘錄自《從AlphaGo的成功說起》，作者張夢迪、鄭錦光、張強、鮑捷。即將發表於CCF會刊2017年3月號

利用既往的棋譜來“訓練”，試圖預測人類最可能在什麼位置落子。如果僅用落子歷史和位置資訊，AlphaGo 的預測成功率是55.7%。如果加上其他特徵，預測成功率可以進一步提高到57%。在數學上，打譜是用一種梯度下降演算法訓練模型。給定一個棋局和一個落子 方式，為了計算人類棋手會有多大概率採用這種下法，AlphaGo用一個13層的卷積網路來訓練這個概率的評估。這也是神經網路應用的經典做法，即基於梯 度下降來逼近一個函數的學習，這裡函數就是棋手如何落子的概率。

再說“左右互搏”（強化學習）。這是在打譜的基礎上，讓不同下法的程式之間相互博弈。強化學習的策略網路和有監督學習（打譜）的網路結構一樣，也同樣利用梯度下降的學習方法。區別在於用一個“回報”（贏棋是1，輸棋是-1）來獎勵那些會導致最終獲勝的策略。

價值網路的學習和策略網路類似，也用類似結構的卷積神經網路。區別在於網路的輸出不是一個落子的概率分佈，而是一個可能獲勝的數值（即“價值”）。這個訓練是一種回歸（regression），即調整網路的權重來逼近每一種棋局真實的輸贏預測。

如 果只是簡單地讓程式之間自由博弈，可能會導致過擬合：對訓練的資料（棋譜）效果很好，但是對於沒見過的棋局效果欠佳。這是因為一盤棋內不同的棋局之間是有 依賴關係的，而價值函數並不考慮這些關係。解決方法是用來自不同對弈過程的棋局的落子位置進行訓練，避免來自同一棋局的狀態之間的“資訊污染”（相關 性）。

有了策略網路和價值網路，就可以進行策略的搜索了。AlphaGo使用了“蒙特卡洛樹搜索”（MCTS）演算法。所謂搜索，就是給定一個棋局，確定下一步的落子位置。這分為“往下搜”和“往回看”兩個環節。在“往下搜”的環節，對給定的棋局，程式選擇最可能獲勝的落子位置，然後如此類推，直到搜尋樹上能分出結果的“葉子”節點。在“往回看”的環節，一個棋局各種不同的演化可能性被綜合評估，用於更新搜尋樹對棋局的評估。

為了提高訓練效率，AlphaGo利用圖形處理器（GPU）運行深度學習演算法（訓練價值網路和策略網路），利用CPU運行樹搜索演算法。因為GPU適合做大輸送量、低邏輯判斷的工作，適合深度學習這種資料量大而邏輯簡單的演算法。中央處理器（CPU）則恰恰相反，適合蒙特卡洛樹搜索這種邏輯複雜的演算法。

本文摘錄自《從AlphaGo的成功說起》，作者張夢迪、鄭錦光、張強、鮑捷。即將發表於CCF會刊2017年3月號