AlphaGo是GoogleDeepMind團隊開發(fā)的一個基于深度神經(jīng)網(wǎng)絡的圍棋人工智能程序，其一共經(jīng)歷了以下幾次迭代^[1]：

?

一個馬爾可夫決策過程（Markov Decision Processes，MDPs）通常包括以下幾個要素：

在定義了以上幾個要素之后，我們可以來描述一個典型的MDPs：從某個起始狀態(tài)開始，選擇采取動作，然后，以的概率轉(zhuǎn)換到下一個狀態(tài)，然后采取動作，并以

的概率轉(zhuǎn)換到下一個狀態(tài)……

如果MDPs的狀態(tài)集合和動作集合是有限大的，則稱之為有限MDPs。??????

通常，我們還會定義另外一個參數(shù)——折扣因子（discountfactor）。定義折扣因子之后，MDPs的總回報可以表示為：。

?

MDPs的核心問題是如何找到一個對所有狀態(tài)都適用的最優(yōu)策略，按照此策略來選擇動作，使總回報的期望最大化。在總回報中加入折扣因子后，為使總回報的期望最大化，須盡可能的將正向回報提前，負向回報推遲。

回想一下圍棋的對弈，起始狀態(tài)是一個空的棋盤，棋手根據(jù)棋面（狀態(tài)）選擇落子點（動作）后，轉(zhuǎn)換到下一個狀態(tài)（轉(zhuǎn)換概率為：其中一個狀態(tài)的概率為1，其他狀態(tài)的概率為0），局勢的優(yōu)劣是每個狀態(tài)的回報。棋手需要根據(jù)棋面選擇合適落子點，建立優(yōu)勢并最終贏下游戲，因此，圍棋可以看作是一個MDPs問題。（達觀數(shù)據(jù)）

定義一個策略??的狀態(tài)值函數(shù)（state-valuefunction）為：?

等式右半部即為總回報的期望值。展開等式的右半部分：

上面的等式稱作貝爾曼方程（Bellman equation），從貝爾曼方程可以看出，當前狀態(tài)的回報的期望包括兩部分：

?

1）當前狀態(tài)的立即回報；

2）后續(xù)狀態(tài)的回報的期望和與折扣因子之積。

?

定義最優(yōu)狀態(tài)值函數(shù)（optimal state-value function）為：

根據(jù)貝爾曼方程有：

定義策略為：

對于任意狀態(tài)和任意策略??，均有：

因此，策略即為最優(yōu)策略。

最優(yōu)策略可通過策略迭代來求解。一次策略迭代包括兩個步驟：

?

1）策略估計（PolicyEvaluation）：基于當前的策略和狀態(tài)值函數(shù)根據(jù)貝爾曼方程更新狀態(tài)值函數(shù)；

2）策略提升（PolicyImprovement）：基于當前的策略和1）中更新后的狀態(tài)值函數(shù)來更新策略。

?

策略迭代求解MDPs問題的算法如圖1所示^[2]。

圖1 策略迭代算法

?

為證明算法的收斂性，定義動作值函數(shù)（action-value function）為：

假設有兩個策略和，對于任意狀態(tài)均有，那么，對于任意狀態(tài)，不等式成立，即策略優(yōu)于策略。

?????????????

因此，在策略迭代中，每一次策略提升后，將得到一個更優(yōu)的解。對于有限MDPs，策略的個數(shù)是有限的，在經(jīng)過有限次的迭代之后，策略將收斂于最優(yōu)解。（達觀數(shù)據(jù)）

?

在策略迭代中，為了估計狀態(tài)值函數(shù)，需要計算并存儲所有狀態(tài)的值函數(shù)。在圍棋中，有超過2 x 10¹⁷⁰的狀態(tài)^[3]，遠遠超出了計算或存儲的極限，因此，策略迭代的方法不再適用。

蒙特卡洛方法（Monte Carlo Method）通過模擬采樣來估計狀態(tài)值函數(shù)和動作值函數(shù)，將采樣結果的均值作為估計值，根據(jù)大數(shù)定律，隨著采樣次數(shù)的增加，估計值將趨近于實際值。蒙特卡洛方法適用于“情節(jié)任務（episodic tasks）”，即不管使用哪種策略，最終都能到達終止狀態(tài)，圍棋是一種“情節(jié)任務”。蒙特卡洛方法對各個狀態(tài)的估計是相互獨立的，即在估計狀態(tài)值函數(shù)或動作值函數(shù)時不依賴于其他狀態(tài)的值函數(shù)，因此，不需要計算或存儲所有狀態(tài)的值函數(shù)。

為估計策略的動作值函數(shù)，把初始狀態(tài)置為，然后開始模擬采樣，在狀態(tài)上采取動作，轉(zhuǎn)換到下一個狀態(tài)，在后續(xù)的狀態(tài)中，依據(jù)策略??來選擇動作，直到到達終止狀態(tài)，記錄下此時的回報。重復執(zhí)行以上操作。對于路徑上的每一個狀態(tài)–動作對（state-actionpair），將所有包含此狀態(tài)–動作對的模擬的回報的均值作為動作值函數(shù)的估計值。以上過程稱之為“深耕（exploitation）”，即在現(xiàn)有的知識下，將每一步都做到最好。

