# AlphaZero 之加速演算法實作

###### tags: `圍棋` `論文` `電腦對局`

* 註: 本論文報告對應版本 v0.4 ~ v0.5，其中描述的一些方法在之後的版本有被修正

## 簡介

DeepMind 提出 AlphaGo Zero 演算法，此演算法雖然強大但卻要消耗大量的計算資源，隨後 Leela Zero 、KataGo 和其它等實作提出一些改進方法，減少了訓練資源。我實作的圍棋程式，Sayuri，使用了部份加速演算法和 Gumbel，也減少了一定的計算資源，比對早期 Leela Zero 的訓練結果，約減少 21.48 倍的計算資源。我實作的的程式開源於此 https://github.com/CGLemon/Sayuri 。

關鍵詞： AlphaZero、SE、LCB、Gumbel

## 1. 前言

DeepMind 在 2017 年提出 AlphaGo Zero 演算法，此算法在不需要人類專家的情況下，僅通過自我對戰便在圍棋上達到超人類（super human）等級的水準 [1]，而後又提出 AlphaZero 並在圍棋、西洋棋和將棋等領域達到一樣的等級 [2]。雖然如此，它卻相當消耗計算資源，在 GTX 1080Ti 上，Pascutto (2017) 估計完整重現此算法約要消耗 1700 年 [10]。經過幾年的演進，不同的實作提出了各種對於 AlphaZero 加速訓練的演算法或技巧，例如 Wu (2019) 在 KataGo 內 通過加入各種改進，相比於 ELF Open Go 達到 50 倍的加速性能 [3]。

Sayuri 是一個基於 AlphaZero 演算法設計的開源圍棋引擎。在這篇論文裡，我嘗將 Leela Zero 、KataGo 和其它圍棋引擎的改進方法實作到 Sayuri 裡，實作的主要改進分為網路結構、搜索演算法和 Gumbel 學習法。我使用一台 RTX 2070 SUPER 的機器，通過自對戰學習 112 萬盤棋之後，我將當前的權重和相似強度的 Leela Zero 第 80 代權重做對比，我估計了消耗的計算總量，如果都換算成等效於 20bx256c 網路計算量的總模擬次數，Sayuri 約使用 2142 百萬次模擬，Leela Zero 約使用 46000 百萬次模擬 [3]，相比之下，總共節省約 21.48 倍的計算資源。

## 2. AlphaZero 的基本描述

AlphaZero 有三個重要的組成部件，分別為 replay buffer、selfplay workers 和 training worker [4]。replay buffer 是一個 FIFO queue，它儲存最新的 $n_{replay}$ 盤自我對戰訓練資料並排出過舊的資料，selfplay workers 使用最新的權重自我對戰產生訓練資料，並放入 replay buffer，training worker 使用 replay buffer 內的資料訓練新的權重。

AlphaZero 在自我對戰時使用 MCTS（Monte-Carlo tree search）決定次一手並產生訓練資料。MCTS 在 AlphaZero 分為三個階段，Select、Expand and Evaluate 和 Backup [1] ，這三個階段完成一次稱為一次模擬（或稱 playout）。Select 階段從根節點開始，會從根節點開始，每次都從自身所有子節點中選擇有最大 $PCUT(a)$ 值的節點下降，直至到葉節點 [1]。

$$
\begin{split}
\
\\ PUCT(a) = Q(a) + C_{puct} P(a) \frac{\sqrt{\Sigma{N(b)}}}{N(a)+1}
\\
\end{split}
$$

</br>

其中 $Q(a)$ 是節點 $a$ 的預期分數，$N(a)$ 是模擬時通過節點 $a$ 的次數，也稱為訪問次數，$C_{puct}$ 為平衡左右兩項的超參數，$P(a)$ 為節點 $a$ 之優先級分數 $\Sigma{N(b)}$ 為節點 $a$ 之父節點的所有子節點的訪問次數總和。

當到達葉節點時為 Expand and Evaluate 階段，此時擴展當前節點可能的後選手，並將網路推論的數值分配到節點上，最後 Backup 從當前節點延當次模擬被選擇的路徑依序根新節點的預期分數 $Q$ 和訪問次數 $N$。

為了避免每次模擬都得到一樣的結果，我們在根結點上施加 Dirichlet Noise，讓低優先的節點也有機會被搜索。

$$
\begin{split}
\
\\ P(a) = 0.75P(a)_{raw} + 0.25 Dir(\alpha = 0.03)
\\
\end{split}
$$

</br>

其中 $Dir$ 是 Dirichlet 分布。

