深度 | 從AlphaGo的成功說起

01-29

原文發表於中國計算機學會通訊，2017年第3期，p76-81
作者: 文因互聯團隊張夢迪、鄭錦光、張強、鮑捷

AlphaGo的基本原理

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

根據谷歌DeepMind團隊發表的論文[1]，我們可以窺探到AlphaGo的基本設計思路。任何完全信息博弈都無非是一種搜索。搜索的複雜度取決於搜索空間的寬度（每步的選擇多寡）和深度（博弈的步數）。對於圍棋，寬度約為250，深度約為150。AlphaGo用價值網路(value network)消減深度，用策略網路(policy network)消減寬度，從而極大地縮小了搜索範圍。

所謂價值網路，是用一個「價值」數來評估當前的棋局。如果我們把棋局上所有棋子的位置總和稱為一個「狀態」，每個狀態可能允許若干不同的後續狀態。所有可能狀態的前後次序關係就構成了所謂的搜索樹。一個暴力的搜索演算法會遍歷這個搜索樹的每一個子樹。但是，其實有些狀態是較容易判斷輸贏的，也就是評估其「價值」。我們把這些狀態用價值表示，就可以據此省略了對它所有後續狀態的探索，即利用價值網路削減搜索深度。

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

更通俗地說，所謂「價值」就是能看懂棋局，一眼就能判斷某給定棋局是不是能贏，這是個偏宏觀的評估。所謂的「策略」，是指在每一步博弈時，各種選擇的取捨，這是個偏微觀的評估。AlphaGo利用模擬棋手、強化自我的方法，在宏觀（價值評估）和微觀（策略評估）兩個方面提高了探索的效率。

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

基於類似的卷積神經網路結構，AlphaGo先做策略學習（學習如何下子），再做價值學習（學習評估局面）。策略學習也分為兩步。第一步是有監督學習，即「打譜」，學習既往的人類棋譜。第二步是強化學習，即「左右互搏」，通過程序的自我博弈來發現能提高勝率的策略（見圖1）。

圖1　策略網路和價值網路的訓練過程

先說「打譜」（有監督學習）。AlphaGo學習了KGS網站上3000萬個落子位置。它先隨機選擇落子位置，利用既往的棋譜來「訓練」，試圖預測人類最可能在什麼位置落子。

如果僅用落子歷史和位置信息，AlphaGo的預測成功率是55.7%。如果加上其他特徵，預測成功率可以進一步提高到57%。

在數學上，打譜是用一種梯度下降演算法訓練模型。給定一個棋局和一個落子方式，為了計算人類棋手會有多大概率採用這種下法，AlphaGo用一個13層的卷積網路來訓練這個概率的評估。這也是神經網路應用的經典做法，即基於梯度下降來逼近一個函數的學習，這裡函數就是棋手如何落子的概率。

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

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

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

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

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

AlphaGo為什麼能贏

拆開看AlphaGo演算法的每個部分，其實都是已有的成熟技術，創新之處是將這些技術進行組合，並在具體的問題上進行優化。

人工智慧是如何打敗職業棋手的？核心是機器在策略學習中的高效率和因此帶來的超越人類的策略的突破。與其說AlphaGo和Master標誌著機器對人類的勝利，不如說是科學家聯手工程師對行業專家的勝利，是通用計算基礎和理論框架日益臻熟的體現。這已不是第一次機器的勝利，情理之中，意料之外。

和當年的國際象棋程序深藍相比，AlphaGo有哪些進步？

它可以用策略網路更「聰明」地選擇應對，用價值網路更「精確」地評估局面。另外，它不再單純依賴於手工構造的評估函數，而是利用了深度學習的特徵學習能力，僅僅使用通用的監督學習演算法和強化學習就實現了領域建模，降低了對人類專家的依賴。

從表面上看，AlphaGo的成功取決於對暴力搜索效率的提升。但在大規模效率提升的基礎上，從量變到質變，計算機甚至可以下出人類從來沒有想過的下法。人在圍棋中引以為豪的大局觀、棋感，可能恰恰是有限計算量限制下的無奈之舉。計算機卻可以跳出這些限制來開創。