?

策略是貪婪的，即在每個狀態(tài)上均以P=1的概率選擇當前最優(yōu)的動作，因此，對于任意動作，狀態(tài)–動作對都不會被選擇，其動作值函數(shù)也不會被估計。估計動作值函數(shù)的目的是幫助我們在狀態(tài)上選擇合適的動作，為了比較動作的收益，我們還需要估計這個狀態(tài)上其他的動作的值函數(shù)。為了估計其他動作的值函數(shù)，一種常用的方法是策略，其中是一個接近于0的小數(shù)，對于每一個狀態(tài)，以的概率選擇非貪婪動作，以的概率選擇貪婪動作。以上過程稱之為“探索（exploration）”，即不滿足于眼前的最好，探索未知中可能存在的更好。

?

在蒙特卡洛方法中，“深耕”使得我們更多的在最有希望的方向上搜索，而“探索”使得我們能夠同時兼顧到其他方向。（達觀數(shù)據(jù)）

?

圍棋的棋面可以看作是一個19 × 19的圖像，每一個棋子對應一個像素點，不同顏色的棋子對應不同的像素值?？紤]到深度神經(jīng)網(wǎng)絡，尤其是卷積神經(jīng)網(wǎng)絡在圖像領域的成功應用，AlphaGo使用卷積神經(jīng)網(wǎng)絡來估計當前的局面，選擇落子的位置。（

AlphaGo Zero所使用的卷積神經(jīng)網(wǎng)絡的輸入是19× 19 × 17的張量其17個通道中，表示t時刻棋盤上第i個位置是否有己方的棋子，表示t時刻棋盤上第i個位置是否有對方的棋子，C是一個常數(shù)，用于標識當前輪次的顏色；網(wǎng)絡包括兩個輸出，值函數(shù)和策略，是網(wǎng)絡的參數(shù)，輸出值函數(shù)的分支稱之為值網(wǎng)絡（Value network），輸出策略的分支稱之為策略網(wǎng)絡（Policy network）。在之前的版本中，值網(wǎng)絡和策略網(wǎng)絡是兩個同架構但分立的網(wǎng)絡，在AlphaGo Zero中，這兩個網(wǎng)絡合并成一個網(wǎng)絡^[4]。

圖2 AlphaGo Zero網(wǎng)絡架構

?

蒙特卡洛樹搜索使用蒙特卡洛方法估計搜索樹上的每個節(jié)點的統(tǒng)計量。AlphaGo將策略迭代與蒙特卡洛樹搜索（Monte Carlo Tree Search，MCTS）結合了起來。對于每個狀態(tài)，根據(jù)策略網(wǎng)絡輸出的策略選擇動作，執(zhí)行MCTS。MCTS輸出策略，通常這個策略要比策略網(wǎng)絡輸出的策略更加健壯，因此，這個過程可以看作是策略迭代中的策略提升；根據(jù)MCTS輸出的策略選擇動作，并轉(zhuǎn)換到下一個狀態(tài)，然后執(zhí)行MCTS…，直到終止狀態(tài)（游戲結束），將游戲的勝者作為模擬的結果，這個過程可以看作是策略迭代中的策略估計，如圖3(a)所示。作為一個訓練樣本，用于訓練神經(jīng)網(wǎng)絡，更新網(wǎng)絡參數(shù)，如圖3(b)所示。在后續(xù)的策略迭代中，使用更新后的神經(jīng)網(wǎng)絡來指導MCTS。

圖3 AlphaGo的強化學習算法

2.1 策略提升

?

在MCTS的過程中，搜索樹上的每個節(jié)點的每條邊維護一個集合，其中，是此條邊被訪問的次數(shù)，是總的動作值函數(shù)，是平均動作值函數(shù)，是在狀態(tài)采取動作的先驗概率。

?

策略提升的一次搜索過程包括以下幾個步驟：

?

1）對于從根節(jié)點到葉節(jié)點之間的每個節(jié)點，動作的選擇策略是，其中，c用于控制策略中“探索”的比重，當c=0時，該策略即為貪婪策略，如圖4(a)所示。

?

圖4 MCTS

?

在MCTS的初期，該策略傾向于選擇先驗概率大、訪問次數(shù)少的動作，隨著搜索的進行，將更多地選擇值函數(shù)大的動作。此外，為了鼓勵“探索”，對于根節(jié)點還會在其策略上疊加一個狄利克雷（Dirichlet）噪聲，，其中。

2）在搜索到達葉節(jié)點后，將輸入到神經(jīng)網(wǎng)絡中計算值函數(shù)和策略。對于此節(jié)點的每條邊，初始化其集合為：

其中是中動作的先驗概率，如圖4(b)所示。

?

3）備份，更新搜索路徑上節(jié)點的邊的集合中的元素

