Day19 AlphaGo
===
雖然很多人都介紹過AlphaGo了，但我今天是用圍棋愛好者的角度切入去探討，加上電腦對局的知識跟大家探討不同角度的AlphaGo，希望可以帶大家看到不同面貌的AlphaGo。

## AlphaGo
首先我們來看一下AlphaGo中很重要的Policy Network跟Value Network，這邊就不贅述他們是怎麼訓練出來的了，只說明功能。
- **Policy Network**：主要作用是根據當前局面 s，預測每個可能走步 a 的機率。
- **Value Network**：主要作用是對棋局進行評估，預測從當前局面 s 的勝率。
- **Rollout Policy Network**：在模擬階段用來快速選點的，不再使用隨機模擬的方式，這樣模擬的對局品質會更高。

接著我們來看一下AlphaGo的MCTS有哪裡不一樣。


圖片擷取自[Mastering the game of Go with deep
neural networks and tree search](https://www.nature.com/articles/nature16961)

這邊他的Simulation改叫做Evaluation，Backpropagation改叫Backup。

### PUCT (Predictor + UCT)
PUCT 是 UCT 的一個改進，而在AlphaGo中又做了點小改變，通過 **Policy network** 輸出走步的機率 $P(s, a)$ 來輔助選擇。

具體的 PUCT 公式如下：

$$
a_t = \arg\max_a \left( Q(s_t, a) + c \cdot P(s_t, a) \cdot \frac{\sqrt{N(s_t)}}{1 + N(s_t, a)} \right)
$$

- $Q(s_t, a)$：表示局面 $s_t$ 下選擇動作 $a$ 的平均獲勝值。
- $P(s_t, a)$：來自 **Policy Network** 的走步機率。
- $N(s_t)$：表示當前局面 $s_t$ 的總拜訪次數。
- $N(s_t, a)$：表示該動作 $a$ 的拜訪次數。
- $c$：探索與利用之間的平衡參數。

再來看一下**Evaluation**階段，AlphaGo 引入了 **Value Network** 來對葉節點進行評估。當到達搜索樹的葉節點後，Value Network將會對當前局面進行評估，輸出一個值 $V(s)$，代表當前勝率。

當模擬結束後進到**Backup**，要更新每個節點的獲勝期望值 $Q(s,a)$ 和拜訪次數 $N(s,a)$。根據模擬結果（勝、負或和局），將葉節點的評估值 $V(s)$ 回溯到根節點，更新所有沿途經過的節點的 $Q(s,a)$。

$$
Q(s,a) = \frac{1}{N(s,a)} \sum_{i=1}^{N(s,a)} V(s^i_L)
$$

這邊加入的$V(s^i_L)$ 就是Value Network評估的勝率值。

我個人認為AlphaGo的精華就是通過強大的Policy Network在 MCTS 的Selection和Expansion階段，通過輸出每個走步的機率，幫助縮小搜索範圍，讓 AlphaGo 尋找到有潛力的走步。

### AlphaGo Zero
AlphaGo Zero 不再依賴人類專家的棋譜數據，使用單一的神經網絡(結合Policy Network跟Value Network)進行自我對弈學習。
MCTS直接改為三階段Selection、Expansion & Evaluation、Backup，與 AlphaGo 的主要區別在於，AlphaGo Zero 在Evaluation階段直接依賴神經網絡進行葉節點評估，不再使用 Rollout Policy 來模擬對局，大幅加速了決策過程。

## AlphaGo強在哪？
> AlphaGo比起人類強在哪？
還記得這句話是黃士傑學長回到實驗室分享時，問大家的一個問題。

每個時代都會誕生不少的高手，但那種遠超當代其他棋手的天才，可能百年都不一定一遇，這裡我們也來分析一下，那些天才，比起同代的高手**到底是強在哪裡？**
### 本因坊道策

這是我在因島的本因坊秀策紀念館拍攝的照片，蠻推薦喜歡圍棋的人可以去朝聖的。

棋聖[道策](https://zh.wikipedia.org/zh-tw/%E6%9C%AC%E5%9B%A0%E5%9D%8A%E9%81%93%E7%AD%96)，實力超越當代棋手非常多，因此有十三段的美名(最高是九段)，發明了著名的圍棋理論[手割](https://zh.wikipedia.org/wiki/%E6%89%8B%E5%89%B2)分析，被稱為近代圍棋之祖，不拘泥於局部，利用棄子爭先，大局觀領先全世界。

以上都是對道策的評價，基本上沒什麼人提到說道策的計算力有多厲害，多是讚嘆道策對棋的理解高出其他人一大截，所謂對棋的理解就是大局觀，就是對全局形勢判斷的能力。

### 吳清源


圖片取自維基百科。
接著我們來看看昭和棋聖[吳清源](https://zh.wikipedia.org/zh-tw/%E5%90%B3%E6%B8%85%E6%BA%90)，在與[本因坊秀哉](https://zh.wikipedia.org/wiki/%E6%9C%AC%E5%9B%A0%E5%9D%8A%E7%A7%80%E5%93%89)的對局中下出了震驚棋壇的星、三三、天元開局，開創了新時代的布局，比起當代的人更注重中央的潛力，十番棋不敗，把當時全日本的高手打到降級。

對吳清源的評價大多也不是什麼戰鬥力非凡、計算精準之類的，而是他下出了前所未見的布局與定石，一樣是大局觀領先全世界。

### 申真諝
[圖片來源](https://www.ntdtv.com/b5/2024/02/06/a103849765.html)

[申真諝](https://zh.wikipedia.org/zh-tw/%E7%94%B3%E7%9C%9F%E8%B0%9E)於2018年登上[Go Ratings](https://zh.wikipedia.org/wiki/Go_Ratings)排行榜第一名，至今ELO分數突破3800分，長期與第二名差距達150~200分以上(第2與第10名差距通常不到50分)。
* 2020年取得第一個世界冠軍，以76勝10敗的成績，創下年度勝率88.37%紀錄。
* 2021年達成韓國國內棋賽大滿貫。
* 2022年創下連續六次打進世界大賽決賽的紀錄，並且在國際大賽中對中國棋手取得24連勝的紀錄(2020~2022)。
* 2023年達成生涯700勝，成為最年輕(23歲1個月22天)和用時最短(11年9個月22天)達成此項紀錄的棋手，上半年達成了29連勝、總戰績的47勝3敗的可怕成績，最後更創下首位年度破百勝的紀錄(111勝)。
* 2024年達成農心盃主將6連勝、跨季16連勝紀錄，連續四年終結比賽。
毫無爭議的當今第一人，每年都在締造新紀錄。

大家對申真諝的評價幾乎都是AI吻合度很高(現在很多人都是以AI來檢視棋手，吻合度愈高代表跟AI愈接近)，在中盤局勢混沌不明時能夠比別人判斷得更清楚。
我們可以發現那些天才都有個共同點，那就是**對棋的理解已經超出同代人不少了，在大局觀上展現出色的判斷能力。**

### 許皓鋐
這邊要補充一下，去年亞運的圍棋項目，**台灣第一人[許皓鋐](https://zh.wikipedia.org/zh-tw/%E8%A8%B1%E7%9A%93%E9%8B%90)接連擊敗世界排名前三的[朴廷桓](https://zh.wikipedia.org/zh-tw/%E6%9C%B4%E5%BB%B7%E6%A1%93)、申真諝、[柯潔](https://zh.wikipedia.org/zh-tw/%E6%9F%AF%E6%B4%81)，奪得金牌**，你沒看錯，其中就包含了締造上面一堆可怕紀錄的申真諝。

[圖片來源](https://www.newsday.tw/news/284513)

### 賴均輔
還有今年的國手山脈盃，**台灣的[賴均輔](https://zh.wikipedia.org/wiki/%E8%B3%B4%E5%9D%87%E8%BC%94)，接連擊敗[范廷鈺](https://zh.wikipedia.org/zh-tw/%E8%8C%83%E5%BB%B7%E9%92%B0)、[卞相壹](https://zh.wikipedia.org/zh-tw/%E5%8D%9E%E7%9B%B8%E5%A3%B9)、申真諝奪冠**。

[圖片來源](https://sports.ltn.com.tw/news/breakingnews/4759363)

這兩年台灣棋手在國際舞台上都有非常好的表現，可惜絕大多數台灣人都不知道這些消息，所以剛好利用這次鐵人賽花點篇幅來分享，讓大家能夠更認識這些台灣之光們，還有歡迎大家一起學圍棋XDD。

回到一開始的問題，那AlphaGo到底強在哪呢？
其實答案很明顯了，那就是大局觀、形勢判斷的能力，AlphaGo對李世石的那五盤棋，常常有一些顛覆當時人類想法的棋出現，反而不是在計算上讓大家驚豔，甚至當時還有人懷疑AlphaGo是不是不會打劫。

應該蠻多人的第一反應都是計算，覺得AlphaGo能夠計算的比人類更深遠，所以才會贏人類，但其實純粹用Policy輸出的走步，不經過計算直接下(就很像是人類所說的用棋感(第一感)下棋)，就已經能達到台灣業餘7段的水準了，在大局觀上甚至是職業頂尖水準，這才是AlphaGo最令我驚訝的地方。
要說到計算力，雖然說人腦肯定算不贏電腦，但**人腦的剪枝能力卻是遠遠大勝電腦**，我們再看一下Day14中的征子範例，雖然要算出吃掉A點的黑子需要計算接近50步，人類幾乎都是一看就知道答案，但是對於電腦來說則是非常困難的問題。


而且在局部戰鬥時，人類還是能下出很多AI沒有算到的妙手，只能說AI還是浪費很多計算資源在計算一些無用的分支上，這點是還遠遠不及人類的。
這邊附上我之前寫的[棋評](https://marsgoat.github.io/XNnote/go/ShinJinSeo.html)，是小申下出連AI也沒算到的「妙手」，會下棋的朋友可以看看。

## 結論
廣義上來說AlphaGo的計算力確實大於人類，但在計算這塊上人類還是有遠超電腦的剪枝能力的。
AlphaGo最強的地方就在於他的Policy Network，以前傳統的選點方式可能是根據一些數學公式，或是遊戲特性寫出來的規則，你都能解釋他是為什麼會選擇這個點，但偏偏AlphaGo你無法解釋，他居然能通過自我學習打敗人類幾百年來的經驗，AlphaGo不只開啟了大AI時代，也替本來很多棋力遇到瓶頸的遊戲開啟了另一條新的研究之路。

## Reference
* [Mastering the game of Go with deep
neural networks and tree search](https://www.nature.com/articles/nature16961)
* [Mastering the game of Go without human knowledge](https://www.nature.com/articles/nature24270)
* [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://arxiv.org/abs/1712.01815)