一、算法簡介

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

1、蒙特卡洛樹搜索

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

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

?1.1 MCTS采樣

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

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

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

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

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

1.2 MCTS更新

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

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

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

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

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

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

3.SelfPlay

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

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

二、算法整體流程介紹

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

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