在 $t$ 時刻決定次一手前，要重複 MCTS 的模擬共 $n_{mcts}$ 次，建立一棵搜索樹，並從根節點根據各子節點的訪問次數比例，得到搜索的機率 $\pi_t$ [1]，例如根節點共 A 、B 和 C 三個子節點，其訪問次數分別為 {A, B, C} = {20, 30, 50}，則相對應的機率為 {0.2, 0.3, 0.5}。$n_{mcts}$ 次模擬後，將得到的搜索機率 $\pi_t$ 和其當前盤面狀態 $s_t$ 並推入 replay buffer 中。當本次棋局完成後，可以得到最終結果 $r$ ，將 $r$ 根據 $t$ 時刻分別轉換成當前盤面狀態的得分 $z_t \in \{-1,0,1\}$ ，最後將 $z_t$ 和 replay buffer 中對應的 $\pi_t$ 和 $s_t$ 放在一起。

每當自我對戰下完 $n_{games}$ 盤棋後，即進入訓練階段，從 replay buffer 中隨機取出資料 $s$ 、$\pi$ 和 $z$，用以訓練神經網路，我們將網路定義為 $f_{\theta}$，代表權重為 $\theta$ 的網路，且 $p,\ v = f_{\theta}(s)$，$p$ 代表輸出的優先級分佈，$v$ 代表輸出的預期得分分數。網路的損失函數定義為下 [1]。

$$
\begin{split}
\
\\ loss = (z-v)^2\ - \pi^{T}\log{p} + c|\theta|^2
\\
\end{split}
$$

</br>

AlphaZero 使用 Residual neural network（ResNet）作為基礎的結構 [13]，一般而言用 $N_{blocks}$ 和 $N_{channels}$ 兩個參數表示網路大小，$N_{blocks}$ 代表 Residual 的 block 數目，$N_{channels}$ 代表 block 使用的 channel 數目。

## 3. 文獻探討

### 3.1 Squeeze and Excitation

由 convolutional neural network（CNN）為主的結構在現代圖像分類上大放異彩，而 Squeeze-and-Excitation（SE）結構能很好的提昇 CNN 的表現，因為它讓不同的 channel 可以有效的相互分享資訊，以提昇辨識性能，Hu 等人 (2018) 便使用此結構獲得 ILSVRC 2017 的第一位 [5]。由於 ResNet 是基於多個 CNN 層堆疊而成的，所以 SE 結構可以很好的適應於 ResNet。在圍棋實作上， Minigo 嘗試引入 SE 結構後得到不錯的結果 [6]，Wu (2019) 也在 KataGo 內設計了特別的 global pooling 結構，同樣的到不錯的性能提升，他設計的結構和 SE 結構的主要概念是相同的 [3]。

</br>

### 3.2 多任務預測

最早的 AlphaGo 網路分別使用 policy network 和 value network，在之後的 AlphaGo Zero 則將兩個網路合併為一個網路，且強度提昇約 500 分 [1]。Wu 等人 (2018) 在他們的 CGI Go Intelligence 中額外加入 multi-labelled 和 board evaluation 兩項任務，並使用監督學習學習之，他們發現在使用相同樹搜索的條件下，使用多任務的網路比沒有使用的網路還要強 [7]，因此讓一個網路同時預測不同的任務是可能有潛在利益的。Wu (2019) 在 KataGo 裡增加三種主要的預測任務應用於強化學習裡，分別為 ownership 、score lead 和 auxiliary policy ，加入這三種任務能有效增加網路強度並減少訓練時間 [3]。

</br>

### 3.3 增加圍棋知識的特徵

AlphaZero 僅輸入過去八手棋的盤面和當前玩家的顏色，因此可能會誤判一些基本的資訊，像是氣、征子和死活等等。Leela Zero 也只使用過去八手棋的盤面和當前玩家的顏色作為輸入資訊，因此 Leela Zero 早期的權重，可能會像圖 1 一樣，無法準確判斷征子結果並迴避之。

<div id="ladder-bug" align="center">
<br/>
<img src="https://i.imgur.com/fBn7SXo.png" width="480"/>
</div>
</br>

圖 1、Leela Zero 0.17 使用第 62 代權重產生征子失誤。

</br>

Wu (2019) 在 KataGo 中加入氣、征子和死活等圍棋知識作為輸入資訊，並比較有無加入圍棋知識對訓練的影響，他發現加入圍棋知識的特徵能較大幅度的增加網路強度並減少訓練時間 [3]。

</br>

### 3.4 最佳的 $C_{puct}$ 數值

