Day20 AlphaZero General === 連續幾天都在介紹理論跟我猜沒什麼人看的公式，是時候該帶大家動手做了，身為一個AI工程師今天就來從零開始實作AlphaGo吧。 開玩笑的，就不要自己造輪子了吧，何況我現在沒有chatGPT + Copilot已經不會寫code了，我怕造出來的輪子長得像下圖這樣。 ![image](https://hackmd.io/_uploads/SJv1e_TC0.png) 今天我們要直接用大神造好的輪子！ ## AlphaZero General 分享一個知名的開源框架：[AlphaZero General](https://github.com/suragnair/alpha-zero-general)，是一個基於 AlphaGo Zero 的自我對弈強化學習框架，以下簡稱AZG。 作者是Surag Nair先生，剛剛看了一下他的linkedin，發現他都博士畢業一年了，雖然他絕對看不到這篇但還是恭喜他。 ### 抱在巨人的大腿上 想當初2018年時，以為他是什麼很厲害的大叔，沒想到其實年紀跟我一樣大，而且也正在讀碩士，怎麼別人的side project都是這種拿到幾千顆星星的大型專案，而我只能寫些屎project(之後會分享)，當年修類神經網路的課，我還是用AZG來完成我的期末project，感恩Surag Nair讚嘆Surag Nair。 我這樣也算是抱在巨人的大腿上吧。 ![image](https://hackmd.io/_uploads/HyvkEdaCR.png) 只要他一抬腳，我也是能飛得又高又遠的。 ![巨人](https://hackmd.io/_uploads/BkENEd6AC.jpg) 最佛心的是他居然還有在更新，比起我2018年用的時候又更好用了，我們實驗室有幾位大神也是Contributors。 ## 使用說明 (安裝python跟各種環境這裡就不教學了，網路上多到數不清了。) 使用AZG的好處就是clone下來馬上就能動，只要執行`main.py`馬上就開始訓練。 ``` python main.py ``` 連狀況都還沒搞清楚，他已經開始Self Play了，甚至都不知道是在Play什麼。 ![image](https://hackmd.io/_uploads/S1-yOOaRC.png) 其實是他已經實作好了幾款遊戲的遊戲邏輯，包含[Othello](https://zh.wikipedia.org/zh-tw/%E5%A5%A7%E8%B3%BD%E7%BE%85)(黑白棋)、Tic Tac Toe、Connect4等遊戲，而且還有Pytorch版跟Keras版，真是貼心。 也可以換成自己想要的遊戲，只需要將遊戲邏輯實作出來即可，一樣可以套用AZG框架。 ### main 這邊也蠻清楚的，設定好參數就能開始訓練。 ``` 'numIters': 1000, 'numEps': 100, # Number of complete self-play games to simulate during a new iteration. 'tempThreshold': 15, # 'updateThreshold': 0.6, # During arena playoff, new neural net will be accepted if threshold or more of games are won. 'maxlenOfQueue': 200000, # Number of game examples to train the neural networks. 'numMCTSSims': 25, # Number of games moves for MCTS to simulate. 'arenaCompare': 40, # Number of games to play during arena play to determine if new net will be accepted. 'cpuct': 1, ``` `numIters` 訓練的總迭代次數，這裡預設是 1000。 `numEps` 每次迭代中進行的自我對弈遊戲數量，就是那一執行馬上就開始的Self Play，這裡預設為 100。這邊在AlphaGoZero論文中是寫25000局，你可以根據不同遊戲的複雜度來設定，或是看你的硬體設備(財力)來決定。 `tempThreshold` 溫度閥值，預設為 15。這跟探索策略有關，影響遊戲前期的隨機性，當遊戲超過一定回合後溫度會降低，從而減少隨機性。 `updateThreshold` 更新閾值，預設為 0.6。這是arenaCompare中新舊神經網路的對戰勝率，設為0.6代表新神經網路勝率高於60%時，就會更新。 `maxlenOfQueue` 訓練神經網路的遊戲樣本Queue的最大長度，預設為 200000，就是最多保留 200000 個遊戲樣本用於訓練。 `numMCTSSims` 每次行動中 MCTS 進行的模擬次數，預設為 25。這決定了在每次選擇動作時，MCTS 要進行多少次模擬，這邊在AlphaGoZero論文中是寫1600次，你可以根據不同遊戲的複雜度來設定，或是看你的硬體設備(財力)來決定。 `arenaCompare` 新舊網路進行對戰的場次，這裡預設為 40 場，我記得之前學長說400場會是一個比較好的數字，具體證明我已經忘了。 `cpuct` 這個就是PUCT公式中的那個常數C $$ 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) $$ 這個C寫成 $C_{puct}$ 這邊預設為1，但其實 $C_{puct}$ 隨著模擬總數動態調整會比較好，具體要怎麼設置大家可以自行嘗試看看，或是參考其他論文的設定，這裡就不展開了。 ### pit 這邊作者有提供黑白棋的pretrained model，所以直接執行`pit.py`就可以跟電腦對戰了。 ``` python pit.py ``` 預設是8x8的黑白棋，有點感動他終於對齊了，2018年時預設的是6x6黑白棋，並且因為棋盤印出來是歪的，有點強迫症的我當初還花了點時間慢慢喬正，不知道作者是什麼時候更新的，感動。 ![](https://hackmd.io/_uploads/Hyo3wBaAC.png) 本來想放我把AI電爆的畫面截圖，但我連玩了好幾場都輸，只能交給大家去嘗試了，還差點玩到忘記發文。 ### MCTS 這段就是PUCT的實際程式碼，大家就可以自由發揮，比如把它改成LCB。 ```python= cur_best = -float('inf') best_act = -1 for a in range(self.game.getActionSize()): if valids[a]: if (s, a) in self.Qsa: u = self.Qsa[(s, a)] + self.args.cpuct * self.Ps[s][a] * math.sqrt(self.Ns[s]) / (1 + self.Nsa[(s, a)]) else: u = self.args.cpuct * self.Ps[s][a] * math.sqrt(self.Ns[s] + EPS) # Q = 0 ? if u > cur_best: cur_best = u best_act = a ``` 這邊是處理葉節點與更新的程式碼，這邊也可以嘗試用之前介紹到的Quick Win、Big Win之類的方式去改進。 ```python= if s not in self.Ps: self.Ps[s], v = self.nnet.predict(canonicalBoard) valids = self.game.getValidMoves(canonicalBoard, 1) self.Ps[s] = self.Ps[s] * valids # masking invalid moves sum_Ps_s = np.sum(self.Ps[s]) if sum_Ps_s > 0: self.Ps[s] /= sum_Ps_s # renormalize else: log.error("All valid moves were masked, doing a workaround.") self.Ps[s] = self.Ps[s] + valids self.Ps[s] /= np.sum(self.Ps[s]) self.Vs[s] = valids self.Ns[s] = 0 return -v ``` ```python= if (s, a) in self.Qsa: self.Qsa[(s, a)] = (self.Nsa[(s, a)] * self.Qsa[(s, a)] + v) / (self.Nsa[(s, a)] + 1) self.Nsa[(s, a)] += 1 else: self.Qsa[(s, a)] = v self.Nsa[(s, a)] = 1 self.Ns[s] += 1 return -v ``` ### Arena 這邊是用來對戰的，可以讓新舊網路進行對戰，統計勝率來決定要不要更新網路。 但是這邊從2018到現在都有一些小問題沒有修正，也有引發了一些討論。 [Different approaches for MCTS instancing in Self Play and Arena #24](https://github.com/suragnair/alpha-zero-general/discussions/24) [MCTS should not keep "tree" between games. #206](https://github.com/suragnair/alpha-zero-general/issues/206) 主要就是在Arena中的每場對戰結束後都沒有將樹給清掉，他會一直維護同一棵樹， ![image](https://hackmd.io/_uploads/SJiN5Dtx1x.png) ![image](https://hackmd.io/_uploads/rJsScDKgkg.png) ![image](https://hackmd.io/_uploads/SkjU5wYeyx.png) **Dirichlet noise** ### Maverick Maverick是目前世界上最強的黑白棋程式，作者為陳彥吉，連續拿了好幾屆的TCGA、TAAI、ICGA金牌，大家可以猜猜他是怎麼做的。 之前日本有開發[世界最弱黑白棋程式](https://www.4gamers.com.tw/news/detail/39795/computer-othello-ai-will-always-let-you-win)，但其實黑白棋你只要能做出最強，那同時也可以最弱(只要把獲勝條件那邊加個負號就好了)，那個標題其實只是一個噱頭吧，所以Maverick也是可以輕鬆比他還弱的，歡迎大家實作自己的黑白棋程式去參加比賽，挑戰這支多年連霸的冠軍程式。 ## 其他開源框架或程式推薦 * [MuZero General](https://github.com/werner-duvaud/muzero-general) MuZero: Mastering Go, chess, shogi and Atari without rules 也是DeepMind發表的，是一個不需要環境的明確規則或模型就能進行學習的強化學習框架，比起AlphaZero又更進一步，這次連規則都不需要就能夠學會下棋，這個可能就比較少人知道了，有興趣的可以去看看原論文。 * [KataGo](https://github.com/lightvector/KataGo) 如果是想訓練圍棋AI的話可以參考一下KataGo，當然其中的一些改進也是可以用在別的遊戲上。 * [Sayuri](https://github.com/CGLemon/Sayuri)和[pyDLGO](https://github.com/CGLemon/pyDLGO)，這邊幫一位優秀的學弟推薦一下，這是他做的圍棋程式，就是**第16屆UEC亞軍的程式**，裡面有很詳細的說明，如果想學習實作圍棋AI的話，這會對你非常有幫助。 * [AlphaZero_Gomoku](https://github.com/junxiaosong/AlphaZero_Gomoku) 什麼？你說我只推薦圍棋？這不是來了嗎，各位觀眾「五子棋」，好了，剩下的大家自己探索吧。 ## 論文推薦 這邊論文多到爆，歡迎大家選喜歡的遊戲去研究。 * [在下棋與訓練階段改進AlphaZero演算法](https://etds.lib.ntnu.edu.tw/thesis/detail/965feca0896757a0aadfca6515239c49/) * [AlphaZero演算法結合快贏策略或迫著空間實現於五子棋](https://etds.lib.ntnu.edu.tw/thesis/detail/da8499e71517ac31e79e84d29238e3ec/?seq=19#) * [改進AlphaZero的大贏策略並應用於黑白棋](https://etds.lib.ntnu.edu.tw/thesis/detail/a0b7ec867dc4fc97ba735836d0156313/) * [基於AlphaZero General Framework實現Breakthrough遊戲](https://etds.lib.ntnu.edu.tw/thesis/detail/e82bb4e52dbfe40bc754965711b9680e/) * [蒙地卡羅樹搜索法的必贏策略以及快速Nonogram解題程式的實作](https://etds.lib.ntnu.edu.tw/thesis/detail/1bfe92a10027d91e6733716bcbdf38fb/) * [增強學習架構與期望最小最大算法之愛因斯坦棋實作比較](https://etds.lib.ntnu.edu.tw/thesis/detail/23e18e98ddd5e9070d36a37d8bb76194/) * [中國跳棋對局程式研發與深度學習之探討](https://etds.lib.ntnu.edu.tw/thesis/detail/fca08fd7f1d9b5020218e3865f8821ce/) * [六貫棋遊戲實作與強化學習應用](https://etds.lib.ntnu.edu.tw/thesis/detail/8fa7a138501962327c9a061add22c6b9/) * [利用有利條件訓練神經網路-以六子棋為例](https://etds.lib.ntnu.edu.tw/thesis/detail/905ca36c60f16bc0ed036ee23aebfcc6/) * [中國跳棋對弈平台與AI的實作](https://etds.lib.ntnu.edu.tw/thesis/detail/7996f1a0c15647b2268cd111e6ac0c86/) * [基於強化學習之Surakarta棋程式開發與研究](https://etds.lib.ntnu.edu.tw/thesis/detail/8fa7a138501962327c9a061add22c6b9/) * [利用AlphaZero框架實作與改良MiniShogi程式](https://etds.lib.ntnu.edu.tw/thesis/detail/aa4a0146968fd11afa1364536f5e55c9/) * [基於AlphaZero作法之國際跳棋程式開發及研究](https://etds.lib.ntnu.edu.tw/thesis/detail/432e98c2a7ac390a1ef5b320fb5259f2/) * [MuZero 演算法結合連續獲勝走步改良外圍開局 五子棋程式](https://etds.lib.ntnu.edu.tw/thesis/detail/7e204adb3f0678bff2d1a6b6ea472573/) * [基於AlphaZero General與MuZero General框架實現點格棋](https://etds.lib.ntnu.edu.tw/thesis/detail/38a8dd6b31567f351a71529de5d90ed9/) * [使用KataGo方法及迫著空間搜尋提升AlphaZero在六子棋的訓練成效](https://etds.lib.ntnu.edu.tw/thesis/detail/40748f8537e0d82a9dee900b261606a1/)