初步認識AlphaGo Zero原理

04-13

本文是對AlphaGo Zero論文的個人初步的理解，難免有理解錯誤的地方，歡迎在評論區指正。

AlphaGo Zero的核心特點可以表述為：

單個神經網路收集棋局特徵，在末端分支輸出策略和棋局終止時的獎勵
自我對弈的強化學習的蒙特卡羅樹搜索(MCTS)
探索與利用的結合（Q+U 置信區間上限）

AlphaGo Zero概述

針對描述當前棋盤的一個狀態（位置） $s$ ，執行一個由神經網路 $f_{ heta}$ 指導的MCTS搜索，MCTS搜索輸出每一步行為（在某個位置落子）的概率。MCTS搜索給出的概率通常會選擇那些比由神經網路 $f_{ heta}(s)$ 給出的執行某一行為的概率要更強大。從這個角度看，MCTS搜索可以被認為是一個強大的策略優化工具。通過搜索來進行自我對弈——使用改善了的基於MCTS的策略來指導行為選擇，然後使用棋局結果（哪一方獲勝，用-1和1分別表示白方和黑方獲勝）來作為標籤數據——可以被認為是一個強大的策略評估工具。

Alpha Zero演算法主體思想就是在策略迭代過程中重複使用上述兩個工具：神經網路的參數得以更新，這樣可以使得神經網路的輸出 $(p, v) = f_{ heta}(s)$ ：移動概率和獲勝獎勵更接近與經過改善了的搜索得到的概率以及通過自我對弈得到的棋局結果，後者用 $(pi, z)$ 表示。得到的新參數可以在下一次自我對弈的迭代過程中讓搜索變得更加強大。（下圖）

圖一 Alpha Zero中的自我對弈強化學習

a. 程序自我對弈完成一個棋局產生一個狀態序列 $s_1,...,s_T$ ，在 $T$ 時刻棋局結束，產生了獲勝方，用 $z$ 表示。在其中的每一個時刻 $T$ ，棋局狀態用 $s_t$ 表示，會在神經網路 $f_{ heta}$ 的引導下執行一次MCTS搜索 ${alpha}_{ heta}$ ，通過MCTS搜索計算得到的概率 $a_t sim {pi}_t$ 確定如何行為（在何處落子）

b. 展示的Alpha Zero里神經網路的訓練過程。神經網路的輸入是某時刻 $t$ 的棋局狀態 $s_t$ 外加一些歷史和額外信息，輸出是一個行為概率向量 $p_t$ 和一個標量 $v_t$ ，前者表示的在當前棋局狀態下採取每種可能落子方式的概率，後者則表示當前棋局狀態下當前棋手（還是黑方？）最終獲勝還是落敗（分別用1和-1表示）。神經網路的訓練目標就是要儘可能的縮小兩方面的差距：一是搜索得到的概率向量 ${pi}_t$ 和網路輸出概率向量 $p_t$ 差距，二是網路預測的當前棋手的最終結果 $v_t$ 和最終遊戲贏家（1, -1表示）的差距。網路訓練得到的新參數會被用來知道下一輪迭代中自我對弈時的MCTS搜索。

圖二 Alpha Zero中的蒙特卡洛樹搜索

a. 每一次模擬過程會通過選擇那些擁有最大Q+U值的邊（表示基於某狀態下的某一行為）來遍歷樹結構。Q指的是行為價值，U指的是一個置信區間上限，可以根據先驗概率P和該邊（行為）被遍歷的次數計算得出

b. 當遍歷到樹中的葉節點時，將使用神經網路來設定該葉節點的Q值以及該葉節點下各種可能行為的概率，即： $(P(s,cdot),V(s)) = f_{ heta}(s)$ 。這些 $P$ 值存儲在節點 $s$ 連接至子節點的邊上。

c. 行為價值Q值會得到更新，以便可以追蹤當前行為下方的子樹里的所有節點 $V$ 值的平均。

d. 當搜索過程結束時，會產生一個搜索概率結果 $pi$ ，該結果與 $N^{1/ au}$ 成正比，其中 $N$ 表示的是從根狀態開始的每一個行為被訪問（模擬）的次數， $au$ 是一個控制火候（溫度）的一個參數

神經網路通過使用MCTS搜索的自我對弈強化學習來進行訓練。一開始神經網路的參數被隨機設置稱 $heta_0$ ，在隨後的每一次迭代中 $igeq1$ ,會通過自我對弈產生許多完整的棋局，在其中每一個完整棋局的一個時間步 $T$ 時，都會利用上一個神經網路的參數來產生搜索策略 $pi_t = alpha_{i-1}(s_t)$ ,並且用這個策略的採樣產生實際自我對弈時的行為。

