1. 棋盤編碼器

AlphaGo所采用的棋盤編碼器為 19×19×49 的特征張量,，其中前48個平面用于策略網(wǎng)絡的訓練,，最后一個平面用于價值網(wǎng)絡的訓練。前48個平面包含11種概念，其更多地利用了圍棋專有的定式，例如它在特征集合中引入了征子和引征的概念,。最后一個平面用來表示當前執(zhí)子方。

AlphaGo的棋盤編碼器也采用了二元特征,，它用8個平面分別代表每個棋子是否有1口,、2口…和至少8口氣。AlphaGo 所使用的特征平面的分類和解釋如下：

2. AlphaGo的網(wǎng)絡架構(gòu)

AlphaGo一共使用了三個神經(jīng)網(wǎng)絡,，包括2兩個策略網(wǎng)絡和1個價值網(wǎng)絡,。其中策略網(wǎng)絡分為快策略網(wǎng)絡和強策略網(wǎng)絡?？觳呗跃W(wǎng)絡的主要作用是為了在保證一定高的預測準確率的情況下同時能夠非常迅速地做出動作預測,。與之相反，強策略網(wǎng)絡的優(yōu)化目標是準確率而不是預測速度,，其網(wǎng)絡更深且預測效果比快策略網(wǎng)絡好2倍,。最后價值網(wǎng)絡用來評判當前棋盤狀態(tài)的好壞，其使用強策略網(wǎng)絡的自我對弈產(chǎn)生的數(shù)據(jù)集訓練出來的,。接下來我們分別看一下這三種網(wǎng)絡,。

(1)強策略網(wǎng)絡

強策略網(wǎng)絡一共有13層卷機網(wǎng)絡，且在整個網(wǎng)絡的訓練過程中,，都保留的原始的19×19的大小,，因此我們需要對中間卷機層進行paddinga操作。此外第一個層卷積核的大小為5,，剩下12層的卷積核的大小為3,，最后一層的卷積核大小為1，且只有一個過濾器,。關(guān)于激活函數(shù),，前12層都采用Relu激活函數(shù)，最后一層由于要得出每個位置的概率值,，因此采用softmax 激活函數(shù),。強策略網(wǎng)絡使用keras實現(xiàn)如下：

model = Sequential()
    model.add(
        Conv2D(192, 5, input_shape=input_shape, padding="same", data_format='channels_first', activation='relu')
    )
 
    for i in range(2, 12):
        model.add(
            Conv2D(192, 3, padding='same', data_format='channels_first', activation='relu')
        )

    model.add(
        Conv2D(filters=1, kernel_size=1, padding='same', data_format='channels_first', activation='softmax')
        )
    model.add(Flatten())

(2)快策略網(wǎng)絡

由于快策略網(wǎng)絡的主要目的是構(gòu)建一個比強策略網(wǎng)絡更小的網(wǎng)絡，從而能夠進行快速評估,，因此讀者可以自行創(chuàng)建一個簡易的網(wǎng)絡從而實現(xiàn)此功能,，這里就不做示例。

(3)價值網(wǎng)絡

價值網(wǎng)絡總共有16層卷機網(wǎng)絡,，其中前12層與強策略網(wǎng)絡完全一致,，第13層是一個額外的卷機層，與第2～12層的結(jié)構(gòu)一致,，而第14層的卷積核大小為1,，并且有一個過濾器,。最后是兩層稠密層,，倒是第二層共有256個輸出,，采用ReLU幾何函數(shù)；最后一層只有一個輸出,，表示當前狀態(tài)的價值,，采用tanh激活函數(shù)。需要注意的是價值網(wǎng)路的輸入維度和策略網(wǎng)絡的輸入維度不同,，前面我們知道價值網(wǎng)絡的輸入比策略網(wǎng)絡的輸入多一層特征值用來記錄當前執(zhí)子方,。價值網(wǎng)絡使用keras實現(xiàn)如下：

model = Sequential()
    model.add(
        Conv2D(192, 5, input_shape=input_shape, padding="same", data_format='channels_first', activation='relu')
    )

    for i in range(2, 13):
        model.add(
            Conv2D(192, 3, padding='same', data_format='channels_first', activation='relu')
        )
        
    model.add(
        Conv2D(filters=1, kernel_size=1, padding='same', data_format='channels_first', activation='relu')
        )
    model.add(Flatten())
    model.add(Dense(256, activation='relu'))
    model.add(Dense(1, activation='tanh'))

