0
| 本文作者： AI研習社-譯站 | 2020-12-02 11:12 |
譯者：AI研習社（Champagne Jin）
雙語原文鏈接：AlphaZero, a novel Reinforcement Learning Algorithm, in JavaScript
在本篇博文中，你將會了解并實現AlphaZero。AlphaZero是一個令人大開眼界且超乎尋常的強化學習算法，它以絕對的優勢戰勝了多名圍棋以及國際象棋冠軍。本文將會帶你使用AlphaZero來解決一個益智小游戲（Dots and Boxes）并將其部署成一個純JavaScript構建的Web應用。
AlphaZero最關鍵也是最令人詫異的一點，就是其能夠在不依賴于外部先驗知識的情況下在棋盤類游戲中獲得超越人類的表現。AlphaZero通過自我博弈汲取經驗知識來不斷精通游戲。
我們會借助于Github上由Surag Nair開發的一個“簡化后的、高度靈活的、經過注釋的且易于理解的”Python版AlphaZero來進行該項目。
你大可以先去這里玩一玩這個游戲。而Web應用以及具體的JavaScript實現代碼可以在這里獲取得到。這份代碼是從該Python實現中移植過來的。
https://carlos-aguayo.github.io/alphazero/
有關AlphaZero的原理，你可以閱讀這篇由Silver，David等人撰寫的論文：“Mastering the game of Go without human knowledge” nature 550.7676 (2017): 354–359.
Dots and Boxes是一個常見的兒童益智游戲，不過其具有令人訝異的復雜度。
該游戲中，兩名玩家輪流在兩個相鄰點之間放置一條水平或垂直線。如果某個 1×1 的小正方形的 4 條邊都被連上了，那么補齊這個小方塊的一方就獲得 1 分，得分的玩家被獎勵多走一步，再連一條線。當棋盤已滿時，游戲結束，并且得分最高的玩家獲勝。
（譯者注：這個游戲相當有意思，建議先去玩玩看，點這里。能不能戰勝AlphaZero就看你了?。?/span>
機器是否能夠產生智能，我們已經為此思考了很久很久。那么，該如何驗證機器具有智能呢？一個常用方法就是玩棋盤游戲，比如國際象棋，看看其是否具有超人的能力，甚至擊敗世界冠軍。
1957年，Herbert Simon預言計算機系統能夠在十年內擊敗國際象棋冠軍。雖說實際上花的時間長了點，但是在1997年5月，計算機擊敗了當時的國際象棋冠軍——Garry Kasparov。
（譯者注：戰勝Kasparov的機器被命名為DeepBlue，意為“深藍”）
盡管這一里程碑事件意義非凡，但人們仍可以爭論這一計算機系統是否“智能”。
這一類計算機系統由以下三個組件構成：
1. 人為定義的評價函數；
2. 博弈樹搜索算法；
3. 極為強悍的硬件設備。
評價函數會將棋盤盤面作為輸入并輸出該盤面的“價值”。高價值表示當前玩家處于非常有利的位置。例如，在國際象棋棋盤上，玩家即將進行“將死”時就會對應一個非常高的值。
博弈樹搜索算法（比如 Minimax）在所有可能的走棋中進行搜索，尋找那些能夠確保得到高價值棋盤盤面的路徑。對于那些已經明知不可能有效的路徑可以直接放棄搜索，從而使算法變得更有效率。這就是 Alpha-beta剪枝 的作用。
最后，搭配上異常強悍的硬件，你就將擁有一臺能夠打敗國際象棋世界冠軍的機器。
問題在哪兒？經驗豐富的棋手人為地精心調制這些評價函數。這些計算機系統還依賴于一本本記錄著最佳走棋的開局棋譜。游戲中局，還會用到通過研究大師們的博弈而精心構造的評價函數。這些函數還會經由象棋大師們進一步的優化調整。
例如，我們完全就可以為 Dots and Boxes 構造一個評價函數。一個合理而直接的選擇就是做一個得分的比較。得分的正向差值越大，游戲盤面就對我們越有利。大多數情況下，這是可行的。然而，在 Dots and Boxes 中，就像許多其他棋盤類游戲一樣，最佳的走法可能需要犧牲短期利益來換取長期利益。在 Dots and Boxes 游戲中，有時最好不要急于得分并獲得額外先手，相反，要迫使對手走某一步棋。因此，我們必須考慮大量復雜場景并精心調制評價函數！
擊敗Kasparov的評價函數需要識別多達8000個盤面特征！而且其中絕大多數都是手動描述并調整的！
所以，倒也不是貶低這個擊敗國際象棋世界冠軍重要里程碑的意思，只是，需要頂級玩家來定義這些計算機的行為并手動調整如此多的變量實在是有夠折騰人的。
AlphaZero是首個能夠在國際象棋、圍棋等游戲中達到超越人類水平、擊敗世界冠軍的計算機系統，且它僅依賴于游戲規則，無需任何人類先驗知識。
僅憑給定的游戲規則，AlphaZero即可進行自我博弈。逐步習得游戲策略與技巧，很快即可獲得超人的表現。
像DeepBlue這樣的系統會需要國際象棋專家的協助，而AlphaZero卻是憑借自我博弈來變強大的。不單單是在國際象棋上，哪怕是圍棋，AlphaZero同樣表現出超越人類的強大統治力?？紤]到圍棋相較于其他棋盤游戲更大的博弈空間等因素，對計算機來說，圍棋是個極為復雜的游戲。
人類從幾千年來數百萬次的博弈中方才積累了諸如圍棋和國際象棋等游戲的技藝，而AlphaZero，一個僅使用游戲規則信息的算法，卻能夠在幾天時間內重新尋獲這些知識并發現新的游戲策略。
甚至還有一部關于它的紀錄片。
（譯者注：這部紀錄片很值得一看，無法訪問YouTube的同學可以在B站觀看，鏈接在此。不過需要注明的是，本紀錄片中實際上使用的是AlphaGo算法，而非AlphaZero，準確來說，AlphaZero是AlphaGo的進階版本，全名為AlphaGo Zero。紀錄片中與李世石博弈的AlphaGo在跟AlphaGo Zero 博弈時，0-100全負，并且，AlphaGo Zero在訓練中未使用任何手工設計的特征或者圍棋領域的專業知識，僅僅以歷史棋面作為輸入，其訓練數據全部來自于自我博弈?？芍^恐怖如斯！）
回想一下，像DeepBlue那樣依賴于人為定義的“評價函數”的系統會把棋盤的盤面狀態作為輸入，再輸出該狀態的“價值”。
如今，對于深度學習模型來說，輸入一張照片然后識別出照片里是貓還是狗簡直簡單到爆了。那么有個想法就是，把棋盤盤面作為一個深度學習模型的輸入并且訓練它，讓它預測這樣的盤面布置是會輸還是會贏。
但是，要訓練一個機器學習模型，就需要數據，海量的數據。從哪兒能得到那么多棋局博弈的數據呢？很簡單，我們就讓電腦自己跟自己下著玩兒，生成一堆棋局，然后再把它們做成一個數據集用來訓練。
這個算法簡單明了：
1. 讓計算機自我博弈數局，記錄每一步走棋。一旦勝負已分，就給之前的每一步走棋打上標簽——棋面最終是“贏”或是“輸”。如此一來，我們就獲得了一個可以用于神經網絡（Neural Network，NN）訓練的數據集，讓該網絡學會判斷給定棋面是“贏面”還是“輸面”；
2. 復制這個神經網絡。用上一步得到的數據集訓練該克隆網絡；
3. 讓克隆網絡與原始神經網絡互相博弈；
4. 上一步中獲勝的網絡留下，敗者棄之；
5. 重復第1步。
呼哈，就像是魔法似的，經過多輪迭代后，你就將獲得一個世界級模型。這個模型在短短4小時內便超越了最強大的計算機象棋程序。
AlphaZero由兩部分構成。我們已經提及了第一部分，就是神經網絡。第二部分則是“蒙特卡洛樹搜索（Monte Carlo Tree Search）”，或者簡稱MCTS。
1. 神經網絡（NN）。以棋面作為輸入，輸出該棋面的“價值”，外加所有可能走法的概率分布。
2. 蒙特卡洛樹搜索（MCTS）。理想情況下，使用神經網絡就足以選擇下一步走法了。不過，我們仍然希望考慮盡可能多的棋面，并確保我們的的確確選擇了最好的走法。MTCS和Minimax一樣，是一種可以幫助我們尋找可能棋面的算法。與Minimax不同的是，MTCS能夠幫助我們更加高效地搜尋博弈樹。
我們不妨先看看AlphaZero在決定下一步走棋（競技模式）時具體干了什么，然后再去探究它的訓練過程，這樣可以幫助我們更容易地理解AlphaZero。
神經網絡在分類這件事兒上表現得異常出色，例如區分貓跟狗。所以這里的想法很簡單直接，神經網絡能學會區分棋局輸贏的類別嗎？更具體地來說，就是讓神經網絡預測一個表示棋局輸贏概率的數值。此外，它還將輸出所有可能走法的概率分布，來表示我們下一步應該如何決策。
神經網絡將博弈狀態作為輸入并輸出一個輸贏概率數值以及所有可能走法的概率分布。對于Dots and boxes這個小游戲來說，游戲狀態由三個元素表示：首先，某一條線是否已被占用，這可以用一個含有0與1的數組來表示，如果玩家已經畫了某條線，則置其為1，否則為0；第二，當前的走法是否是空過；第三，雙方玩家的得分。我們可以用這三個元素來表示所有需要的信息，用其計算當前盤面的價值并預測下一步的走法。
讓我們分析一下下圖中的博弈情形，該輪輪到藍色玩家走。藍色方有兩個選擇，按照圖中上面的走法來畫線就會輸，按照下面的走法就會贏。
（譯者注：左下角是每根線的編號。如果你剛剛已經在網頁上跟AlphaZero玩過這個游戲了，那么相信這張圖是很容易理解的。上方第一種走法只顧眼前短期利益，最終葬送好局。）
如果藍色方走23再走21，那么紅色方必贏。然而，如果藍色方走23后再走9，那藍色方就贏了。要是AlphaZero在藍色方，它怎么知道哪一種走法能夠贏下來呢？
你可以用這個在線notebook復現我們即將呈現的效果。
將棋面送入神經網絡，我們就能得到下一步走在不同位置的概率：
| move_probability[0]: 9.060527501880689e-12 move_probability[1]: 3.9901679182996475e-10 move_probability[2]: 3.0028431828490586e-15 move_probability[3]: 7.959351400188552e-09 move_probability[4]: 5.271672681717021e-11 move_probability[5]: 4.101417122592821e-12 move_probability[6]: 1.2123925357696643e-16 move_probability[7]: 6.445387395019553e-23 move_probability[8]: 2.8522254313207743e-22 move_probability[9]: 0.0002768792328424752 move_probability[10]: 1.179791128073232e-13 move_probability[11]: 5.543385303737047e-13 move_probability[12]: 3.2618200407341646e-07 move_probability[13]: 4.302984970292259e-14 move_probability[14]: 2.7477634988877216e-16 move_probability[15]: 1.3767548163795204e-14 move_probability[16]: 8.998188305575638e-11 move_probability[17]: 7.494002147723222e-07 move_probability[18]: 8.540691764924446e-11 move_probability[19]: 9.55116696843561e-09 move_probability[20]: 4.6348909953086714e-12 move_probability[21]: 0.46076449751853943 move_probability[22]: 2.179317506813483e-20 move_probability[23]: 0.5389575362205505 move_probability[24]: 5.8165523789057046e-15 |
同時，我們還能得到當前棋局的贏面有多大：
| -0.99761635 |
你可以在這里查閱與這些輸出相關的代碼。
這些輸出值有一些很有意思的地方，我們來細品一下：
在所有可能畫線的位置，23號、21號以及9號的概率值最大。如果神經網絡選擇在23號以及21號位置處畫線，那么它就能夠得到1分。另外，23號才是能夠贏下來的走法，而相應地，從網絡輸出的概率來看，23號位置的概率（0.53）恰好比21號的（0.46）稍微高一點兒。
神經網絡也會給不能夠畫線的位置輸出一個概率值。雖然如此，但是代碼上還是要進行限制，以確保計算機不會在不合規則的位置畫線。
棋面的輸贏概率為-0.99。這意味著AlphaZero認為它已經輸掉游戲了。這個概率值的范圍是-1（輸）到1（贏）。這個值本應該很接近于1（贏）而不是-1（輸）的，畢竟我們知道目前這個局面贏面很大。也許我們應該多訓練幾輪來讓AlphaZero準確預估棋面的輸贏概率。
我們很容易利用神經網絡的輸出來決定下一步的走法。
在棋盤游戲中（現實生活中也是），玩家在決定下一步怎么走的時候往往會“多想幾步”。AlphaZero也一樣。我們用神經網絡來選擇最佳的下一步走法后，其余低概率的位置就被忽略掉了。像Minimax這一類傳統的AI博弈樹搜索算法效率都很低，因為這些算法在做出最終選擇前需要窮盡每一種走法。即使是帶有較少分支因子的游戲也會使其博弈搜索空間變得像是脫韁的野馬似的難以駕馭。分支因子就是所有可能的走法的數量。這個數量會隨著游戲的進行不斷變化。因此，你可以試著計算一個平均分支因子數，國際象棋的平均分支因子是35，而圍棋則是250。
這意味著，在國際象棋中，僅走兩步就有1,225（352）種可能的棋面，而在圍棋中，這個數字會變成62,500（2502）。在Dots and Boxes游戲中，對于一個3×3大小的棋盤，初始的分支因子數是24，隨著棋盤不斷被填充，這個數字會不斷減少（除非空過）。所以，在行至中局，分支因子變為15的時候，僅走3步就會有多達2730（15*14*13）種可能的棋面。
現在，時代變了，神經網絡將指導并告訴我們哪些博弈路徑值得探索，從而避免被許多無用的搜索路徑所淹沒?，F在神經網絡告訴我們23號和21號都是非常值得一探究竟的走法。
接著，蒙特卡洛樹搜索算法就將登場啦！
神經網絡為我們指示了下一步可能的走法。蒙特卡洛樹搜索算法將幫助我們遍歷這些節點來最終選擇下一步的走法。
去這個鏈接看看論文中有關蒙特卡洛樹搜索的圖形化描述。
使用MCTS的具體做法是這樣的，給定一個棋面，MCTS共進行N次模擬。N是模型的超參數。N次模擬結束后，下一步的走法將是這N次模擬中所經次數最多的一步。你可以由這里的代碼一窺究竟：
| # https://github.com/suragnair/alpha-zero-general/blob/5156c7fd1d2f3e5fefe732a4b2e0ffc5b272f819/MCTS.py#L37-L48 for i in range(self.args.numMCTSSims): # self.args.numMCTSSims, the number of MCTS simulations to compute self.search(canonicalBoard) # "search" is a MCTS simulations s = self.game.stringRepresentation(canonicalBoard) # Count how many times we have visited each node counts = [self.Nsa[(s, a)] if (s, a) in self.Nsa else 0 for a in range(self.game.getActionSize())] if temp == 0: # Pick the node that was visited the most bestAs = np.array(np.argwhere(counts == np.max(counts))).flatten() bestA = np.random.choice(bestAs) probs = [0] * len(counts) probs[bestA] = 1 return probs |
進行N次MCTS模擬
一次MCTS模擬從當前的棋盤狀態出發，沿著博弈樹中具有最大“置信區間上界（UCB）”值（后文會給出定義）的節點不斷向下追溯，直到遇到之前從未見過的棋盤狀態，也叫做“葉子”狀態。這就是原論文中Part A所謂的“選擇（Select）”。
置信區間上界是什么呢？用數學形式來說就是 Q(s, a) + U(s, a)。其中 s 是狀態，a 是走法。Q(s, a) 是我們希望由走法“a”構成狀態“s”能夠獲得的期望值，與Q-Learning中的期望值一致。記住了，在這種情況下，該值的范圍是-1（輸）到1（贏）。U(s, a) ∝ P(s, a) / (1 + N(s, a))。這意味著U正比于P和N。其中，P(s, a) 是元組 (s, a) 的先驗概率值，這個值是從神經網絡那里得到的，而 N(s, a) 是已經訪問過狀態 s 與對應的走法 a 的次數。
| # Upper Confidence Bound ucb = Qsa[(s,a)] + Ps[s,a] * sqrt(Ns[s]) / (1 + Nsa[(s,a)] |
UCB的要點在于，其起初更傾向于具有較高先驗概率（P）和較低訪問次數（N）的走法，但漸漸地會傾向于具有較高動作價值（Q）的走法。
你不妨看看這里的代碼好好理解一下。
| # https://github.com/suragnair/alpha-zero-general/blob/5156c7fd1d2f3e5fefe732a4b2e0ffc5b272f819/MCTS.py#L105-L121 cur_best = -float('inf') best_act = -1 # pick the action with the highest upper confidence bound 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 a = best_act next_s, next_player = self.game.getNextState(canonicalBoard, 1, a) next_s = self.game.getCanonicalForm(next_s, next_player) # Recursively visit the node v = self.search(next_s) |
Part A——選擇具有最高置信區間上界值的走法
一旦找到一個葉子狀態，就把這個棋面狀態送入神經網絡。這是論文中稱作的Part B，“擴展與評估”。且看代碼。
| # leaf node 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]) self.Ps[s] /= sum_Ps_s # renormalize self.Vs[s] = valids self.Ns[s] = 0 |
Part B——擴展與評估
最后，我們將傳回神經網絡返回的值。這就是論文所說的Part C——“備份”。您可以在此處看到相關代碼。
| v = self.search(next_s) 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 |
Part C——備份
讓我們來看看AlphaZero面對上文提及的棋面時會決定如何走。
AlphaZero會進行50次蒙特卡洛樹搜索模擬。
你可以用這個在線notebook復現下面展示的結果。
下面展示的就是每次迭代的路徑：
| Simulation #1 -> Expand root node Simulation #2 -> 23 Simulation #3 -> 21 Simulation #4 -> 9 Simulation #5 -> 17 Simulation #6 -> 12 Simulation #7 -> 19 Simulation #8 -> 3 Simulation #9 -> 18 Simulation #10 -> 23,24 Simulation #11 -> 21,24 Simulation #12 -> 23,24,21 Simulation #13 -> 21,24,23,24 Simulation #14 -> 23,24,9 Simulation #15 -> 23,24,17 Simulation #16 -> 21,24,9 Simulation #17 -> 23,24,12 Simulation #18 -> 23,24,18 Simulation #19 -> 21,24,17 Simulation #20 -> 23,24,21,24,9 Simulation #21 -> 21,24,19 Simulation #22 -> 23,24,3 Simulation #23 -> 21,24,18 Simulation #24 -> 23,24,19 Simulation #25 -> 21,24,23,24,17 Simulation #26 -> 23,24,21,24,18 Simulation #27 -> 23,24,21,24,3 Simulation #28 -> 21,24,3 Simulation #29 -> 23,24,21,24,19 Simulation #30 -> 21,24,12 Simulation #31 -> 23,24,21,24,9,24 Simulation #32 -> 21,24,23,24,12 Simulation #33 -> 23,24,21,24,9,24,18 Simulation #34 -> 21,24,23,24,9,24,17 Simulation #35 -> 23,24,21,24,9,24,12 Simulation #36 -> 23,24,21,24,9,24,3 Simulation #37 -> 21,24,23,24,9,24,19 Simulation #38 -> 23,24,21,24,9,24,18,17 Simulation #39 -> 21,24,23,24,9,24,18,17,24 Simulation #40 -> 23,24,21,24,9,24,18,17,24,19 Simulation #41 -> 21,24,23,24,9,24,18,17,24,19,24 Simulation #42 -> 23,24,9,21 Simulation #43 -> 23,24,9,18 Simulation #44 -> 23,24,9,17 Simulation #45 -> 23,24,9,19 Simulation #46 -> 23,24,9,12 Simulation #47 -> 23,24,9,21,24 Simulation #48 -> 23,24,9,3 Simulation #49 -> 23,24,9,21,24,18 Simulation #50 -> 23,24,9,21,24,17 |
上面顯示的結果的意思是：在第一次模擬中，由于算法之前并未見過這個棋面，因此輸入的棋面實際上是一個“葉子”狀態節點，需要先“擴展”這個節點。所謂擴展就是把棋面送到神經網絡里對每個位置進行概率評估。
| Simulation #1 -> Expand root node |
在第二次模擬中，因為上步我們已經擴展了根節點，因此它不再是一個“葉子”節點了，就此，我們可以對具有最高置信區間上界值的節點進行搜索：
| # https://github.com/suragnair/alpha-zero-general/blob/5156c7fd1d2f3e5fefe732a4b2e0ffc5b272f819/MCTS.py#L105-L121 cur_best = -float('inf') best_act = -1 # pick the action with the highest upper confidence bound 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 a = best_act next_s, next_player = self.game.getNextState(canonicalBoard, 1, a) next_s = self.game.getCanonicalForm(next_s, next_player) # Recursively visit the node v = self.search(next_s) |
具有最大置信區間上界值的是23號位置。搜索算法深入在23號位置畫線的狀態，由于這個狀態在之前搜索算法也沒見過，因此這也是個“葉子”節點狀態，搜索算法會“擴展”這個狀態。就這樣，第二次模擬也完成啦。
| Simulation #2 -> 23 |
這個時候，還記得上面神經網絡輸出的輸贏概率嗎，神經網絡認為在23號位置畫線必輸無疑。神經網絡可以進行更多輪的訓練來確保這的確是個很差的走法。不過目前來說，這就足夠了，我們后面會認識到這一點的。
接下來的模擬中，會依次搜索剩下的走法中具有最大置信區間上界的狀態，不過只有下面給出的這些。因為在訪問完以下這些走法之后，搜索算法會發現剩下的狀態都具有很低的概率，也就是說其置信區間上界都很低，也就不必搜索了。
| Simulation #3 -> 21 Simulation #4 -> 9 Simulation #5 -> 17 Simulation #6 -> 12 Simulation #7 -> 19 Simulation #8 -> 3 Simulation #9 -> 18 |
在之后的模擬中，一個令人興奮的模式逐漸揭開面紗。記住，能夠贏下來的走法序列是23，24（對應空過），9。
（譯者注：填上23號之后，由于補全了一個正方形，因此對方空過。這里給出的序列是兩方的走法序列。）
| Simulation #10 -> 23,24 Simulation #11 -> 21,24 Simulation #12 -> 23,24,21 Simulation #13 -> 21,24,23,24 Simulation #14 -> 23,24,9 Simulation #15 -> 23,24,17 Simulation #16 -> 21,24,9 Simulation #17 -> 23,24,12 Simulation #18 -> 23,24,18 Simulation #19 -> 21,24,17 Simulation #20 -> 23,24,21,24,9 Simulation #21 -> 21,24,19 Simulation #22 -> 23,24,3 Simulation #23 -> 21,24,18 Simulation #24 -> 23,24,19 |
在第10至第24次模擬中，很明顯，MCTS已經把注意力放在了21號節點與23號節點上。這說得通，因為這兩種走法都能讓我方得1分。
| Simulation #33 -> 23,24,21,24,9,24,18 Simulation #34 -> 21,24,23,24,9,24,17 Simulation #35 -> 23,24,21,24,9,24,12 Simulation #36 -> 23,24,21,24,9,24,3 Simulation #37 -> 21,24,23,24,9,24,19 Simulation #38 -> 23,24,21,24,9,24,18,17 Simulation #39 -> 21,24,23,24,9,24,18,17,24 Simulation #40 -> 23,24,21,24,9,24,18,17,24,19 Simulation #41 -> 21,24,23,24,9,24,18,17,24,19,24 |
在第33至第41次模擬中，搜索算法深入探究了那些導致敗局的走法。這里要注意到一件有意思的事情。盡管追究得很深，但是搜索算法并沒有抵達游戲終局，后面還有可以走的步驟。
| Simulation #42 -> 23,24,9,21 Simulation #43 -> 23,24,9,18 Simulation #44 -> 23,24,9,17 Simulation #45 -> 23,24,9,19 Simulation #46 -> 23,24,9,12 Simulation #47 -> 23,24,9,21,24 Simulation #48 -> 23,24,9,3 Simulation #49 -> 23,24,9,21,24,18 Simulation #50 -> 23,24,9,21,24,17 |
接著，在第42次至第50次模擬中，通過神經網絡的場外援助，搜索算法意識到了23，24，21或者21，24，23都不是好的走法，這下子，它全然投入到能夠獲勝的走法序列：23，24，9。
在50次模擬后，是時候做出決定了。MCTS選擇了其訪問次數最多的位置。下面列出了每個走法的訪問次數（只統計路徑中的第一個位置）：
| counts[3] = 1 counts[9] = 1 counts[12] = 1 counts[17] = 1 counts[18] = 1 counts[19] = 1 counts[21] = 15 counts[23] = 28 |
3，9，12，17，18以及19號位置只在最初10次模擬中訪問了1次。接著MCTS專注于21和23號位置，且在最后9次模擬中都先走23號。因為23號位置被訪問次數最多，達到了28次之多，因此MCTS最終返回23作為下一步的走法。
關鍵點是什么？
通過每一次模擬，MCTS依靠神經網絡， 使用累計價值（Q）、神經網絡給出的走法先驗概率（P）以及訪問對應節點的頻率這些數字的組合，沿著最有希望獲勝的路徑（換句話說，也就是具有最高置信區間上界的路徑）進行探索。
在每一次模擬中，MCTS會盡可能向縱深進行探索直至遇到它從未見過的盤面狀態，在這種情況下，它會通過神經網絡來評估該盤面狀態的優劣。
如果我們將上述方法與使用帶有Alpha-Beta剪枝以及一個評價函數的Minimax之類的傳統方法進行比較，我們可以發現以下幾點：
在Minimax中，博弈樹的搜索深度是由算法設計者自行設定的。它無論如何都會搜索到那個深度，然后用那個可愛的評價函數進行盤面評估。要是沒有Alpha-Beta剪枝的話，它就得訪問給定深度下所有可能的盤面節點，極為低效。在上面的情形中，如果還可以走8步，要搜索的深度為3，就意味著總共需要評估336個盤面狀態。使用MCTS，僅僅用了50次模擬，也就是50次評估，而且在搜索中還盡可能搜索得足夠深。
Alpha-Beta剪枝能夠幫助我們將336這個數字減少。然而，卻并不能幫我們找到一條優良的博弈路徑。
我們是一直在用神經網絡來對盤面進行評估的，而不是某個認為定義的評價函數。
很有意思的是，在起初幾步中，神經網絡并沒有做出正確的盤面評估。然而，隨著在博弈樹中搜索的深度提升，它自動修正了它的輸出，而且搜索并未抵達游戲終局。
最后，要注意到AlphaZero的優雅與簡潔。而在Alpha-Beta剪枝中，你的不斷跟蹤alpha和beta參數來知悉哪些路徑被砍掉了，你還得用一個人為定義的評價函數，更不要說這個函數又笨重又丑陋。MCTS與NN讓所有這一切都變得異常優雅與簡潔。你甚至可以在JavaScript中把這一切都搞定！
至此，我們還缺最后一個關鍵部分。究竟該如何訓練這個神經網絡呢？
不要害怕，嘻嘻，賊簡單。我們之前提到的步驟是：
1. 讓計算機在“訓練模式”下自我博弈數局，記錄每一步走棋。一旦勝負已分，就給之前的每一步走棋打上標簽——棋面最終是“贏”或是“輸”。如此一來，我們就獲得了一個可以用于神經網絡（Neural Network，NN）訓練的數據集，讓該網絡學會判斷給定棋面是“贏面”還是“輸面”；
2. 復制神經網絡。用上一步得到的數據集訓練該克隆網絡；
3. 讓克隆網絡與原始神經網絡互相博弈；
4. 上一步中獲勝的網絡留下，敗者棄之；
5. 重復第1步。
什么叫在“訓練模式”下進行博弈呢？這個區別非常細微。當在“競技模式”下博弈時，我們會選擇訪問次數最多的走法。而在“訓練模式”下，在游戲剛開始的一定步數內，我們會將不同走法的訪問次數變成概率分布，以此鼓勵網絡對不同的走法進行探索。舉個例子，假設有3中可能的走法，對應的訪問次數分別是[2, 2, 4]。那么在競技模式中，由于第三種走法的訪問次數最多，所以我們就選擇第三種走法。但是在訓練模式中，我們會將[2, 2, 4]變成一個概率分布，因為2+2+4=8，因此概率分布就是[2/8, 2/8, 4/8] 或者說是 [0.25, 0.25, 0.5]。換句話說，我們在50%的情況下會選擇第三種走法，而第一以及第二種走法有25%的概率被選中。
接著，我們用一個簡單的井字棋來描述一下數據集的構建。
在上面這副圖片中，1號玩家執X獲勝。
我們可以將盤面中未落子的地方記作0，1號玩家打X的位置記作1，2號玩家打圈的地方記作-1。
那么，上圖中的棋盤各個盤面就可以變成下邊這樣：
| 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 -> 0 0 0 -> -1 0 0 -> -1 1 0 -> -1 1 0 -> -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 -1 0 1 |
或者，我們將盤面降為一維表示，就是這樣：
| [0, 0, 0, 0, 0, 0, 0, 0, 0] [1, 0, 0, 0, 0, 0, 0, 0, 0] [1, 0, 0,-1, 0, 0, 0, 0, 0] [1, 0, 0,-1, 1, 0, 0, 0, 0] [1, 0, 0,-1, 1, 0,-1, 0, 0] [1, 0, 0,-1, 1, 0,-1, 0, 1] |
然后我們要做兩件事情。第一件事，找到所有屬于1號玩家輪次的棋盤盤面。我們只會給神經網絡喂入1號玩家的相關盤面數據。在井字棋中，很容易就能挑選出來。而2號玩家輪次的那些盤面，直接將其數據取相反數，使其變為1號玩家視角下的盤面狀態。
也就是，將：
| [0, 0, 0, 0, 0, 0, 0, 0, 0] # Player 1 turn [1, 0, 0, 0, 0, 0, 0, 0, 0] # Player 2 turn [1, 0, 0,-1, 0, 0, 0, 0, 0] # Player 1 turn [1, 0, 0,-1, 1, 0, 0, 0, 0] # Player 2 turn [1, 0, 0,-1, 1, 0,-1, 0, 0] # Player 1 turn [1, 0, 0,-1, 1, 0,-1, 0, 1] # Player 2 turn |
變為：
| [ 0, 0, 0, 0, 0, 0, 0, 0, 0] # Player 1 turn [-1, 0, 0, 0, 0, 0, 0, 0, 0] # Player 1 turn [ 1, 0, 0,-1, 0, 0, 0, 0, 0] # Player 1 turn [-1, 0, 0, 1,-1, 0, 0, 0, 0] # Player 1 turn [ 1, 0, 0,-1, 1, 0,-1, 0, 0] # Player 1 turn [-1, 0, 0, 1,-1, 0, 1, 0,-1] # Player 1 turn |
第二件事，我們對獲得的每一條數據向后增加1位數據，“1”表示1號玩家贏，“-1”表示1號玩家輸。如此一來，數據就變成了：
| [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] # Winning board [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0] # Losing board [ 1, 0, 0,-1, 0, 0, 0, 0, 0, 1] # Winning board [-1, 0, 0, 1,-1, 0, 0, 0, 0, 0] # Losing board [ 1, 0, 0,-1, 1, 0,-1, 0, 0, 1] # Winning board [-1, 0, 0, 1,-1, 0, 1, 0,-1, 0] # Losing board |
嗯，這個數據集現在有模有樣了呢！你看，這樣一來，我們就獲得了一批用于訓練神經網絡的數據，并讓神經網絡學習判斷盤面的輸贏。
哦，我們好像漏掉了概率。那些不同走法的概率分布怎么得到呢？記住了，在訓練模式下，我們每一步也還是會進行MCTS模擬的。正如我們會記錄下不同的盤面，我們也會將對應的概率進行記錄。
然后我們就會復制（或者說是克?。┥窠浘W絡，并用新獲得的數據訓練這個克隆網絡，我們所期望的，是用上新獲得的數據后，這個克隆網絡可以變得更強一點兒。通過與原始網絡進行對抗，我們可以驗證其是否真的變強了。如果克隆網絡的勝率超過55%，我們就把原始網絡丟掉，這個克隆網絡便可取而代之。
這個過程會一直重復下去，神經網絡也在這個過程中不斷變強。
你可以在這兒看到論文中的相關圖表。
數據集中如何包含更多更具代表性的數據呢？相較于神經網絡輸出的原始走法概率分布，數據集會傾向于根據MCTS生成的概率來選擇更具借鑒性的走法。通過讓MCTS搜索足夠多較深的博弈路徑，神經網絡可以獲取更優質的數據并更加高效地學習。
試試看用這個Colab Notebook訓練一個Dots and Boxes模型吧。
幾個月前，我發了一篇博文，帶你大致過了一遍使用TensorFlow.js將Keras或者TensorFlow模型部署至JavaScript的過程。這里我們要做的事情大差不差。我們會把用Keras訓練得到的模型轉換成能夠被TensorFlow.js調用的模型。
這個Notebook展示了如何將一個預訓練的Dots and Boxes博弈模型轉換為一個TensorFlow.js模型。
一旦轉換完成，這個模型就能夠很輕松地使用JavaScript進行調用。不妨看看這里。
在本篇博文中，你認識了AlphaZero，一個能夠在雙方零和博弈的棋盤游戲中戰勝世界冠軍的強化學習算法。
你也了解了它是如何使用蒙特卡洛樹搜索算法以及神經網絡來找到最佳的下一步走法，以及如何訓練這樣一個神經網絡。
AI研習社是AI學術青年和AI開發者技術交流的在線社區。我們與高校、學術機構和產業界合作，通過提供學習、實戰和求職服務，為AI學術青年和開發者的交流互助和職業發展打造一站式平臺，致力成為中國最大的科技創新人才聚集地。
如果，你也是位熱愛分享的AI愛好者。歡迎與譯站一起，學習新知，分享成長。