發生下列任意情況之一，遊戲終止於時間 $T$ ：

雙方都Pass
搜索value降低至一個被resignation（割捨？）的閾值
遊戲對弈達到設定的最大步數

遊戲結束後，會給出一個最終獎勵 $r_T in left{ -1, +1 ight}$ , 每一個時間步 $T$ 的數據以 $(s_t, pi_t, z_t)$ 的形式保存，其中 $z_t = pm r_T$ 是從 $T$ 時刻玩家的立場得到的勝利者的獎勵（是不是可以理解成： $T$ 時刻不管是白方還是黑方，只要最終贏得棋局， $z_t = 1$ 即成立？）。

自我對弈過程中的最後幾次迭代過程中產生的數據 $(s,pi,z)$ 將會以均等的概率被選中來訓練神經網路。神經網路的損失函數由下式確定： $l = (z-v)^{2} - {pi}^ op logP + c || heta||^2$ 。

式中, $c$ 是控制參數 $L2$ 正則項的一個係數。

方法細節

訓練神經網路使用了圍棋的特點：旋轉和鏡像棋局時結果不變，這是一個訓練神經網路的數據擴增的辦法。同樣棋子的黑白色也是可以互換進行數據擴增的，實現這個效果的方式是從當前時刻玩家的立場來表示棋局（具體參考神經網路架構）
神經網路使用的是目前最強大的殘差網路，具體的參數設置也是相應的。
MCTS搜索參數通過高斯處理優化來選擇
自我對弈訓練路線分成三個組件：神經網路的參數 $heta_i$ 持續得到優化，玩家 $alpha_{ heta_i}$ 持續得到評估，當前最強玩家 $alpha_{ heta_star}$ 被用來生成新的自我對弈數據
學習率是逐漸衰減的annealed，動量參數0.9，交叉熵和均方差損失的權重相等，L2正則項係數為 $c=10^{-4}$
優化過程每1000個訓練步會產生一個checkpoint，將有一個評估子(evaluator)來評估；這個checkpoint也可能會被用來產生下一個batch的自我對弈數據。
Evaluator(接第6點）： checkpiont將用來和截止當前獲得的最好的神經網路 $f_{ heta_star}$ 進行比較。使用400個完整遊戲來進行評估，每一次移動要進行1600次MCTS模擬，使用 an infinitesimal temperature τ → 0。如果checkpoint對比之前的最好網路能贏得55%的勝率，checkpoint將稱為當前的最佳玩家 $alpha_{ heta_star}$ ,後續的自我對弈數據將使用這個新最佳玩家。
自我對弈：在每一次迭代過程中，當前最佳玩家 $alpha_{ heta_star}$ 將進行25000次完整的自我對弈，每一次移動使用1600次MCTS搜索模擬。每一次完整的自我對弈的前30步，參數temperature被設定為1（ $au = 1$ ），這是早期鼓勵探索的設置。遊戲剩下的步數，該參數將逐漸降低至0（ $au ightarrow0$ ）。在搜索樹的根節點 $s_0$ ,會通過加入Dirichlet noise來鼓勵額外的探索： $P(s,a) = (1-epsilon)p_a + epsiloneta_a$ ，式中 $eta sim Dir(0.03)$ ， $epsilon = 0.25$ 。這種雜訊設置基本可以保證所有的移動可能性都能被嘗試到。
自我對弈：為了節省計算資源，那些明顯的會輸的遊戲會被裁剪（割棄）掉，這個閾值 $v_{resign}$ 是通過保持一定(5%)的假陽性率(指的是如果Alpha Zero沒有割棄的話，該局遊戲本可能能贏)來自動設定的。為了測量這個假陽性率，會在10%的自我對弈棋局中禁用「裁剪」，這些棋局將被一直對弈到棋局終止。
監督學習：為了比較。單獨通過監督學習訓練一個與AlphaZero網路架構相同的神經網路 $heta_{SL}$ ，訓練數據 $(s,pi,z)$ 來源於KGS數據集，同時設定針對人類專家的移動a的概率為1：： $pi_a = 1$ 。訓練參數也與先前的網路架構相同，但是均方差那個損失部分被乘了一個0.01的係數。
搜索演算法：搜索數中的每一個節點 $s$ 會為每一個合法的行為 $ain A(s)$ 設置一條邊(Edge)，在這個邊中，會存儲下面幾個統計數據： $left{ N(s,a),W(s,a),Q(s,a),P(s,a) ight}$ 式中， $N(s,a)$ 是該邊被遍歷的次數， $W(s,a)$ 是總的行為價值， $Q(s,a)$ 是平均行為價值， $P(s,a)$ 是選擇該邊代表的行為的先驗概率。演算法通過不停的迭代三個階段(圖二中的a-c)來選擇實際要採取的行為(圖二中的d)

搜索階段演算法

1. 搜索演算法階段1（圖二a）——選擇 Select

每一次模擬的第一個階段起自搜索樹的根節點 $s_0$ ，在第 $L$ 個時間步結束於搜索樹的葉節點 $s_L$ 。對於其中的任意時間 $t<L$ ，根據搜索樹內的統計數據來決定選擇哪一個模擬行為 $a_t = underset{a}{argmax}(Q(s_t, a) + U(s_t, a))$ ，

其中： $U(s,a) = c_{puct}P(s,a)frac{sqrt{sum_{b}{N(s,b)}}}{1+N(s,a)}$ ， $c_{puct}是決定探索程度的一個係數$

2. 搜索演算法階段2（圖二b）——擴展和評估蒙特卡羅搜索樹 Expand & Evaluate

葉節點 $s_L$ 將會等待來自神經網路的評估 $(d_i (p), v) = f_ heta (d_i (s_L ))$ ,其中 $d_i$ 是一個dihedral reflection或rotation， $iin[1..8]$ 。這些等待評估的狀態會被送入一個隊列，在神經網路評估隊列里的狀態時（使用mini_batch_size=8），搜索將被暫時鎖定。當神經網路得到結果後，該葉節點會被展開，同時每一條可能的邊 $(s_L,a)$ 會以下面的數據進行初始化： $left{ N(s_L,a)=0,W(s_L,a)=0,Q(s_L,a)=0,P(s_L,a)=P_a ight}$ 同時來自神經網路的對該葉節點的價值估計也會影響路徑中每一個節點的統計數據 $W$ （見下）。隨後進行回溯過程。

3. 搜索演算法階段3（圖二c）——回溯 Backup

對於 $t leq L$ ,每一個邊的統計結果將被更新。首先： $N(s_t,a_t) = N(s_t,a_t)+1$ ;其次： $W(s_t,a_t) = W(s_t,a_t)+v$ , $Q(s_t,a_t) = frac{W(s_t,a_t)}{N(s_t,a_t)}$

4. 搜索演算法階段4（圖二d）——產生實際行為 Play

路徑中所有節點統計數據得到更新後，在根節點 $s_0$ 處，AlphaZero將要根據最新的統計數據來產生一個實際的行為 $pi(a|s_0) = N(s_0, a)^{1 / au}/sum_{b}{N(s_0,b)^{1/ au}}$ ，式中 $au$ 是一個控制搜索程度的參數。在隨後的時間步(time_steps)中，這個搜索樹將會繼續使用，對應於實際所採取的行為的子節點將變成根節點，該子節點下的子樹的統計數據將會被保留，而這顆樹的其餘部分將會丟棄(discarded)。 AlphaZero將放棄搜索某子樹，如果該子樹的根節點和最佳價值子節點的價值低於某一個閾值 $v_{resign}$

神經網路架構

由殘差模塊構成的CNN，輸入為19*19*17。輸入是17個特徵，使用了既往8個回合的16個特徵以及一個當前玩家信息特徵: $s_t = [X_t , Y_t , X_{t?1}, Y_{t?1}, ..., X_{t?7}, Y_{t?7} , C]$

其中 $X_t$ 內包含的是當前棋手的數據：加入當前棋手執黑棋，那麼此時棋盤上所有黑棋對應的位置取值1，白棋和空白位置取值0。類似的 $Y_t$ 反映的就是白棋信息，當前棋盤上所有白棋的位置取值1，黑棋和空白處取值0. C內的所有（19*19）個數據要麼都是1，要麼都是0，如果此時是黑棋要落子則取1，白棋落子則取0. 網路的其餘架構參考論文原文。

網路的共同部分多數是用3*3的卷積核（stride = 1)，256個特徵數，後接BatchNormalization和Relu單元。每一個殘差單元包括:[參考論文原文]

對於策略端：輸出特徵數為19*19+1，分別代表在棋盤上所有可能位置落子的可能性以及Pass的可能性。

對於價值端：全連接一個256個特徵的隱藏層，最後以tanh的激活方式輸出[-1,1]之間的值。