在原本的 PUCT 公式裡，$C_{puct}$ 數值是固定的，但 Forstén (2018) 發現最佳的 $C_{puct}$ 會隨訪問數增加而上升 [11]，經過調整和測試，他發現最佳的 $C_{puct}$ 值和訪問數有 $O(sqrt(log(n)))$ 的關係，因此他在 Leela Zero 的 $C_{puct}$ 值中添加 $O(sqrt(log(n)))$ 項。Silver 等人 (2018) 也在 AlphaZero 的 $C_{puct}$ 值中添加 $O(log(n))$ 項 [2]，兩者具有相同的意義。在 AlphaZero 的版本中，將 $C_{puct}$ 值的重新定義為

$$
\begin{split}
\
\\ C_{puct}(a) \ & = \ C_{init} + \log(\frac{N(a) + 1 + C_{base}}{C_{base}})
\\
\end{split}
$$

</br>

其中 $N$ 為節點 $a$ 的訪問次數，其它參數 $C_{init}$ 和 $C_{base}$ 為平衡的參數。

</br>

### 3.5 Lower Confidence Bound (LCB)

AlphaZero 會選擇則訪問數最大的子節點為次一手，Forstén (2019) 在 Leela Zero 測試使用 LCB 演算法取代原本 AlphaZero 的演算法，並取得不錯的成效 [12]。LCB 和 UCB 概念類似，UCB 選擇信賴分數最高的節點，而 LCB 反之選擇信賴分數最低節點。LCB 的演算法如下

$$
\begin{split}
\
\\ z(d) & \sim ApproxT(\pi_{alpha},\ d)
\\ LCB(a) &= Q(a) - z(N(a)) \times Var(a)/N(a)
\\
\end{split}
$$

</br>

其中 $ApproxT(z,\ d)$ 為 Student's T 分佈的 CDF 達到 $\pi_{alpha}$ 且自由度為 $d$ 的條件下的 z 分數，$Q(a)$ 為節點 $a$ 的預期分數，$Var(a)$ 為節點 $a$ 子樹下所有預期分數的變異數，$N(a)$ 為節點 $a$ 的訪問次數。

### 3.6 Gumbel 學習法

雖然實作上 AlphaZero 能訓練出強大的網路，但在數學上它並不保證學習能提昇網路表現。Danihelka 等人 (2022) 提出結合蒙地卡羅樹搜索（MCTS）和 Gumbel 的演算法，且保證此算法能提昇網路表現 [8]。Sayuri 使用其中兩個重要的算法，Sequential Halving with Gumbel 和 Learning an improved policy。

Gumbel trick 依據機率 $p$ 採集樣本，將原本的機率 $p$ 轉換成 logits 值，並混入 Gumbel 噪音，每此採集 logit 值最大的樣本。

$$
\begin{split}
\
\\ (g \in R^{k}) \ & \sim \ Gumbel(0)
\\ A \ & = \ argmax(g(a) + logit(a))
\\
\end{split}
$$

其中 $logit(a)$ 為 $p$ 中樣本 $a$ 的 logit 值，$A$ 為被採集的樣本，$Gumbel$ 為 Gumbel 分佈。

</br>

今將此模型使用在樹搜索上並混合節點的預期分數，加入預期分數項可以減少不好的節點被選擇的機率。令 $Actions_{root}$ 為根節點上所有可能合法手，即為根節點上所有的子節點，節點 $a \in Actions_{root}$ ，也就是說此模型僅在根結點才使用 Gumbel trick。

$$
\begin{split}
\
\\ A_t \ & = \ argmax(g(a) + logit(a) + \sigma(Q(a)))
\\ \sigma(Q(a)) & = (c_{visit} + Max(N(b))) \times c_{scaling}Q(a)
\end{split}
$$

</br>

其中 $Max(N(b))$ 為根節點中所有子節點裡訪問數最大的值， $c_{visit}$ 和 $c_{scaling}$ 為平衡輸出的超參數。$A_t$ 為時刻 $t$ 選擇的子節點。

Sequential Halving 會選擇 $n_{seq}$ 個後選手，每一輪會模擬 $n_{seq}$ 次，並淘汰剩剩餘的一半的後選手，直至剩下 1 個後選手或模擬次數達到 $n_{mcts}$ 次為止。而 Sequential Halving with Gumbel 使用 Gumbel trick 作為選擇並淘汰後選手的依據。

當完成 $n_{mcts}$ 模擬後，可以直接使用 $A_{n_{mcts}}$ 作為網路的學習目標 $\pi$ ，但更好的方法為 Learning an improved policy，將原本網路輸出的 logits 值混合子節點的 CompletedQ 值，並再次轉換為新的搜索率 $\pi$，此方法可以有效的提昇訓練表現。

