AlphaGo中的關鍵組件

論文的模型看似復雜，不過將其拆分為以下部件逐一理解會比較容易

1. 有監(jiān)督學習得到的策略網絡。這一策略網絡通過學習人類高手的棋盤颈渊，從而能夠在給定某個棋盤狀態(tài)時，以較高準確率預測人類高手的落子點
2. 強化學習得到的策略網絡。進行自我對弈蝴光，根據對弈的結果用policy gradient的方法更新策略網絡
3. 狀態(tài)值評估網絡。使用部件2進行自我對弈的數據集進行訓練达址，因此也是由強化學習訓練得到的蔑祟，該網絡在輸入一個棋盤狀態(tài)時，能給出該狀態(tài)下獲勝的概率沉唠。
4. 改進的蒙特卡洛搜索樹疆虚。用于做對弈的模擬演算，這個改進的版本將上述部件整合在一起满葛，提供了更具智能的模擬装蓬。

上述部件的實現

有監(jiān)督學習的策略網絡

這一網絡目的是學習預測人類高手的落子的概率分布，用于最終搜索算法的先驗信息纱扭。使用的網絡結構是卷積神經網絡牍帚，由卷積層與非線性激活函數構成，最后的輸出層是softmax層乳蛾，該層的作用是將輸出歸一化暗赶，使之能表示所有合法落子點的概率，即, 其中s為輸入網絡的棋盤狀態(tài)肃叶。

數據集是從KGS圍棋服務器得到的3千萬個棋局蹂随，每一個棋局包含一個棋盤狀態(tài)s和一個人類落子的位置a。那么棋盤信息如何進行卷積操作呢因惭，這里是將19x19的棋盤看成一個19x19的圖像一樣看待岳锁，這樣就可以用圖像的卷積方法了。

最終訓練得到的網絡能很好的預測人類在給定棋盤時的落子點的概率分布蹦魔，概率越大表示人類越有可能在該點落子激率。這就得到了有監(jiān)督的策略網絡咳燕，這個網絡的預測準確率能達到。 不過于此同時乒躺，他們還訓練了一個快速的但是準確率較低的策略網絡招盲，這個快速策略在之后的蒙特卡洛搜索樹中會用得到。

強化學習的策略網絡

該部件旨在提升有監(jiān)督的策略網絡嘉冒， 它為之后的狀態(tài)值評估網絡提供了對弈的數據曹货。在網絡結構上，與有監(jiān)督的網絡的網絡結構完全相同讳推，并且其網絡的初始權重就是網絡學習到的權重顶籽。

該網絡的學習是基于策略的學習，使用的是策略梯度算法银觅。我們知道強化學習最常應用在游戲中礼饱，那么同樣的，這里的“游戲”的過程是一個左右互博的過程设拟，即當前的策略網絡與某個對手策略進行相互博弈慨仿，這里的對手是隨機的從訓練過程中的前面一些迭代次數的策略網絡中選擇出來的，這里的隨機選擇能避免過擬合的情況纳胧。

定義在狀態(tài)下執(zhí)行的收益是：如果該局勝利則+1镰吆，如果該局失敗則-1。則在時間t的期望收益為跑慕。因此在每一個時間點t万皿，網絡的參數需要更新的梯度為

在對Pachi的對弈中，僅使用強化學習得到的策略能獲得85%的勝率核行，而僅使用有監(jiān)督的策略網絡只能得到15%的勝率

強化學習的狀態(tài)值評估網絡

該網絡 在最終的搜索算法中會用于對節(jié)點的評估牢硅。它評估給定棋盤狀態(tài)s和策略p時雙方的收益值，即

該網絡的網絡架構與之前兩個相似芝雪，但是不同的是網絡最后只輸出一個預測值而非概率分布减余。給定一組“狀態(tài)s-結果z”的樣本，該網絡的損失函數為