中國棋手柯潔在與Master對弈後說：「人類數千年的實戰演練進化，計算機卻告訴我們人類全都是錯的。我覺得，甚至沒有一個沾到圍棋真理的邊。從現在開始，我們棋手將結合計算機，邁向全新的領域達到全新的境界。」

簡明人機對抗史

目前，在人機對戰類遊戲中，人工智慧解決得比較出色的基本上都是零和遊戲。其中，比較出名的人工智慧機器有：深藍[2]、Watson[3]、AlphaGo[1]和最近剛剛拿了德州撲克比賽第一名的Libratus[4]。

深藍是IBM研發的一款針對國際象棋對戰的計算系統。1997年，深藍以3.5:2.5的比分戰勝了當時的國際象棋世界冠軍帕斯卡羅夫。深藍能夠取得這個巨大成功，主要歸功於IBM當時為之設計的高性能超級計算機。這台計算機擁有32個IBM RS/6000 SP核， 256個處理器，能夠在一秒鐘內完成對200萬個狀態的分析。即使深藍使用的是接近「暴力搜索」的演算法，這種計算能力對於深藍在分析國際象棋局面上已然足夠。

2011年，由IBM團隊研發的智能問答系統Watson在問答遊戲「危險邊緣(Jeopardy! )」中擊敗了之前的人類贏家布拉德·魯特(Brad Rutter)和肯·詹寧斯(Ken Jennings)。Watson是問答系統技術的集大成者，其中關鍵的技術創新有：一套複雜的證據可信度評估系統，讓機器從數萬種可能的選擇中發現最可能的答案；運用新興的語義網技術和結構化知識庫，融合常識知識；綜合運用基於知識庫和基於信息檢索的技術，降低知識獲取和表達的成本。

在很長一段時間，圍棋被認為是在遊戲對戰人工智慧中，人類智慧守護的最後一片土地。MoGo[5]在2008年的美國圍棋公開賽上，第一次在19×19的全尺寸棋盤上擊敗了職業選手（與AlphaGo不同，這位職業選手讓了9個子）。到2016年，AlphaGo以4:1的戰績擊敗職業九段選手李世石，以及之後Master更以快棋60贏0負的驚人戰績橫掃線上圍棋平台。就如本文之前提到的，在圍棋中，由於搜索的複雜度，單純的「暴力搜索」的演算法已然不再適用。

2017年1月，由卡內基梅隆大學(CMU)教授桑德霍爾姆(Sandholm)帶領開發的Libratus又為人工智慧攻克了一個戰場：德州撲克。撲克不同於圍棋，是非完整信息博弈。Libratus採用的方法里包括了博弈論。大量的經濟學、金融、政治和社會問題都可以在博弈論的框架下建模，因此，Libratus的成功打開了在諸多新領域應用人工智慧的大門。

從深藍到Libratus，人機對抗中部分關鍵項目和演算法的回顧如表1所示。

表1　人機對抗中部分關鍵項目和演算法

下一個賽點會在哪裡

可以看到，目前人工智慧所攻克的棋牌類遊戲，基本屬於動態雙人非合作的零和博弈，存在前提假設是參與者有明確的策略空間和收益函數，並且都是與時間無關的。

這裡參與者策略空間是在當前的牌局或者棋局下可以採取的行為。收益函數指當所有參與者都採取某種策略後，當前參與者所獲得的收益。零和意味著參與者勝/負/平的遊戲結果簡潔明了。在這樣相對封閉的遊戲空間中，給定明確參數，相對較短時間，通過海量輪次的深度學習和強化學習，人工智慧技術可能會發現一些人類沒有發現的特徵，找出一些人類沒有意識到的相關性，走出一些人類沒法理解的棋，也就是人們常說的「AI棋」。

當探索人工智慧所能征服的下一個領域的時候，將面臨如下挑戰：

1.面對多人合作博弈，策略空間和收益函數都難以確定。
2.面對非零和博弈，強化學習所依賴的回報函數難以確定。
3.面對開放的領域空間，時間維度因素對強化學習的影響難以確定。