3. 策略網(wǎng)絡的訓練

(1) 監(jiān)督學習初始化策略網(wǎng)絡(behavior cloning)

AlphaGo最開始使用監(jiān)督學習方法對策略網(wǎng)絡進行預訓練，每個游戲狀態(tài)編碼為一個張量,，而訓練所使用的標簽是一個與棋盤尺寸相同的向量,，并在實際動作落子處填入1，其余位置為0,，訓練流程圖如下：

我們用同樣的方法訓練強策略網(wǎng)絡和快策略網(wǎng)絡,，通過監(jiān)督學習訓練的網(wǎng)絡已經(jīng)可以很大概率地打敗業(yè)余玩家了，但是如果想要贏得職業(yè)玩家還需要繼續(xù)進行提升,。

(2) 自我對弈(self-play)

DeepMind使用多個不同版本的強策略網(wǎng)絡與當前最強版本的強策略網(wǎng)絡進行對弈,，這么做能夠防止過擬合并且在總體上能夠得到更好的表現(xiàn)。在這里我們采用更簡單的方法,，直接讓上面訓練好的強策略網(wǎng)絡進行自我對弈,，機器人對弈的代碼如下：

def simulate_game(black_player, white_player, board_size):
    game = GameState.new_game(board_size)
    moves = []
    agents = {
        Player.black: black_player,
        Player.white: white_player,
    }

    while not game.is_over():
        next_move = agents[game.next_player].select_move(game)
        moves.append(next_move)
        game = game.after_move(next_move)

    game_result = scoring.compute_game_result(game)

    return game_result

def experience_simulator(num_games, agent1, agent2):
    collector1 = experience.ExperienceCollector()
    collector2 = experience.ExperienceCollector()

    color = Player.black
    for i in range(num_games):
        collector1.begin_episode()
        collector2.begin_episode()
        agent1.set_collector(collector1)
        agent2.set_collector(collector2)

        if color == Player.black:
            black_player, white_player = agent1, agent2
        else:
            black_player, white_player = agent2, agent1
        game_record = simulate_game(black_player, white_player)
        if game_record.winner == color:
            collector1.complete_episode(reward=1)
            collector2.complete_episode(reward=-1)
        else:
            collector1.complete_episode(reward=-1)
            collector2.complete_episode(reward=1)
        color = color.other

    return experience.combine_experience([collector1, collector2])

代碼中的'ExperienceCollector’類用于儲存和處理對弈過程中生成的棋譜狀態(tài)，相應的動作以及動作獎勵的數(shù)據(jù)序列 ( s 1 , a 1 , r 1 , s 2 , . . . , s t , a t ) (s_{1}, a_{1}, r_{1}, s_{2},..., s_{t}, a_{t}) (s1?,a1?,r1?,s2?,...,st?,at?),。其中每個動作的獎勵取決于勝負,。具體而言，如果此輪博弈player獲得勝利,，那么player所有的動作獎勵值都為1,，否則為-1。每一輪次比賽結(jié)束后,，（狀態(tài),，動作，獎勵）序列值都會存儲到player和opponent的經(jīng)驗收集器中,，雙方的經(jīng)驗值可以結(jié)合一起用于之后訓練的數(shù)據(jù)集,。在實現(xiàn)指定輪次的對弈之后，我們用其生成的經(jīng)驗值訓練強策略網(wǎng)絡,。

(3) 策略剃度算法訓練策略網(wǎng)絡(Policy Gradient)

