0
| 本文作者： AI研習(xí)社-譯站 | 2020-12-02 11:12 |
譯者：AI研習(xí)社（Champagne Jin）
雙語(yǔ)原文鏈接：AlphaZero, a novel Reinforcement Learning Algorithm, in JavaScript
在本篇博文中，你將會(huì)了解并實(shí)現(xiàn)AlphaZero。AlphaZero是一個(gè)令人大開(kāi)眼界且超乎尋常的強(qiáng)化學(xué)習(xí)算法，它以絕對(duì)的優(yōu)勢(shì)戰(zhàn)勝了多名圍棋以及國(guó)際象棋冠軍。本文將會(huì)帶你使用AlphaZero來(lái)解決一個(gè)益智小游戲（Dots and Boxes）并將其部署成一個(gè)純JavaScript構(gòu)建的Web應(yīng)用。
AlphaZero最關(guān)鍵也是最令人詫異的一點(diǎn)，就是其能夠在不依賴于外部先驗(yàn)知識(shí)的情況下在棋盤類游戲中獲得超越人類的表現(xiàn)。AlphaZero通過(guò)自我博弈汲取經(jīng)驗(yàn)知識(shí)來(lái)不斷精通游戲。
我們會(huì)借助于Github上由Surag Nair開(kāi)發(fā)的一個(gè)“簡(jiǎn)化后的、高度靈活的、經(jīng)過(guò)注釋的且易于理解的”Python版AlphaZero來(lái)進(jìn)行該項(xiàng)目。
你大可以先去這里玩一玩這個(gè)游戲。而Web應(yīng)用以及具體的JavaScript實(shí)現(xiàn)代碼可以在這里獲取得到。這份代碼是從該P(yáng)ython實(shí)現(xiàn)中移植過(guò)來(lái)的。
https://carlos-aguayo.github.io/alphazero/
有關(guān)AlphaZero的原理，你可以閱讀這篇由Silver，David等人撰寫的論文：“Mastering the game of Go without human knowledge” nature 550.7676 (2017): 354–359.
Dots and Boxes是一個(gè)常見(jiàn)的兒童益智游戲，不過(guò)其具有令人訝異的復(fù)雜度。
該游戲中，兩名玩家輪流在兩個(gè)相鄰點(diǎn)之間放置一條水平或垂直線。如果某個(gè) 1×1 的小正方形的 4 條邊都被連上了，那么補(bǔ)齊這個(gè)小方塊的一方就獲得 1 分，得分的玩家被獎(jiǎng)勵(lì)多走一步，再連一條線。當(dāng)棋盤已滿時(shí)，游戲結(jié)束，并且得分最高的玩家獲勝。
（譯者注：這個(gè)游戲相當(dāng)有意思，建議先去玩玩看，點(diǎn)這里。能不能戰(zhàn)勝AlphaZero就看你了！）
機(jī)器是否能夠產(chǎn)生智能，我們已經(jīng)為此思考了很久很久。那么，該如何驗(yàn)證機(jī)器具有智能呢？一個(gè)常用方法就是玩棋盤游戲，比如國(guó)際象棋，看看其是否具有超人的能力，甚至擊敗世界冠軍。
1957年，Herbert Simon預(yù)言計(jì)算機(jī)系統(tǒng)能夠在十年內(nèi)擊敗國(guó)際象棋冠軍。雖說(shuō)實(shí)際上花的時(shí)間長(zhǎng)了點(diǎn)，但是在1997年5月，計(jì)算機(jī)擊敗了當(dāng)時(shí)的國(guó)際象棋冠軍——Garry Kasparov。
（譯者注：戰(zhàn)勝Kasparov的機(jī)器被命名為DeepBlue，意為“深藍(lán)”）
盡管這一里程碑事件意義非凡，但人們?nèi)钥梢誀?zhēng)論這一計(jì)算機(jī)系統(tǒng)是否“智能”。
這一類計(jì)算機(jī)系統(tǒng)由以下三個(gè)組件構(gòu)成：
1. 人為定義的評(píng)價(jià)函數(shù)；
2. 博弈樹搜索算法；
3. 極為強(qiáng)悍的硬件設(shè)備。
評(píng)價(jià)函數(shù)會(huì)將棋盤盤面作為輸入并輸出該盤面的“價(jià)值”。高價(jià)值表示當(dāng)前玩家處于非常有利的位置。例如，在國(guó)際象棋棋盤上，玩家即將進(jìn)行“將死”時(shí)就會(huì)對(duì)應(yīng)一個(gè)非常高的值。
博弈樹搜索算法（比如 Minimax）在所有可能的走棋中進(jìn)行搜索，尋找那些能夠確保得到高價(jià)值棋盤盤面的路徑。對(duì)于那些已經(jīng)明知不可能有效的路徑可以直接放棄搜索，從而使算法變得更有效率。這就是 Alpha-beta剪枝 的作用。
最后，搭配上異常強(qiáng)悍的硬件，你就將擁有一臺(tái)能夠打敗國(guó)際象棋世界冠軍的機(jī)器。
問(wèn)題在哪兒？經(jīng)驗(yàn)豐富的棋手人為地精心調(diào)制這些評(píng)價(jià)函數(shù)。這些計(jì)算機(jī)系統(tǒng)還依賴于一本本記錄著最佳走棋的開(kāi)局棋譜。游戲中局，還會(huì)用到通過(guò)研究大師們的博弈而精心構(gòu)造的評(píng)價(jià)函數(shù)。這些函數(shù)還會(huì)經(jīng)由象棋大師們進(jìn)一步的優(yōu)化調(diào)整。
例如，我們完全就可以為 Dots and Boxes 構(gòu)造一個(gè)評(píng)價(jià)函數(shù)。一個(gè)合理而直接的選擇就是做一個(gè)得分的比較。得分的正向差值越大，游戲盤面就對(duì)我們?cè)接欣?。大多?shù)情況下，這是可行的。然而，在 Dots and Boxes 中，就像許多其他棋盤類游戲一樣，最佳的走法可能需要犧牲短期利益來(lái)?yè)Q取長(zhǎng)期利益。在 Dots and Boxes 游戲中，有時(shí)最好不要急于得分并獲得額外先手，相反，要迫使對(duì)手走某一步棋。因此，我們必須考慮大量復(fù)雜場(chǎng)景并精心調(diào)制評(píng)價(jià)函數(shù)！
擊敗Kasparov的評(píng)價(jià)函數(shù)需要識(shí)別多達(dá)8000個(gè)盤面特征！而且其中絕大多數(shù)都是手動(dòng)描述并調(diào)整的！
所以，倒也不是貶低這個(gè)擊敗國(guó)際象棋世界冠軍重要里程碑的意思，只是，需要頂級(jí)玩家來(lái)定義這些計(jì)算機(jī)的行為并手動(dòng)調(diào)整如此多的變量實(shí)在是有夠折騰人的。
AlphaZero是首個(gè)能夠在國(guó)際象棋、圍棋等游戲中達(dá)到超越人類水平、擊敗世界冠軍的計(jì)算機(jī)系統(tǒng)，且它僅依賴于游戲規(guī)則，無(wú)需任何人類先驗(yàn)知識(shí)。
僅憑給定的游戲規(guī)則，AlphaZero即可進(jìn)行自我博弈。逐步習(xí)得游戲策略與技巧，很快即可獲得超人的表現(xiàn)。
像DeepBlue這樣的系統(tǒng)會(huì)需要國(guó)際象棋專家的協(xié)助，而AlphaZero卻是憑借自我博弈來(lái)變強(qiáng)大的。不單單是在國(guó)際象棋上，哪怕是圍棋，AlphaZero同樣表現(xiàn)出超越人類的強(qiáng)大統(tǒng)治力?？紤]到圍棋相較于其他棋盤游戲更大的博弈空間等因素，對(duì)計(jì)算機(jī)來(lái)說(shuō)，圍棋是個(gè)極為復(fù)雜的游戲。
人類從幾千年來(lái)數(shù)百萬(wàn)次的博弈中方才積累了諸如圍棋和國(guó)際象棋等游戲的技藝，而AlphaZero，一個(gè)僅使用游戲規(guī)則信息的算法，卻能夠在幾天時(shí)間內(nèi)重新尋獲這些知識(shí)并發(fā)現(xiàn)新的游戲策略。
甚至還有一部關(guān)于它的紀(jì)錄片。
（譯者注：這部紀(jì)錄片很值得一看，無(wú)法訪問(wèn)YouTube的同學(xué)可以在B站觀看，鏈接在此。不過(guò)需要注明的是，本紀(jì)錄片中實(shí)際上使用的是AlphaGo算法，而非AlphaZero，準(zhǔn)確來(lái)說(shuō)，AlphaZero是AlphaGo的進(jìn)階版本，全名為AlphaGo Zero。紀(jì)錄片中與李世石博弈的AlphaGo在跟AlphaGo Zero 博弈時(shí)，0-100全負(fù)，并且，AlphaGo Zero在訓(xùn)練中未使用任何手工設(shè)計(jì)的特征或者圍棋領(lǐng)域的專業(yè)知識(shí)，僅僅以歷史棋面作為輸入，其訓(xùn)練數(shù)據(jù)全部來(lái)自于自我博弈?？芍^恐怖如斯?。?/span>
回想一下，像DeepBlue那樣依賴于人為定義的“評(píng)價(jià)函數(shù)”的系統(tǒng)會(huì)把棋盤的盤面狀態(tài)作為輸入，再輸出該狀態(tài)的“價(jià)值”。
如今，對(duì)于深度學(xué)習(xí)模型來(lái)說(shuō)，輸入一張照片然后識(shí)別出照片里是貓還是狗簡(jiǎn)直簡(jiǎn)單到爆了。那么有個(gè)想法就是，把棋盤盤面作為一個(gè)深度學(xué)習(xí)模型的輸入并且訓(xùn)練它，讓它預(yù)測(cè)這樣的盤面布置是會(huì)輸還是會(huì)贏。
但是，要訓(xùn)練一個(gè)機(jī)器學(xué)習(xí)模型，就需要數(shù)據(jù)，海量的數(shù)據(jù)。從哪兒能得到那么多棋局博弈的數(shù)據(jù)呢？很簡(jiǎn)單，我們就讓電腦自己跟自己下著玩兒，生成一堆棋局，然后再把它們做成一個(gè)數(shù)據(jù)集用來(lái)訓(xùn)練。
這個(gè)算法簡(jiǎn)單明了：
1. 讓計(jì)算機(jī)自我博弈數(shù)局，記錄每一步走棋。一旦勝負(fù)已分，就給之前的每一步走棋打上標(biāo)簽——棋面最終是“贏”或是“輸”。如此一來(lái)，我們就獲得了一個(gè)可以用于神經(jīng)網(wǎng)絡(luò)（Neural Network，NN）訓(xùn)練的數(shù)據(jù)集，讓該網(wǎng)絡(luò)學(xué)會(huì)判斷給定棋面是“贏面”還是“輸面”；
2. 復(fù)制這個(gè)神經(jīng)網(wǎng)絡(luò)。用上一步得到的數(shù)據(jù)集訓(xùn)練該克隆網(wǎng)絡(luò)；
3. 讓克隆網(wǎng)絡(luò)與原始神經(jīng)網(wǎng)絡(luò)互相博弈；
4. 上一步中獲勝的網(wǎng)絡(luò)留下，敗者棄之；
5. 重復(fù)第1步。
呼哈，就像是魔法似的，經(jīng)過(guò)多輪迭代后，你就將獲得一個(gè)世界級(jí)模型。這個(gè)模型在短短4小時(shí)內(nèi)便超越了最強(qiáng)大的計(jì)算機(jī)象棋程序。
AlphaZero由兩部分構(gòu)成。我們已經(jīng)提及了第一部分，就是神經(jīng)網(wǎng)絡(luò)。第二部分則是“蒙特卡洛樹搜索（Monte Carlo Tree Search）”，或者簡(jiǎn)稱MCTS。
1. 神經(jīng)網(wǎng)絡(luò)（NN）。以棋面作為輸入，輸出該棋面的“價(jià)值”，外加所有可能走法的概率分布。
2. 蒙特卡洛樹搜索（MCTS）。理想情況下，使用神經(jīng)網(wǎng)絡(luò)就足以選擇下一步走法了。不過(guò)，我們?nèi)匀幌Ｍ紤]盡可能多的棋面，并確保我們的的確確選擇了最好的走法。MTCS和Minimax一樣，是一種可以幫助我們尋找可能棋面的算法。與Minimax不同的是，MTCS能夠幫助我們更加高效地搜尋博弈樹。
我們不妨先看看AlphaZero在決定下一步走棋（競(jìng)技模式）時(shí)具體干了什么，然后再去探究它的訓(xùn)練過(guò)程，這樣可以幫助我們更容易地理解AlphaZero。
神經(jīng)網(wǎng)絡(luò)在分類這件事兒上表現(xiàn)得異常出色，例如區(qū)分貓跟狗。所以這里的想法很簡(jiǎn)單直接，神經(jīng)網(wǎng)絡(luò)能學(xué)會(huì)區(qū)分棋局輸贏的類別嗎？更具體地來(lái)說(shuō)，就是讓神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)一個(gè)表示棋局輸贏概率的數(shù)值。此外，它還將輸出所有可能走法的概率分布，來(lái)表示我們下一步應(yīng)該如何決策。
神經(jīng)網(wǎng)絡(luò)將博弈狀態(tài)作為輸入并輸出一個(gè)輸贏概率數(shù)值以及所有可能走法的概率分布。對(duì)于Dots and boxes這個(gè)小游戲來(lái)說(shuō)，游戲狀態(tài)由三個(gè)元素表示：首先，某一條線是否已被占用，這可以用一個(gè)含有0與1的數(shù)組來(lái)表示，如果玩家已經(jīng)畫了某條線，則置其為1，否則為0；第二，當(dāng)前的走法是否是空過(guò)；第三，雙方玩家的得分。我們可以用這三個(gè)元素來(lái)表示所有需要的信息，用其計(jì)算當(dāng)前盤面的價(jià)值并預(yù)測(cè)下一步的走法。
讓我們分析一下下圖中的博弈情形，該輪輪到藍(lán)色玩家走。藍(lán)色方有兩個(gè)選擇，按照?qǐng)D中上面的走法來(lái)畫線就會(huì)輸，按照下面的走法就會(huì)贏。
（譯者注：左下角是每根線的編號(hào)。如果你剛剛已經(jīng)在網(wǎng)頁(yè)上跟AlphaZero玩過(guò)這個(gè)游戲了，那么相信這張圖是很容易理解的。上方第一種走法只顧眼前短期利益，最終葬送好局。）
如果藍(lán)色方走23再走21，那么紅色方必贏。然而，如果藍(lán)色方走23后再走9，那藍(lán)色方就贏了。要是AlphaZero在藍(lán)色方，它怎么知道哪一種走法能夠贏下來(lái)呢？
你可以用這個(gè)在線notebook復(fù)現(xiàn)我們即將呈現(xiàn)的效果。
將棋面送入神經(jīng)網(wǎng)絡(luò)，我們就能得到下一步走在不同位置的概率：
| 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 |
同時(shí)，我們還能得到當(dāng)前棋局的贏面有多大：
| -0.99761635 |
你可以在這里查閱與這些輸出相關(guān)的代碼。
這些輸出值有一些很有意思的地方，我們來(lái)細(xì)品一下：
在所有可能畫線的位置，23號(hào)、21號(hào)以及9號(hào)的概率值最大。如果神經(jīng)網(wǎng)絡(luò)選擇在23號(hào)以及21號(hào)位置處畫線，那么它就能夠得到1分。另外，23號(hào)才是能夠贏下來(lái)的走法，而相應(yīng)地，從網(wǎng)絡(luò)輸出的概率來(lái)看，23號(hào)位置的概率（0.53）恰好比21號(hào)的（0.46）稍微高一點(diǎn)兒。
神經(jīng)網(wǎng)絡(luò)也會(huì)給不能夠畫線的位置輸出一個(gè)概率值。雖然如此，但是代碼上還是要進(jìn)行限制，以確保計(jì)算機(jī)不會(huì)在不合規(guī)則的位置畫線。
棋面的輸贏概率為-0.99。這意味著AlphaZero認(rèn)為它已經(jīng)輸?shù)粲螒蛄?。這個(gè)概率值的范圍是-1（輸）到1（贏）。這個(gè)值本應(yīng)該很接近于1（贏）而不是-1（輸）的，畢竟我們知道目前這個(gè)局面贏面很大。也許我們應(yīng)該多訓(xùn)練幾輪來(lái)讓AlphaZero準(zhǔn)確預(yù)估棋面的輸贏概率。
我們很容易利用神經(jīng)網(wǎng)絡(luò)的輸出來(lái)決定下一步的走法。
在棋盤游戲中（現(xiàn)實(shí)生活中也是），玩家在決定下一步怎么走的時(shí)候往往會(huì)“多想幾步”。AlphaZero也一樣。我們用神經(jīng)網(wǎng)絡(luò)來(lái)選擇最佳的下一步走法后，其余低概率的位置就被忽略掉了。像Minimax這一類傳統(tǒng)的AI博弈樹搜索算法效率都很低，因?yàn)檫@些算法在做出最終選擇前需要窮盡每一種走法。即使是帶有較少分支因子的游戲也會(huì)使其博弈搜索空間變得像是脫韁的野馬似的難以駕馭。分支因子就是所有可能的走法的數(shù)量。這個(gè)數(shù)量會(huì)隨著游戲的進(jìn)行不斷變化。因此，你可以試著計(jì)算一個(gè)平均分支因子數(shù)，國(guó)際象棋的平均分支因子是35，而圍棋則是250。
這意味著，在國(guó)際象棋中，僅走兩步就有1,225（352）種可能的棋面，而在圍棋中，這個(gè)數(shù)字會(huì)變成62,500（2502）。在Dots and Boxes游戲中，對(duì)于一個(gè)3×3大小的棋盤，初始的分支因子數(shù)是24，隨著棋盤不斷被填充，這個(gè)數(shù)字會(huì)不斷減少（除非空過(guò)）。所以，在行至中局，分支因子變?yōu)?5的時(shí)候，僅走3步就會(huì)有多達(dá)2730（15*14*13）種可能的棋面。
現(xiàn)在，時(shí)代變了，神經(jīng)網(wǎng)絡(luò)將指導(dǎo)并告訴我們哪些博弈路徑值得探索，從而避免被許多無(wú)用的搜索路徑所淹沒(méi)。現(xiàn)在神經(jīng)網(wǎng)絡(luò)告訴我們23號(hào)和21號(hào)都是非常值得一探究竟的走法。
接著，蒙特卡洛樹搜索算法就將登場(chǎng)啦！
神經(jīng)網(wǎng)絡(luò)為我們指示了下一步可能的走法。蒙特卡洛樹搜索算法將幫助我們遍歷這些節(jié)點(diǎn)來(lái)最終選擇下一步的走法。
去這個(gè)鏈接看看論文中有關(guān)蒙特卡洛樹搜索的圖形化描述。
使用MCTS的具體做法是這樣的，給定一個(gè)棋面，MCTS共進(jìn)行N次模擬。N是模型的超參數(shù)。N次模擬結(jié)束后，下一步的走法將是這N次模擬中所經(jīng)次數(shù)最多的一步。你可以由這里的代碼一窺究竟：
| # 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 |
進(jìn)行N次MCTS模擬
一次MCTS模擬從當(dāng)前的棋盤狀態(tài)出發(fā)，沿著博弈樹中具有最大“置信區(qū)間上界（UCB）”值（后文會(huì)給出定義）的節(jié)點(diǎn)不斷向下追溯，直到遇到之前從未見(jiàn)過(guò)的棋盤狀態(tài)，也叫做“葉子”狀態(tài)。這就是原論文中Part A所謂的“選擇（Select）”。
置信區(qū)間上界是什么呢？用數(shù)學(xué)形式來(lái)說(shuō)就是 Q(s, a) + U(s, a)。其中 s 是狀態(tài)，a 是走法。Q(s, a) 是我們希望由走法“a”構(gòu)成狀態(tài)“s”能夠獲得的期望值，與Q-Learning中的期望值一致。記住了，在這種情況下，該值的范圍是-1（輸）到1（贏）。U(s, a) ∝ P(s, a) / (1 + N(s, a))。這意味著U正比于P和N。其中，P(s, a) 是元組 (s, a) 的先驗(yàn)概率值，這個(gè)值是從神經(jīng)網(wǎng)絡(luò)那里得到的，而 N(s, a) 是已經(jīng)訪問(wèn)過(guò)狀態(tài) s 與對(duì)應(yīng)的走法 a 的次數(shù)。
| # Upper Confidence Bound ucb = Qsa[(s,a)] + Ps[s,a] * sqrt(Ns[s]) / (1 + Nsa[(s,a)] |
UCB的要點(diǎn)在于，其起初更傾向于具有較高先驗(yàn)概率（P）和較低訪問(wèn)次數(shù)（N）的走法，但漸漸地會(huì)傾向于具有較高動(dòng)作價(jià)值（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——選擇具有最高置信區(qū)間上界值的走法
一旦找到一個(gè)葉子狀態(tài)，就把這個(gè)棋面狀態(tài)送入神經(jīng)網(wǎng)絡(luò)。這是論文中稱作的Part B，“擴(kuò)展與評(píng)估”。且看代碼。
| # 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——擴(kuò)展與評(píng)估
最后，我們將傳回神經(jīng)網(wǎng)絡(luò)返回的值。這就是論文所說(shuō)的Part C——“備份”。您可以在此處看到相關(guān)代碼。
| 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——備份
讓我們來(lái)看看AlphaZero面對(duì)上文提及的棋面時(shí)會(huì)決定如何走。
AlphaZero會(huì)進(jìn)行50次蒙特卡洛樹搜索模擬。
你可以用這個(gè)在線notebook復(fù)現(xiàn)下面展示的結(jié)果。
下面展示的就是每次迭代的路徑：
| 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 |
上面顯示的結(jié)果的意思是：在第一次模擬中，由于算法之前并未見(jiàn)過(guò)這個(gè)棋面，因此輸入的棋面實(shí)際上是一個(gè)“葉子”狀態(tài)節(jié)點(diǎn)，需要先“擴(kuò)展”這個(gè)節(jié)點(diǎn)。所謂擴(kuò)展就是把棋面送到神經(jīng)網(wǎng)絡(luò)里對(duì)每個(gè)位置進(jìn)行概率評(píng)估。
| Simulation #1 -> Expand root node |
在第二次模擬中，因?yàn)樯喜轿覀円呀?jīng)擴(kuò)展了根節(jié)點(diǎn)，因此它不再是一個(gè)“葉子”節(jié)點(diǎn)了，就此，我們可以對(duì)具有最高置信區(qū)間上界值的節(jié)點(diǎn)進(jìn)行搜索：
| # 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) |
具有最大置信區(qū)間上界值的是23號(hào)位置。搜索算法深入在23號(hào)位置畫線的狀態(tài)，由于這個(gè)狀態(tài)在之前搜索算法也沒(méi)見(jiàn)過(guò)，因此這也是個(gè)“葉子”節(jié)點(diǎn)狀態(tài)，搜索算法會(huì)“擴(kuò)展”這個(gè)狀態(tài)。就這樣，第二次模擬也完成啦。
| Simulation #2 -> 23 |
這個(gè)時(shí)候，還記得上面神經(jīng)網(wǎng)絡(luò)輸出的輸贏概率嗎，神經(jīng)網(wǎng)絡(luò)認(rèn)為在23號(hào)位置畫線必輸無(wú)疑。神經(jīng)網(wǎng)絡(luò)可以進(jìn)行更多輪的訓(xùn)練來(lái)確保這的確是個(gè)很差的走法。不過(guò)目前來(lái)說(shuō)，這就足夠了，我們后面會(huì)認(rèn)識(shí)到這一點(diǎn)的。
接下來(lái)的模擬中，會(huì)依次搜索剩下的走法中具有最大置信區(qū)間上界的狀態(tài)，不過(guò)只有下面給出的這些。因?yàn)樵谠L問(wèn)完以下這些走法之后，搜索算法會(huì)發(fā)現(xiàn)剩下的狀態(tài)都具有很低的概率，也就是說(shuō)其置信區(qū)間上界都很低，也就不必搜索了。
| Simulation #3 -> 21 Simulation #4 -> 9 Simulation #5 -> 17 Simulation #6 -> 12 Simulation #7 -> 19 Simulation #8 -> 3 Simulation #9 -> 18 |
在之后的模擬中，一個(gè)令人興奮的模式逐漸揭開(kāi)面紗。記住，能夠贏下來(lái)的走法序列是23，24（對(duì)應(yīng)空過(guò)），9。
（譯者注：填上23號(hào)之后，由于補(bǔ)全了一個(gè)正方形，因此對(duì)方空過(guò)。這里給出的序列是兩方的走法序列。）
| 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已經(jīng)把注意力放在了21號(hào)節(jié)點(diǎn)與23號(hào)節(jié)點(diǎn)上。這說(shuō)得通，因?yàn)檫@兩種走法都能讓我方得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次模擬中，搜索算法深入探究了那些導(dǎo)致敗局的走法。這里要注意到一件有意思的事情。盡管追究得很深，但是搜索算法并沒(méi)有抵達(dá)游戲終局，后面還有可以走的步驟。
| 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次模擬中，通過(guò)神經(jīng)網(wǎng)絡(luò)的場(chǎng)外援助，搜索算法意識(shí)到了23，24，21或者21，24，23都不是好的走法，這下子，它全然投入到能夠獲勝的走法序列：23，24，9。
在50次模擬后，是時(shí)候做出決定了。MCTS選擇了其訪問(wèn)次數(shù)最多的位置。下面列出了每個(gè)走法的訪問(wèn)次數(shù)（只統(tǒng)計(jì)路徑中的第一個(gè)位置）：
| 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號(hào)位置只在最初10次模擬中訪問(wèn)了1次。接著MCTS專注于21和23號(hào)位置，且在最后9次模擬中都先走23號(hào)。因?yàn)?3號(hào)位置被訪問(wèn)次數(shù)最多，達(dá)到了28次之多，因此MCTS最終返回23作為下一步的走法。
關(guān)鍵點(diǎn)是什么？
通過(guò)每一次模擬，MCTS依靠神經(jīng)網(wǎng)絡(luò)， 使用累計(jì)價(jià)值（Q）、神經(jīng)網(wǎng)絡(luò)給出的走法先驗(yàn)概率（P）以及訪問(wèn)對(duì)應(yīng)節(jié)點(diǎn)的頻率這些數(shù)字的組合，沿著最有希望獲勝的路徑（換句話說(shuō)，也就是具有最高置信區(qū)間上界的路徑）進(jìn)行探索。
在每一次模擬中，MCTS會(huì)盡可能向縱深進(jìn)行探索直至遇到它從未見(jiàn)過(guò)的盤面狀態(tài)，在這種情況下，它會(huì)通過(guò)神經(jīng)網(wǎng)絡(luò)來(lái)評(píng)估該盤面狀態(tài)的優(yōu)劣。
如果我們將上述方法與使用帶有Alpha-Beta剪枝以及一個(gè)評(píng)價(jià)函數(shù)的Minimax之類的傳統(tǒng)方法進(jìn)行比較，我們可以發(fā)現(xiàn)以下幾點(diǎn)：
在Minimax中，博弈樹的搜索深度是由算法設(shè)計(jì)者自行設(shè)定的。它無(wú)論如何都會(huì)搜索到那個(gè)深度，然后用那個(gè)可愛(ài)的評(píng)價(jià)函數(shù)進(jìn)行盤面評(píng)估。要是沒(méi)有Alpha-Beta剪枝的話，它就得訪問(wèn)給定深度下所有可能的盤面節(jié)點(diǎn)，極為低效。在上面的情形中，如果還可以走8步，要搜索的深度為3，就意味著總共需要評(píng)估336個(gè)盤面狀態(tài)。使用MCTS，僅僅用了50次模擬，也就是50次評(píng)估，而且在搜索中還盡可能搜索得足夠深。
Alpha-Beta剪枝能夠幫助我們將336這個(gè)數(shù)字減少。然而，卻并不能幫我們找到一條優(yōu)良的博弈路徑。
我們是一直在用神經(jīng)網(wǎng)絡(luò)來(lái)對(duì)盤面進(jìn)行評(píng)估的，而不是某個(gè)認(rèn)為定義的評(píng)價(jià)函數(shù)。
很有意思的是，在起初幾步中，神經(jīng)網(wǎng)絡(luò)并沒(méi)有做出正確的盤面評(píng)估。然而，隨著在博弈樹中搜索的深度提升，它自動(dòng)修正了它的輸出，而且搜索并未抵達(dá)游戲終局。
最后，要注意到AlphaZero的優(yōu)雅與簡(jiǎn)潔。而在Alpha-Beta剪枝中，你的不斷跟蹤alpha和beta參數(shù)來(lái)知悉哪些路徑被砍掉了，你還得用一個(gè)人為定義的評(píng)價(jià)函數(shù)，更不要說(shuō)這個(gè)函數(shù)又笨重又丑陋。MCTS與NN讓所有這一切都變得異常優(yōu)雅與簡(jiǎn)潔。你甚至可以在JavaScript中把這一切都搞定！
至此，我們還缺最后一個(gè)關(guān)鍵部分。究竟該如何訓(xùn)練這個(gè)神經(jīng)網(wǎng)絡(luò)呢？
不要害怕，嘻嘻，賊簡(jiǎn)單。我們之前提到的步驟是：
1. 讓計(jì)算機(jī)在“訓(xùn)練模式”下自我博弈數(shù)局，記錄每一步走棋。一旦勝負(fù)已分，就給之前的每一步走棋打上標(biāo)簽——棋面最終是“贏”或是“輸”。如此一來(lái)，我們就獲得了一個(gè)可以用于神經(jīng)網(wǎng)絡(luò)（Neural Network，NN）訓(xùn)練的數(shù)據(jù)集，讓該網(wǎng)絡(luò)學(xué)會(huì)判斷給定棋面是“贏面”還是“輸面”；
2. 復(fù)制神經(jīng)網(wǎng)絡(luò)。用上一步得到的數(shù)據(jù)集訓(xùn)練該克隆網(wǎng)絡(luò)；
3. 讓克隆網(wǎng)絡(luò)與原始神經(jīng)網(wǎng)絡(luò)互相博弈；
4. 上一步中獲勝的網(wǎng)絡(luò)留下，敗者棄之；
5. 重復(fù)第1步。
什么叫在“訓(xùn)練模式”下進(jìn)行博弈呢？這個(gè)區(qū)別非常細(xì)微。當(dāng)在“競(jìng)技模式”下博弈時(shí)，我們會(huì)選擇訪問(wèn)次數(shù)最多的走法。而在“訓(xùn)練模式”下，在游戲剛開(kāi)始的一定步數(shù)內(nèi)，我們會(huì)將不同走法的訪問(wèn)次數(shù)變成概率分布，以此鼓勵(lì)網(wǎng)絡(luò)對(duì)不同的走法進(jìn)行探索。舉個(gè)例子，假設(shè)有3中可能的走法，對(duì)應(yīng)的訪問(wèn)次數(shù)分別是[2, 2, 4]。那么在競(jìng)技模式中，由于第三種走法的訪問(wèn)次數(shù)最多，所以我們就選擇第三種走法。但是在訓(xùn)練模式中，我們會(huì)將[2, 2, 4]變成一個(gè)概率分布，因?yàn)?+2+4=8，因此概率分布就是[2/8, 2/8, 4/8] 或者說(shuō)是 [0.25, 0.25, 0.5]。換句話說(shuō)，我們?cè)?0%的情況下會(huì)選擇第三種走法，而第一以及第二種走法有25%的概率被選中。
接著，我們用一個(gè)簡(jiǎn)單的井字棋來(lái)描述一下數(shù)據(jù)集的構(gòu)建。
在上面這副圖片中，1號(hào)玩家執(zhí)X獲勝。
我們可以將盤面中未落子的地方記作0，1號(hào)玩家打X的位置記作1，2號(hào)玩家打圈的地方記作-1。
那么，上圖中的棋盤各個(gè)盤面就可以變成下邊這樣：
| 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號(hào)玩家輪次的棋盤盤面。我們只會(huì)給神經(jīng)網(wǎng)絡(luò)喂入1號(hào)玩家的相關(guān)盤面數(shù)據(jù)。在井字棋中，很容易就能挑選出來(lái)。而2號(hào)玩家輪次的那些盤面，直接將其數(shù)據(jù)取相反數(shù)，使其變?yōu)?號(hào)玩家視角下的盤面狀態(tài)。
也就是，將：
| [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 |
變?yōu)椋?/p>
| [ 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 |
第二件事，我們對(duì)獲得的每一條數(shù)據(jù)向后增加1位數(shù)據(jù)，“1”表示1號(hào)玩家贏，“-1”表示1號(hào)玩家輸。如此一來(lái)，數(shù)據(jù)就變成了：
| [ 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 |
嗯，這個(gè)數(shù)據(jù)集現(xiàn)在有模有樣了呢！你看，這樣一來(lái)，我們就獲得了一批用于訓(xùn)練神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)，并讓神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)判斷盤面的輸贏。
哦，我們好像漏掉了概率。那些不同走法的概率分布怎么得到呢？記住了，在訓(xùn)練模式下，我們每一步也還是會(huì)進(jìn)行MCTS模擬的。正如我們會(huì)記錄下不同的盤面，我們也會(huì)將對(duì)應(yīng)的概率進(jìn)行記錄。
然后我們就會(huì)復(fù)制（或者說(shuō)是克?。┥窠?jīng)網(wǎng)絡(luò)，并用新獲得的數(shù)據(jù)訓(xùn)練這個(gè)克隆網(wǎng)絡(luò)，我們所期望的，是用上新獲得的數(shù)據(jù)后，這個(gè)克隆網(wǎng)絡(luò)可以變得更強(qiáng)一點(diǎn)兒。通過(guò)與原始網(wǎng)絡(luò)進(jìn)行對(duì)抗，我們可以驗(yàn)證其是否真的變強(qiáng)了。如果克隆網(wǎng)絡(luò)的勝率超過(guò)55%，我們就把原始網(wǎng)絡(luò)丟掉，這個(gè)克隆網(wǎng)絡(luò)便可取而代之。
這個(gè)過(guò)程會(huì)一直重復(fù)下去，神經(jīng)網(wǎng)絡(luò)也在這個(gè)過(guò)程中不斷變強(qiáng)。
你可以在這兒看到論文中的相關(guān)圖表。
數(shù)據(jù)集中如何包含更多更具代表性的數(shù)據(jù)呢？相較于神經(jīng)網(wǎng)絡(luò)輸出的原始走法概率分布，數(shù)據(jù)集會(huì)傾向于根據(jù)MCTS生成的概率來(lái)選擇更具借鑒性的走法。通過(guò)讓MCTS搜索足夠多較深的博弈路徑，神經(jīng)網(wǎng)絡(luò)可以獲取更優(yōu)質(zhì)的數(shù)據(jù)并更加高效地學(xué)習(xí)。
試試看用這個(gè)Colab Notebook訓(xùn)練一個(gè)Dots and Boxes模型吧。
幾個(gè)月前，我發(fā)了一篇博文，帶你大致過(guò)了一遍使用TensorFlow.js將Keras或者TensorFlow模型部署至JavaScript的過(guò)程。這里我們要做的事情大差不差。我們會(huì)把用Keras訓(xùn)練得到的模型轉(zhuǎn)換成能夠被TensorFlow.js調(diào)用的模型。
這個(gè)Notebook展示了如何將一個(gè)預(yù)訓(xùn)練的Dots and Boxes博弈模型轉(zhuǎn)換為一個(gè)TensorFlow.js模型。
一旦轉(zhuǎn)換完成，這個(gè)模型就能夠很輕松地使用JavaScript進(jìn)行調(diào)用。不妨看看這里。
在本篇博文中，你認(rèn)識(shí)了AlphaZero，一個(gè)能夠在雙方零和博弈的棋盤游戲中戰(zhàn)勝世界冠軍的強(qiáng)化學(xué)習(xí)算法。
你也了解了它是如何使用蒙特卡洛樹搜索算法以及神經(jīng)網(wǎng)絡(luò)來(lái)找到最佳的下一步走法，以及如何訓(xùn)練這樣一個(gè)神經(jīng)網(wǎng)絡(luò)。
AI研習(xí)社是AI學(xué)術(shù)青年和AI開(kāi)發(fā)者技術(shù)交流的在線社區(qū)。我們與高校、學(xué)術(shù)機(jī)構(gòu)和產(chǎn)業(yè)界合作，通過(guò)提供學(xué)習(xí)、實(shí)戰(zhàn)和求職服務(wù)，為AI學(xué)術(shù)青年和開(kāi)發(fā)者的交流互助和職業(yè)發(fā)展打造一站式平臺(tái)，致力成為中國(guó)最大的科技創(chuàng)新人才聚集地。
如果，你也是位熱愛(ài)分享的AI愛(ài)好者。歡迎與譯站一起，學(xué)習(xí)新知，分享成長(zhǎng)。
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見(jiàn)轉(zhuǎn)載須知。
