標籤：

深入淺析AlphaGo Zero與深度強化學習

02-10

Jing Conan Wang 王晶

jingconanwang AT gmail.com

註：如果文中一些公式不能正常顯示，可以訪問谷歌文檔或者石墨文檔。

AlphaGo的巨大成功掀起了圍棋界三千年未有之大變局，也使得深度強化學習漸為大眾熟悉。尤其是本周推出了AlphaGo Zero完全摒棄了人類知識，並且三天內碾壓了早期版本的AlphaGo，更足顯強化學習和深度學習結合的巨大威力。我博士的研究方向之一就是強化學習，畢業之後有幸加入Google從事機器學習方面工作，非常自豪能以非常近的角度見證這樣一個過程。相信這僅僅只是開始，越來越多的領域也會掀起新的革命。AlphaGo Zero的論文側重於描述效果，對於方法的論述比較簡短，沒有相關背景的人讀起來會有一些困難（點擊閱讀論文）。所以我結合自己的理解寫了一個關於強化學習和AlphaGoZero演算法的詳細描述。轉載請務必注名來源和出處。

概要

  • AlphaGo Zero無需任何人類歷史棋譜，僅使用深度強化學習，從零開始訓練三天的成就已遠遠超過了人類數千年積累的圍棋知識。
  • 強化學習能夠考慮到了演算法對於環境的影響, 特別適合解決多回合博弈或者順序決策問題
  • 在強化學習中，數據在運行過程中自主收集，這是AlphaGo Zero能擯棄人類棋譜的原因。
  • 強化學習的速度限制通常來源於環境給予反饋的時延。弈棋類問題可以通過左右互搏得到即時反饋，所以弈棋類問題對於強化學習來說還算比較容易的問題。
  • 在強化學習中知識存儲在值函數中，深度強化學習就是利用深度神經網路來逼近值函數的一類強化學習方法。AlphaGo Zero使用了華人提出的ResNet進行深度學習，提升達到600Elo。
  • AlphaGo Zero使用的強化學習方法稱為Policy Iteration （策略迭代法）。Alphago Zero交替使用深度學習評估策略(policy evaluation)和蒙特卡洛樹搜索優化策略(policy improvement)。

介紹

強化學習（Reinforcement Learning）是機器學習裡面一個分支。如果說強化學習在AlphaGo之前版本裡面還是初試牛刀的話，那在AlphaGo zero裡面強就真正大顯神威。根據deepmind的論文，新版本AlphaGo Zero經過三天的訓練輕易達到對老版本的100:0的勝率，並且完全無需人類棋譜。可以說，AlphaGo Zero僅僅三天的成就就遠遠超過了人類數千年的圍棋探索。

為什麼強化學習能夠這麼強？這要和它的特點有關係。強化學習和傳統機器學習的區別有如下幾點

  • 傳統機器學習假設演算法本身對於環境無影響，強化學習破除了這個限制，能夠考慮到了演算法對於環境的影響, 這使得強化學習特別適合解決多回合博弈或者順序決策問題（sequential decision making）問題。事實上，這類問題在生活中是非常普遍的，比如股市的交易。傳統機器學習可以預測股票價格，但是只有不使用結果進行買賣模型才會長期有效。如果你預測完了之後你根據據測去做多或著做空這個股票，那麼其他的股票買家可能因為你的行為改變了自身行為，你原來的訓練的模型便會失效，而強化學習可以考慮到這點。
  • 在強化學習中，數據是在運行過程中自主收集。這解決了機器學習中常見的訓練數據難於獲取的問題。AlphaGo Zero之所以能夠完全摒棄人類知識就是因為所有的數據都是通過機器互博生成。從這個意義上來說，強化學習的演算法具有自主學習能力。這就是強化學習在機器人領域裡面使用比較廣泛的原因。但是要注意到的是，通常強化學習的速度限制並不是來自於演算法的訓練，而是來自於環境給予反饋的延時。比如說股票交易里，股票的漲跌必須過一段時間才能發生，股市關閉的時候也不可能有反饋。所以就不可能像AlphaGo Zero這麼快。

具有強化學習能力的程序或機器人被稱為代理（Agent）。代理所解決的問題被抽象為環境（environment）。注意，這裡的並不是說我們通常意義的環境，而實際上是一個具有特定行為的另一個代理。環境可以處於多種狀態，狀態之間的轉換可以用馬科夫過程表述（markovian decision process）。代理的目標是通過與環境的交互學會環境的內在狀態和與環境打交道的最優策略。

