如果你經歷過 2016 年，且對圍棋或 AI 稍有研究，那你肯定聽過 AlphaGo 的偉大事蹟 —— 在和世界頂尖圍棋高手李世石的五盤較量中，AlphaGo 以 4:1 擊敗李世石。

圍棋被稱為世界上最複雜的遊戲。圍棋標準 19 x 19 盤面的所有走法龐大到難以窮舉，所需的計算能力堪稱所有遊戲之最。能打敗頂尖棋手的西洋棋 AI Deep Blue 早在 1996 年就被開發出來，但 2016 年之前應該鮮少有人相信有電腦 AI 可以擊敗職業圍棋手。

那麼 RL 到底怎麼被用來訓練 AlphaGo，讓他能夠超越人類？

AlphaGo

(Silver et al., 2016) Mastering the game of Go with deep neural networks and tree search

圍棋遊戲在 RL 框架裡，大概是這樣定義：

• Agent：AlphaGo AI。
• Environment：圍棋遊戲。
• State：盤面上的棋子擺放、輪到誰下等等。
• Action：下一手的落點。
• Reward：最終獲勝與否。

AlphaGo model 主要包含三個元件：

1. Policy network：根據盤面預測下一個落點的機率。
2. Value network：根據盤面預測最終獲勝的機率，類似預測盤面對兩方的優劣。
3. Monte Carlo tree search (MCTS)：類似在腦中計算後面幾步棋，根據幾步之後的結果估計現在各個落點的優劣。

—— AlphaGo 中的元件。

AlphaGo 能下棋之前，會先用現成 data 和 RL 訓練好 policy network 和 value network。接著下棋時，在每一步會需要模擬計算各種落點下面幾步棋的進行，尋找勝率最高的落點。因為行棋可能性太多，會利用 MCTS 結合訓練好的 policy network 和 value network 來優化搜尋過程。

接著來分別介紹一下這些元件。

Policy Network

Policy network 給定 input state，會 output 每個 action 的機率。

AlphaGo 中包含三種 policy network：

1. Supervised learning (SL) policy network
2. Reinforcement learning (RL) policy network
3. Rollout policy network

在 RL 之前，我們會先用 supervised learning 訓練出一個還不錯的 SL policy network。方法很簡單，只要有棋譜，每一步都是一個 state-action pair，我們就從這些 data 來訓練。AlphaGo 的 SL policy network 訓練在 3 千萬筆這樣的 data 上，訓練出來的 model 有 57% 預測準確率。

但是 supervised learning 還不夠。用這樣的方法訓練，結果再好也不過跟人類能打罷了，因為終究是在模仿人類。因此我們在 SL policy network 之上用 RL 訓練，讓他自己不斷嘗試不同走法，這樣才有機會真正走出人類沒想過的好棋並打敗人類。

因此 Alphago 中的 RL policy network 和 SL policy network 架構相同，不過藉由 RL 繼續訓練下去。方法是讓這個 policy network 和另一個不同的 policy network 對下，贏的話 reward 是 +1，輸的話是 -1，最後將 reward 返回到 network 裡做 gradient descent。最後訓練出的 RL policy network 對上 SL policy network 的勝率有 80%，大有進步。

最後是 rollout policy network，也是用 SL 訓練，差別是 network 較小，evaluation 比較快，但精準度較低。這個 policy network 目的是讓 MCTS 裡的 simulation 更快，後面會提到。

Value Network

除了 policy network，我們還需要一個預測勝率的 value network。Input 是 state，output 是勝率值。

這個 network 也可以用 supervised learning 訓練，data 是歷史對局中的 state-outcome pair，loss 是 mean squared error (MSE)。

Monte Carlo Tree Search (MCTS)

有了 policy 和 value network，最後我們用 Monte Carlo tree search (MCTS) 結合這些 network 做 planning，決定遊戲進行時的下一步。

所謂 tree search 就是將計算過程用樹狀結構表示，由 root 往下展開後，根據 leaf node 的遊戲結果，回饋給中途每個 node 來計算勝率。

以圍棋來說，用窮舉法來計算會讓整個 tree 太大，因此不可行。於是我們利用 Monte Carlo tree search 來減小 search space，過程大致包含四步驟：

—— MCTS 四步驟示意圖。