數據集是用前面介紹的強化學習的策略網絡進行自我對弈得到的3千萬個棋盤狀態(tài)和對應的結果惩系。另外為了避免因為棋盤之間有關聯性而帶來的模型過擬合問題位岔，這些數據集的每一個樣本都是從不同的一局對弈中獲取的，也就是說3千萬個棋盤狀態(tài)對應的是3千萬盤的獨立的對弈堡牡。

蒙特卡洛樹搜索

這是將前面的部件整合在一起的算法抒抬。由于下一節(jié)會詳細展開，因此這里不贅述晤柄。

整合上述部件的蒙特卡洛樹搜索

在學習本文的改進版蒙特卡洛樹搜索之前擦剑，先了解以下原始的蒙特卡洛樹搜索

原始的蒙特卡洛樹搜索[1]

• 目的

  該算法的目的是給定一個”游戲狀態(tài)“并選擇“勝率最高的下一步”

• 主要思想

  眾所周知，蒙特卡洛就意味著模擬，在這里也是一樣惠勒，蒙特卡洛樹搜索會多次模擬博弈赚抡，并嘗試根據模擬結果預測最優(yōu)的移動方案。

  蒙特卡洛樹搜索的主要概念是搜索捉撮，即沿著博弈樹向下的一組遍歷過程怕品。

  1. 單次遍歷會從當前節(jié)點根據節(jié)點的信息選擇子節(jié)點向下遍歷妇垢，直到一個沒有完全展開的節(jié)點巾遭，未完全展開表示其子節(jié)點至少有一個未訪問到。
  2. 遇到未完全展開的節(jié)點時闯估，它的一個未訪問子節(jié)點將會作為單次模擬的根節(jié)點灼舍，從該節(jié)點開始模擬運行至產生游戲結果。
  3. 模擬的結果將會反向傳播回當前樹的根節(jié)點并更新博弈樹的節(jié)點統(tǒng)計數據涨薪。一旦搜索受限于時間或計算力而終止骑素，下一步行動將基于收集到的統(tǒng)計數據進行決策。

• 算法

  1. 遍歷

     向下遍歷的過程并不是隨機的刚夺。對于已經未完全展開的節(jié)點献丑，選擇未訪問的子節(jié)點，若當前節(jié)點已經完全展開那么對子節(jié)點有一個評估函數侠姑，每次向下遍歷均選擇評估值最大的子節(jié)點進行遍歷创橄。評估函數如下
     
     其中是當前節(jié)點，是子節(jié)點莽红，是節(jié)點的模擬獲勝次數妥畏，是節(jié)點的總模擬次數，是節(jié)點v的總模擬次數安吁。c是一個可調節(jié)的參數醉蚁。

     這個函數中的前一個加數表示的是該節(jié)點的模擬勝率，后一個加數表示的是訪問次數的多寡鬼店。這兩項結合在一起的意義則是遍歷過程中會盡量選擇勝率高的節(jié)點進行展開(這點與極大極小策略一致)网棍，但是同時會鼓勵探索很少訪問的節(jié)點。

     綜上所述妇智，遍歷環(huán)節(jié)的偽代碼為：

     while(完全展開(node)):
        node = best_uct(node)
     return 未訪問的子節(jié)點(node)
     

  2. 模擬與反向傳播

     前一個步驟遍歷到了一個未訪問（未評估）的節(jié)點滥玷，那么接下來就從該節(jié)點開始進行模擬，在原始算法中采用完全隨機（即均勻分布）的方法向下模擬俘陷，直到游戲結束返回一個結果（例子：象棋中從某一棋盤狀態(tài)開始隨機走棋罗捎，直到自己被將死或者對方被將死）。

     接著將該結果記錄在節(jié)點中拉盾，并且從節(jié)點向上傳播桨菜，更新第一步的遍歷路徑上的所有節(jié)點的信息。舉個例子，如果模擬的結果是獲勝倒得，那么路徑上所有節(jié)點的獲勝次數都會加一泻红。

  3. 算法結束與預測

     對于博弈樹很大的游戲來說，上述算法可以執(zhí)行特別久霞掺，那么什么時候終止 MCTS谊路？答案是：只要資源允許，就可以一直運行 MCTS菩彬，因為與其他蒙特卡洛方法一樣缠劝，模擬的次數越多，得到的結果通常會越準確骗灶。

     而MCTS 算法結束運行之后惨恭，算法預測的最好的一步是有最高訪問量的一步，因為它的獎勵值評估結果最好