代理演算法和環境的一次交互稱為迭代。演算法需要有一個基本的策略（policy），在每次迭代過程中，演算法會根據這個策略選擇一個動作（action）。在接收到演算法的動作之後，環境會返回一個信號（reward），正代表獎勵，負代表懲罰。代理會根據這個信號來評價自己先前策略是否好。下圖是一個強化學習的示意圖：

用強化學習解決問題，我們需要首先把要解決的問題轉化成為一個環境（environment）。環境需要如下的要素：

  • 狀態空間（state space）：對於圍棋來說，每一個棋盤布局（記為s）就是一個狀態。所有可能的棋盤布局就是狀態空間。
  • 動作空間 （action space）：對於圍棋來說，所有可能落子的位置就是一個動作空間
  • 可行動作 （allowable action）： 在給定狀態下，什麼動作是可行，什麼是不可以的。在圍棋里，就是給定一個棋盤，哪裡可以落子，哪裡不可以。
  • 狀態轉化：你落子之後，對手可能會下的子。如果是兩台alpha zero互搏的話，相互是對方環境的一個部分。
  • 獎勵函數：你落子之後得到的信號。在圍棋裡面，就是勝率的一個正函數。勝率越大，獎賞越大。

在強化學習裡面，知識可以通過一個稱為狀態－動作值函數（state-action value function) 的結構的存儲。通常大家用符號Q(s,a)來表示這個函數，這就是所謂Q-learning的來歷。簡而言之，Q(s,a)是對於狀態s，採取動作a的期望獎勵(expected reward)。

在最早期的強化學習演算法裡面，Q(s,a)就是一張表的形式來存儲的。每次演算法會查這個表，然後選取能夠帶來期望收益最大的動作。需要注意的是，實際過程中演算法還需要考慮到過早收斂的問題（可以用探索exploration來解決，我們會稍後聊到）。顯而易見，如果狀態空間很大，或者是連續空間，那麼查表就不管用了，需要使用函數逼近的方式，這就是神經網路的強項了。

在深度強化學習就是利用深度神經網路來逼近值函數的一類強化學習方式。而AlphaGo就是深度強化學習的代表。

下面開始正式的介紹AlphaGo Zero的實現。

深度神經網路

在AlphaGo裡面，並沒有直接用神經網路逼近狀態－動作值函數Q(s,a)，而且用來逼近另外一種值函數－－狀態值函數。簡而言之：

  • V(s)是棋盤布局s下自己的平均勝率。

V的定義域要遠遠小於Q，所以逼近起來容易一些。但是V中的信息需要一定的轉化才能用來決定落子位置。

先介紹一種經典的方式（雖然AlphaGo Zero沒有採用這種方式）：大概的方式是先通過V重建出Q，然後再用查表法類似的概念來確定落子位置。如何重建呢？要點在於如下公式

其中P(s, a, s) 是在布局s的情況下，落子a處，對方落子之後，布局會變為s的概率。r(s,a) 是這一步的收益（但是在AlphaGoZero裡面實際是一個常量，只取決於最終的勝負）。這個公式的意思是，如果一個落子能夠平均意義上將我的帶到一個更好的布局，那麼這個落子的平均期望收益就更好。如果我們有辦法知道轉化概率P(.,.,.)的話，那麼就可以通過V來重建出Q。

那麼我們怎麼才能夠知道概率呢？一個常用的方式是蒙特卡洛模擬演算法。也就是說我試很多次在布局s的情況下選擇落子，然後用真正跳到布局s的頻數除以總共試的次數就是估計的概率了。不幸的是，這個方法對於模擬次數要求很高，不是很實用。

在AlphaGo早期版本裡面，利用了另外一個神經網路來解決這個問題。大概的思路是把估計Q和根據Q的信息預測下一步的落子位置的這個兩個部分合起來當作一個黑箱，用神經網路來直接預測落子位置。在AlphaGo論文裡面

  • 用來逼近值函數V的神經網路被稱為 Value Network
  • 用來預測落子位置的神經網路被稱為 Policy Network

