一、算法簡介

? ? ? ? 簡單地說，Alphazero=MCTS + SL(策略網(wǎng)絡(luò)+價(jià)值網(wǎng)絡(luò)) +Selfplay + resnet。 其中MCTS指的是蒙特卡洛樹搜索，主要用于記錄所有訪問過的棋盤狀態(tài)的各種屬性，包括該狀態(tài)訪問次數(shù)，對(duì)該狀平均評(píng)價(jià)分?jǐn)?shù)等。 SL指監(jiān)督學(xué)習(xí)算法，監(jiān)督網(wǎng)絡(luò)輸出價(jià)值v和策略pai，用于擬合mcts推測出的策略和價(jià)值，并泛化到未見過的狀態(tài)上。 Selfplay是一種訓(xùn)練方法，步驟是：實(shí)例化蒙特卡羅樹和SL網(wǎng)絡(luò)，進(jìn)行自我博弈，以產(chǎn)生多樣化的數(shù)據(jù)進(jìn)行訓(xùn)練和更新。 resnet 眾所周知是一種卷積神經(jīng)網(wǎng)絡(luò)，主要用于棋盤的特征提取。下面從采樣和更新兩個(gè)角度對(duì)上述幾個(gè)部件進(jìn)行介紹。文中所引代碼來自alphazero GitHub 五子棋

1、蒙特卡洛樹搜索

? ? ? ? 顧名思義，蒙特卡洛樹搜索是一種利用樹形數(shù)據(jù)結(jié)構(gòu)進(jìn)行搜索的算法，其節(jié)點(diǎn)存儲(chǔ)是棋盤狀態(tài)，根節(jié)點(diǎn)存儲(chǔ)的是棋盤初始狀態(tài)，其子節(jié)點(diǎn)存儲(chǔ)是當(dāng)前狀態(tài)可能的下一狀態(tài)。節(jié)點(diǎn)上存儲(chǔ)的屬性包括棋盤當(dāng)前棋子位置s，訪問s的次數(shù)n，對(duì)節(jié)點(diǎn)的估值v。

?圖一、蒙特卡洛樹搜索的采樣和更新（select, expand, simulate為采樣，backpropagate為更新）?

?1.1 MCTS采樣

? ? ? ? mcts(蒙特卡洛樹搜索）的采樣分為三步：節(jié)點(diǎn)選擇，節(jié)點(diǎn)拓展，和模擬推演。三步是依次執(zhí)行的。

? ? ? ? 1.節(jié)點(diǎn)選擇：初始化根節(jié)點(diǎn)，從根節(jié)點(diǎn)開始，對(duì)所有可能的子節(jié)點(diǎn)計(jì)算puct值，選擇值最大的進(jìn)入，puct計(jì)算公式如下

? ? ? ? 其中vi 是該節(jié)點(diǎn)的價(jià)值，N是父節(jié)點(diǎn)被訪問次數(shù)，ni為本節(jié)點(diǎn)被訪問的次數(shù)，C為超參數(shù)用于平衡利用和探索。

????????2.節(jié)點(diǎn)擴(kuò)展：如果當(dāng)前節(jié)點(diǎn)已經(jīng)是樹的葉子節(jié)點(diǎn)，則需對(duì)樹進(jìn)行節(jié)點(diǎn)擴(kuò)展，具體步驟為：從可能的動(dòng)作中選取一個(gè)執(zhí)行，進(jìn)入下一狀態(tài)，并將這個(gè)新節(jié)點(diǎn)加入到父節(jié)點(diǎn)的子節(jié)點(diǎn)集中。

????????3.模擬推演：在將一個(gè)新節(jié)點(diǎn)加入樹后，需要從這個(gè)節(jié)點(diǎn)的狀態(tài)出發(fā)（如果此節(jié)點(diǎn)非終止?fàn)顟B(tài)），進(jìn)行模擬推演，直至到達(dá)種植狀態(tài)。在模擬中，不適用樹來做決策，而是使用強(qiáng)化學(xué)習(xí)的actor和critic網(wǎng)絡(luò)做決策。

1.2 MCTS更新

? ? ? ? 1. 反向回溯：??在模擬對(duì)局進(jìn)行到終局狀態(tài)后，一般會(huì)有勝負(fù)和的情況，記勝利的結(jié)局價(jià)值為1 失敗的結(jié)局價(jià)值為-1，從葉子節(jié)點(diǎn)開始一次反溯其父節(jié)點(diǎn)，將沿途每個(gè)節(jié)點(diǎn)的訪問次數(shù)+1，總價(jià)值加上新的結(jié)局價(jià)值，并用新的總價(jià)值除以訪問次數(shù)得到平均價(jià)值。反向傳播就是利用此次勝負(fù)結(jié)果，從這次推演的葉子節(jié)點(diǎn)開始，迭代查詢出所有的父節(jié)點(diǎn)，并更新這些父節(jié)點(diǎn)上的價(jià)值估值vi 。

