怎麼設定根節點
本篇文章將實現AlphaZero的核心搜尋演算法：蒙特卡洛樹搜尋
蒙特卡洛樹搜尋（MCTS）
你可能熟悉術語蒙特卡洛［1］，這是一類演算法，反覆進行隨機抽樣以獲得某個結果。
例如上圖，在單位正方形中選擇隨機點，計算圓內有多少個點，可以用來估計pi/4的值
本文中我們將詳細介紹MCTS的所有步驟。但首先我們從更廣泛的理解層面來說，在遊戲的MCTS中，我們從給定的棋盤狀態開始重複模擬玩法，一般情況下的MCTS我們會一直執行這些模擬直到遊戲結束。但AlphaZero的［2］MCTS實現與傳統的MCTS不同，因為在AlphaZero中我們也有一個神經網路，它正在接受訓練，為給定的板子狀態提供策略和值。
AlphaZero中搜索演算法的輸入是一個棋盤的狀態（比如σ）和我們想要執行MCTS的迭代次數（也稱為播放次數）。在這個遊戲的例子中，搜尋演算法的輸出是從σ中抽樣一個執行動作的策略。
該樹將迭代構建。樹的每個節點都包含一個棋盤狀態和關於在該狀態下可能採取的有效操作的資訊。
節點由一個狀態板和鍵-值對組成，其中鍵是一個動作元組，對應的值是在父節點的狀態上應用該動作元組後獲得的節點。子節點是惰性初始化的（即僅在需要時初始化）
一開始，樹只有根節點。它將包含輸入狀態σ和在σ下可以採取的有效動作。
下面是Node類的程式碼。
MCTS的每一次模擬分為4個步驟：選擇（selection）、展開expansion）、求值（evaluation）和回溯（backup），下面我們詳細進行說明
選擇
MCTS演算法的第一步是選擇。從根節點開始選擇最佳邊，直到到達樹的末端（表示遊戲結束的終端節點/尚未探索的節點，例如上圖中標記為None的節點）。
但“最佳邊”是什麼意思呢？應該如何遍歷樹？如何做到樹遍歷的方式是在探索和使用之間取得平衡呢？（這裡的探索也是神經網路主導的）
首先解釋下這裡的探索（exploration）和使用（exploitation）的含義：
想象一下：你從來沒有吃過豆腐腦，你也不知道甜的還是鹹的好吃（比如對於北方人來說可能都沒聽有甜的豆腐腦）。所以只能自己嘗試，假設吃了一個甜的感覺很好。但當你聽到還有鹹的的時候，因為還沒有嘗試過，肯定想嘗試下，這樣找到一個新的口味，這個就是探索。但是如果假設你一天只能吃一種口味的，而你更新換甜味的，想吃甜的，這就是使用。
簡單總結下：選擇的行動的目標都是能夠獲得積極獎勵的，但是如果行動已經瞭解，這就是使用；行動是找到一些能給你帶來更好獎勵的行動（以前沒有的），這就是探索。但是因為一次只能進行一個動作，所以就需要在兩者之間取得良好的平衡。
AlphaZero使用PUCT（應用於樹的預測器置信上限）規則來實現這種平衡。該規則是根據經驗設計的，也是受到Rosin’s work in a bandits-with-predictors setting［3］的工作的推動。DeepMind最近的一篇論文［4］討論了PUCT的一些替代方案。我們將在後面關於未來方向的部分中討論這些替代方案。我們先試著理解PUCT規則。
動作值Q（s， a）表示在狀態s下透過動作a獲得的平均獎勵。一開始，Q（s， a）是零。這個action-value代表我們在任何給定時間對獎勵函式的瞭解，因此它與使用有關。
假設我們訓練過的神經網路以0。3的機率表示我們應該執行某個動作a。那麼將0。3的機率包含在PUCT規則的探索部分。狀態s屬於父節點，透過在“s”上執行動作“a”獲得的狀態屬於子節點。但是這樣會導致經常訪問MCTS中的某個節點，為了避免這種情況並鼓勵探索其他節點，子節點的訪問計數包含在分母中，並使用父節點的總訪問數進行規範化。
為什麼要取父節點訪問次數的平方根？PUCT規則是根據經驗設計的，這是作者所嘗試的所有選擇中最有效的，也就是說是一個可以配置的超引數。我們也可以直接將其視為一種對子節點進行歸一化的方式：分母中的 N+1 項。
在上圖中可以看到超引數c_puct。這個常數平衡探索採和使用條件。這個超引數的典型值是2。
現在已經對如何獲得PUCT（s， a）有了一定的瞭解，讓我們繼續MCTS中的選擇步驟。
選擇步驟如下面的塊所示，即從根節點開始，重複查詢具有最大PUCT值的子節點，直到到達狀態仍然為None（尚未展開/初始化）的節點。
consider_node = root// terminal nodes also have a None statewhile consider_node。state is not None：
best_node = find_child_with_maximum_puct_value（consider_node）
consider_node = best_nodeconsider_node has to be expanded
上面動圖顯示了重複查詢pput值最大的子節點，直到到達狀態仍然為None的節點
展開和求值
在選擇了特定的動作後，下一步就就是展開並對該節點進行求值（因為其狀態仍為 None）。 這裡的展開表示透過初始化選定節點的狀態來擴充套件樹。 這種新的狀態是從遊戲規則中獲得的。如果它是一個終端節點，我們將狀態保留為 None 並在節點中設定一個標誌，將其標記為帶有獲勝者資訊的終端節點。
所選節點的所有新邊也被初始化。 例如上面動圖中顯示的樹在展開所選節點後將如下圖所示。
接下來就是展開節點的計算，評估指玩家在該節點的期望獎勵。傳統的 MCTS 使用 rollout 策略從擴充套件節點執行 rollout，以找出遊戲結束時的值， 這個策略可以是均勻隨機的。而AlphaZero的MCTS與傳統的MCTS不同，在AlphaZero的MCTS中，使用神經網路的值輸出來確定展開節點的值。
比如當評估一個國際象棋的位置時，我們會在腦海中計算一些走法，然後在計算結束時只使用的直覺來判斷結果會有多好。在計算結束時不會像傳統的 MCTS 那樣進行操作，也不會在遊戲結束之前使用隨機動作模擬那個操作，我們只選擇幾個我們認為比較好的位置進行操作。
下面是程式碼的實現。
回溯
在對展開的節點進行評估之後，還需要更新從根節點到展開節點的所有節點的Q值（由總獎勵值和總訪問次數實現）。這被稱為MCTS的回溯（Backup）步驟。
這一點的實現比較簡單方法是使用遞迴地實現選擇函式，
開始遊戲
上面的四個步驟在一定次數的迭代中執行。如果它們運行了1000次迭代，那麼總共將擴充套件最多1000個新節點（我們之所以說最大值，是因為某些終端節點可能被訪問多次）。
在這些迭代結束後，觀察根節點和它的子節點可能看起來像這樣。
這些訪問計數在根節點輸出策略。 AlphaZero 使用的想法是，如果一個節點被更多地訪問，那麼我們應該分配一個更高的機率來執行給該節點的根節點的動作。
某個動作的輸出策略機率值與N^（1/τ）成正比，其中N是透過該動作獲得的根節點子節點的訪問次數，τ是某個溫度（temperature ）值。
從上圖中我們可以看到，從AlphaZero中搜索獲得的每個動作的輸出策略與被提升為1/τ的結果子節點的訪問計數成正比，其中τ是某個溫度值。τ的高值將導致更統一的策略。可以在程式碼中設定為1。
然後從這個輸出策略中抽樣一些動作，為給定的狀態進行一些操作。使用訪問計數來構造輸出策略是合理的，因為使用PUCT值來指導蒙特卡羅樹搜尋。這些PUCT價值觀平衡了探索和使用。向根節點返回更多值的節點將被更頻繁地訪問，而一些節點將透過探索被隨機訪問。
這樣整個AlphaZero的最基本的概念就介紹完了
References
［1］ https：//en。wikipedia。org/wiki/Monte_Carlo_method
［2］ Silver， D。， Hubert， T。， Schrittwieser， J。， Antonoglou， I。， Lai， M。， Guez， A。， Lanctot， M。， Sifre， L。， Kumaran， D。， Graepel， T。， Lillicrap， T。， Simonyan， K。， & Hassabis， D。 （2018）。 A general reinforcement learning algorithm that Masters Chess， Shogi， and go through self-play。 Science， 362（6419）， 1140–1144。 https：//doi。org/10。1126/science。aar6404
［3］ Rosin， C。 D。 （2011）。 Multi-armed bandits with episode context。 Annals of Mathematics and Artificial Intelligence， 61（3）， 203–230。 https：//doi。org/10。1007/s10472-011-9258-6
［4］ Danihelka， I。， Guez， A。， Schrittwieser， J。， & Silver， D。 Policy Improvement by planning with Gumbel。 Deepmind。 Retrieved February 23， 2022， from https：//deepmind。com/research/publications/2022/Policy-improvement-by-planning-with-Gumbel
https：//avoid。overfit。cn/post/eac92335f439429d99b4abd58517b899
作者：Bentou