---
tags: Knock Knock! Deep Learning
---
Day 27 / DL x RL / 令世界驚艷的 AlphaGo
===

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

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

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

## AlphaGo

[(Silver et al., 2016) Mastering the game of Go with deep neural networks and tree search](https://deepmind.com/research/publications/mastering-game-go-deep-neural-networks-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 $p_{\sigma}$
2. Reinforcement learning (RL) policy network $p_{\rho}$
3. Rollout policy network $p_{\pi}$

在 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 $s_L$，我們想要估計這個 node 的勝算。首先從 $s_L$ 往下 expand 一層。
3. **Evaluation**：每個 $s_L$ 的 child node 會開始 rollout，也就是跟著 rollout policy network 預測的 action 開始往下走一陣子，取得 outcome $z$。最後 child node 的勝算會是 value network 對這個 node 預測的勝率和 $z$ 的結合。
4. **Backup**：$s_L$ 會根據每個 child node 的勝率更新自己的勝率，並往回 backup，讓從 root 到 $s_L$ 的每個 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](https://deepmind.com/blog/article/alphago-zero-starting-scratch)

其實 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](https://web.stanford.edu/~surag/posts/alphazero.html)
2. [AlphaGo Zero Explained In One Diagram](https://medium.com/applied-data-science/alphago-zero-explained-in-one-diagram-365f5abf67e0)
3. [AlphaGo: How it works technically?](https://medium.com/@jonathan_hui/alphago-how-it-works-technically-26ddcc085319)
4. [(Video) Monte Carlo Tree Search (MCTS) Tutorial](https://www.youtube.com/watch?v=Fbs4lnGLS8M)