在討論策略梯度算法之前,，我們先了解一下策略學習(Policy- Based Reinforcement Learning), 策略學習通過使用神經(jīng)網(wǎng)絡估計策略函數(shù)(policy function), 從而進一步的估計狀態(tài)價值函數(shù)(state-value function):
V ( s ; θ ) = ∑ a π ( a ∣ s ; θ ) . Q π ( s , a ) V\left( s;\theta \right) =\sum^{}_{a} \pi \left( a\mid s;\theta \right) .Q_{\pi }\left( s,a\right) V(s;θ)=a∑?π(a∣s;θ).Qπ?(s,a)
policy- based的核心思想就是通過更新 θ \theta θ值從而最大化狀態(tài)價值函數(shù)的期望，而更新 θ \theta θ的方法就是策略梯度上升方法,，雖然稱為策略梯度但是本質(zhì)上可以理解為隨機梯度,，其隨機性來自于狀態(tài) s s s,。策略梯度算法的推導公式如下：
g ( a , θ ) = ? log ? π ( a ∣ s ; θ ) ? θ ? Q π ( s , a ) g\left( a,\theta \right) =\frac{\partial \log \pi \left( a|s;\theta \right) }{\partial \theta } \cdot Q_{\pi }\left( s,a\right) g(a,θ)=?θ?logπ(a∣s;θ)??Qπ?(s,a)
g ( a , θ ) g\left( a,\theta \right) g(a,θ)是 ? V ( s ; θ ) ? θ \frac{\partial V\left( s;\theta \right) }{\partial \theta } ?θ?V(s;θ)?的無偏估計，其中 Q π ( s , a ) Q_{\pi }\left( s,a\right) Qπ?(s,a)時動作價值函數(shù),，其大小是對在狀態(tài) s s s下動作 a a a的打分,。在推導出策略梯度之后，我們使用梯度上升更新 θ \theta θ值：
θ t + 1 = θ t + β ? g ( a t , θ t ) \theta_{t+1} =\theta_{t} +\beta \cdot g\left( a_{t},\theta_{t} \right) θt+1?=θt?+β?g(at?,θt?)
在AlphaGo中運用策略梯度訓練強策略網(wǎng)絡的時候,，每一個動作的獎勵值(-1 or 1),，就是公式中的 Q π ( s , a ) Q_{\pi }\left( s,a\right) Qπ?(s,a)的對于每一個特定狀態(tài)下相應動作的無偏估計。根據(jù)公式,，在用keras實現(xiàn)的時候,，損失函數(shù)我們使用'categorical_crossentropy’更新參數(shù)。示例代碼如下：

    def train(self, experience):
        self._model.compile(loss='categorical_crossentropy',
                            optimizers=keras.optimizers.SGD(lr=self.lr, clipnorm=self.clip))
        n = experience.states.shape[0]
        num_moves = self._encoder.board_width * self._encoder.board_height
        y = np.zeros((n, num_moves))
        for i in range(n):
            action = experience.actions[i]
            reward = experience.rewards[i]
            y[i][action] = reward

        self._model.fit(experience.states, y, batch_size=self.batch_size, epochs=self.epochs)

2016年,，AlphaGo對戰(zhàn)當時最強的開源圍棋機器人Pachi（相當于業(yè)余2段）的獲勝概率達到了85%,，令人驚嘆；雖然之前有人僅用卷積網(wǎng)絡進行過動作預測,，但對戰(zhàn)Pachi的獲勝率沒有超過10%,，可見，自我博弈對于圍棋機器人的能力提升要遠勝于單純使用監(jiān)督學習,。

4. 價值網(wǎng)絡的訓練

除了訓練策略網(wǎng)絡選擇下棋的位置,，Alphago還運用了價值網(wǎng)絡模擬狀態(tài)價值函數(shù)來評估當前狀態(tài)的好壞，以此來輔助蒙特卡洛樹搜索（MCTS）,。狀態(tài)價值函數(shù)的定義如下：
V π ( s ) = E ( U t ∣ S t = s ) V_{\pi }\left( s\right) =E\left( U_{t}|S_{t}=s\right) Vπ?(s)=E(Ut?∣St?=s)
其中當 U t U_{t} Ut?的值接近1時表示的那前狀態(tài)接近于贏的狀態(tài),；當其值接近于-1時表示當前棋局狀態(tài)接近于輸。因此神經(jīng)網(wǎng)絡的輸入應該是編碼后的當前棋局,，而輸出結(jié)果是一個位于 [ ? 1 , 1 ] [-1,1] [?1,1]之間的數(shù)值,。我們使用訓練的數(shù)據(jù)是之前策略網(wǎng)絡自我博弈存儲的棋盤數(shù)據(jù)，訓練代碼如下：

    def train(self, experience):
        self.model.compile(loss='mse', optimizer=keras.optimizers.SGD(lr=self.lr))
        n = experience.state_values.shape[0]
        y = np.zeros((n,))
        for i in range(n):
            reward = experience.rewards[i]
            y[i] = 1 if reward > 0 else -1

        self.model.fit(experience.state_values, y, batch_size=self.batch_size, epochs=self.epochs)