AlphaGo Zero在此基礎上又進一步改進。將兩個網路融合稱為一個神經網路。對於每一個可能的棋盤布局s，這個神經網路輸出如下兩個結果：

  • 當前勝率(v)：在當前的盤面下己方取勝的概率。v就是之前版本里value network的輸出。
  • 落子概率(p)：這是一個向量，每一個維度對應棋盤上的一個位置，向量的第a個元素是落子到位置a的概率。p就是之前版本里policy network的輸出。

蒙特卡洛樹搜索MCTS

前一部分提到的落子概率也被稱為策略（policy）。有了落子概率，非常簡單的方式是直接按照這個概率進行落子。但是事實上這會導致神經網路總是原地踏步。這是因為Policy Network的訓練數據是自己和自己下棋（self-play）生成的輸出，僅僅自己學習自己是不會有改進的。

圖：AlphaGo Zero結構圖

所以這裡需要有一個辦法來利用值函數的信息來優化這個策略。在AlphaGo系列演算法裡面是使用蒙特卡洛樹搜索（MCTS）來進行策略優化的。上圖是AlphaGo的結構圖，MCTS的輸出 pi 是依據值函數V得到的一個更優策略，它將被用於通過self－play來生成數據供深度神經網路學習。MCTS也是AlphaGo能夠通過self－play不斷變強的最重要的原因。

這一種強化學習方法被稱為 Policy Iteration （策略迭代法）。這個方法裡面交替執行如下兩步：

  • 策略評估 （policy evaluation）：估計當前policy的value function。也就是神經網路在做的事情
  • 策略優化 （policy improvement）：使用蒙特卡洛樹搜索根據估計的value function改進的policy

下面詳細介紹一下這個策略優化是怎麼進行的。在圍棋行棋的過程中，每一次落子都有多種變化，可以用一個多叉樹來表示。樹的每一個節點代表了一種棋盤布局s，每一個邊代表了在一種布局s下的一種落子方式a。

在MCTS裡面，每一個邊存儲四個信息

  • Q(s, a): 平均收益：這個就是前文提到的狀態－動作值函數。
  • N(s, a)：訪問次數
  • W(s,a): 總收益
  • P(s,a): 出現狀態s並且選擇了動作a的先驗概率。這個先驗概率就是神經網路預測的落子概率。

AlphaGo Zero的MCTS有如下的四個步驟。我們會依次介紹：

推演落子規則 (Select)

在每一個節點s，AlphaGo Zero會根據如下的公式來選擇下一次落子位置：

其中Q(s, a)是對於狀態動值函數的估計值。U(s,a)是一個confidence interval 的upbound。決定探索（exploration）的程度。

MCTS在進行搜索的過程中，嘗試重建狀態動作值函數Q。然後根據查表法類似的原理選擇能使期望收益最大的動作。注意到這個增加了一個額外的選項U(s,a)。為什麼這個選項重要呢？有兩個原因

  • 即使我們Q的估計完全準確，如果我們每次都選最優的，那麼演算法很快會收斂到一個局部解跳不出來了，所以我們需要避免讓演算法老走一樣的棋，增加一些探索其他選項的機會。這就跟小孩子學習一樣，必須通過適當的犯錯才能夠學習到更多。
  • 我們里的值函數只是一個估計值，不一定準確。

推演和判定 (Expand and Evaluate)

AlphaGo Zero會根據前面的落子規則不斷的落子，這就相當於棋手在腦海中進行推演。但是圍棋的搜索空間即使對於計算機來說也是太大，AlphaGo zero只會推演（模擬）到一定步數就停止了。假設最後的布局是s, 那麼AlphaGo Zero會調用深度神經網路來預測這局推演結束時自己的勝率v(s) 。這樣的推演過程會進行多次。

復盤 (Backup)

等一次推演結束後，AlphaGo zero會根據推演的結果更新自己的知識，也就是值函數Q（s，u）。

對於任意棋盤布局s和任意一種可能落子方案，AlphaGo Zero會依據最終的勝率調整落子的知識（存儲在值函數Q(s, a) 裡面）。值函數的更新公式如下：

對於這個公式的理解重點在於這個求和符號 s,a ightarrow s , 它代表的是一次推演出現了在布局s的情況下AlphaGo Zero選擇了落子a處，並且這次推演最終布局是s。N(s, a)是說有多少次這種情況發生。v(s)是最終盤面的勝率，相當於最終的獎勵。這個獎勵被平均分配到每次決策中。