$$
\begin{split}
\
\\ \pi &= Softmax(logits + \sigma(CompletedQ(a)))
\\
\\ CompletedQ(a) &= \begin{cases}
Q(a), \ \ \ if\ \ N(a) > 0
\\ v_{\pi}, \ \ \ otherwise
\\ \end{cases}
\\
\end{split}
$$

</br>

Gumbel 不只是在數學上保證能提昇網路表現，它還能大幅提昇訓練效率，相比於傳統的 AlphaZero-like 演算法，在達到相同強度的條件下，可以節省約有 5 到 20 倍的總模擬次數 [8]。

</br>

## 4. Sayuri 之實作

### 4.1 網路結構和輸入

Sayuri 網路部份採用 ResNet 加上 SE 結構，但和一般 SE 結構不同的是，在 global pooling 部份採用 KataGo 的 global pooling 結構，整個 SE 結構設計如下。

* 輸入的資料 $X$（大小為 $b\times b\times c$）
* 一個 Global Pooling layer（輸出為大小 $3c$）
* 一個 fully connected layer（輸出為大小 $s$）
* 一個 fully connected layer（輸出為大小 $2c$）
* 輸出切分成 $gammas$（大小 $c$） 和 $betas$（大小 $c$）
* $X$ 以 channelwise 相乘 $gammas$，以 channelwise 相加 $betas$

</br>

輸入給網路的資訊除了基本的歷史資訊之外，也加入額外的圍棋知識特徵以提昇網路性能，所有輸入資訊如表 1。

表 1、Sayuri 輸入給網路的所有特徵，總計共 38 層。

| 總層數 | 特徵名稱 |
| :--------: | :-------- |
| 24 | 過去八手的歷史資訊（我方棋子、對方棋子、行棋位置）|
| 1 | 打劫的位置 |
| 1 | pass-alive 和 pass-dead 的區域 |
| 4 | 棋串的氣（1 到 4 氣） |
| 4 | 處於征子的棋子和征子打吃的位置 |
| 2 | 貼目 / 20 |
| 1 | 棋盤的交叉數目 / 361 |
| 1 | 所有位置填充 1 |

</br>

### 4.2 搜尋實作