5. 蒙特卡洛樹搜索（MCTS）

再介紹AlphaGo如何將策略網(wǎng)絡和價值網(wǎng)絡用語優(yōu)化蒙特卡洛樹搜索算法之前,，我們先來了解蒙特卡洛樹搜索的搜索思想,。蒙特卡洛樹搜索的是蒙特卡洛算法族的一員，蒙特卡洛算法的中心思想就是利用隨機性來分析并解決一些復雜的問題,。

我們以下圍棋為例,，把模擬進行的每一個隨機棋局稱為一次推演(rollout)。前面說過蒙特卡洛算法的核心思想就是其隨機性,，通過選擇隨機動作來建立一個良好的策略咋看似乎是不可行的,，但是如果讓兩個勢均力敵的AI進行博弈，當游戲進行了幾百輪,，幾千輪甚至幾萬輪,，如果發(fā)現(xiàn)一方持續(xù)比另一方贏的多，那么我們可以認為對于這種游戲，前者相較于后者掌握了一些優(yōu)勢,，至于為什么會有這樣的結(jié)果并不需要我們深入探究,。我們可以將類似的思想應用于圍棋。一般地,，蒙特卡洛樹搜索包括三個步驟：

[ 1 ] [1] [1] 搜索新的棋局,，并將新的棋局添加到MCTS樹中；
[ 2 ] [2] [2] 從新添加的棋局開始模擬隨機對弈,；
[ 3 ] [3] [3] 根據(jù)隨機對弈的結(jié)果更新樹節(jié)點的統(tǒng)計數(shù)據(jù),。

接下來我們分別探究這三個步驟,。

(1) 搜索新的棋局

每一輪開始我們都要在搜索樹中添加一個新的節(jié)點，即AI都要執(zhí)行一個新的動作,。然而由于每一個回合中AI能夠運用的時間是有限的,，如果在動作A上多消耗一次推演，那么在動作B上就要少消耗一次推演時間,。因此,，為了獲得最佳效果，我們需要采取適當?shù)牟呗詠磉x取要添加新節(jié)點的葉節(jié)點位置,，這里我們采用搜索樹置信區(qū)間上界公式(Upper Confidence bound for Trees formula),，簡稱UCT公式，來決定選擇繼續(xù)探索哪個分支,。接下來我們先來了解一下UCT公式,。

UCT公式

和常見的搜索算法一樣，MCTS也存在深度搜索和廣度搜索之間的平衡問題,。在這里,，我們分別稱之為深入挖掘(exploitation)和廣泛搜索(exploration)。

深入挖掘：即想要對迄今為止搜索到的比較理想的動作進行更加深入的挖掘,，隨著你對這些分支進行更加多的推演,，你的估算也會更加準確，誤報率也會下降,；在MCTS中,，我們使用獲勝百分率 w w w作為深入挖掘的目標，其定義為當前棋局下一個執(zhí)子方所贏得的總次數(shù)與當前節(jié)點所儲存的總推演數(shù)之間的比值,。

廣泛搜索：另一方面,，如果一些節(jié)點只被訪問了幾次，那么他所得到的評估就可能有很大的誤差,。因此我們可以把更多的時間花在提高那些訪問次數(shù)少的節(jié)點的推演次數(shù),。根據(jù)以上定義，廣泛搜索的目標函數(shù)如下：
log ? N n \sqrt{\frac{\log N}{n} } nlogN? ?
其中 n n n代表從當前節(jié)點開始的所有推演數(shù),， N N N表示所有分支的推演總數(shù),，也就是根節(jié)點中存儲的推演總數(shù),。

將以上兩種目標結(jié)合起來，就構(gòu)成了UCT公式：
w + c log ? N n w+c\sqrt{\frac{\log N}{n} } w+cnlogN? ?
這里參數(shù) c c c被稱為溫度參數(shù),，當溫度高時,，搜索將更發(fā)散，當溫度較低時,，搜索將更集中,，一般取值為0.5。

