摘要：介紹蒙特卡羅樹搜索由于年作為的一個組成部分引入，令人印象深刻的是其出色的引擎的能力，同時也是的核心組件。蒙特卡羅樹搜索主要目的是給出一個狀態來選擇最佳的下一步。之前蒙特卡羅樹搜索產生的一些統計數據可能仍然存在于你正在考慮的新分支中。

摘要： 一直以來，學術界普遍認為在圍棋游戲中機器是遠不能和人類相比的，它被認為是未來十年內人工智能需要實現的目標之一。令人驚訝的是，在2016年3月由谷歌發明的Alpha Go以4-1擊敗了韓國的世界冠軍。

蒙特卡羅樹搜索由RémiCoulom于2006年作為Crazy Stone的一個組成部分引入，令人印象深刻的是其出色的引擎的能力，同時也是Alpha Go / Zero的核心組件。蒙特卡羅樹搜索主要目的是：給出一個狀態來選擇最佳的下一步。我們回顧AlphaGo / Zero，試圖解釋在Alpha Go中使用了哪些蒙特卡羅樹搜索變體。

兩人有限零和順序游戲

在該環境下，蒙特卡羅樹搜索內運行的是一個游戲，其本身是一個很抽象、很廣義的術語，因此在這里我們專注于單一游戲類型：二人有限零和順序博弈。把它分解成以下幾個部分：

游戲意味著需要處理互動的情況，一些參與者（一個或多個）。

“有限”一詞表明，在任何時間點，參與者之間存在有限的交互方式。

兩人博弈意味著兩個參與者參與了我們的游戲。

連續的，因為參與者交替地移動他們的動作。

最后，零和游戲意味著雙方都有相反的目標，換句話說：在游戲的任何終端狀態，所有玩家的收益總和等于零。
圍棋、象棋或井字棋都是兩人有限零和順序游戲。事實上，有兩個人參與，總是有限的動作，并且兩個參與者的目標是完全相反的（所有游戲的結果總和為零）。

形式上，游戲由一些基本的數學實體表示。在博弈理論書中，你可以找到以下定義：

定義1.一個廣泛的表單游戲由一個元組定義：

從計算機程序員的角度來看，一個正式的定義可能有點混亂。幸運的是，我們可以使用一個眾所周知的數據結構來簡化表示為：一個游戲樹。
游戲樹是一個樹，其中每一個節點代表游戲的某些狀態。從節點到其子節點（如果存在）的轉換是一個移動。節點的子節點的數目稱為分支因子，樹的根節點代表游戲的初始狀態。如果游戲樹的終端節點沒有子節點，游戲就不能繼續了。讓我們試著描述（部分）看到的井字游戲樹：
1.在頂部，你可以看到樹的根部，代表井字游戲的初始狀態，空白紙板（標記為綠色）。
2.從一個節點到另一個節點的任何轉換都表示一個移動。
3.井字游戲的分支因素各不相同- 它取決于樹的深度。
4.游戲結束于終端節點（標記為紅色）。
游戲樹是一個遞歸數據結構，所以在選擇最佳移動后，最終會在子節點中實現，而子節點實際上是其子樹的根節點。因此，你可以把一個游戲看作是一個“最佳的下一步”序列的代表，每次都有一個游戲樹（不同的根節點）。通常在實踐中，你不必記住通往當前狀態的路徑，因為它不是當前游戲狀態中的關注點。

我們的最終目標是在給定游戲狀態和游戲樹暗示的情況下找到最佳的下一步行動。我們假設在國際象棋中，你知道你的對手是一個業余愛好者，你可以選擇簡單的策略來欺騙他并迅速獲勝。但是，針對強大對手的時候采用相同策略會對你產生不利影響。如果你根本不了解你的對手，那么有一個非常激進的策略叫做minimax，假設你的對手很厲害，那么這個策略可以得到最大化效果。在A和B之間的兩人有限零和序貫博弈時，minimax
算法可以用下面的遞歸公式來描述：

簡單地說，假設你的對手試圖最大限度地限制你，而你利用minimax算法將會產生最大的回報，這也是minimax算法的由來
。我們需要的只是擴展整個游戲樹，并根據遞歸公式給出的規則來反向傳播。

minimax算法的最大弱點是擴展整個游戲樹的必要性，對于具有高度分支因素的游戲（如圍棋或象棋），它會產生巨大的游戲樹并導致失敗。

接下來我介紹兩種方法，一種方法是將我們的游戲樹擴展到一定的閾值深度D。但是，我們不能保證閾值樹級別D中的任何節點都是終端。因此，我們需要一個函數來評估一個非終端游戲狀態。這對人類來說是很自然的：通過看國際象棋或圍棋，即使游戲仍在繼續，你也能預測贏家。例如：