1. Selection：從 root 開始，藉由 policy network 預測下一步落點的機率，來選擇要繼續往下面哪一步計算。選擇中還要考量每個 state-action pair 出現過的次數，盡量避免重複走同一條路，以平衡 exploration 和 exploitation。重複這個步驟直到樹的深度達到 max depth L。
2. Expansion：到達 max depth 後的 leaf node ，我們想要估計這個 node 的勝算。首先從 往下 expand 一層。
3. Evaluation：每個 的 child node 會開始 rollout，也就是跟著 rollout policy network 預測的 action 開始往下走一陣子，取得 outcome z。最後 child node 的勝算會是 value network 對這個 node 預測的勝率和 z 的結合。
4. Backup： 會根據每個 child node 的勝率更新自己的勝率，並往回 backup，讓從 root 到 的每個 node 都更新勝率。

最後 search 完有了每個 node 的勝率，AlphaGo 會選擇往勝率最高的地方走。

整個過程其實就是人類在下圍棋時，會考量各個選點往下走的變化圖，並根據變化結果決定每個選點的勝率，最後走在勝率最大的地方。

看到這裡應該會意識到，policy network 和 value network 好像都可以用來預測下一手，但他們並沒有認真考慮後面變化之後帶來的影響。MCTS 才是尋找最大勝率落點的過程，而 policy network 和 value network 的預測值是用來協助減小 search space 和估計勝率。

Results

AlphaGo 和一些其他圍棋 AI 對戰的勝率是 99.8%，和人類職業棋手 Fan Hui 對戰結果是 5:0。這也是第一次圍棋 AI 打敗人類職業棋手。

除了拿來對戰，AlphaGo model 還可以用來分析對戰過程中的勝率和變化圖，提供人類棋手參考學習。

—— AlphaGo 可以用來分析棋局。

AlphaGoZero

(Silver et al., 2017) Mastering the game of Go without human knowledge

其實 RL 在 AlphaGo 中不算功勞巨大。AlphaGo 的訓練過程仰賴許多人類棋局的 data，包括 SL policy network 和 value network 的訓練。

直到 AlphaGoZero 的出現，RL 的真實力才真的讓人震驚。他做出了以下改變：

• 訓練過程中沒有使用 human data，純粹依靠 RL。
• Input feature 只包含棋盤上的黑白子。
• 沒有 policy network 和 value network 之分，只用了一個 network。
• 使用了更簡單的 tree search 方法，不需要 rollout。

這個 single network 接收 input state 預測兩個值：下一手的機率，和下一手的價值，其實就是 policy network 和 value network 的結合。訓練過程一開始隨機 initialize network，接著讓自己和自己對戰，並完全用勝負 reward 來進行 RL 訓練。

雖然一開始預測勝負的準確度不及 supervised learning，但隨著訓練越來越久，準確度最終超越了 supervised learning，勝率也超越了先前的 AlphaGo。

—— AlphaGoZero 倒吃甘蔗，最終訓練成果能超越人類更多。

AlphaGoZero 的訓練過程有點像經歷了幾千年人類下圍棋的歷史，訓練中途可以看到他已經自己學會了一些定石（局部雙方的固定走法），甚至自己發明新的定石。現在的 AlphaGoZero 應該是沒有 AI 存在的話，很多年以後人類圍棋的發展結果吧。

結語

身為時常關注圍棋界的棋迷，AI 帶來的改變還是滿深刻的。有些定石被 AI 的新定石淘汰，也有些被淘汰的定石被 AI 肯定而回歸。下完棋後的覆盤講解，大部分的老師都會用 AI 分析勝率和最佳選點，彷彿 AI 成了正確解答。透過和 AI 下棋，一些原本被環境資源限制的職業棋手，也能藉由和更強的對手練習而更接近世界級的水平。

雖然 AI 很強，也不可否認他為圍棋的學習提供了方便的管道，但我覺得這般如同解答本的 AI 出現，也不盡然全是好處。學生不會寫可能選擇直接看答案，甚至為了讓考試更高分選擇背答案。熱絡的討論會被 AI 選點取代，有趣的想法會被勝率駁回。那麼下圍棋會不會有一天只剩勝負了呢？

無論如何，以圍棋的複雜度來說，AlphaGo 和 AlphaGoZero 的出現證明了 RL 的巨大學習潛能。但這種學習能力是不是能被應用在遊戲與機器人界以外的應用領域，仍然是 RL 發展的巨大挑戰。

Checkpoint

• AlphaGo 中，policy network 和 value network 分別在 MCTS 中的什麼步驟中使用？為什麼他們能幫助 MCTS 減小 search space？
• MCTS 中，為什麼 rollout 時要使用不太準確但計算更快的 rollout policy network？

參考資料

1. A Simple Alpha(Go) Zero Tutorial
2. AlphaGo Zero Explained In One Diagram
3. AlphaGo: How it works technically?
4. (Video) Monte Carlo Tree Search (MCTS) Tutorial