* 註：v0.6 後的算法描述寫在[這裡](https://hackmd.io/@yrHb-fKBRoyrKDEKdPSDWg/BJgfay0Yc#Sayuri-%E4%B9%8B%E6%A8%B9%E6%90%9C%E5%B0%8B%E5%AF%A6%E4%BD%9C)

Sayuri 的搜索過程混合 Gumbel 和 PUCT 演算法，搜尋分為兩個階段，第一個階段為 Gumbel 搜尋階段，第二個階段為 PUCT 搜尋階段，也就是最初的 $n_{gumbel}$ 次模擬使用 Gumbel 演算法，剩餘的 $n_{mcts}-n_{gumbel}$ 次使用 PUCT 演算法。

在 PUCT 演算法的部份，$C_{puct}$ 定義採用 AlphaZero 改進的版本以調整最佳值，並在選擇次一手時採用 LCB 演算法提昇自對戰品質。

表 2、Sayuri 自對戰使用的一些參數設置。

| 參數 | 數值 |
| :--------: | :--------: |
| $n_{replay}$ | 500000 |
| $n_{mcts}$ | 100 |
| $n_{gumble}$ | 50 |
| $n_{seq}$, $c_{visit}$, $c_{scaling}$ | 16, 50, 0.1 |
| $C_{init}$, $C_{base}$ | 1.25, 19652 |
| $N_{blocks}$, $N_{channels}$ | 6, 128 |

</br>

## 5. 實驗結果

Leela Zero 是由 Pascutto (2019) 根據 AlphaGo Zero 的論文實實作並開源的圍棋程式 [9]，由於 AlphaGo Zero 和 AlphaZero 本身沒有開源，而 Leela Zero 為開源的且有豐富的資料，因此我認為對比 Leela Zero 能一定程度上看出本實作相對於 AlphaZero 改進的效果。

我選取 Sayuri 通過自對戰 112 萬盤棋產生的權重，對比 Leela Zero 第 80 代權重，根據表 3 的結果，在一百盤的對戰中， Sayuri 的勝率為 49%，因此我認為兩者的強度是類似的，最後將自對戰中的總模擬次數轉換成相對於 20bx256c 網路的模擬次數作為總計算量，根據計算總量對比的結果，Sayuri 節省了約 21.48 倍的計算量。

表 3、Sayuri 0.4.1 使用自對戰 112 萬盤棋產生的權重，對比 Leela Zero 0.17 使用第 80 代權重的對戰結果，Sayuri 的參數為 ```./Sayuri -w WEIGHTS.txt -t 1 -b 1 -p 100 --friendly-pass --reuse-tree --lcb-reduction 0 --score-utility-factor 0.1 --cpuct-init 0.5``` ，Leela Zero 的參數為 ```./leelaz -w WEIGHTS.gz --noponder -g -t 1 -b 1 -q -p 100```

| 引擎 | 黑勝 | 白勝 | 勝率 | 總計算量 | 強度 |
| :--------: | :------: | :------: | :------: | :------: |:------: |
| Sayuri 0.4.1 | 22 | 27 | 49% | 2142M | 業餘高手 |
| Leela Zero 0.17 | 23 | 28 | 51% | 46000M | 業餘高手 |

</br>

## 6. 結論

通過加入各種改進，相較於最初的 AlphaGo Zero 演算法，整體性能大幅提昇，將我的實作對比 Leela Zero ，可以節省約 21.48 倍的計算量。但對比 Wu (2019) 在 KataGo 的結果，它在達到 Leela Zero 0.17 使用第 80 代權重強度時，可以節省約 100 倍的計算量 [3]，因此我認為 Sayuri 還有較大的改進空間。

由於訓練時有多個參數可以調整，不同參數可能可以優化訓練結果，而我本次自對戰訓練並沒有嘗試不同參數，因此我認為參數調整這部份有較大的進步空間，未來要嘗試調整不同的參數，並研究何種參數可以較大影響訓練性能，希望能超過 KataGo 的性能表現。

## 參考文獻

[1] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel and Demis Hassabis, “Mastering the game of go without human knowledge,” Nature, 550:354–359, 2017.

[2] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis, “A general reinforcement learning algorithm that masters chess, shogi, and go through selfplay,” Science, 362(6419):1140–1144, 2018.

[3] David J. Wu, “Accelerating Self-Play Learning in Go,” 2019, arXiv preprint, arXiv:1902.10565.

[4] Yuandong Tian, Jerry Ma, Qucheng Gong, Shubho Sengupta, Zhuoyuan Chen, James Pinkerton, and C. Lawrence Zitnick, “Elf opengo: An analysis and open reimplementation of alphazero,” In Thirty-Sixth International Conference on Machine Learning, 2019.

[5] Jie Hu, Li Shen, Samuel Albanie, Gang Sun, and Enhua Wu, “Squeeze-and-excitation networks,” In IEEE Conference on Computer Vision and Pattern Recognition, pages 7132–7141, 2018

[6] Seth Troisi, “[Experiment] Squeeze and Excitation,” 2019, Minigo project issue, https://github.com/tensorflow/minigo/issues/683

[7] Ti-Rong Wu, I-Chen Wu, Guan-Wun Chen, Ting han Wei, Tung-Yi Lai, Hung-Chun Wu, and Li-Cheng Lan, “Multi-labelled value networks for computer go,” IEEE Transactions on Games, 10(4):378–389, 2018.

[8] Ivo Danihelka, Arthur Guez, Julian Schrittwieser, David Silver, “Policy improvement by planning with Gumbel,” In International Conference on Learning Representations, ICLR, 2018.

[9] Gian-Carlo Pascutto, “Leela Zero project main webpage,” https://zero.sjeng.org/, last accessed: 2022-03-14.

[10] Gian-Carlo Pascutto, “[Computer-go] Zero performance,” http://web.archive.org/web/20190205013627/http://computer-go.org/pipermail/computer-go/2017-October/010307.html, last accessed: 2022-03-14.

[11] Henrik Forstén, “Add O(sqrt(log(n))) scaling to tree search,” 2018, Leela Zero project issue, https://github.com/leela-zero/leela-zero/pull/2072

[12] Henrik Forstén, “Pick chosen move based on normal distribution LCB,” 2019, Leela Zero project issue, https://github.com/leela-zero/leela-zero/pull/2290

[13] Kaiming He, Zhang, Xiangyu Zhang, Shaoqing Ren, “Jian Sun. Deep residual learning for image recognition,” 2016, In IEEE Conference on Computer Vision and Pattern Recognition, 770–778.

## 雜物區
[GCP 1700 years](http://web.archive.org/web/20190205013627/http://computer-go.org/pipermail/computer-go/2017-October/010307.html)
[KataGO 論文](https://arxiv.org/abs/1902.10565)
[AGZ 論文](https://discovery.ucl.ac.uk/id/eprint/10045895/1/agz_unformatted_nature.pdf)
[AZ 論文](https://arxiv.org/abs/1712.01815)

[Resnet Paper](https://arxiv.org/abs/1512.03385)