定義好UCT公式之后我們就可以計算每個葉節(jié)點的UCT值,，從而選擇數(shù)值較高的葉節(jié)點進行擴展,。

(2) 模擬對弈并更新各節(jié)點數(shù)據(jù)

從新添加的節(jié)點開始，每一回合隨機選擇一個合法的動作,，直到棋局終盤,。然后進行終盤結(jié)算，并得到獲勝方,，之后將這次推演的結(jié)果記錄在新節(jié)點中,，并回溯之前的祖先節(jié)點更新他們的數(shù)據(jù)。

上述過程是MCTS的一次推演,，再經(jīng)過固定輪次的推演之后我們就可以停止推演,，這個時候我們回到原先的葉節(jié)點，選擇獲勝率 w w w最高的那個動作即可,。

6. AlphaGo改進版的蒙特卡洛樹搜索

前面我們已經(jīng)介紹了蒙特卡洛樹搜索的算法思想,，AlphaGo將神經(jīng)網(wǎng)絡和蒙特卡洛樹搜索相結(jié)合，是的樹搜索算法更加強大,。接下來我們將分點介紹改進版的蒙特卡洛樹搜索和傳統(tǒng)MCTS算法的區(qū)別,。

(1) 選擇下一步動作(selection)

假設(shè)當前處于葉節(jié)點狀態(tài)為 s s s, 那么對于所有的合法動作，我們按照以下公式計算各個動作的得分,，選取最高得分的動作為下一步動作：
a ′ = a r g m a x a [ Q ( a ) + π ( a ∣ s ; θ ) 1 + N ( a ) ] a^{\prime} =argmax_{a}\left[ Q\left( a\right) + \frac{\pi \left( a\mid s;\theta \right) }{1+N\left( a\right) } \right] a′=argmaxa?[Q(a)+1+N(a)π(a∣s;θ)?]
其中 π ( a ∣ s ; θ ) \pi \left( a\mid s;\theta \right) π(a∣s;θ)是強策略網(wǎng)絡給動作 a a a的打分,，這里我們將這些概率分布稱為該動作的先驗概率（prior probability)。 N ( a ) N(a) N(a)是出于當前狀態(tài)下,，動作 a a a被選擇的次數(shù),。整個這一項我們可以這么理解：選擇動作 a a a在當前狀態(tài)下對后續(xù)越有利， π ( a ∣ s ; θ ) \pi \left( a\mid s;\theta \right) π(a∣s;θ)的值越大,；但是當這個動作被探索很多次之后,，也就是 N ( a ) N(a) N(a)越來越大，會導致整個這一項的值變小,，從而減少繼續(xù)探索這個動作的次數(shù),。另一項 Q ( a ) Q(a) Q(a)被稱作動作-價值函數(shù)，其初始值為0，稍后我們給出其定義,。強策略網(wǎng)絡預測對各個動作的打分 π ( a ∣ s ; θ ) \pi \left( a\mid s;\theta \right) π(a∣s;θ)的代碼實現(xiàn)如下：

    def policy_probabilities(self, game_state):
        encoder = self.policy_agent.encoder
        outputs = self.policy_agent.predict(game_state)
        legal_moves = game_state.legal_moves()
        if not legal_moves:
            return [], []
        encoded_points = [encoder.encode_point(move.point) for move in legal_moves if move.point]
        legal_outputs = outputs[encoded_points]
        # normalize the output probabilities
        normalized_outputs = legal_outputs / np.sum(legal_outputs)

        return legal_moves, normalized_outputs

(2) 擴展搜索樹(Expansion)

當我方選擇完下一步動作之后,，對手也會進行下一步動作。這里我們采用快策略網(wǎng)絡模擬對手的動作,，并在所有的合法動作之中隨機選擇一個動作應用到棋盤上,，生成新的狀態(tài) s t + 1 s_{t+1} st+1?，也就是下一個節(jié)點,。之后結(jié)合快策略網(wǎng)絡迅速的推演出讓快策略網(wǎng)絡自我博弈,，直到到達最終棋局。這也是為什么需要快策略網(wǎng)絡,，因為只有推演速度夠快,，才能在短時間內(nèi)完成大量的推演。

