AlphaGo外傳——機器學習與演算法智能

阿狗數學的遠房親戚AlphaGo，即阿爾法圍棋，它是由谷歌旗下的DeepMind公司創始人Demis Hassabis團隊開發的人工智慧程序。這個程序在2016年和2017年出盡風頭，它讓圍棋高手陷入窘境，讓天才對未來憂心忡忡。那麼，AlphaGo的類腦機制的智商因何如此之高？

2015年10月，AlphaGo的初始版本AlphaGo Fan以5比0的傲人戰績擊敗歐洲圍棋三連冠棋手樊麾；2016年3月，升級版AlphaGo Lee與圍棋世界冠軍、職業九段棋手李世石對戰，以4比1的比分獲勝；2016年末至2017年初，再次升級的新版AlphaGo Master在中國棋類網站上以「大師」（Master）為註冊帳號與中日韓數十位圍棋高手進行快棋對決，連戰60局未嘗一敗；2017年5月，在中國烏鎮圍棋峰會上，AlphaGo Master與排名世界第一的棋手柯潔對決3局，無一敗北。見好就收，AlphaGo團隊宣布不再參加圍棋比賽，退出了人類圍棋圈。圍棋界普遍認為，AlphaGo的棋力已經超過了人類頂級職業棋手的水平。

2017年10月18日，DeepMind公司發布了AlphaGo的最新版本AlphaGo Zero。這個Zero經過三天三夜的訓練，就以100比0的離奇戰績擊潰Lee。再經過近四十天的訓練，它又擊敗了Master。Zero最引人注目的不僅僅在於它的戰績，更在於它完全脫離了人類棋譜，僅僅依靠自我訓練，就以更少的計算力度「超越」了前輩。AlphaGo神奇戰績的秘密都藏在它的腦組織：演算法之中。

根據AlphaGo團隊發表的首篇論文，任何完全信息博弈都是一種搜索，而搜索的複雜性則由搜索空間的寬度與深度決定。對圍棋來說，搜索寬度約為250，深度約為150。AlphaGo的早期版本，包括Lee和Master，其主要原理是深度學習、強化學習與蒙特卡羅樹搜索。

深度學習主要在於建立兩個受過訓練的模型網路：價值網路和策略網路。AlphaGo利用價值網路來削減搜索的深度，利用策略網路來削減搜索的寬度，從而極大地縮小了搜索空間。

價值網路是一種用來評估、度量當前棋盤狀態的神經網路。它的輸入是棋盤中19×19個點的狀態，輸出是獲勝的期望值。理論上總存在一個高級函數，它可以用來計算這個期望值。但遺憾的是，目前還沒有找到計算期望值的高級函數，所以人們只能用多層的神經元網路來擬合這個函數。對某些棋盤狀態輸贏是很容易判斷的，因而它們的後續狀態並不需要繼續探索。價值網路的目的就是通過確定那些輸贏容易判斷的棋盤狀態來削減搜索深度。

策略網路則是一種根據當前的棋盤狀態，評估每種著子的勝率，並從中選擇最大勝率著子的神經網路。其實這就是給出選擇可能著子的概率分布。同樣，也存在一個高級函數，它可以用來計算所述概率分布。也出於同樣原因，人們只能利用多層神經元網路來擬合所述高級函數。因為有些著子獲勝概率極低，可以忽略，因此可以利用策略網路確定可忽略的著子來削減搜索寬度。

AlphaGo具體使用深度卷積神經網路（CNNs）來訓練價值網路與策略網路。神經網路是用來模擬人類或動物大腦，利用多個神經元共同計算逼近某種複雜函數的方法。任何一種價值判斷都可以理解為某種從輸入到輸出的多元函數。數學上已經證明，使用神經網路可以無限逼近上述多元函數。由於圍棋盤可以看作一幅19×19的圖像，所以AlphaGo團隊選擇了適合處理圖像的深度（即多層的）卷積神經網路來構建價值網路與策略網路。

基於深度卷積神經網路，AlphaGo先進行策略網路學習，再進行價值網路學習。策略網路學習又分為兩步，第一步是有監督的學習，即學習人類的既往棋譜，也就是KGS圍棋平台上的3000萬個著子位置。AlphaGo會隨機選擇著子位置，利用以往的棋譜來預測人類棋手可能的應對著子位置，從而判斷每種著子的勝率。如果僅使用著子歷史和位置信息，預測成功率為55.7%；加上其他因素，成功率可以提高到57%。第二步是強化學習，即在監督學習策略網路的基礎上，不斷讓當前策略網路與前一策略網路進行對弈，並利用輸贏不同的反饋來優化策略網路。價值網路訓練與策略網路訓練類似，不過輸出的是獲勝的概率。

除了策略網路和價值網路，AlphaGo還有一個重要組成部分：快速著子分析模塊。該模塊與監督學習策略網路一樣，由人類棋譜訓練而來，可以看作是一個簡化版的監督學習策略網路，用於快速得到蒙特卡羅樹搜索過程中節點的模擬勝率。