本文的蒙特卡洛樹搜索

1. 節(jié)點信息

   與原始的算法不同耙旦，本文的搜索樹中的節(jié)點不僅包含有動作值脱羡，訪問計數，還有另外的一個信息免都，即先驗動作概率分布锉罐。 當一個節(jié)點第一次被訪問到時，該節(jié)點對應的棋盤狀態(tài)送入有監(jiān)督學習到的策略網絡中绕娘，得到該節(jié)點狀態(tài)對應的動作概率分布脓规，將其賦值給該節(jié)點的先驗動作概率分布

2. 遍歷

   與原算法相同的是，對于已經完全展開的節(jié)點业舍，需要有評估函數對其子節(jié)點進行評估抖拦，從而選擇子節(jié)點進行向下遍歷，不同的是這里的評估函數不同舷暮，變?yōu)槿缦碌墓?br>
   也即由以下公式求下一步動作
   

3. 模擬與反向傳播

   與原算法中只通過隨機策略進行模擬的方法不同态罪，本文方法對一個葉節(jié)點的評估有兩個方面：

   • 通過狀態(tài)值估計網絡直接進行評估
   • 通過有監(jiān)督的學習得到的快速走子策略進行模擬，注意這里的模擬除了策略與原算法不一樣以外下面，其余是完全一樣的

   最后的評估函數由上述兩項加權求和得到：
   
   其中是一個可調節(jié)的參數复颈，是狀態(tài)值估計網絡的評估，是通過策略進行模擬的結果沥割。

   反向傳播時耗啦，對遍歷的路徑上的節(jié)點計數加一，并且對路徑上的節(jié)點更新
   
   注意我這里的公式與論文中的公式有所不同机杜，是因為論文中是計算了所有模擬的評估值之和帜讲，而我這邊只寫了一次模擬，因此我這里的加法與論文中的求和本質上是一致的椒拗。

4. 算法結束與預測

   與原算法相同似将，當算法結束時获黔，算法預測的最好的一步是有最高訪問量 的一步

總結與思考

1. 有監(jiān)督學習得到的策略在最終的搜索中作為節(jié)點的先驗信息，在節(jié)點的遍歷中起了指導的作用在验。
2. 有監(jiān)督學習得到的快速走子策略在搜索中被用作模擬的策略玷氏，使得對葉節(jié)點的評估更具準確。
3. 強化學習得到的策略在搜索中沒有直接的作用腋舌，而是間接通過狀態(tài)值評估網絡的方式在葉節(jié)點的評估中發(fā)揮作用
4. 狀態(tài)值評估網絡在搜索中對葉節(jié)點進行評估盏触，部分代替了原始蒙特卡洛樹搜索中的模擬評估，不僅加快了評估的速度块饺，還能以更大局觀的眼光評估葉節(jié)點狀態(tài)
5. 關于哪個部件使得算法能超越了人類的問題赞辩，我認為，有監(jiān)督的學習得到的策略網絡由于是用人類的棋譜學習的刨沦，因此無論學的多好诗宣，其結果也只能是接近人類而非超過人類膘怕。因此我認為使之超過人類的主要是強化學習和蒙特卡洛樹搜索的功勞想诅。

[1]. https://www.jiqizhixin.com/articles/monte-carlo-tree-search-beginners-guide