為了應對這些情況，人工智慧可能採取的策略是對領域抽象建模，設定前提條件，構造封閉問題空間，實現對真實領域的映射。這個過程必然會依賴人類的智慧，也是將人工智慧技術擴展到其他領域的關鍵瓶頸所在。

那麼，未來可能突破的領域會有怎樣的特點呢？我們用金融投資領域作為例子。這裡的金融投資是指對公司價值進行分析判斷來進行的投資活動，而非日內交易型的投機活動。在該前提下，參與者的策略空間和收益函數是經過系統研究的，有一系列的價值策略投資理論作為支撐。

對於金融投資，結束條件的界定可以進行分類處理，比如單筆交易、時間周期和投資的計量結果是「可微分的」。回報函數可以抽象為在某種具體某種類型的投資約束條件下的盈虧。時間維度問題，可以依靠金融和法律知識去構建一個局部的單一時間維度的場景，也可以通過演算法去把不同時間維度標準化。

對這樣的領域，儘管存在領域知識要求非常高、信息不完備、非封閉世界等困難，我們是可能融合AlphaGo和Libratus的方法論，開發出優於初級人類分析師的AI程序的。

人工智慧技術在向其他領域擴展的時候，很大程度上依賴於人類對該領域的建模和抽象。大眾對人工智慧技術好奇，核心關注點往往是人工智慧是否擺脫人類影響，是否具有自由意識和思維等。這裡涉及到人工智慧的諸多哲學問題，包括概念框架問題、常識表徵問題和現象意識問題等。

AlphaGo在過去一年的成功，引發了媒體和很多領域對人工智慧的強大興趣和一些不必要的擔心。現在的人工智慧，離這種擔心所對應的強人工智慧，還有很遠的距離。給定目標問題求解的能力，和可以自主尋找問題、設定目標的能力還是有很大差距的。技術落地的設計、工程化也有很長的路要走。

參考文獻

[1] Silver D, Huang A, Maddison C J, et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529(7587): 484-489.

[2] Campbell M, Hoane A J, Hsu F. Deep Blue[J]. Artificial Intelligence, 2002, 134(1-2): 57-83.

[3] Ferrucci D, Brown E, Chu-Carroll J, et al. Building Watson: An overview of the DeepQA project[J]. AI Magazine, 2010, 31(3): 59-79.

[4] Brown N, Sandholm T. Strategy-based warm starting for regret minimization in games. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16), 2016:432-438.

[5] Gelly S, Wang Y, Teytaud O, et al. Modification of UCT with patterns in Monte-Carlo Go[J]. HAL-INRIA, 2006.

[6] Coulom R. Efficient selectivity and backup operators in Monte-Carlo tree search. Proceedings of International Conference on Computers and Games. Springer Berlin Heidelberg, 2006: 72-83.

[7] Brügmann B. Monte Carlo Go[R]. Technical report, Physics Department, Syracuse University, 1993.

[8] Kocsis L, Szepesvári C. Bandit based Monte-Carlo planning. Proceedings of European Conference on Machine Learning. Springer Berlin Heidelberg, 2006: 282-293.

[9] Gelly S, Wang Y, Teytaud O, et al. Modification of UCT with patterns in Monte-Carlo Go[J]. HAL-INRIA, 2006.

[10] Enzenberger M, Muller M, Arneson B, et al. Fuego—an open-source framework for board games and Go engine based on Monte Carlo tree search[J]. IEEE Transactions on Computational Intelligence and AI in Games, 2010, 2(4): 259-270.

[11] Bowling M, Burch N, Johanson M, et al. Heads-up limit hold』em poker is solved[J]. Science, 2015, 347(6218): 145-149.

[12] Morav?ík M, Schmid M, Burch N, et al. DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker. arXiv preprint arXiv:1701.01724, 2017.

[13] Tian Y, Zhu Y. Better computer go player with neural network and long-term prediction. arXiv preprint arXiv:1511.06410, 2015.