如圖4(c)所示。?在多次搜索之后，根據(jù)根節(jié)點上的各條邊的訪問次數(shù)輸出策略

，是溫度參數(shù)，用于控制“探索”的比重，如圖4(d)所示。

?

2.2 策略估計

在狀態(tài)上，按照策略提升返回的策略選擇落子位置。在游戲的初期（前30手，），為了鼓勵“探索”、提升棋局的多樣性，將溫度參數(shù)的值設為1，即，選擇落子位置的概率正比于節(jié)點的這條邊在策略提升中被訪問的次數(shù)；在30手之后，溫度參數(shù)，此時，策略是貪婪的，以P=1的概率選擇訪問次數(shù)最多的邊。

在狀態(tài)上執(zhí)行動作后，進入到下一個狀態(tài)，將搜索樹上所對應的節(jié)點作為新的根節(jié)點，執(zhí)行MCTS，返回提升后的策略，…，直到游戲結束，將游戲的勝者作為狀態(tài)的值函數(shù)的估計值。

?

這個過程即self-play。為了提高搜索的效率，在策略提升時，當搜索到葉節(jié)點后，使用值網(wǎng)絡估計狀態(tài)值函數(shù)作為收益返回，避免繼續(xù)向下搜索，限制搜索的深度；在策略估計時，使用策略提升輸出的策略來指導動作的選擇，限制搜索的廣度。另外，如果值網(wǎng)絡估計的局勢的收益（勝率）低于一個閾值之后，便放棄此局游戲。

2.3 旋/翻轉(zhuǎn)不變性

?

將圍棋的棋盤旋轉(zhuǎn)或翻轉(zhuǎn)之后，不會影響局勢，落子的位置也只需要做相應的變換即可。即，如果狀態(tài)被旋轉(zhuǎn)或翻轉(zhuǎn)，值網(wǎng)絡的輸出不變，策略網(wǎng)絡的輸出做相應的變換，假設d為變換函數(shù)，則有。在策略提升中，當搜索到達葉節(jié)點后，從8種旋/翻轉(zhuǎn)變換中隨機地選取一種對葉節(jié)點的狀態(tài)進行變換，變換之后的狀態(tài)作為神經(jīng)網(wǎng)絡的輸入。

圖5 旋轉(zhuǎn)和翻轉(zhuǎn)

在self-play的每一局游戲中，會生成一系列的狀態(tài)–策略–值元組

這一系列狀態(tài)是強關聯(lián)的。為了避免過擬合這種關聯(lián)，每局游戲只隨機地選擇一個元組來組成訓練集^[5]。

模型優(yōu)化的損失函數(shù)是，其中，第一項為值網(wǎng)絡的輸出與self-play實際結果的均方誤差，第二項為策略網(wǎng)絡的輸出與策略提升的輸出的交叉熵，第三項為L2正則項。在損失函數(shù)中，由于，（值網(wǎng)絡的最后一層使用tanh激活函數(shù)），因此，均方誤差對損失函數(shù)的貢獻被限定在范圍內(nèi)。給予均方誤差和交叉熵相同的權重，避免由于過擬合了狀態(tài)值函數(shù)而出現(xiàn)“模型能夠精準預測游戲勝負卻輸出糟糕的策略”的現(xiàn)象。

模型參數(shù)更新使用帶動量和學習率衰減的隨機梯度下降方法，動量因子設為0.9，學習率在優(yōu)化的過程中從0.01衰減到0.0001。每次從最近的500,000局游戲中隨機地選取一個大小為2048的mini-batch，每1000次更新之后，對模型進行評估。

?

?

更新后的模型與當前最優(yōu)的模型對戰(zhàn)400局，即，在策略提升中，分別使用和來估計葉節(jié)點的值函數(shù)和各條邊的先驗概率，在選擇落子位置時，溫度參數(shù)，在每一步均貪婪地選擇訪問次數(shù)最多的邊。如果新模型的勝率大于55%，則新模型成為當前最優(yōu)的模型，并使用此模型進行self-play生成訓練數(shù)據(jù)，以確保訓練數(shù)據(jù)的質(zhì)量。

?

人工智能在很多領域已經(jīng)顯示出了超越人類的水準，并且還在不斷的攻城略地。達觀數(shù)據(jù)作為中國知名的文本智能處理企業(yè)，利用先進的文字語義自動分析技術，為企業(yè)、政府等各大機構提供文本自動抽取、審核、糾錯、搜索、推薦、寫作等智能軟件系統(tǒng)，讓計算機代替人工實現(xiàn)業(yè)務流程自動化，大幅度提高企業(yè)效率。

?

[1]https://deepmind.com/research/alphago/

[2]Sutton, R.S. and Barto, A.G., 2011. Reinforcement learning: An introduction.

[3]https://en.wikipedia.org/wiki/Go_(game)

[4]Silver, David, et al.”Mastering the game of Go without human knowledge.”?Nature?550.7676 (2017): 354

[5]Silver, David, et al.”Mastering the game of Go with deep neural networks and treesearch.”?nature?529.7587 (2016): 484