# 圍棋引擎 Sayuri 開發日誌
###### tags: `電腦對局` `圍棋`
## 簡介
Sayuri 是一個開原的圍棋程式，下面紀錄了一些實作方法、演算法和理論，項目位置在這裡：https://github.com/CGLemon/Sayuri
建議的閱讀順序是由上往下看，因為有些東西會重複出現。
歡迎補充或是改正錯誤或錯字。如有任何問題，可以通過 email 聯繫我，你的問題可以幫助我改進這份文章
信箱：```cglemon000@gmail.com```
</br>
## 引用文章資料
如果可以的話，盡量引用 [ref] 或延伸閱讀的資料，而不要直接引用本篇資料，本篇文章屬於二手資料（~~加本人不專業見解~~），引用二手資料的話，你可能會被教授噴爆，你交的報告可能會零分。引用的格式可以參考以下，但實際狀況請看自身報告要求。
如果是 GitHub 的 issue，格式為 "作者, 標題，來源，時間"，例如作者是 Henrik Forstén，標題為 Add O(sqrt(log(n))) scaling to tree search，來源為 https...，你最後時間檢索的時間為 2023 年 1 月 1 號，範例如下
[1] 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, last accessed: 2023-1-1.
</br>
如果是論文，則是 "作者（群）, 標題, 期刊，時間" 標示，注意，如果是已經發表在期刊上的論文，盡量不要引用 arxiv 的來源，請標注期刊、此篇論文的序號和發布時間，例如 “Mastering the game of go without human knowledge” 格式為
[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.
</br>
## 符號運用
由於本篇文章橫跨時間較久遠，會有一些符號的名稱沒有統一好，因此在這裡先標示好一些符號代表的意義，以避免誤解。在所有有關數搜索的部份，符號定義為
* $W(a)$：節點 $a$ 累積的勝利次數（Elder MCTS），或預期分數/勝率的累積次數（Deep Learning）。
* $N(a)$：節點 $a$ 累積的搜索次數，或稱模擬次數
* $Q(a)$：代表節點 $a$ 的 $W(a)/N(a)$ ，數值介於 0 到 1 之間
* $P(a)$：節點 $a$ 的策略分數，數值介於 0 到 1 之間
* $\Sigma{N(b)}$：通常 $b$ 代表自己和所有兄弟節點，會和 $\Sigma$ 一起出現
</br>
## 棋盤資料結構
如果同學們以前有自己嘗試實做圍棋棋盤，應該可以發現圍棋棋盤和圖論有莫大的關係，首先棋盤大部份點和點之間是等價的，二來棋盤是一個平面圖，這些圖論性質暗示者在棋盤上找某些特定元素可能會非常困難，像是找出棋盤上活棋棋串，有些甚至無法保證可以找出來，像是雙活。慶幸的是，基本常用的資料結構是有定論的，接下來我們要討論如何快速計算棋盤上每一塊棋串的狀態
### MailBox
我們知道如果程式中分支條件越多，性能就會越低，假設我要找棋盤上某一點四周的氣，那就必須用四個分支條確保不會搜尋到到棋盤外，而且搜尋四周邊是使用次數非常多的功能，這將會有巨大的性能消耗，為了解決這個問題，我們要使用一個棋盤遊戲中常用的資料結構，MailBox 。假設我有一個大小為五棋盤如下
a b c d e
1 . . . . .
2 . . . . .
3 . . . . .
4 . . . . .
5 . . . . .
改進前的資料結構虛擬碼如下（注意這邊是使用一維陣列）
BLACK = 0
WHITE = 1
EMPTY = 2
INVLD = 3 # out of board value
find_adjacent(index):
type_count[4] = {0,0,0,0}
for adjacent in index
if adjacent is out of board
type_count[INVLD] += 1
else
type = board[adjacent]
type_count[type] += 1
MailBox 的核心概念就是在棋盤外圍加一圈無效區域（標示為 ```-``` 的位置），這樣就不用特別判斷是否超出邊界
a b c d e
- - - - - - -
1 - . . . . . -
2 - . . . . . -
3 - . . . . . -
4 - . . . . . -
5 - . . . . . -
- - - - - - -
改進後的資料結構虛擬碼如下，可以看見不僅性能提，整個程式碼也簡潔不少
BLACK = 0
WHITE = 1
EMPTY = 2
INVLD = 3 # out of board value
find_adjacent(vertex):
type_count[4] = {0,0,0,0}
for adjacent in vertex
type_count[type] += 1
在本程式的實做當中，如果是使用改進前版本的座標表示法，則稱為 index ，一般用於輸出盤面資料給外部使用。如果是使用改進後版本的座標表示法，則稱為 vertex，，一般用於內部棋盤搜尋。
### 棋串（string）
棋串可以看成是整個棋盤中的子圖（sub-graph），而且它是一個節點循環的圖，我們來看看下列結構，board position 是當前盤面，可以看到有兩個黑棋棋串，vertex position 是當前 vertex 的座標數值（一維陣列），string identity 是棋串的 identity，這邊注意的是 identity 指到的位置是整個棋串的 root vertex 位置，像是 identity 為 16 的棋串，其 16 的 vertex 座標必在此棋串內，此位置也為此棋串的根節點，至於為甚麼要這樣做，稍後再來討論，最後 next position 指向下一個節點位置，而且它們是循環的，像是 identity 為 16 的棋串，他的 next position 串接起來為 (17->18->16) -> (17->18->16) -> ... 無限循環
board position
a b c d e
1| . . . . .
2| . x x x .
3| . . . . .
4| . x x . .
5| . . . . .
vertex position
a b c d e
1| 8 9 10 11 12
2| 15 16 17 18 19
3| 22 23 24 25 26
4| 29 30 31 32 33
5| 36 37 38 39 40
string identity
a b c d e
1| . . . . .
2| . 16 16 16 .
3| . . . . .
4| . 30 30 . .
5| . . . . .
next position
a b c d e
1| . . . . .
2| . 17 18 16 .
3| . . . . .
4| . 31 30 . .
5| . . . . .
假設今天我們要找一個棋串的氣，只要從一個節點開始走下去，依序計算直到走到原位置，虛擬碼如下
conut_liberty(vertex):
start_pos = identity[vertex] # get the start vertex postion
next_pos = start_pos
liberty_set = set()
{
for adjacent in next_pos
if board[adjacent] == EMPTY
liberty_set.add(adjacent) # add the adjacent vertex to set
next_pos = next[next_pos] # go to next vertex postion
} while(next_pos != start_pos)
liberties = length(liberty_set)
### 儲存棋串（string）資訊
剛剛講了 identity 指向棋串的 root vertex，這 root vertex 可以儲存棋串的狀態資訊，當需要用到這些資訊時，不必每次都重算，像是棋串棋子數目，或是棋串氣數等等。本程式實做的資料結構如下
string identity
a b c d e
1| . . . . .
2| . 16 16 16 .
3| . . . . .
4| . 30 30 . .
5| . . . . .
string stones
a b c d e
1| . . . . .
2| . 3 . . .
3| . . . . .
4| . 2 . . .
5| . . . . .
string liberty set
a b c d e
1| . . . . .
2| . A . . .
3| . . . . . # A = liberty set of string 16
4| . B . . . # B = liberty set of string 30
5| . . . . .
### 合併棋串（string）
兩個棋串合併時，只要簡單的交換雙方接觸點的 next position，並把 string identity 、string stones 和 string liberty set 更新即可，如下所示。如果是多個棋串合併，只要簡單的把兩兩棋串一個個合併就好。
board position
a b c d e
1| . . . . .
2| . x x x .
3| . [x] . . .
4| . x . . .
5| . . . . .
Merge two strings...
string identity
a b c d e a b c d e
1| . . . . . 1| . . . . .
2| . 16 16 16 . 2| . 16 16 16 .
3| . 30 . . . >> 3| . 16 . . .
4| . 30 . . . 4| . 16 . . .
5| . . . . . 5| . . . . .
next position
a b c d e a b c d e
1| . . . . . 1| . . . . .
2| . 17 18 16 . 2| . 30 18 16 .
3| . 30 . . . >> 3| . 17 . . .
4| . 23 . . . 4| . 23 . . .
5| . . . . . 5| . . . . .
string stones
a b c d e a b c d e
1| . . . . . 1| . . . . .
2| . 3 . . . 2| . 5 . . .
3| . . . . . >> 3| . . . . .
4| . 2 . . . 4| . . . . .
5| . . . . . 5| . . . . .
string liberty set
a b c d e a b c d e
1| . . . . . 1| . . . . .
2| . A . . . 2| . C . . .
3| . . . . . >> 3| . . . . . # set C = set A + set B
4| . B . . . 4| . . . . .
5| . . . . . 5| . . . . .
### 偵測合法手
依據不同的圍棋規則，合法手會有不同定義，為了方便討論問題，這裡依據 Tromp-Taylor 規則且禁止自殺的實做給予合法手兩個基本條件
1. 此手棋下下去後，最終結果不為零氣，即是不能自殺
2. 禁止同一盤棋中歷史出現相同盤面（super ko）
先討論第一點不能自殺，避免自殺有三種方式
1. 四周至少有一點為空點
2. 四周與自身相同的顏色的棋串，至少一塊棋超過一氣
3. 四周與自身相異的顏色的棋串，至少一塊棋為一氣（提吃）
虛擬碼如下
is_suicide(vertex):
for adjacent in vertex
if board[adjacent] == EMPTY ＃ 第一點條件
return false
if board[adjacent] == MY_COLOR &&
string_liberties[adjacent] > 1: ＃ 第二點條件
return false
if board[adjacent] == OPP_COLOR &&
string_liberties[adjacent] == 1: ＃ 第三點條件
return false
return true
以上其中一個條件滿足，則必不是自殺手。接著討論禁止相同盤面，由於偵測相同盤面會比較消耗計算力，一般我們以偵測劫為主，也就是被吃掉的子是否為熱子，如果出現吃掉熱子棋況，則為非法手。熱子的定義為
1. 吃到一顆對方的棋子
2. 下的棋子最終結果只有一氣
3. 下的棋子最終結果只有一顆子
虛擬碼如下
is_ko(vertex):
if captured_count == 1 &&
string_stones[vertex] == 1 &&
string_liberties[vertex] == 1
return true
return false
此三項都滿足，則必為熱子。如果為相同盤面但不是劫的情況，就沒有特別的算法，只能實際將棋子擺到棋盤上後，再看是否當前盤面和歷史盤面有重複。
</br>
## Zobrist Hashing
Zobrist Hashing 是一種在棋盤遊戲中快速有效的哈西值計算方法，它利用棋盤每次更新只會影響部份的特性設計。另有一個 2x2 的圍棋棋盤共 4 個可以落子的點，每個點上的的狀態有黑棋、白棋和空格 3 種，那我們需要宣告一個 4 x 3 的陣列儲存棋盤上每個點可能的 hashing 狀態，每個狀態都是一隨機數，用 C 語言```uint64 hash[4][3]``` 表示之，共 12 個隨機數，假設此當前棋盤已經有一些落子，用一維陣列表示此棋盤狀態為 ```{黑棋, 空格, 白棋, 空格}```，則其 Zobrist Hashing 值為下
```
uint64 compute_hash(state)
res = 0x1234567812345678 # 初始哈西值
for i = 0~3
if state[i] == 黑棋
res ^= hash[i][0]
if state[i] == 白棋
res ^= hash[i][1]
if state[i] == 空格
res ^= hash[i][2]
return res
```
這套算法的特點為可以局部更新第二個 ```空格``` 改成 ```黑棋``` 就不需要從頭重新計算，因為兩次相同的 xor 運算可以互相抵銷，利用這個特性，只需要更新部份的值，更新方式如下
```
res ^= hash[1][2] ＃ 第二次空格計算，取走空格的值
res ^= hash[1][0] ＃ 第一次黑棋計算，加入黑棋的值
```
</br>
## 無條件活（pass-alive）
延伸閱讀：[無條件活定理](https://zhuanlan.zhihu.com/p/110998764), [Benson's Definition of Unconditional Life](https://senseis.xmp.net/?BensonsAlgorithm)
圍棋並沒有明確定義死活，事實上我們也很難用數學的方式定義死活，因為死活是相當多樣的，例如這個[特殊雙活](https://senseis.xmp.net/?Hanezeki)，但好在 Beason algorithm 為我們定義了最小的活棋，也就是無條件活，無條件活代表某一棋塊在我們持續虛手的情況下保證活棋，如下圖的黑棋，黑棋只要虛手就能保證白棋吃不掉它，它已經處於無條件活狀態。
<div id="pass-alive-01" align="center">
<img src="https://i.imgur.com/jXrgm3t.jpg" alt="drawing" width="500"/>
</div>
</br>
一般我們會將有兩個眼睛的棋塊視為活棋，這是因為對方無法同時下兩個點，且無法從眼睛內部堵上所有的氣，所以無法吃掉兩個眼睛的棋串，這兩個特性就是 Beason algorithm 的核心精神。此後為了方便討論，我們都只探討黑棋的無條件活，接者我們定義兩件事
1. 關鍵區域（vital）：對於某塊黑棋，白棋無法在這個區域堵上這塊黑棋在這個區域內所有的氣
2. 活棋：對於某塊黑棋存在兩個以上關鍵區域
例如下圖黑棋共有兩個區塊 A 和 B，白棋在 A 區塊無法完全堵上所有的氣，所以 A 區塊是黑棋的關鍵區域，但白棋可以 B 區塊包圍黑棋堵上所有的氣，所以 B 區塊不是黑棋的關鍵區域
<div id="pass-alive-02" align="center">
<img src="https://i.imgur.com/VjfG66n.jpg" alt="drawing" width="500"/>
</div>
</br>
Beason algorithm 的過程為，依序掃描棋盤上所有棋串，如果此棋串沒有兩個以上關鍵區域，則將此棋串移除，之後重新檢查所有棋串，直到所有棋串都是活棋或是移除所有棋串為止，虛擬碼如下。
</br>
```
running = true
while running:
running = false
for string in board_strigs:
if string's vital < 2:
remove string from board_strigs
running = true
break
```
</br>
使用 Beason algorithm 可以讓程式在下棋的過程中避免下出無意義手，在我過去的比賽經驗裡，如果棋局已經是和棋，雙方程式還是可能會持續下棋，直到把所有可以填的眼睛都填掉為止，才會虛手，如果有實作 Beason algorithm，可以強制程式虛手加速終局流程。要注意的是 Beason algorithm 在不同規則下會有不同結論，例如能否下自殺手會影響關鍵區域的判斷，甚至某些情況下 Beason algorithm 根本不適用，例如 Tromp-Taylor 必須將所由死棋提掉，此規則下 Beason algorithm 得到的結果反而可能會虧目。
</br>
## 蒙地卡羅樹搜索（Monte Carlo Tree Search）
延伸閱讀：[蒙地卡羅樹搜索論文](https://www.remi-coulom.fr/CG2006/)
早期的圍棋程式是由多個模組系統相互結合工作，像是攻殺模組，打劫模組等等，雖然每多增加一個模組，程式的判斷能力會增加，但問題是每個模組都會返回一個最局部佳解，到底哪個局部最佳解是全局最佳解很難判斷，不論是模組還是最後的選擇，都需要大量的人類知識。直到 2006 年 ，Rémi Coulom 發布了一種突破性的啟發式搜索，他成功結合 negamax tree[[ref]](https://en.wikipedia.org/wiki/Negamax) 和蒙地卡羅方法，更重要的是，它只需要少量的圍棋知識，就可以有不錯的強度，此方法稱為蒙地卡羅樹搜索（MCTS）[[ref]](https://www.remi-coulom.fr/CG2006/)。
### 實做原理
我們可以簡單的將搜索過程分為四個步驟，分別為為下，此四個階段輪迴一次稱為一次 playout 或模擬
* 選擇（selection）
* 擴展（Expansion）
* 模擬（Simulation）
* 更新（Backpropagation）
（[圖源](https://zh.wikipedia.org/zh-tw/%E8%92%99%E7%89%B9%E5%8D%A1%E6%B4%9B%E6%A0%91%E6%90%9C%E7%B4%A2)）
</br>
#### 選擇（selection）
此階段要選擇潛在報酬率最高的子節點，這個問題同時也是大名鼎鼎的多臂老虎機問題 (Multi-armed bandit problem)[[ref]](https://en.wikipedia.org/wiki/Multi-armed_bandit)，此問題簡單來講就是要選擇最小損失的策略，假設 $u^{*}$ 是理論最佳分數，而 $u^{+}$ 是實際得分，我們要做的事情是優化策略，盡可能使 $|u^{*} - u^{+}|$ 最小化[[ref]](http://pasky.or.cz/go/prace.pdf)。這個問題有多個不同的可行解法，這裡我們選用上信賴區間算法（UCB），UCB 公式分成兩個部份，一個是平均收益，另一個是平均收益的誤差，可以用數學化的方式描述，區分為平均收益項和平均收益的變異數平方項，兩者相加就是最大的潛在收益，公式如下
$$
\begin{split}
\
\\ Upper\ Value = Avg(N(a))\ +\ C_{param} *\ \sqrt{Var(N(a))}
\\
\end{split}
$$
根據採用的演算法不同，變異數計算會有不同的變體。而 MCTS 提出的同一年，就有人嘗試將 UCB1 演算法套用在樹搜索上[[ref]](https://link.springer.com/chapter/10.1007/11871842_29)，UCB1 是一個非常簡單的演算法，它不需要真的計算變異數，而是直接用模擬數量間的比例取代之，神奇的是，雖然簡單但它的預測效果相當不錯，實際偏差不會太大，唯一的限制是，它假設每次收益介於零到一之間。此公式這是我們現代常見的 UCT 公式。
$$
\begin{split}
\
\\ UCT(a) = \frac{W(a)}{N(a)} + C_{param} \sqrt{\frac{\Sigma{N(b)}}{N(a)+1}}
\\
\end{split}
$$
* $W(a)$：節點 $a$ 累積的勝利次數
* $N(a)$：節點 $a$ 累積的搜索次數
* $\Sigma{N(b)}$：所有子節點的總搜索次數
</br>
UCT 也可以結合 heuristic ，將額外的圍棋知識當作加分項目，例如我們認為叫吃（圍棋術語）很重要，可以直接將叫吃的得分寫在後方，增加此項被選中的機率
$$
\begin{split}
\
\\ UCT(a) = \frac{W(a)}{N(a)} + C_{param} \sqrt{\frac{\Sigma{N(b)}}{N(a)+1}}\ +\ Bouns_{cap}
\\
\end{split}
$$
* $Bouns_{cap}$：叫吃的額外得分
</br>
我們通過 UCT 不斷選擇最佳節點，直到葉節點為止。
#### 擴展（Expansion）
擴展所有合法手，此階段並不一定要執行，我們可以等到累積一定數量的訪問數，例如累積到 40 次，再展開此節點，這是因為隨機模擬的次數如果太少，選擇階段可能會不穩定，導致展開不好的節點，使展開的樹形有偏差。另外需要累積的訪問數也和 MCTS 的種類有關，例如 Pachi 使用 8 次，這是因為它混合 RAVE 演算法[[ref]](https://github.com/kobanium/Ray/issues/148)，而 Sayuri 沒有使用特別的處裡，要選擇較大數值，為 40 次。
#### 模擬（Simulation）
此階段要決定此節點誰勝誰負，我們通過隨機模擬的方式，隨機落子直到終盤，根據最終結果決定誰勝誰負。模擬為 MCTS 最重要的部份，模擬的質量會大幅影響 MCTS 的強度，所謂的隨機落子並非真的隨機，基本上圍棋有兩種模擬策略[[ref]](http://pasky.or.cz/go/prace.pdf)
1. 基於規則，利用圍棋的基本知識，選出候選手，由後選手中隨機挑下一手。
2. 基於機率，利用機器學習算法，計算每一手的機率，根據計算的機率挑選。偶後會提到實做方法。
雖然此階段分數給的過於直接，看起來很不准，但一般而言，一次完整的 MCTS 要經過上萬次的模擬 ，多次累積下來，平均分數會逐漸收斂，趨於平穩。
#### 更新（Backpropagation）
延當初選擇的路徑，依序對節點更新，一般會更新的有節點累積的勝場數和模擬次數（即訪問次數）。
### 選擇最佳子節點
通常一輪正常的搜索要經過上萬次的模擬，完成後要選擇最佳節點，通常會直接選擇訪問次數最多的節點當作最佳手，完全不使用勝率和目差等額外資訊，因為單次模擬得到的資訊往往會有偏差，如果子節點模擬次數不夠，那勝率資訊明顯是不穩定的，即使給予大量的總模擬量，仍會有某些子節點模擬量不足，另外就算每個節點都給足夠的模擬量，結果仍是偏差的，因為隨機模擬在盤面還很空曠的時候，不管怎樣模擬，勝率都差不多，分辨不出子節點的好壞。因此考慮這些資訊會使得結果有很大偏差。
### Progressive Widening
由於大部分的子節點很難在短時間內用通過 UCT 比較出好壞，那大部分的計算資源可能會浪費在較不好的節點，有個方法可以避免此情況，首先通過一些算法找到不同著手的好壞的先後次序，稱為 Move Ordering，再根據 Move Ordering 逐步展開和搜索次數決定允許搜尋的範圍，例如初始只能搜索 Move Ordering 最好的節點，達到 40 訪問數後，變成搜索 Move Ordering 最好的前兩個節點，達到 300 訪問數後，變成前三個節點。
其允許展開的訪問數閾值為下，當訪問數 $v$ 大於 $t_{n}$，代表允許搜尋最多 n 個子節點。
$$
\begin{split}
\
\\ t_{n+1} = t_n + 40 \times 1.4 n,\ t_0 = 0
\\
\end{split}
$$
</br>
### 和 Alpha-Beta Search 比較
GCP（Leela Zero 作者）曾經說過，在西洋棋上 MCTS 和 Alpha-Beta Search 最後展開的樹形類似，兩者間沒有明顯差距[[ref]](https://www.chessprogramming.org/UCT)，在西洋棋上 MCTS 並沒有佔優勢。這是因為西洋棋相對圍棋有個特點，它的行棋策略對於電腦來說較為簡單，在任意盤面中，電腦可以通過快速且有策略的行棋，找到一個相對穩定且可準確估值的盤面，此過程類似於 MCTS 的模擬（但不需要下到終局）。而圍棋則不同，它長久以來沒有穩定的估值方法，由於 Alpha-Beta Search 有容易裁剪分數較差節點的特性，它容易在圍棋中把好的節點裁剪，因此 Alpha-Beta Search 不適合應用在圍棋上的。而 MCTS 使用模擬數值不斷累積的方式，動態調整每個節點的重要程度，這是我認為 MCTS 在圍棋上明顯優於 Alpha-Beta Search 的主要原因。
</br>
## Minorization-Maximization 演算法
延伸閱讀：[Computing Elo Ratings of Move Patterns in the Game of Go](https://www.remi-coulom.fr/Amsterdam2007/)、[Ray 引擎實做的論文](https://uec.repo.nii.ac.jp/?action=pages_view_main&active_action=repository_view_main_item_detail&item_id=1980&item_no=1&page_id=13&block_id=21)
</br>
長久以來，電腦圍棋並沒有一個有效預測當前局面好壞的演算法，這是由於局面情勢時常變化，厚勢變孤棋，要子變棄子，別說電腦，甚至有時連職業高手也會錯判形式。但神奇的是，預測下一步卻比較容易實做，Minorization-Maximization（後簡稱 MM）演算法便是其中一個重要方法，在 2007 年時，由 Rémi Coulom 發表[[ref]](https://www.remi-coulom.fr/Amsterdam2007/)，當時實做的準度就達到 34% ，之後便廣泛被使用，此情況直到後來的深度學習才被終結[[ref]](https://arxiv.org/abs/1412.3409)。MM 是以 pattern 為基礎，計算每個 pattern 的 elo 分數，elo 分數我們可以簡單理解為強度，elo 分數越高代表此 pattern 越好，之後只要比較每手棋所有 pattern 的 elo 分數總和，就可以知道那一手棋是比較好的。
### Pattern 的資料結構
Pattern 是一個紀錄 NxN (N 為奇數)大小的棋盤區域的資料結構。以下圖片紅線框起來的區域為 3x3 大小的 Pattern。
<div id="patterns" align="center">
<img src="https://i.imgur.com/dMGvgPa.png" alt="drawing" width="500"/>
</div>
<br>
（[圖源](https://hdl.handle.net/11296/5h8qtv)）
</br>
除了 NxN 的正方形區域以外，還有延伸的鑽石形模組，它包含更大的區域空間，圖片上的數字代表模組大小。例如 N=4 時，則 3 和 4 的位置為模組大小。
<div id="dimand-patterns" align="center">
<img src="https://i.imgur.com/c0EmZFp.png" alt="drawing" width="500"/>
</div>
<br>
（[圖源](https://hdl.handle.net/11296/mty58v)）
</br>
### Bradley-Terry 模型
我們用 Bradley-Terry （後簡稱 BT）模型計算不同 pattern 間的獲勝機率，以 $\gamma$ 表示 elo，而 pattern $i$ 對 pattern $j$ 的勝率如下。
$$
\begin{split}
\
\\ P(i \mspace{5mu} beat \mspace{5mu} j) = \frac{\gamma_{i}}{\gamma_{i} + \gamma_{j}}
\\
\end{split}
$$
</br>
如果是一群 $\gamma$ 之間的關係，不同的 $\gamma$ 可以用相乘連接成一體，例如 1-2 對於 2-3-5 以及 1-3-4-5 的勝率為
$$
\begin{split}
\
\\ P(...) = \frac{\gamma_{1}\gamma_{2}}{\gamma_{1}\gamma_{2} + \gamma_{2}\gamma_{3}\gamma_{5} + \gamma_{1}\gamma_{3}\gamma_{4}\gamma_{5}}
\\
\end{split}
$$
</br>
根據 BT 模型，我們可以簡單的將一群 $\gamma$ 關係的整理為下
$$
\begin{split}
\
\\ P(R_{j}) = \frac{A_{ij}\gamma_{i} + B_{ij}}{C_{ij}\gamma_{i} + D_{ij}}
\\
\end{split}
$$
其中
1. $R_j$：第 j 群 $\gamma$ 間的勝率關係
2. $\gamma_i$： i 在第 j 群 $\gamma$ 間的勝率
3. $A_{ij}$ 、$C_{ij}$：和 $\gamma_i$ 有關的獨立係數
4. $B_{ij}$ 、$D_{ij}$：和 $\gamma_i$ 無關的獨立係數
</br>
### 更新方法
根據原論文的推導，最終 $\gamma_i$ 的最優解為下。中間的推導，有興趣的同學可以到延伸閱中看 [Ray 引擎實做的論文](https://uec.repo.nii.ac.jp/?action=pages_view_main&active_action=repository_view_main_item_detail&item_id=1980&item_no=1&page_id=13&block_id=21)，此作者的推導比原論文清晰。
$$
\begin{split}
\
\\ \gamma_i \Leftarrow \frac{W_i}{\sum^{N}_{j=1} \frac{C_{ij}}{C_{ij}\gamma_{i} + D_{ij}} }
\\
\end{split}
$$
其中可以將 $E_j 取代 C_{ij}\gamma_{i} + D_{ij}$
1. $W_i$： $\gamma_i$ 的勝利次數
2. $E_{j}$：第 $j$ 群所有的 $\gamma$
<br>
但由於直接使用最佳解更新，會導致其無法逼近，因此要對它作正規化，新的公式為
$$
\begin{split}
\
\\ \gamma_i \Leftarrow \frac{W_i + 1}{ \sum^{N}_{j=1} \frac{C_{ij}}{E_j} + \frac{2}{1+\gamma_i}}
\\
\end{split}
$$
<br>
### 結合其它特徵訓練
不只是 pattern ，也可以嘗試加入一些圍棋的知識 ，像是下在第幾線、和前一手棋距離多遠或打吃的種類等等，這些可以有效增加次一手資訊。下圖為 Sayuri 實做的 MM 訓練結果，紅色是是分數最高的點，黃色次之，綠色最低，可以看見大部分預測的點都在符合棋理位置上。
<div id="mm-predict" align="center">
<img src="https://i.imgur.com/DmOGSgC.png" alt="drawing" width="600"/>
</div>
<br>
### 應用於 MCTS
用 MM 演算法可以預測下一手位置，所以也可以應用於蒙地卡羅樹搜索的隨機模擬階段。但完整的 MM pattern 太大，隨機模擬又要求速度，因此通常只會訓練 3x3 的 pattern 外加常用的圍棋特徵作為資料集。模擬的方法為，計算每一手 gamma 分數，之後依據 gamma 值轉換成機率分佈。使用 MM 做模擬，其估值的準確度遠勝於完全隨機模擬。
我們也可以將 MM 的分數放置在 UCT 的 heuristic 項，確保搜索時預測分數最佳的節點能最先被搜索，例如以下是 Ray 的 heuristic 項實做範例[[ref]](https://github.com/kobanium/Ray)
$$
\begin{split}
\
\\ UCT(a) = \frac{W(a)}{N(a)} + C_{param} \sqrt{\frac{\Sigma{N(a)}}{N(a)+1}}\ +\ 0.35\ R(a)\ \sqrt{\frac{1000}{1000+\Sigma{N(b)}}}
\\
\end{split}
$$
* $W(a)$：節點 $a$ 累積的勝利次數
* $N(a)$：節點 $a$ 累積的搜索次數
* $\Sigma{N(b)}$：所有子節點的總搜索次數
* $R(a)$：節點 $a$ 之 MM 的預測分數
</br>
## 深度學習於圍棋的應用
延伸閱讀：[AlphaGo 論文](https://www.nature.com/articles/nature16961)
前面提到了 MM 學習法，藉由預測下一手的位置，可以大幅度提高蒙地卡羅樹搜索質量，但可惜的是 MM 學習法雖然準確性看起來不錯，但實際上它對於的圍棋基本概念不太敏感，像是打劫、叫吃或死活等等，因此容易在複雜盤面時失誤。但自 2014 後，深度捲積網路[[ref]](https://arxiv.org/abs/1412.3409)開始在此項任務上超越 MM 學習法的精準度，甚至面對複雜盤面也能有不錯的預測準確度。
### 策略（policy）網路
捲積神經網路用於圍棋最早可追溯到 1993 年[[ref]](https://proceedings.neurips.cc/paper/1993/hash/e2a2dcc36a08a345332c751b2f2e476c-Abstract.html)，但由於早年間的硬體和理論都不完備，神經網路沒有取得很好的效果，直到約 2012 年左右，AlexNet 在 ImageNet 上大放異彩[[ref]](https://zh.wikipedia.org/zh-tw/AlexNet)，現代的深度神經網路才開使用於圍棋上。
DeepMind 在 2015 年的論文顯示出，三層捲基層（128 filters）就可以明顯好過 MM 學習法，當疊加到 12 層時，可以達到 55％ 的驚人準確度，此時單就策略網路（沒有 MCTS）就有低段水準 [[ref]](https://arxiv.org/abs/1412.6564)。精準度相比 MM 最好的結果約上升 15％，看起來沒有很多，但實際上策略網路不僅是準度的提昇，預測的平滑度也大幅度提昇，此平滑度是指在不同盤面的狀態下，預測準度是較平均的，不會出現在布局階段預測準度很好，但中盤戰鬥的預測準度卻很糟糕等現象，但 MM 相比下，平滑度就糟糕很多。神經網路經過多年的優化，截止到 2022 的 10 月底前，當前最強的開源程式 Kata Go 單策略網路就能在 KGS 達到 8D 水準（帳號名稱 NeuralZ06）。
以下為 Sayuri 實做的策略網路和 MM 方法，下圖為兩種方法的比較，換黑棋下，左圖為策略網路預測結果，右圖是 MM 預測結果，要注意的是，兩個方法的運作原理不同，所以兩圖標注的顏色不能直接比較，但相同的是顏色越鮮艷代表預測的分數越高（紅>黃>綠>籃紫），可以看見右上的黑棋已經死了，但 MM 大部分的預測點都在右上角，相比下策略網路準確的將焦點放在右下和左下的要點上。看起來 MM 好像很糟糕，但事實上大部盤面，其策略網路和 MM 的預測非常相似，但一旦發生如下圖等較複雜的情況，MM 就容易失誤。
<div>
<div id="policy-predict-cmp" align="center">
<img src="https://i.imgur.com/72zn8q7.png" alt="drawing" width="350"/>
<img src="https://i.imgur.com/7CETVXW.png" alt="drawing" width="350"/>
</div>
</br>
### 價值（value）網路
根據黃士傑在 2022 年 TCGA 的直播所述，此方法是他的同事提出的，起初，黃士傑還不相信價值網路可以超過傳統方法（蒙地卡羅方法），但實做後效果卻驚為天人。價值網路和傳統方法的準確度以現代開源實做來看（Pachi vs Leela），引入價值網路的確對 MCTS 有顯著的提昇，因為價值網路比多次隨機模擬得到的分數可信度還高。
一般而言價值網路的輸出介於 -1 到 1 之間，我們會重新壓縮到 0 到 1 之間以符合 UCB1 的假設條件，之後會將此值稱為預期分數或是勝率
### 應用於 MCTS
主要改進點為取消模擬階段，改用神經網路估値取代隨機模擬，且選點公式改成 PUCT[[ref]](https://www.chessprogramming.org/Christopher_D._Rosin#PUCT)，其中 $P$ 為次一手的機率（策略分數）。
$$
\begin{split}
\
\\ PUCT(a) = \frac{W(a)}{N(a)} + C_{param}P(a)\frac{\sqrt{\Sigma{N(b)}}}{N(a)+1}
\\
\end{split}
$$
* $W(a)$：節點 $a$ 累積的預期分數
* $N(a)$：節點 $a$ 累積的搜索次數
* $\Sigma{N(b)}$：所有子節點的總搜索次數
* $P(a)$：節點 $a$ 的策略分數
</br>
我們可以將次一手的機率當作一種剪枝，因為在 PUCT 公式下，大部分節點都是沒辦法展開的，這極大的增加搜索效率，事實上，只需要將 MCTS 的樹根轉換成策略網路加 PUCT，剩餘的子樹仍使用傳統方法，其強度能增加倆、三子以上，可以說主要強度的提升都拜此所賜。
前面說過模擬要累積一定次數才展開節點，而基於價值網路的方法則不需要，換個說法，價值網路相當於做多次的隨機模擬，它得到的分數已經是穩定且可信的，而且同個盤面再重新估値一次，得到的值還是一樣，做第二次沒有意義，因此只須累積一次即可展開節點。
### First Play Urgency (FPU)
對於所有葉節點，也就是未搜尋過的節點，這些節點本身沒有價值分數，我們應該給予一個虛擬的價值數值，以穩定 MCTS 的搜索，此分數稱為 $FPU$ 。由於價值網路的估計值有一定的準確度，我們可以簡單的認為其價值分數和父節點從網路得到的價值分數是一樣的，公式如下
$$
\begin{split}
\
\\ PUCT(a) = FPU + C_{param}P(a)\frac{\sqrt{\Sigma{N(b)}}}{N(a)+1}
\\
\end{split}
$$
* $FPU$：葉節點的分數，和父節點的價值分數相同
</br>
這樣比直接將未搜尋過的節點設定為 0.5（平手分數）還要合理，可以避免不好的節點太快被展開，也比設為 0（輸家分數，AlphaGo 論文實做）效果還要好。我們也可以對 $FPU$ 加上懲罰項，例如被展開節點的策略分數總和，這可以避免低策略的葉節點太快被展開
$$
\begin{split}
\
\\ FPU = V_{parent} - C_{reduction}\Sigma{P(b)}(N(b) != 0)
\\
\end{split}
$$
* $\Sigma{P(b)}(N(b) != 0)$：被展開節點的策略分數總和
* $C_{reduction}$：懲罰係數
</br>
### 最佳的 $C_{puct}$ 的數值
一般 $C_{puct}$ 的值會是固定的，但 Leela Zero 團隊的 Henrik Forstén 發現最佳的 $C_{puct}$ 的值會隨著模擬總數增加而上升，例如模擬總數為 100 時 $C_{puct}$ 為 0.5 為最佳值，而 1600 時最佳值為 0.8 。經過調整和測試，最佳值會以 $O(sqrt(log(n)))$ 增加，因此他修改公式為 [[ref]](https://github.com/leela-zero/leela-zero/pull/2072)
$$
\begin{split}
\
\\ C_{puct} = C_{init} + sqrt(log(C_{logpuct} * N + C_{logconst}))
\\
\end{split}
$$
* $N$：此節點的總模擬次數
* $C_{init}$：第一個參數，Leela Zero 使用 0.5
* $C_{logpuct}$：第二個參數，Leela Zero 使用 0.015
* $C_{logconst}$：第三個參數，Leela Zero 使用 1.7
</br>
Deep Mind 也發現相同的現象，並在 AlphaZero 增加 $O(log(n))$ 獎勵項，他們修改公式為[[ref]](https://www.science.org/doi/10.1126/science.aar6404)
$$
\begin{split}
\
\\ C_{puct} = C_{init} + C_{factor} * log((N + 1 + C_{base})/C_{base})
\\
\end{split}
$$
* $N$：此節點的總模擬次數
* $C_{init}$：第一個參數，AlphaZero 使用 1.25
* $C_{factor}$：第二個參數，AlphaZero 使用 1
* $C_{logconst}$：第三個參數，AlphaZero 使用 19652
</br>
雖然兩個方法差了一個 $sqrt$ ，但在短期內兩者提昇的幅度相似，長期而言 AlphaZero 的 $C_{puct}$ 數值會提昇比較有效率，因此 Sayuri 在實做中採用 AlphaZero 的方法。
### Lower Confidence Bound (LCB)
AlphaZero 會選擇則訪問數最大的子節點為次一手，Forstén 在 Leela Zero 測試使用 LCB 演算法取代原本 AlphaZero 的演算法，並取得不錯的成效 [[ref]](https://github.com/leela-zero/leela-zero/pull/2290)。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$ 的訪問次數。
如果直接計算整棵子樹的預期分數的變異數，整個過程會相當消耗時間，我們可以使用一個可以一筆一筆資料迭代的演算法取代原本直接計算整棵樹的方法，例如 Leela Zero 和 Sayuri 使用的 Welford's online algorithm 或 KataGo 使用的 Naive algorithm，這裡介紹 Naive algorithm ，由於它的計算較簡單，且 KataGo 作者表示它的精度在 MCTS 使用上已經足夠，不需要使用精度更高的 Welford's online algorithm [[ref]](https://github.com/lightvector/KataGo/issues/585#issuecomment-1200160698)。
其每次迭代時，保存當前節點 $a$ 預期分數和預期分數平方的總和。
$$
\begin{split}
\
\\ Sum(a) & \leftarrow Sum(a) + q
\\ SumSq(a) & \leftarrow SumSq(a) + q^{2}
\\
\end{split}
$$
</br>
當要取節點 $a$ 的變異數時，則計算如下 [[ref]](https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Welford's_online_algorithm)
$$
\begin{split}
\
\\ Var(a) = (SumSq(a) − (Sum(a) × Sum(a)) / N(a)) / (N(a) − 1)
\\
\end{split}
$$
</br>
### Dynamic $C_{puct}$
此方法最先由 KataGo 提出，KataGo 用網路預測了當前的不確定性，如果當前節點的不確定性越大則 $C_{puct}$ 應該越大，深挖此節點直到直到不確定性下降，反之則應該減小 $C_{puct}$ 的值。但KataGo 的實際實做較為複雜，因此 Sayuri 的實做參考 [Aoba Zero](https://github.com/kobanium/aobazero)，前面講了 LCB 計算的過程中，有計算 $Var(a)$，此為預期分數的變異數，也就是預期分數的不確定性，可以用此值調整 $C_{puct}$ 範圍，其演算法為下。此實做在較低的模擬量時，可以有效提昇強度。
$$
\begin{split}
\
\\ k &= C_{factor} * (Var(a)/N(a))
\\ k &= max(k_{lower}, k)
\\ k &= min(k_{upper}, k)
\\ \alpha &= 1 / (1 + \sqrt{(N(a)/k_{base})})
\\ k &= \alpha * k + (1 - \alpha ) * 1
\\ C_{dynamic} &= k * C_{puct}
\\
\end{split}
$$
* $N$：此節點的總模擬次數
* $k_{factor}$：第一個參數，Sayuri 使用 4
* $k_{base}$： 第一個參數，Sayuri 使用 10000
* $k_{lower}$：Dynamic k 的下限，Sayuri 使用 0.5
* $k_{upper}$：Dynamic k 的上限，Sayuri 使用 1.4
</br>
### 後言
事實上 AlphaGo 是基於上個時代最頂尖算法的改良，它不像 MM 和 MCTS 一樣是完全顛覆上個世代算法，我個人認為，MM 和 MCTS 等技術奠定現代電腦圍棋的雛型，而 AlphaGo 將此模型推向下個階段。
</br>
## 惰性載入（Lazy Loading）
由於 19 路的訓練資料往往比較龐大，一次把所有訓練資料載入可能需要數百到上千 GB 的記憶體，顯然不存在這樣大記憶體的普通機器，因此我們採用惰性載入的策略解決這個問題，其核心思維是，當需要資料時，才從硬碟載入記憶體。我們分成下面三部份討論。
* 資料切割
* 打亂 buffer
* 下採樣（down-sample）
### 資料切割
由於 GPU 需要等待 CPU 準備好資料後，它才能開始執行，載入資料的延遲時間越短越好，因此最好將一整個資料切割成多份放在硬碟裡，切割時可以盡量細緻一點，如每五十盤遊戲切成一份，如此可以提升載入性能，減少延遲時間。
### 打亂 buffer
上述切割資料並仔入的作法有一個副作用，如果我是一個接一個載資料並使用，不同的兩份資料將難以打亂，這會使資料擴散度下降，舉個例子，假設我們有 A、B、C 三份資料，如果我們依序載入並使用，那 A 的資料永遠無法在 B 之後出現。這裡有一個間單解決方法，我們設計一個 buffer ，當 buffer 剩餘量第於某個值，則重新載入新資料再打亂之，用同個例子，假設 A、B、C 三份資料分別都有 1000 資料，它的處理過成為
1. 設定 buffer 的大小為 1000，當 buffer 內的剩餘資料少於 500 時，重新裝填
2. buffer 載入 A 的 1000 份資料，並打亂之
3. buffer 使用 500 份，此時 buffer 剩餘 500，因此載入 B 內的 500 資料，並打亂之
4. 重複步驟三的邏輯，直到訓練結束
在整過過程中，A 的資料有機會出現在 B 之後，增加資料擴散性質。甚至在設計良好的情況下，它的延遲時間不會有明顯上升。
### 下採樣（down-sample）
這個方法出自於 Leela Zero, 在載入資料時，有一定的機率丟棄，如此可以有效的增加資料擴散度，和打亂 buffer 有異曲同工之妙，在我的經驗中使用下採樣會比直接增加 buffer 大小效果還好。Sayuri 的下採樣率為 1/16，也就是每份資料有 15/16 的機率被丟棄，換句話說，載入 A 時，平均會有 937.5 份資料被丟棄。此方法唯一的缺點是，大的下採樣率會使延遲明顯提昇。
### Lazy Loading 之實做
Sayuri 的實作為，當 buffer 內的資料被拿走一個時，就馬上填充一個並打亂之，為了增加打亂的效率，使用了 Fisher-Yates shuffle 演算法。你可以到這裡看 [Lazy Loader](https://github.com/CGLemon/LazyLoader) 的實際實作。
</br>
## 平行化蒙地卡羅樹搜索（Parallel MCTS）
蒙地卡羅樹搜索的過程分為四個步驟，分別為
* 選擇（selection）
* 擴展（Expansion）
* 模擬（Simulation）
* 更新（Backpropagation）
（事實上在 AlphaGo 裡擴展和模擬合併成 evaluation step，但為了方便討論，擴展和模擬分開）
我們知道多個執行緒同時搜尋同一棵樹，勢必要上鎖，最簡單的方式就是全部的步驟都上鎖，但實際實作中上鎖的範圍和方式取決於平行化的策略，有些平行化策略甚至不需要上鎖，根據電腦對局理論[[ref]](https://www.books.com.tw/products/0010757091)這本書，蒙地卡羅樹的平行方法主要分為四種
* 葉節點平行化
* 根節點平行化
* 樹同步平行化
* 節點同步平行化
### 葉節點平行化
這是一個以生產者消費者[[ref]](https://zh.wikipedia.org/zh-tw/%E7%94%9F%E4%BA%A7%E8%80%85%E6%B6%88%E8%B4%B9%E8%80%85%E9%97%AE%E9%A2%98)為模型製作出來的平行方法，生產者用一個執行緒完成選擇、擴展和更新步驟，而多個執行緒完成模擬步驟，這是一個非常直觀且有效的平行方法，過程中除了緩衝區以外，剩餘部份都不要上鎖，具體實作方法可以看由 pachi 作者實作的 michi[[ref]](https://github.com/pasky/michi)。此方法的平行效率會隨執行緒數目上升而下降。
### 根節點平行化
搜索前在根節點選出幾個候選步，之後分別對每個候選步分別平行搜索，這個方法最大的好處是不需要上鎖，實作簡單，但壞處是容易浪費計算資源計算錯誤的候選步。台灣一些比較間單的圍棋引擎，就是採用此種方法。
### 樹同步平行化
在更新階段鎖住整顆樹樹，由於加速效果不佳，這個方法基本沒人使用。
### 節點同步平行化
它的核心思維是每個節點都用自己專屬的瑣，這個方法只有在兩以上個執行緒同時在同一個節點上時，才會使執行緒等待，因此在節點分支數目夠多的情況下，它的加速效果可以接近線性，但缺點也很明顯，它實作上會比較麻煩，設計不良容易產生 dead lock 問題。現代多數圍棋引擎多使用此方法的變體，如 Leela Zero 和 Kata Go 均是，Sayuri 也採用此方法。
</br>
接下來要來簡單討論節點同步平行化方法的實作方法之一，為了簡化問題，這裡的描述和 Sayuri 的實作會有些許不同。我們先定義每個節點的資料，部份資料屬於原子類別[[ref]](https://en.cppreference.com/w/cpp/atomic/atomic)
* $W(a)$：節點 $a$ 累積的預期分數，它是一個原子類別
* $N(a)$：節點 $a$ 累積的搜索次數，它是一個原子類別
* $T(a)$：節點 $a$ 以下正在搜索的執行緒數目，它是一個原子類別
* $S(a)$：紀錄節點 $a$ 是否是葉節點，它是一個原子類別
* $P(a)$：節點 $a$ 的策略分數
* $\text{mutex}(a)$：節點 $a$ 的瑣
</br>
### 選擇
用 PUCT 演算法找到最大分數的子節點，持續往下搜索直到葉節點，由於此階段拿到的資料都是原子類別，所以這裡不需要上鎖。其中 $C_{param}$ 、$VirtualLoss$ 為超參數，要自己設定。$VirtualLoss$ 是一個懲罰項，越多執行緒在同一個子樹下，其懲罰數值會越大，目的是盡量避免多個執行緒同時搜尋同一個子樹（一般而言 $VirtualLoss$ 會懲罰搜索次數，或累積的預期分數）。
$$
\begin{split}
\
\\ PUCT(a) = \frac{W(a)}{N(a)} + C_{param}P(a)\frac{\sqrt{\Sigma{N(b)}}}{N(a)+1}\ -\ T(a) * \text{VirtualLoss}
\\
\end{split}
$$
</br>
還有，路徑上選擇到的每一個節點其執行緒數目 $T(c)$ 都要加一，其中 $c$ 是路徑上的節點。
### 擴展
擴展前要對 $\text{mutex}(a)$ 上鎖，如果兩個以上執行緒在這個階段爭奪同一個瑣，爭奪成功的執行緒擴展葉節點。爭奪失敗的執行緒需要等待到 $mutex(a)$ 釋放，之後檢查 $S(a)$ 的裝態，正常情況 $S(a)$ 將會是非葉點狀態，爭奪失敗的執行緒會退回選擇階段。
### 模擬
計算網路的輸出得到預期分數和策略分數，將策略分數分配給子節點，並將 $S(a)$ 轉為非葉點狀態，最後釋放瑣 $\text{mutex}(a)$。
### 更新
延路逕上更新價值分數，路徑上每個節點之 $W(c)$ 加上價值分數，$N(c)$ 加一， $T(c)$ 減一。由於更新的資料都是原子類別，所以不需要上鎖。
</br>
此種平行化方式有個缺點，由於只有擴展階段時有上鎖，剩餘階段可能相互錯位或是同時執行，會使選擇階段時有些許錯誤，或是和循序執行的最佳結果不同，但整體而言只要模擬次數夠多並不影響最終結果。
</br>
## Residual Networks
延伸閱讀：[Residual Networks 論文](https://arxiv.org/abs/1512.03385)
理論而言，越深的網路可以有更強的擬合能力和更好的準確性，但實際上，直接疊加網路並不能有更好的結果，反而可能有降解（degradation）現象，降解（degradation) 代表網路無法簡單的被訓練，Resnet 作者認為這是由於深度過深，梯度無法順利傳遞下去導致的梯度消失/爆炸。下圖顯示 56 層的捲積層不論在訓練時或推論時，其準確度都比 34 層的表現更差。
</br>
為了解決此問題，作者提出 shortcut 結構，簡單粗暴的將最初的輸入加到最後的輸出中，此結構能夠讓梯度直接穿透多層網路，很好的避免了梯度消失/爆炸的問題，此種應用 shortcut 結構堆疊的網路稱為 Residual Networks（簡稱 Resnet）。Resnet 最大的好處和突破為，它可堆疊的層數幾乎沒有上限，基本上越深準度會越好，甚至在原論文中使用超過 1000 層的網路，也不會發生退化問題。通常我們稱一個 shortcut 結構為一個 block。
</br>
雖然在原本論文中，作者實作了多種不同變體的 block，但一般應用在棋盤遊戲的 Resnet 比較簡單，每層使用的 kernel size 固定為 3，每一個 block 使用兩個捲積層和兩個正規層，不使用 Max Pooling。一般的殘差結構程式碼如下。
```python=
class ConvBlock(nn.Module):
def __init__(self, channels, relu):
super().__init__()
self.conv = nn.Conv2d(channels, channels, kernel_size=3, padding=1)
self.bn = nn.BatchNorm2d(channels)
def forward(self, x):
x = self.conv(x)
x = self.bn(x)
return F.relu(x, inplace=True) if self.relu else x
class ResBlock(nn.Module):
def __init__(self, channels):
super().__init__()
self.conv1 = ConvBlock(channels, True)
self.conv2 = ConvBlock(channels, False)
def forward(self, x):
identity = x
out = self.conv1(x)
out = self.conv2(out)
out = out + identity
return F.relu(out, inplace=True)
```
</br></br>
## Squeeze-and-Excitation Networks
延伸閱讀：[Squeeze-and-Excitation Networks 論文](https://arxiv.org/abs/1709.01507)
近年來由於 Transformer 在各種任務中獲得巨大的成功，自注意力結構引起了廣泛的討論。事實上，Squeeze-and-Excitation 的結構（簡稱 SE）也可以看成一種自注意的結構，它使用 global pooling 的方式，提取每個 channel 的特徵，通過兩個全連接層和 sigmoid 後，再對應每個 channel 相乘於原本的輸出。我們可以這樣理解 SE 結構，此結構能夠讓網路自己決定哪個輸出的 channel 比較重要，比較重要的輸出可以獲得較大的加分項。
</br>
分別在 2018 年後 2019 ，Leela Chess Zero 和 Mini Go 都嘗試加入 SE 結構且都獲得不錯的成果[[ref]](https://github.com/tensorflow/minigo/issues/683)。KataGo 的作者也借用的此觀念，設計出不同於 SE 結構的網路但類似概念的結構，同樣使用 global pooling 提昇表現，初次使用在 GoNN 裡，雖然結構不同，但強度都同樣獲得相當明顯的提昇，作者也評價 global pooling 為此專案最成功的嘗試。Sayuri 依照 Leela Chess Zero 的網路結構設計使用 bias 的 SE 結構，也就是除了原本的相乘項外，額外加入 bias 項，用 pytorch 表示如下
```python=
class ConvBlock(nn.Module):
# 定義在 Residual Networks 裡
class ResBlock(nn.Module):
def __init__(self, channels):
super().__init__()
self.conv1 = ConvBlock(channels, True)
self.conv2 = ConvBlock(channels, False)
# 可以用 average pooing 或 max pooling
# 推薦使用 average pooing
self.pooling = CustomizedPooling()
assert channels%2 == 0, ''
self.squeeze = FullyConnect(channels, channels//2, True)
self.excite = FullyConnect(channels//2, 2*channels, False)
def _apply_se(self, x):
b, c, _, _ = x.size()
x = self.pooling(x)
x = self.squeeze(x)
x = self.excite(x)
# 拆分成 gammas 和 betas
# gamma 會對每個 channel 相乘
# beta 會對每個 channel 相加
gammas, betas = torch.split(x, self.channels, dim=1)
gammas = torch.reshape(gammas, (b, c, 1, 1))
betas = torch.reshape(betas, (b, c, 1, 1))
return torch.sigmoid(gammas) * x + betas
def forward(self, x):
identity = x
out = self.conv1(x)
out = self.conv2(out)
out = self._apply_se(out) + identity
return F.relu(out, inplace=True)
```
</br>
最後，雖然 SE 結構可以大幅度提昇強度，但卻會損失一定的性能，因此 KataGo 並沒有在每一層 block 加入 global pooling，如此能在保證性能的得前提下增加強度。Sayuri 也採用相同的方法。
</br>
## 輔助預測頭（Auxiliary Heads）
最早期的 AlphaGo 架構，其 Value Network 和 Policy Network 是分開的，但在新的 AlphaGo Zero 上則將兩個網路合併為一個網路，你可能會認為這樣做並不能增加精準度，反而還可能會下降，但事實上，合併後的網路其準確度有明顯的提昇，而且推論的速度會比較快（分開要跑兩次，合併後只要跑一次），相比於未合併的版本，合併版本的 Elo 分數提升超過 500 分。這個就是多任務預測，用同一個網路預測多個任務，通過不同的預測頭，網路可以同時學習到更多資訊。
在 2017 年後，各種基於多任務預測的網路相繼提出，如交大的 CGI 提出的多標籤（multi-labelled）和棋盤估計（board evaluation）的網路[[ref]](https://ndltd.ncl.edu.tw/cgi-bin/gs32/gsweb.cgi/login?o=dnclcdr&s=id=%22108NCTU5394086%22.&searchmode=basic)，一個是預測動態貼目的勝率，一個是預測地域，CGI 在蒙地卡羅樹搜索階段，並沒有用到這兩個資訊，但整體網路的強度卻提昇了，相比未使用的網路，有超過六成的勝率。Leela Chess Zero 增加預測剩餘步數的預測頭，輔助運用剩餘時間。KataGo 則進一步採用 self-play 階段才能得到的資訊用於訓練中，像是 MCTS 的 root value 等等。結論是同時給予網路多個訓練資訊，基本有利無弊。
由於受到 KataGo 啟發，Sayuri 也採用多任務預測的網路，除了基本的策略（policy）網路和價值（value）頭，主要還有
* 輔助策略（auxiliary policy）
* 地域（ownership）
* 領先目數（score lead）
</br>
自 v0.6 版本後，又額外新增
* 短期的價值/目數（short-term value/score）
* 短期的價值/目數誤差（short-term value/score error）
* 輔助軟性策略（auxiliary soft policy）
* 樂觀策略（optimistic policy）
</br>
### 1. 輔助策略（auxiliary policy）
此方法首先由 facebook 的研究提出[[ref]](https://arxiv.org/abs/1511.06410)，輔助策略為一種長期策略，此頭為預測敵方下一手的位置，有句棋諺為，「敵之要點即我之要點」，加入長期策略有助於讓主策略頭更容易注意到重要的位置。
### 2. 地域（ownership）
最早由 [jmgilmer/GoCNN](https://github.com/jmgilmer/GoCNN) 專案提出，可以預測棋盤每一點是屬於黑棋或是白棋。下圖是 Sayuri 使用 ownership 預測地域的示意圖。通常，地域的預測難度是比較低的，因此它可以在訓練早期給予整個網路大量的梯度，加速訓練過程和強度，不論是監督學習或是強化學習都是如此[[ref]](https://arxiv.org/abs/1902.10565)。另外地域也能輔助一些其它判斷，例如當地域尚未明確時，可以在自對中禁止虛手，避免棋局過早結束。
<div id="pass-alive-02" align="center">
<img src="https://i.imgur.com/aSVwDv6.png" alt="drawing" width="600"/>
</div>
</br>
### 3. 領先目數（score lead）
最早由 KataGo 提出，領先目數為預測當前玩家可以贏多少目數。訓練時，可以用 huber loss 取代原本的 MSE loss，以避免極端值對 loss 的影響。
$$
\text{huber}(x,y, \delta) = \begin{cases}
\delta ^{2}/2 - \delta(\text{abs}(x-y)-\delta) & , \text{ if $\ \text{abs}(x-y)$ $>$ $\delta$} \\
(x-y)^{2}/2 & , \text{ O.W.}
\end{cases}
$$
</br>
訓練領先目數的預測頭，可以和預測的勝率關聯起來，因為基本上贏得目數越多，勝率也會越高，因此可以提升價值（value）頭的準確度，並且 MCTS 也會傾向下出優勢較大的棋（因為勝率較高）。
### 4. 短期的價值/目數（short-term value/score）
最早由 KataGo 提出，本質上它是預測 Temporal-Difference 數值，公式如下，其中 $k$ 值為累積的時間範圍，KataGo 在十九路上是累積未來六手棋（長期的話，則可以延伸到更多手棋），$Q(root)_{i}$ 為未來第 $i$ 手棋的 MCTS 根節點的 Q 值。
$\text{TD}_{value} = (1- \lambda) \Sigma_{k < i} \lambda^{i}Q(root)_{i}$
$\text{TD}_{score} = (1- \lambda) \Sigma_{k < i} \lambda^{i}Score(root)_{i}$
</br>
但 Sayuri 並不是直接使用蒙地卡羅的數值，而是有經過平均處理，此方法靈感來源於 [shengkelong](https://github.com/shengkelong) 的實驗，我將一定範圍內的分數做平均，例如第 $j$ 手時，則取 $j-z$ 到 $j+z$ 手所有分數的平均。這是因為 Gumbel 的模擬量較少，可能會導致分數有較大的震盪，將之平均以減少單次震盪的影響。最終 Sayuri 使用的公式為
$\text{TD}_{value} = (1- \lambda) \Sigma_{k < i} \lambda^{i}Q(avg)_{i}$
$\text{TD}_{score} = (1- \lambda) \Sigma_{k < i} \lambda^{i}Score(avg)_{i}$
### 5. 短期的價值/目數誤差（short-term value/score error）
此為預測「短期的價值/目數的網路預測和真實資料間的**平方差距**」，此預測主要得目的為知道當前狀態的不確定性，如果網路預測的誤差較大，代表網路不太確定當前狀態的好壞，反之則是網路確信當前結果。由於平方差距是一個距離概念，它沒有負值，因此 KataGo 使用 softplus 激活函數確保輸出都是正值，最後使用前面提到的 Huber loss 作為損失函數。
目前沒有實驗表明，誤差預測可以直接提昇強度，但誤差預測可用於其它啟發式搜索和訓練，例如後面要提到的樂觀策略（ Optimistic Policy）。
### 6. 輔助軟性策略（auxiliary soft policy）
最早由 [lionfenfen](https://github.com/lionffen) 於自己的獨立研究中提出，並最終實做於 KataGo ，此方法的概念很簡單，就是新增一個預測頭，並預測下一手的分佈，基本上和策略頭預測的東西一樣，唯一不一樣的是，分佈乘上 (1/T) 次方，T 為較大的溫度常數，舉個例子
原本的策略分佈看起來像是
```
60% A
36% B
3% C
1% D
<0.1% on a few other moves.
```
(1/T) 次方的策略分佈看起來像是
```
30% A
26% B
14% C
11% D
<6% on a few other moves
```
這個方法很神奇，不同網路間的輸出是相互影響的，軟性策略能讓主策略更容注意到低分佈的位置，如例子中 C 和 D 的位置，這一定程度上緩解了主策略頭太過銳利 (sharp) 的問題。
### 7. 樂觀策略（optimistic policy）
最早由 Reid McIlroy-Young, Craig Falls 等人討論，爾後被實做到 KataGo 裡，它基於 ```short-term value/score``` 和 ```short-term value/score error``` 等預測頭，其基本實做想法很簡單，它使用了 Z 分數[[ref]](https://zh.wikipedia.org/zh-tw/%E6%A8%99%E6%BA%96%E5%88%86%E6%95%B8) 的概念，計算當前價值網路輸出的誤差，一般計算的誤差有預期分數和領先目數，分別為 $Z_{value}$ 和 $Z_{score}$ ，此 $Z_{value}$ 和 $Z_{score}$ 會作為損失函數的因子。以下是普通策略頭的損失函數
$P_{loss} = \text{CrossEntropy}(\pi, \text{target})$
以下是樂觀策略損失函數
$\text{factor}=clamp(0.0, 1.0, \text{sigmoid}(Z_{value}-1.5) * 3) + \text{sigmoid}(Z_{score}-1.5) * 3))$
$P_{loss} = \text{factor} \times \text{CrossEntropy}(\pi, \text{target})$
我們可以這樣理解這損失函數，要是當前網路預測的不確定性越高，當前策略的損失值就越大。而 $Z_{value}$ 和 $Z_{score}$ 的實際算法為
$Z_{value} = (V_{\text{short}} - V_{\text{short_pred}}) / \sqrt{V_{\text{short_err_pred}} + \epsilon}$
$Z_{score} = (S_{\text{short}} - S_{\text{short_pred}}) / \sqrt{S_{\text{short_err_pred}} + \epsilon}$
$V_{\text{short}}$ 為 $\text{TD}_{value}$ 未來六手棋的情況，樂觀策略約可以提昇 35 ~ 90 Elo ，但目前我們並不清楚樂觀策略實際是如何工作的，也不清楚它在強化學習系統中會如何回饋，因此在自我對戰中並沒有使用樂觀策略。
</br>
## 通過 Mask 同時訓練不同大小盤面
延伸閱讀：[KataGo 方法：Training on Multiple Board Sizes via Masking](https://github.com/lightvector/KataGo/blob/master/docs/KataGoMethods.md)
捲積神經網路有個神奇特性，它可以自動適應不同大小的圖片，如果輸入 10x20 大小的圖片，輸出也會是 10x20，我們利用此特性，訓練時，同時訓練不同大小盤面。但有個問題，訓練時是以一個 mini-batch 為單位訓練，只能固定一個大小進行計算，為此 KataGo 提出 mask 方法解決這個問題，方法為替 mini-batch 內個每筆資料設置對應大小的 mask ，每當進行捲積運算時，就清除 mask 外部的值，如下圖，上方是沒有清除的結果，下方是有清除的結果，可以看到，如果沒有清除的話，經過兩次以上捲積運算， mask 外部的值是會影響最終捲積計算結果的。
([圖源](https://raw.githubusercontent.com/lightvector/KataGo/master/images/docs/maskconv.png))
</br>
mask 的運算用程式表示為
```python=
conv_layer = nn.Conv2d(...)
x = conv_layer(inputs)
# mask 的 channels 數只需要一個，例如 x 的大小為
# x.size = (32, 18, 19 ,19)
# 則 mask 只需要
# mask.size = (32, 1, 19 ,19)
outputs = mask * x
```
</br>
同樣會受盤面大小影響的運算有，Max Pooling, Average Pooling 和 Batch Norm 等，它們都需要借助 mask 計算正確的空間數值，例如 Average Pooling 為
```python=
class AveragePooling(nn.Module):
def __init__(self):
super().__init__()
def forward(self, x, mask):
# 假設
# x.size = (32, 18, 19 ,19)
# mask.size = (32, 1, 19 ,19)
# 計算每筆資料的空間個數
mask_sum_hw = torch.sum(mask, dim=(1,2,3))
div = torch.reshape(mask_sum_hw, (-1,1))
# 計算 average
pooled = torch.sum(x, dim=(2,3), keepdims=False) / div
return pooled
```
</br>
間單說起來這個 mask 技巧，就是將不使用的空間乘上零，大部分情況下這是正確的，但少部份情況下會不成立，例如通過 softmax 運算，我們知道 softmax 計算的是相對大小，只是將不使用的空間歸零，最後計算出來的數值也不會是零，這裡有一個常用的技巧，就是將不使用的空間加上大的負數，這樣計算的結果就會是正確的，如下所示。
```python=
CRAZY_NEG = -5000
outputs = softmax(inputs + (1 - mask) * CRAZY_NEG)
```
</br>
此技巧不只能使網路可以輸出對應不同大小棋盤的直，還能使不同大小棋盤相互學習彼此資訊，進而加速強化學習效率，但此現象需要累積一定盤數後才會發生，在訓練的早期反而會拖慢效率 [[ref]](https://arxiv.org/abs/1902.10565)。
## Batch Renormalization
延伸閱讀：[Batch Renormalization](https://arxiv.org/abs/1702.03275)
Batch Normalization 堪稱深度學習的黑魔法，它的基本概念很簡單，就是將輸出盡可能往零附近壓縮，之所以這麼做很好理解，因為大部分的激勵函數（如：sigmoid、tanh）在零附近會比較敏感，通過 Batch Norm ，不但可以加速訓練速度，也可以增加進準度，訓練時它的具體計算如下
$$
\begin{split}
\
\\ X &= Inputs
\\
\\ M &= Mean(X)
\\
\\ V &= Variance(X)
\\
\\ Outputs &= \frac{X-M}{\sqrt{V+\epsilon}}
\end{split}
$$
</br>
每次計算的 Mean 和 Variance 會累加至 Running Mean 和 Running Var， Running Mean 和 Running Var 可以視作每次 Mean 和 Variance 的平均值。
$$
\begin{split}
\
\\ Running\ Mean\ &= 0.9 \times Running\ Mean\ + 0.1 \times Mean(X)
\\
\\ Running\ Var\ &= 0.9 \times Running\ Var\ + 0.1 \times Variance(X)
\end{split}
$$
</br>
推論階段則使用 Running Mean 和 Running Var
$$
\begin{split}
\
\\ M &= Running\ Mean\
\\
\\ V &= Running\ Var\
\\
\\ Outputs &= \frac{X-M}{\sqrt{V+\epsilon}}
\end{split}
$$
</br>
這裡你可能會發現一件事，訓練時每次計算時的 Mean 和 Variance 都不一樣，如果每一次的 batch size 足夠大，那麼訓練上的結果會是穩定的，反之如果 batch size 太小（例如 32 以下），會使得 Running Mean 和 Running Var 和訓練階段計算的值相差太大，導致訓練結果崩潰。
Batch Renormalization 可以有效解決這個問題，依據論文，將 Running Mean 和 Running Var 使用到訓練階段，如此可以減少訓練階段和推論階段的差距。訓練階段的具體計算如下，$stop\_grad$ 代表截斷梯度傳送，$clip$ 代表截斷數值的上下限，以下是 Sayuri 的實作，和論文實作有些許不一樣。
$$
\begin{split}
\
\\ M &= Mean(X)
\\
\\ V &= Variance(X)
\\
\\ r &= stop\_grad(clip_{[1/r_{max}, r_{max}]}(\sqrt{\frac{V}{Running\ Var}}))
\\
\\ d &= stop\_grad(clip_{[-d_{max}, d_{max}]}(\frac{M-Running\ Mean}{\sqrt{Running\ Var}}))
\\
\\ Outputs &= \frac{X-M}{\sqrt{V+\epsilon}} \times r + d
\end{split}
$$
</br></br>
## Fixup Initialization
延伸閱讀：[Kata Go 方法：Fixup Initialization](https://github.com/lightvector/KataGo/blob/master/docs/KataGoMethods.md)
Batch Normalization 雖然可以加速訓練的速度和增加穩定度，但會引發一個直接的問題，就是訓練階段和推論階段的輸出值是不一樣的，這可能會導致在一些極端情況下，網路推論出現非預期數值，KataGo 和 Leela Chess Zero 都有出現過相關問題，其中一個解決方法是利用 Batch Renormalization，Leela Chess Zero 採用此種方法，另一個方法較為直接，就是直接移除 Batch Normalization ， KataGo 採用此種方法。
移除 Batch Normalization 方法源自於 [Fixup Initialization: Residual Learning Without Normalization](https://arxiv.org/abs/1901.09321)，本論文描述的方法只能應用在殘差網路中。雖然論文中描述的方法比較複雜，但 Kata Go 簡化了它，它的步驟為
* 移除 Batch Normalization 本身的計算
* 對每個殘差層 block 的第一個捲積權重乘上 ```1/sqrt(殘差層 block 數目)```
* 對每個殘差層 block 的第二個捲積權重乘上 ```0```
</br>
由於移除了 Batch Normalization ，所以訓練上會變得比較不穩定，要是訓練初期的學習率太大，可能會導致梯度爆炸。因此在最前面幾千個 steps 裡（只佔總訓練的一小部份），要使用較低的學習率，直到穩定梯度之後才能一步步提高學習率。
</br>
(2022-10-18)：此方案將被放棄，因為 Fixup 練出的網路強度會略弱 Batch Norm 類的方法。[[ref]](https://github.com/lightvector/KataGo/issues/689)
</br></br>
## 加速捲積運算
現代的圍棋引擎實做基本都是基於捲積神經網路，因為大部分的時間都花費在捲積運算，所以減少捲積計算的時間能直接大幅增加整體計算性能。
### Winograd 演算法
捲積網路是現代神經網路的重要成員，在網路資料上或多或少可以看到三維捲積的運作原理，它是將權重和鄰近空間區域相乘的一種算法，但在實際的硬體上這樣相乘是沒有效率的
</br>
一般三維捲積算法的過成為
1. 將三維矩陣重新排列轉換成二維
2. 將轉換的矩陣和權重做矩陣乘法，得到的值即為輸出
</br>
所以三維捲積最影響性能的部份為矩陣相乘，快速捲積類似於 Strassen 演算法，其思維是將矩陣中的乘法拆分多個加法，由於在計算機中，多個加法會快於一個乘法，藉此來達到加速的效果，至於 WinoGrad 拆解基本觀念，可以看[這裡](https://www.cnblogs.com/shine-lee/p/10906535.html)。
使用 Winograd 演算法後，過程變為
1. 將權重 W 通過計算和重新排列轉換為 U
2. 將輸入 I 通過計算和重新排列轉換為 V
3. 將 V 和 U 進行矩陣相乘（要將 V 分成 k 份和 U 相乘），輸出為 M
4. 將輸出 M 通過計算和重新排列轉換為最終輸出 O
其中步驟一是可以提前計算的，實際所需的計算為步驟二到步驟四。在 Sayuri 實做中，Winograd 計算性能相比專門加速的 cuDNN 大慨可以提昇 1.75 倍左右（較小的 batch size 情況下）。
在正常情況下 Winograd 會加速計算流程，但一些計算任務中則不一定，由於在步驟三中，要將 V 拆分成 k 個子矩陣，以 Sayuri 的實做為例，要分成 36 個小矩陣，在現代的矩陣計算庫，矩陣太小不利於優化，所以要是計算的盤面大小越小，相對的性能損耗就越多，甚至在小盤面的 CPU 計算上 Winograd 反而會慢於一般的捲積算法。
</br>
### 合併 Batch Normalization Layer
為了防止過擬合，一般而言，捲積層後都會加入 Batch Normalization，我們可以將兩者視為一個完整的部件，它總共有六層參數分別為
1. 捲積層的主權重，我們稱為 ${C_W}$
2. 捲積層的偏差權重，我們稱為 ${C_B}$
3. BN 層的平均權重，我們稱為 ${B_M}$
4. BN 層的標準差權重，我們稱為 ${B_S}$ （已經和 ${\epsilon}$ 參數合併）
5. BN 層的 Gamma 權重，我們稱為 ${B_{\gamma}}$
6. BN 層的 Beta 權重，我們稱為 ${B_{\beta}}$
而其中 Batch Normalization 層是可以被合併的，變成只有 ${C^{'}_W}$ 和 ${C^{'}_B}$ 兩個而已，轉換公式如下，須注意一下 ${C^{'}_W = C_W / B^{'}_S}$ 不是簡單的向量除法。在 Sayuri 的實做中，這樣大該可以提昇 5% 左右的性能。
$$
\begin{split}
\
\\ B^{'}_S &= B_S/B_{\gamma}
\\
\\ B^{'}_M &= B_M - B_{\beta}B^{'}_S
\\
\\ C^{'}_B &= (C_B - B^{'}_M)/B^{'}_S
\\
\\ C^{'}_W &= C_W / B^{'}_S
\\
\end{split}
$$
</br>
### 半精度浮點數計算
屬於特殊的硬體加速，雖然會損失一定精度，但在這幾年的顯卡上有可觀的性能增益。[這裡](https://hackmd.io/@yrHb-fKBRoyrKDEKdPSDWg/ryvMkGHRs)有簡單的使用教學。
</br>
## AlphaZero
延伸閱讀： [AlphaGo Zero 論文](https://discovery.ucl.ac.uk/id/eprint/10045895/1/agz_unformatted_nature.pdf)、[AlphaZero 論文](https://arxiv.org/abs/1712.01815)
在 2017 年 Deep Mind 提出一種無須棋已有的譜當作基礎，也能成功學習圍棋的強化學習模型，稱為 AlphaGo Zero，這對於圍棋來說是具突破性的，因為在此之前應用於圍棋的強化學習模型都需要棋譜，例如模擬平衡法[[ref]](https://www.remi-coulom.fr/CG2010-Simulation-Balancing/)，沒有棋譜的話效果有限。在 2018 年後，Deep Mind 對之前的模型作略微修改，提出效果更好的學習模型稱為 AlphaZero ，基本上這幾年的圍棋引擎都是以 AlphaZero 的模型為基礎開發，我將著重介紹它的原理。
### 訓練流程
AlphaZero 模型有三個重要部件
* **Replay Buffer :** 它是一個 queue ，當訓練的資料被產生出來後，會放在 buffer 一段時間，直到被新資料排出為止。
* **Selfplay Pipe :** 通過用最新權重自我對戰的方式，產生訓練資料。
* **Training Pipe :** 使用 buffer 內的資料訓練新的權重
在每一個訓練的輪回中，基本流程為
1. Selfplay Pipe 產生訓練資料，並將資料推入 Replay 中，在 AlphaZero 實做中，一次產生 2 萬 5 千局遊戲的資料。
2. Buffer 移出過舊的資料，在 AlphaZero 實做中，buffer 會儲存最新的 50 萬局遊戲資料。
3. Training Pipe 載入當前權重，使用 buffer 的資料再次進行短時間訓練，在 AlphaZero 實做中，每次只會訓練 1000 stpes，而 batch size 為 4096。
### Dirichlet Noise
在 PUCT 的演算法中，它是不存在隨機性的，它總是試圖找到最佳手，如果不處理，在自我對戰中每一盤都會下出一樣的招法，AlphaZero 解決的方法為對 Policy 添加噪音，添加的方式如下
$$
\begin{split}
\
\\ P^{'}_i = 0.75 * P_i + 0.25 * Dirichlet(\alpha=0.03)_i
\end{split}
$$
如此可以在不影響 policy 的主要搜尋方向的情況下，又可以搜索一些候選招法。
### 產生訓練資料
每次搜索完可以產生一個機率分佈，例如現在有 A 、B 和 C 三個合法手，經過 100 次 playouts 後，假設最終結果為 {A, B, C} = {75, 25, 0} ，那機率分佈為 {0.75, 0.25, 0}，這個機率分佈就是神經網路要學習的策略機率。至於價值數值則是直接根據最終輸贏結果產生，例如，此盤是黑棋勝利，則對於黑方而言，價值分數是 1，對於白方而言，價值分數是 -1，總之要以當前網路的角度填入價值分數。
假設有一盤棋，它共有 20 手棋，它產生的訓練資料看起來會像是下方。其中 $x$ 是網路的輸入，也就是當前盤面的資料，$z$ 是價值分數，$prob$ 是策略分數。
$$
\begin{split}
\
\\ &Data\ Size = 20
\\
\\ &Data_i = (x,\ z,\ prob)
\\
\\ &z \in \{1,\ -1\}
\\
\\ &\Sigma prob_i = 1
\end{split}
$$
</br>
### 增加布局階段的多樣性
為了有效增加對局多樣性，我們直接依據 MCTS 的機率分佈（需加入噪音）決定下一手的機率，例如 {A, B, C} = {75, 25, 0} 代表 75% 的機率下 A 點，25% 的機率下 B 點，一般而言我們只在布局階段隨機落子， AlphaGo Zero 是使用前三十手，但根據 CGI 的主作者吳敵融博士說，每一手棋都可以使用隨機落子，不需要限於布局階段，而且最終練出的效果可能更好，唯一的缺點是需要更長的時間等待訓練收斂
### 每手的模擬次數
在一開始的 AlphaGo Zero ，它們選用每手 1600 模擬次數，在後續版本中改成每手棋 800 模擬次數，這是因為因為使用兩倍的模擬次數並不使訓練效益提升兩倍（以總模擬量的觀點），根據 Leela Zero 團隊的研究 [[ref]](https://github.com/leela-zero/leela-zero/issues/1416)，當超過 1000 次模擬左右，它的平均增加效益會隨者手數增加而下降，雖然根據不同定義，最佳模擬次數是會漂移的，但基本上 1600 的確是有點太高了，1000 以下會是比較好的選擇。
另外模擬次數不能選擇太低，因為網路的策略頭要學習其 MCTS 執行完成後的機率分佈，如果模擬次數太少，由於 PUCT 本身會優先搜尋 policy（策略分數）較好的節點，模擬次數不夠會導致隱藏的好手不能被發現，這會使得結果有偏差。
### Reuse Tree
搜尋完成後，當準備換成下一方搜尋時，當前搜尋的結果不用完全丟棄，可以將部份子樹給下一方使用，例如當前子樹有兩個，分別為 {A, B} ，其節點數為 {200, 100} ，如果當前落子為 A，則下一方落子時可以直接使用 A 下方子樹共 200 個節點，如此可以節省計算力。但 Reuse Tree 在自對戰中有個缺點，在根節點有施加噪音，根節點和子節點的搜尋方式不同，所以被重複使用的子樹不包含由噪音產生的隨機搜尋，解決方式也很簡單，就是每手都故固定額外搜尋 N 次，例如 AlphaGo Zero 則是 Reuse Tree 後再額外搜尋 1600 次 [[ref]](https://www.nature.com/articles/nature24270)。
### Playout Cap Randomization
雖然越高的模擬次數可以訓練更好的策略頭，但過大的數值會大幅降低整體的訓練效率（以最後的網路總計算量對比）。KataGo 提出一個方法可以緩解這個問題，稱為 Playout Cap Randomization [[ref]](https://arxiv.org/abs/1902.10565)，它將搜尋分為兩個部份，第一部份為"快速搜尋"，第二部份為"完整搜尋"，在快速搜尋時，使用較小的模擬次數 ，但將此訓練資料給丟棄，而完整搜尋時，使用較大的模擬次數 ，此訓練資料將會被保存下來，甚麼時候使用快速搜尋和完整搜尋是隨機的。KataGo 使用的範例參數為，快速搜尋使用 100 次模擬 ，完整搜尋使用 600 次模擬，快速搜尋出現的機率為 75%。
為甚麼 Playout Cap Randomization 可以增加訓練效率？主要原因是因為訓練資料對於策略網路和價值網路是不平衡的，對於策略網路，由於資料是機率分佈，每筆資料相異性較大，而對於價值網路來說，它是 1 和 -1 的二元資料，相異性較小，如果要增加它的相異性，最好辦法就是增加訓練資料的遊戲總數目。Playout Cap Randomization 由於只保存完整搜尋的訓練資料，策略網路的性能得以保存，而使用快速搜尋使更多的遊戲產出，價值網路的性能得以保存。
再來講解為甚麼這個方法稱為 Playout Cap Randomization？看起來實做原理和名稱八竿子打不著，這是有點歷史和實做原因的，在當前開源實做中，我們計算搜尋次數有兩種方式，一個為本回合實行的模擬次數，稱為 playouts ，另一個為根節點累積的模擬次數，稱為 visits，這兩種計數方式看起來一樣，但有兩點不同，第一個是，visits 會包含根節點但 playouts 不會，也就是說 visits 一定會大於等於 (playouts + 1) ，第二個是，當前開源實做會使用 reuse tree ，所以 visits 也會包含會重複使用的子樹但 playouts 不會，因此 visits 等於 (playouts + reused + 1)，如果使用 visits 當作次數限制，則稱為 visit cap ，如果使用 playouts 則稱為 playout cap [[ref]](https://arxiv.org/abs/1902.10565v2) ，LeelaZero 、KataGo 和 Sayuri 都使用 visit cap。由於會 reuse tree ，每次重複次數利用的可能會不同，所以每手的 playout cap 都會不一樣，早期論文稱為 Playout Cap Oscillation，當前則稱為 Playout Cap Randomization。另外 "快速搜尋" 和 "完整搜尋" 的 visit cap 不一樣，因此在論文中又稱為 Visit Cap Oscillation。
### 擴張訓練資料
圍棋具有旋轉對稱和鏡像對成的性質，總共八個對稱方向，這個非常重要，因為相當於 50 萬局棋經過擴張後，有 400 萬局棋。擴張訓練資料可以大幅度減少訓練時間和最終強度。
### NN Cache
最早由 Leela Zero 實做 [[ref]](https://github.com/leela-zero/leela-zero/pull/471)，可以通過 Hash Table 儲存網路計算結果，由於在數搜索中不同路徑可能會達到同一狀態，同一狀態可以通過 NN cache 分享結果以減少計算資源，以此加速自我對戰。
### Score Utility
單使用勝率引導 MCTS 會引發一些問題，像是 "Win a litter, lose a lot." ，MCTS 容易在勝利的情況下不斷退讓，直至贏一點點而已，可以藉由加入領先目數的資訊，迫使 MCTS 嘗試下最優落點。前面說 MCTS 不引入勝率以外的資訊是因為不準確，但神經網路能預測相當穩定的數值，因此引入此類資訊不會使 MCTS 崩潰。 Sayuri 加入的方式如下
$$
\begin{split}
\
\\ PUCT(a) = \frac{W(a)}{N(a)} + C_{param}P(a)\frac{\sqrt{\Sigma{N(b)}}}{N(a)+1}\ +\ C_{utility}\tanh(\frac{ScoreLead(a)}{C_{score\_div}})
\\
\end{split}
$$
使用 score utility 有另外的好處，在自對戰時，我們可以給在根節點虛手的玩家加 0.5 目，如此當盤面沒有比虛手還要大的落點，也就是理論上棋局已經結束，則 MCTS 會偏向虛手而不會繼續填地，會略為增加下棋效率和最終模型虛手的友善程度。
</br>
## Gumbel AlphaZero
延伸閱讀： [Gumbel MuZero 論文](https://www.deepmind.com/publications/policy-improvement-by-planning-with-gumbel)
雖然 AlphaZero 可以訓練出強大的網路權重，但需要消耗大量的計算在自對戰上，於 2021 年 DeepMind 開發新的加速算法，Gumbel Learning，此算法可以大幅度提昇前期的運算效率（但後期依舊需要巨大算力，截至 2023 年為止，此問題無解），在極端情況下，每次的模擬量甚至可以低於十六次。
一般 AlphaZero 最大的問題為，搜索時可能無法充分搜索不同的子節點，如果增加噪音強制展開較差的節點，則可能導致訓練目標的 policy 品質下降。Gumbel AlphaZero 透過改進搜索和訓練方法解決兩者矛盾。
### 根節點搜索
Gumbel Trick 是一種根據原本機率抽樣的技巧，此方法抽樣的最終分佈會和原本機率分佈近似，例如，機率分佈為 {0.1, 0.2, 0.7}，那 Gumbel Trick 抽樣的分佈比值也會近似此值。抽樣的方法如下，此有一機率分佈，取其 logit 值並加上 Gumbel 噪音，之後每次抽樣時取最大值
$$
\begin{split}
\
\\ (g \in R^{k}) \ & \sim \ Gumbel(0)
\\ A \ & = \ argmax(g(a) + logits(a))
\\
\end{split}
$$
</br>
其中 $Gumbel(0)$ 為 Gumbel 分佈，$logit(a)$ 為節點 $a$ 機率的 logit 值。除了原來的機率，我們可以混合每個節點的預期分數，以平衡不同節點的策略值和預期分數值，當某個節點的預期分數較大時，代表此節點較好，此節點被抽樣的機率應該提升，反之預期分數教低，代表此節點較差，此節點被抽樣的機率也應該下降
$$
\begin{split}
\
\\ val(a)\ & = \ logits(a) + \sigma(Q(a))
\\
\end{split}
$$
</br>
其中 $\sigma$ 為任意單調函數。我們每次在根節點選擇時子節點時，都使用 Gumbel Trick 抽樣，但在非根節點則不需要，這點等一下討論。
```python=
for _ in range(playouts):
sample = argmax(g(a) + val(a)) # 選取最佳節點
path = PUCT(sample) # PUCT 選取 sample 子樹中後續最佳路徑直到葉節點，請
# 看蒙地卡羅樹搜索的部份，path 為路徑
update(path) # 更新路徑的節點，請看蒙地卡羅樹搜索的部份
```
</br>
### 不重覆抽樣
上述闡述的 Gumbel Trick 在根節點的應用為重覆抽樣的演算法，在極端情況下，某一節點可能被多次連續抽樣，例如，在 16 次的模擬中，同一節點被抽樣 15 次，顯然這可能導致搜索的範圍不夠寬範。這裡引入不重覆抽樣算法 Sequential Halving ，基本算法為，從 N 個後選樣本中，每此都選取一半後選樣本，並丟棄一半樣本，直到只剩一個樣，例如有 16 個樣本，第一輪丟棄 8 個樣本，剩下 8 個樣本，第二輪丟棄 4 個樣本，最終剩下 4 個樣本，直到剩下一個樣本。
</br>
Sequential Halving with Gumbel 分為兩個階段，第一階段為抽樣 N 個候選節點，但已經被抽樣的樣本在本輪不能再被抽樣
```python=
samples = list()
for _ in range(N):
sample = (argmax(g(a) + logits(a)),
a not in samples) # a 不能從 samples 再次被抽到
path = PUCT(sample) # PUCT 選取 sample 子樹中後續最佳路徑直到葉節點，請
# 看蒙地卡羅樹搜索的部份，path 為搜索路徑
update(path) # 更新路徑的節點，請看蒙地卡羅樹搜索的部份
samples.append(sample) # 紀錄被採樣的節點
```
</br>
第二個階段為對 N 個候選節點做 Sequential Halving，這邊假設多做 K 次模擬，注意已經被抽樣的樣本直到 Sequential Halving 丟棄一半樣本前不能再被抽樣
```python=
temp = list()
for _ in range(K):
sample = (argmax(g(a) + logits(a)),
a not in samples) # a 不能從 samples 再次被抽到
samples.remove(sample) # 採樣過後的節點在本輪不能
temp.append(sample) # 再次被抽到
path = PUCT(sample) # PUCT 選取 sample 子樹中後續最佳路徑直到葉節點，請
# 看蒙地卡羅樹搜索的部份，path 為搜索路徑
update(path) # 更新路徑的節點，請看蒙地卡羅樹搜索的部份
if (samples 一半被抽樣):
samples = temp
temp = list()
if (samples 只剩一個樣本):
break
```
</br>
基本的概念大概就這樣，但在抽樣的部份，實做上還是有點不一樣的，在實做上每丟棄一半過程的模擬數是一樣的，例如總共需要 8 個樣本，代表 N = 8
</br>
* 第一階段
1. 模擬 8 次，抽樣 8 個節點。
</br>
* 第二階段
1. 模擬 8 次，8 個節點中，其中 4 個節點，每個節模擬 2 次，沒有抽取的節點被丟棄。
2. 模擬 8 次，4 個節點中，其中 2 個節點，每個節模擬 4 次，沒有抽取的節點被丟棄。
3. 模擬 8 次，2 個節點中，其中 1 個節點，每個節模擬 8 次，沒有抽取的節點被丟棄。
4. 剩餘 1 個節點，結束
</br>
此外每輪模擬次數不一定和抽樣的節點一樣多，可以是它的倍數，例如 8 次或 16 次，實際值為 $floor(\frac{M}{log_2({N}){N}})$，N 為第一階段的抽樣數，M 為總模擬次數，為 N+K。具體實做可以參考原論文作者的 [MCTX](https://github.com/deepmind/mctx) 和延伸閱讀的論文。
### 輸出最佳手
當模擬完成後，最後就輸出最佳手，但 ```samples``` 不一定只剩一個，甚至在第一階段都沒抽樣足夠的的節點，例如需要 4 個節點，但只模擬 3 次，抽樣 3 個節點。因此分成兩中情況
* 模擬完全完成，```samples``` 內只剩一個節點，此手即為最佳手
* 模擬沒有完全完成，此情況實做中有多種解法，最簡單的方法可以從 ```samples``` 再次做 Gumbel Trick 隨機抽一手當作最佳手輸出。而原論文則是多做一輪模擬，此模擬選到的節點當作最佳手
### 產生 target policy 訓練資料
假設共有 A 個合法手，我們抽樣了 N 個節點，我們要如何產生 policy 訓練資料？最簡單的方法為，實際落子的位置，機率設為 1，其餘為 0，也就是 one-hot 的訓練資料。但我們也可以用改進原本 policy 的思維來設計，試想，如果節點 a 的預期分數較好，代表此點的機率應該上升，反之下降，可以寫為下方的基本形式
$$
\begin{split}
\
\\ P_{target} = \text{softmax}(logit(a) + \sigma(Q(a)))
\\
\end{split}
$$
</br>
但有個問題是共有 A - N 個節點尚未搜尋，這些點的實際預期分數未知。未知的預期分數應該符合兩點，一、不能高過 N 個節點中的最高點，顯然為被抽樣的節點，本身大機率不會是好的節點; 二、不能低過 N 個節點中的最低點，這有點反直覺，但從優化來看的話，就相當合理，抽樣的 N 個節點中，實際的好手只有少數幾手而已，大部分抽樣的節點都不是好選擇，因此我們會希望 policy 下次可以嘗試未被抽樣的節點。論文中提供一個方法可以嘗試近似平均值，如下
$$
\begin{split}
\
\\ Q_{approx} = \Sigma(P(b)Q(b))(N(b) != 0)
\\
\end{split}
$$
</br>
其中 $b$ 節點為有訪問數不零的節點，所有 A 個節點中分為訪問數為零和不為零的節點，可以簡單假設訪問數為零的節點，其預期分數和平均分數一樣為 $Q_{approx}$ ，概念類似於 FPU。最後所有節點都會有預期分數，所有預期分數總稱為 $Q_{completed}$，總結來講為
* 當 $N(a)$ 不為零 ，$Q_{completed}(a) = Q(a)$
* 當 $N(a)$ 為零 ，$Q_{completed}(a) = Q_{approx}$
</br>
最後產生 policy 的訓練資使 $Q_{completed}$，變成
$$
\begin{split}
\
\\ P_{target} = \text{softmax}(logit(a) + \sigma(Q_{completed}(a)))
\\
\end{split}
$$
</br>
### 非根節點搜索
在原論文中有描述新的搜索方法取代 PUCT ，但論文方法對於 reuse tree 和 NN-cache 有較大的副作用，且提昇有限，甚至沒有，因此採用單純的 PUCT 即可。
### 參數選擇
單調函數為 $\sigma(q) = C_{scale}(C_{visits} + N(b)_{max}) \times q$ ，$C_{scale} = 1$ 、$C_{visits} = 50$ 且 $N(b)_{max}$ 為根節點的子節點中訪問數最大值。抽樣數 N 為一般為大於 16 的數。
### 其它實做
* [TamaGo](https://github.com/kobanium/TamaGo) : 一個用純 python 撰寫的 Gumbel AlphaZero 引擎
</br>
## Sayuri 之樹搜尋實作
Sayuri 結合 KataGo 提出的方法和 Gumbel AlphaZero，最後一些結果表明，在不需要大量調整參數的情況下，可以快過 KataGo g104 和 Gumbel AlphaZero。下圖中，橘色點為 Sayuri v0.6 估算的性能表現，對比 KataGo 和 LeelaZero，沒有使用樂觀策略
</br>
### 算法描述
Sayuri 核心使用 Sequential Halving with Gumbel 加速學習速度。雖然 Sequential Halving with Gumbel 可以快速擴展可能的候選節點，但它有兩缺點，第一點為 Gumbel 在模擬量不夠時有較大的隨機性，會使的網路收斂下降，第二點為 Sequential Halving 的樹形和網路的 policy 沒有玩全正相關，就算某個節點的機率高達 99.99% ，樹形也不會變的更深，這導致，後續 reuse tree 和 NN cache 使用率下降
為了解決雖機性問題，我們簡單使用 Playout Cap Randomization （後簡稱 PCR） ，由於有快速搜尋階段，可以讓遊戲的勝負結果更穩定，在我一些對比實驗中，純 Gumbel 使用 16 次模擬，對比 Gumbel + PCR 平均使用 5.333 次模擬，後者的模擬次數更低，但性能卻高出前者 800 Elo 以上，且 Gumbel + PCR 在更長遠的訓練上，只要後續的模擬次數有提高，並沒有看到奇怪的學習偏差。
第二點 Sequential Halving 樹形利用率的問題，我們採用兩階段的搜尋，分別為
1. Sequential Halving with Gumbel 階段
2. PUCT + Dirichlet Noise 階段
Gumbel 最大的優勢是僅須少數節點就可以正常學習，但一旦超過 100 次模擬，對比 AlphaZero 增益就會明顯下降，因此我們在執行足夠的 Sequential Halving 搜尋後，即切換回利用率更加高效 PUCT 階段，並且我們使用 PCR ，PUCT 可以更好的提昇 PCR 的利用率。經過我在 9 路上實驗，僅用 Gumbel 對比 Gumbel + PUCT，在相同的強度下，後者約能節省 20% 以上的計算資源。
</br>
# （努力施工中......）
### 雜物區
* [台大電腦對局](https://www.iis.sinica.edu.tw/~tshsu/tcg/index.html)
* [Alphago Zero 論文](https://discovery.ucl.ac.uk/id/eprint/10045895/1/agz_unformatted_nature.pdf)
* [pyDLGO 介紹](https://github.com/CGLemon/pyDLGO/blob/master/docs/Methods.md)
* [A New Approach to Game Tree Searching](http://www.robinupton.com/research/phd/)
* [policy improvement by planning with gumbel](https://www.deepmind.com/publications/policy-improvement-by-planning-with-gumbel)
* [一個蒙地卡羅之電腦圍棋程式之設計](https://ir.nctu.edu.tw/bitstream/11536/45925/1/558001.pdf)
Sign in with Wallet
Connect another wallet