? ? ? ??實(shí)際Alphazero算法中使用的mcts細(xì)節(jié)比上面描述的有所不同，在第三節(jié)算法流程中介紹

2、策略網(wǎng)絡(luò)和價(jià)值網(wǎng)絡(luò)

? ? ? ? 采樣：在mcts采樣到達(dá)第三步模擬推演時(shí)，開始使用策略網(wǎng)絡(luò)和價(jià)值網(wǎng)絡(luò)推演，從當(dāng)前狀態(tài)s開始，每次選擇一動(dòng)作a執(zhí)行，直至到達(dá)終點(diǎn)獲得勝負(fù)結(jié)果。

? ? ? ? 更新：這里需要注意，雖然網(wǎng)絡(luò)結(jié)構(gòu)用了策略網(wǎng)絡(luò)和狀態(tài)價(jià)值網(wǎng)絡(luò)形式建模，但是其損失函數(shù)完全不同于actor critic的loss。actor critic 使用的是強(qiáng)化學(xué)習(xí)中的策略梯度損失和td error進(jìn)行更新。而alphazero中的策略網(wǎng)絡(luò)和價(jià)值網(wǎng)絡(luò)更新方式是監(jiān)督學(xué)習(xí)的方法，策略網(wǎng)絡(luò)使用交叉熵損失，求網(wǎng)絡(luò)輸出策略和節(jié)點(diǎn)統(tǒng)計(jì)策略的差異。 價(jià)值網(wǎng)絡(luò)使用均方差損失，求網(wǎng)絡(luò)輸出價(jià)值和節(jié)點(diǎn)monte carlo方法統(tǒng)計(jì)的價(jià)值均值之間的損失?！久商乜灞旧砭褪且环N通過采樣擬合近似計(jì)算問題的解或者概率分布，所以不能因?yàn)槠鋷в胁呗院蛢r(jià)值網(wǎng)絡(luò)就默認(rèn)用actor和critic的思想去理解，那就錯(cuò)了】

? ? ? ? 更新方式：價(jià)值網(wǎng)絡(luò)和策略網(wǎng)絡(luò)的輸入是棋局推演中每一step的state，價(jià)值網(wǎng)絡(luò)輸出每一state的預(yù)估價(jià)值【范圍[-1,1]】其label是該局最終的勝負(fù)情況，勝則+1，負(fù)則-1。策略網(wǎng)絡(luò)輸出的是每一state下采取的策略的概率分布，其標(biāo)簽為，使用的是均方差誤差做回歸損失，而policy的標(biāo)簽使用的是mcts推導(dǎo)出的策略分布，使用的是交叉熵?fù)p失做分類的損失。兩項(xiàng)損失的和是網(wǎng)絡(luò)的總損失

3.SelfPlay

? ? ? ? selfplay 即使用模型和自己對(duì)戰(zhàn)，因?yàn)槟Ｐ驮趯W(xué)習(xí)和變化，所以可以產(chǎn)生不同分布的數(shù)據(jù)，相比于alphago的對(duì)棋譜訓(xùn)練增加數(shù)據(jù)多樣性，增強(qiáng)了泛化性。

? ? ? ? alphazero要使用 mcts和sl 完成自博弈的過程，就需要mcts和sl 既可以輸出先手的策略，也可以輸出后手的策略。為實(shí)現(xiàn)這一點(diǎn)，mcts采取的方式是，在節(jié)點(diǎn)價(jià)值從葉子節(jié)點(diǎn)向根節(jié)點(diǎn)迭代更新時(shí)，每一次都傳入 -value，即相鄰兩節(jié)點(diǎn)估值符號(hào)相反，這樣使得每一個(gè)節(jié)點(diǎn)上的估值都是當(dāng)前player對(duì)棋局的估值。 sl中的value和policy因?yàn)槭菍W(xué)習(xí)擬合mcts的輸出，所以其也具有了輸出先后手策略和價(jià)值的能力。

二、算法整體流程介紹

????????整體偽代碼如下

初始化價(jià)值網(wǎng)絡(luò) V 和策略網(wǎng)絡(luò) pi對(duì)于 i 在范圍 1500 內(nèi)循環(huán)：# 通過自對(duì)弈收集數(shù)據(jù)環(huán)境重置()初始化根節(jié)點(diǎn)當(dāng)未完成時(shí)循環(huán)：動(dòng)作, 動(dòng)作概率 = 玩家獲取動(dòng)作()# 通常在 get_action 函數(shù)中涉及 400 次選擇和擴(kuò)展。# 如果任何一次迭代達(dá)到游戲結(jié)束，更新 MCTS 節(jié)點(diǎn)的值。當(dāng)前狀態(tài) = 下一狀態(tài)將根節(jié)點(diǎn)移至當(dāng)前狀態(tài)的節(jié)點(diǎn)如果收集到的數(shù)據(jù) > 批量大小：使用收集到的數(shù)據(jù)訓(xùn)練策略網(wǎng)絡(luò)和價(jià)值網(wǎng)絡(luò)