760
探索Alpha-Go —— AI是如何在圍棋項目上打敗人類的
更多深度文章，請關注：https://yq.aliyun.com/cloud
作者介紹：irek Stanek
Head of mobile dev at @Azimo. Artificial Intelligence adept.
I dream big and do the code . More dev blog posts on https://frogermcs.github.io/
AI工程師的一項必須技能就是理解並能解釋領域內的高度技術性的論文。我在AI Nanodegree課程中的一個課題就是分析《自然》雜誌上關於AlphaGo的一篇文章——《Google Deepmind system which for the first time in history beat elite professional Go player, winning by 5 games to 0 with European Go champion — Fan Hui》。這篇文章的目的是為了使得這些知識更通俗易懂，尤其是對初學者和首次接觸的人。
AlphaGo和數學
AlphaGo是穀歌DeepMind小組研發的針對圍棋的AI。而在AlphaGo 出現之前，有預測稱根據現有的最新技術，能擊敗人類職業圍棋選手的AI還要十年才會出現。
為什麼圍棋比國際象棋簡單，但是卻引起了這麼多的關注？
是因為複雜性。
圍棋和國際象棋都是完美信息的遊戲，每個玩家完全知道以前發生過的所有事件，因此遊戲存在最優解。如果使用搜索樹的方法尋找最優解，國際象棋存在10¹²³種解，而圍棋存在10³⁶⁰種解（譯者注：可以簡單理解為圍棋棋盤比較大因此解多）。而一般的多核處理器每秒鍾可以做10⁹次運算，意味著如果要算盡圍棋的解需要花費的時間比宇宙存在的時間還要長。
AlphaGo和其他AI遊戲程序的最高級別目標是有效減少搜索空間，在合理的時間（AlphaGo的每次運動時間為5s）內，盡可能快的結束遊戲。
為了估計每個遊戲狀態的價值，AlphaGo使用蒙特卡羅樹搜索（MCTS）——通過基於搜索空間的隨機抽樣擴展搜索樹——來分析最優的動作。 MCTS在遊戲中基於許多playouts來運作，這些playouts是在隨機落子的遊戲中生成的；每個playout的結果都倍用來衡量遊戲樹中不同節點的權重，這樣在未來的playouts中，好的節點更有可能被選中。通過附加策略增強的MCTS（例如預測人類專家動作）使我們有可能實現strong-amateur級別遊戲。
下一步會基於預先訓練好的深度卷積網絡。這種技術現在廣泛用於圖像分類、人臉識別或玩Atari遊戲。旁注：人們可以從Facebook的Intro to AI movies開始了解深度學習或卷積網絡的工作原理。
AlphaGo使用神經網絡的目標是：有效位置評估（價值網絡）和行動抽樣（策略網絡）。
策略網絡
為了訓練策略網絡，機器學習有兩個階段。
第一階段是監督學習（SL）（它擴展了MCTS解決方案，用於預測人類職業棋手的行動）。 SL策略網絡已經根據KGS Go Server的3000萬個案例進行了訓練。經過訓練的網絡能夠準確預測專家行動，準確率高達57％（其他研究團隊最高為44.4％）。
然而雖然新的準確性提高了，但評估速度明顯較慢。因此有了另一個被稱為快速推出（FR）的策略。它不太準確（27％），但更快（2μs至3ms），被用於在評估MCTS中的節點時運行rollouts一直到遊戲結束。
第二階段是增強學習（RL）。SL擅長預測下一個最有可能的行動，而RL能夠預測最能夠獲勝的行動。在這個階段，AlphaGo通過隨機選擇迭代之前的自己進行了120萬場遊戲。
相比RL，SL能夠贏得超過80％的遊戲；而與Pachi相比，這個數值高達85%（Pachi是一個基於蒙特卡洛樹搜索啟發式的開源程序，在KGS業餘愛好者中排第二）。而之前的基於SL的解決方案在對陣Pachi時，隻能夠贏得約11％的遊戲。
價值網絡
訓練的最後階段主要集中在位置評估（position evaluation）（估計當前行動的獲勝概率）。對KGS數據集的訓練會導致過擬合，為了防止這種情況，新的訓練集是由自動播放數據產生的（3000萬個不同的位置，每個都是從不同的遊戲種抽取的） 。
訓練價值函數比使用rollout策略的蒙特卡洛算法更準確，其單次評估準確率與使用強化學習策略的蒙特卡羅算法類似（但計算量減少了15000倍）。
策略和價值網絡搜索
AlphaGo在蒙特卡羅搜索樹中使用策略和價值網絡的組合。遊戲樹的搜索由下麵4個階段組成：
- 選擇 - 模擬通過選擇具有最大動作值Q（這個移動有多好）的edge來遍曆樹。
- 擴展 - 如果任何節點被擴展，則由SL策略網絡處理一次，以獲得每個行動的先驗概率。
- 評估 - 每個節點通過價值網絡和FR策略進行評估。
- 備份 - 動作值Q由評估步驟收集的值進行更新。當遊戲代理的時間結束時，通過最高動作值Q選擇最佳移動。
結果
AlphaGo的表現是眾所周知的。在2015年，它擊敗人類職業棋手樊麾，歐洲多個聯賽的冠軍。這是機器第一次在圍棋中擊敗了職業棋手。在與其它最好的圍棋程序（如Crazy Stone, Pachi, Zen等）進行的比賽模擬中，AlphaGo獲勝率高達99.8%。 AlphaGo的分布式版本對單機版本的勝率為77％，意味著它不僅表現強勁，而且還具有很好的可擴展性。在與樊麾的比賽中，AlphaGo花費的步數要比當年深藍大戰Kasparov少了1000倍，意味著落子更加智能。
這些所有結論清楚地表明，多虧了AlphaGo，我們在尋找General AI and the Singularity的路上又近了一步。
本文由北郵@愛可可-愛生活老師推薦，阿裏雲雲棲社區組織翻譯。
文章原標題《Understanding AlphaGo How AI beat us in Go-game of profound complexity》，作者：Mirek Stanek，譯者：壯如山的漢子，審閱：
文章為簡譯，更為詳細的內容，請查看原文。
最後更新：2017-04-07 21:25:10