真正落子(Play)

在不斷的推演復盤再推演的過程中，行棋會不斷的優化。經過一段時間優化，推演的落子概率就是一個更加好的策略。MCTS的輸出

其中 pi_{a} 是落子到位置a的概率， au 是一個參數，用來指定溫度。如果溫度越高，落子越隨機，溫度越低落子越確定。

深度學習訓練

在AlphaGo Zero里使用的是有監督的深度學習。而訓練樣本來自於自己和自己博弈的訓練數據（self play）。每一步Alpha Zero都會根據MCTS來選擇落子處，直到分出勝負。勝者的單步獎勵（記為z）是＋1，負者的單步獎勵是－1。

前文提到AlphaGo Zero裡面的神經網路實際上是把AlphaGo裡面的Policy Network和Value Network糅合在一起了，所以這個神經網路也有兩個目標

  • 讓輸出的落子概率p和MCTS的輸出 pi 越接近越好
  • 讓預測的值函數v和實際的獎勵z越接近越好

最終的要優化的損失函數是

損失函數l包含三項：第一項是為了優化值函數的預測，第二項是為了優化落子概率的預測，第三項是為了防止過擬合。

AlphaGo Zero每1000步會將一個神經網路存檔，並且把這個存檔和歷史最優版本比較，如果勝率超過歷史最優的55%，這個版本將會被更新為歷史最優。並且在生成數據時，只使用歷史最優的神經網路的self－play數據作為深度網路的訓練數據。這樣可以增加演算法的優化速度。

AlphaGo Zero里使用的是深度殘差網路（ResNets），論文裡面提到ResNets帶來了600 Elo的提升。這個方法是何凱明孫劍等人在微軟亞洲研究院工作期間提出，何凱明現在在facebook，孫劍是曠視的首席科學家。這可以看出華人科學在現在在深度學習領域裡面有舉足輕重的地位。

論文裡面還提到了很多工程實現和調參的細節。我暫時還沒有自己實現，但這些細節應該對AlphaGo Zero最終效果起到了至關重要的幫助。這邊文章主要描述方法，有機會我會另闢文描述工程實現。

關於新老AlphaGo的區別和AlphaGo Zero意義的個人看法

新版方法上面並沒有增加，反而是減少了很多部分：依據人類棋譜學習的監督學習部分，快速走子部分都被拿掉了。兩個神經網路被融合成一個。在我看來，少就是多，這就是這篇文章最重大的意義。

第一版本由好幾個部分拼湊起來，像是接力跑一樣，到底是哪個部分最核心最關鍵也說不好。許多人會認為基於人類歷史棋譜的學習是最重要的部分。但是這邊文章證明的是，人類歷史棋譜不僅不幫忙，很有可能是限制演算法效率的因素。人類的圍棋知識可能陷入了一個局部最優。如果從這個點出發優化，可以做到比人好一些，但是不可能拿到望塵莫及的地步。

AlphaGo Zero直接用強化學習從頭開始學習，沒有條條框框，可以探索出完全不同的方式。我認為這就是為什麼新版會強很多的原因。

另外為什麼會新版快很多？ 第一拿掉了很多無用的部分，計算效率當然更高。第二應該是團隊的工程能力和對工具的熟悉度都有了很大提升，Deepmind 2015年加入Google，2016年初第一版的時候對於Google的架構很有可能還不是那麼熟悉，這一版本肯定進行了大量的優化。

Reference

  • https://deepmind.com/blog/alphago-zero-learning-scratch/
  • https://storage.googleapis.com/deepmind-media/alphago/AlphaGoNaturePaper.pdf
  • Deep Residual Learning for Image Recognition： arxiv.org/abs/1512.0338

推薦閱讀：

※阿爾法狗： 對，我是會下圍棋，所以你就害怕了？
※柯潔和阿法狗對戰之後，對柯潔的影響有多大？柯潔的棋力提升了多少？
※柯潔 VS AlphaGo，誰將旗開得勝？
※柯潔被打敗，但中美人工智慧的戰爭才剛剛開始
※從圍棋角度看李世石與 AlphaGo 的第二局比賽有哪些關鍵之處？

TAG:AlphaGo | 围棋软件 | GoogleDeepMind |