我們使用policy_rollout函數(shù)用來實現(xiàn)這一快速推演策略,，這個函數(shù)在每次推演的時候都從快策略網(wǎng)絡中選擇最強的動作,，直至達到最大推演次數(shù)，然后查看勝負結(jié)果,。如果執(zhí)子方獲勝，則返回1,；如果對手獲勝,，則返回-1；否則,，返回0,。

 def policy_rollout(self, game_state):
        for step in range(self.rollout_limit):
            if game_state.is_over():
                break
            move_probabilities = self.rollout_policy_agent.predict(game_state)
            encoder = self.rollout_policy_agent.encoder
            # filter all the moves and retain all th legal moves  
            valid_moves = [m for index, m in enumerate(move_probabilities)
                           if Move(encoder.decode_point_index(index)) in game_state.legal_moves()]

            max_index, max_value = max(enumerate(valid_moves), key=operator.itemgetter(1))
            max_point = encoder.decode_point_index(max_index)
            move = Move(max_point)
            game_state = game_state.after_move(move)

        next_player = game_state.next_player
        winner = game_state.winner
        if winner is not None:
            return 1 if winner == next_player else -1
        else:
            return 0

(3) 評估葉節(jié)點(Evaluation)

AlphaGo評估下一個動作產(chǎn)生的待擴展節(jié)點的依據(jù)為以下公式：
V ( s t + 1 ) = λ ? v ( s t + 1 ) + ( 1 ? λ ) ? r V(s_{t+1}) = \lambda \cdot v(s_{t+1}) +(1-\lambda) \cdot r V(st+1?)=λ?v(st+1?)+(1?λ)?r
其中r為快搜索策略下得到的棋局終盤時候的結(jié)果，其值為1或者-1,； v ( s t + 1 ) v(s_{t+1}) v(st+1?)為之前我們訓練的價值網(wǎng)絡的輸出,，它也可以表示在狀態(tài) s t + 1 s_{t+1} st+1?的情況下，我們的勝算有多大,； λ \lambda λ默認值為0.1,。

因為樹搜索挑選動作時要模擬很多局棋局，因次對于每一個棋局,，狀態(tài) s t + 1 s_{t+1} st+1?都會有很多個對應的 v ( s t + 1 ) v(s_{t+1}) v(st+1?)值,，對所有這些值進行累加并除以該節(jié)點的訪問次數(shù)，就得到了我們先前提到的 Q ( a t ) Q(a_{t}) Q(at?)值,。注意,，這里狀態(tài) s t + 1 s_{t+1} st+1?由于對手下棋動作的隨機性，所以不一定是同一個狀態(tài),，因此在計算 Q ( a t ) Q(a_{t}) Q(at?)的時候,，各個分支的節(jié)點的 V V V值是分開進行進行歸一化的。

(4) 真正地擴展樹節(jié)點(Final Decision)

在進行以上步驟之后，我們只需要選擇訪問計數(shù)多的節(jié)點作為真正的擴展節(jié)點即可,。這樣的做法是合理的,，因為節(jié)點計數(shù)的訪問會隨著Q值的提高而增多，在進行了足夠多的模擬之后,，訪問計數(shù)就能夠成為衡量該動作相對價值的一個良好指標了,。選擇下一步動作的代碼如下：

    def select_move(self, game_state):
        for simulation in range(self.num_simulations):
            current_state = game_state
            node = self.root
            for depth in range(self.depth):
                if not node.children:
                    if current_state.is_over():
                        break
                    moves, probs = self.policy_probabilities(current_state)
                    node.add_children(moves, probs)

                move, node = node.select_child()
                current_state = current_state.after_move(move)

            value = self.value_agent.predict(current_state)
            rollout = self.policy_rollout(current_state)
            weighted_value = (1 - self.lambda_value) * value + self.lambda_value * rollout

            node.update_values(weighted_value)

        move = max(self.root.children, key=lambda move:self.root.children.get(move).visit_conut)
        self.root = AlphaGoNode
        if move in self.root.children:
            self.root = self.root.children[move]
            self.root.parent = None
        return move

本文參考書籍：《深度學習與圍棋》