克服游戲樹大小問題的另一種方法是通過alpha-beta修剪算法修剪游戲樹。Alpha-beta修剪算法以minimax方式遍歷游戲樹，避免某些樹枝的擴展。結果最多與minimax相同，但alpha-beta修剪算法通過減少搜索空間來保證改進。

蒙特卡羅樹搜索的主要概念是搜索。搜索是一組沿著游戲樹的遍歷，單次遍歷是從根節點（當前游戲狀態）到未完全展開的節點的路徑。未完全展開的節點意味著至少有一個子節點未被訪問，而沒有被探索。遇到未完全展開的節點時，其子節點不會選擇成為一個根節點。然后將模擬結果反向傳播到當前游戲樹節點以統計數據。一旦搜索（受時間或計算能力限制）終止，則根據收集的統計信息選擇移動。
讓我們試著接著上面簡單描述的關鍵問題，以便慢慢理解所有的部分：
1.什么是擴展或不完全擴展的游戲樹節點？
2.在搜索過程中，下一個（子）節點如何選擇？
3.什么是模擬？
4.什么是反向傳播？
5.在擴展的游戲樹節點中傳播和更新哪些統計數據？
6.最后的移動如何選擇？

模擬

我們首先關注模擬，因為它不會嚴重依賴其他術語的定義。模擬是一種單一的游戲行為，是一系列從當前節點開始，并終止于可計算游戲結果的終端節點的動作序列。模擬是通過在該節點處開始以某種方式隨機游戲來計算的游戲樹節點評估近似值。在模擬過程中如何選擇動作？在模擬過程中，選擇一個稱為“轉出策略”的函數：

它消耗一個游戲狀態并產生下一個移動/動作。在實踐中，它被設計成能夠快速地模擬，默認的轉出策略函數是一個統一的隨機函數。

最簡單形式的模擬只是隨機的一系列動作，從給定的游戲狀態開始并終止。模擬對于我們所談論的游戲來說總是會產生一個評估，勝利、失敗或平局，通常任何結果都是模擬的合法結果。

給定一個根節點加上游戲規則，我們可以遍歷它，而不需要將整個樹存儲在內存中。在最初的形式中，它根本沒有擴展并且處于游戲樹的根部，其余節點未被訪問。一旦我們考慮到一個動作，就會想象這個動作會產生什么樣的結果。
蒙特卡羅樹搜索游戲樹也有同樣的區別。節點被視為訪問或未訪問，對于要訪問的節點意味著如果一個節點的所有子節點都被訪問，則節點被認為是完全擴展的，否則它沒有完全擴展，但是可能會進一步擴展。

在實踐中，一旦搜索開始，所有的根節點都未被訪問。如果其中一個被選中，第一個模擬立即開始。請注意，在模擬過程中，由轉出策略函數選擇的節點不被考慮訪問。它們是未經許可的，只有模擬開始的節點被標記為已訪問過。

一旦完成了一個葉節點的模擬，其結果已準備好傳播回當前的游戲樹根節點，然后模擬開始的節點被標記為已訪問。

反向傳播是從葉節點（模擬開始）到根節點的遍歷。模擬結果被傳送到根節點，并且對于反向傳播路徑上的每個節點更新某些統計信息。反向傳播保證每個節點的統計數據反映在其所有后代中開始的模擬結果（因為模擬結果被傳送到游戲樹根節點）。

在搜索的一開始，由于我們還沒有開始任何模擬，所以首先選擇未訪問的節點。單個模擬從根節點開始遍歷到葉節點，結果又反向傳播到根節點，然后根節點被認為完全展開。

當前的節點標記為藍色，并且已完全展開，它必須存儲其節點統計信息：總體模擬結果和總訪問次數。這同樣適用于其子節點。

我們現在知道成功實施蒙特卡羅樹搜索所需的所有條件，但我們什么時候才能真正結束蒙特卡羅樹搜索程序？答案是：它取決于上下文。如果你構建了一個游戲引擎，那么你的“思考時間”可能是有限的，再加上計算機的計算能力也有限制。一旦蒙特卡羅樹搜索程序完成，最好的移動通常是訪問次數N最多的移動，因為它的估計價值最高（經常被探索）。

在使用蒙特卡羅樹搜索選擇你的移動后，你所選擇的節點將成為你的對手移動的游戲狀態。一旦他選擇了他的移動，你將再次開始蒙特卡羅樹搜索程序。之前蒙特卡羅樹搜索產生的一些統計數據可能仍然存在于你正在考慮的新分支中。這帶來了重新使用統計數據而不是從頭開始構建新樹的想法，事實上這也是Alpha Go / Alpha Zero的創建者所做的。

文章標題《Monte Carlo Tree Search – beginners guide》

詳細內容請查看原文。