在通過深度學習與強化學習完成價值網路、策略網路與快速著子分析模塊的構建後，AlphaGo通過蒙特卡羅樹搜索來實現思考搜索，其過程大致如下。

首先假定當前棋局狀態為S，並且對每種可能的著子a，都有著子價值Q(S,a)、初始概率P(S,a)及訪問次數N(S,a)。然後針對當前棋局，蒙特卡羅樹搜索不斷地進行棋局模擬。

在一次棋局模擬過程中，假設從根節點(S,a)出發到達第t個節點時的棋局狀態是S(t)，這時在所有可能的著子a中找出著子a(t)，使得Q(S(t),a)+u(S(t),a)最大。式中的Q(S(t),a)為當前節點的著子價值，它是由之前所有經過該節點的棋局模擬的最終勝率求平均得到，而且u(S(t),a)正比於P(S(t),a)/[1+N(S(t),a)]，其中初始概率P(S(t),a)為通過策略網路得到的獲勝概率，訪問次數N(S(t),a)為到目前為止所有棋局模擬過程中經過節點(S(t),a)的次數（這裡引入節點訪問次數是為了鼓勵嘗試新的節點）。

之後將著子a(t)作為棋局模擬的下一節點，並重複這一過程直至一個從未展開過的節點，該節點的子節點的初始概率在之前的棋局模擬中尚未計算。接下來對該節點的所有子節點計算最終勝率和初始概率，其中最終勝率是由通過價值網路得到的獲勝概率與通過快速著子分析模塊多次模擬棋局得到的模擬勝率加權平均所得到的。在選定最佳著子後，利用該著子的最終勝率，對當前棋局模擬經過的所有節點的著子價值與訪問次數進行更新。最後，完成本次棋局模擬，並開始下一次棋局模擬。

在蒙特卡羅樹搜索結束之後，由於每次棋盤模擬都是選擇最佳節點，AlphaGo會選擇根節點下訪問次數最多的子節點作為下一步的著子節點。至於蒙特卡羅樹搜索什麼時候終止，這要看AlphaGo有多少時間來走下一步棋。

以上是AlphaGo在Zero之前的幾個版本所使用的演算法。而在2017年10月推出的Zero與前輩相比，棋力有了很大提高，當然所用的演算法也有很大改善。下面我們來看一下Zero的演算法有哪些改進。

首先，取代之前同時使用策略網路與價值網路，Zero使用同一神經網路，輸入棋局狀態和歷史著子，輸出當前棋局的獲勝概率以及選擇可能著子的概率分布。然後，不再進行監督學習，Zero只進行強化學習，拋棄了人類棋局經驗。之後，與以前的需要在棋局之前進行訓練的強化學習網路不同，Zero可以直接通過棋局進行自我訓練。

最後，Zero在棋局中使用改進後的蒙特卡羅樹搜索來實現思考過程。之前的棋局模擬是在到達未展開的節點時結束，而改進後的棋局模擬在下列三種情形發生時也會結束：對手認輸，得到的最終勝率低於閾值，棋局模擬長度達到所規定的最大長度。在每次棋局模擬結束，Zero還會根據棋局模擬結果與神經網路計算結果來調整神經網路的參數，更新神經網路並開始下一輪棋局模擬。

Zero在不斷與自己對弈的過程中，獲得了許多關於圍棋博弈的新知識，並糾正了一些人類有關圍棋博弈的錯誤觀念。換句話說，Zero在探索圍棋博弈的過程中，大大提高了自身的博弈能力，其圍棋博弈技術與策略在某些方面已經超越了人類。目前尚無合理的解釋，Zero是如何在如此短的時間內達到了如此高的水平。

在圍棋領域AlphaGo雖然已經在某種程度上超越了人類，可是它已經堅定地退出了圍棋界，人們再也無法看到它與人類交手的場景。然而我們有足夠的理由相信，其他類似於AlphaGo的人工智慧程序譬如BetaOx（百牛），還會出現，還會在不遠的將來讓許多其他領域的天才在與其挑戰中一敗塗地。更令人擔憂的是，人工智慧會不會使很多職業人士失去自己熱愛的工作，無奈地離開自己的工作崗位？我們是應該期待還是拒絕人工智慧時代的到來呢？

（本文參考了AlphaGo團隊的兩篇論文《Mastering the game of Go withdeep neural networks and tree search》、《Mastering the game of Go without human knowledge》，張夢迪等人的《從AlphaGo的成功說起》，趙浩彤的《科普一下AlphaGo的論文演算法並談談自己的思考》和陳老師與待字閨中的《AlphaGo其實挺「笨」的》等著作。文中的圖片均來自網路及所列參考文獻。）?? 來源：阿狗數學AlgoMath

推薦閱讀：