本文主要是將有關蒙特卡洛樹搜索的文獻（2011年之前）進行歸納，概述了核心算法的推導，給出了已經提出的許多變化和改進的一些結構，并總結了MCTS方法已經應用于的博弈和其他領域的結果。

蒙特卡洛樹搜索是一種通過在決策空間中隨機抽樣，并根據結果建立搜索樹，在給定域內尋找最優決策的方法，它平衡了探索（exploration）和利用（exploitation）。

一、背景

二、蒙特卡洛樹搜索

蒙特卡洛樹搜索基于兩個基本概念：一個動作的真實值可以使用隨機模擬來近似；這些值可以有效地調整策略為最佳優先策略。

基本算法包括迭代地構建一個搜索樹，直到達到一些預定義的計算預算——通常是時間、內存或迭代約束——此時搜索停止，并返回性能最好的根操作。搜索樹中的每個節點表示域的一個狀態，指向子節點的定向鏈接表示導致后續狀態的操作。

每次搜索迭代都將應用四個步驟：

• 選擇（selection）：從根節點開始，遞歸地應用子選擇策略通過樹向下移動，直到到達最緊急的可擴展節點。如果節點表示非終端狀態并且有未訪問（即未擴展）子節點，則節點是可擴展的。
• 擴展（expansion）：根據可用的操作，添加一個（或多個）子節點以展開樹。
• 模擬（simulation）：根據默認策略，從新節點開始運行模擬，以產生結果。
• 反向傳播（backpropagated）：模擬結果通過選定的節點進行“備份”（即反向傳播），以更新其統計信息。

這些步驟可以分為兩種不同的策略：

• 樹策略（tree policy）：從已包含在搜索樹中的節點中選擇或創建一個葉節點（選擇和擴展）
• 默認策略（default policy）：從給定的非終端狀態發揮域，已產生值估計（模擬）

Upper Confidence Bounds for Trees (UCT）?

UCB1是解決MCTS中的探索-利用困境的一個很有前途的候選對象：每當在現有的樹中選擇一個節點（動作）時，該選擇都可以被建模為一個獨立的多武裝強盜問題（multiarmed bandit problem），一個子節點?j 被選擇去最大化：

方程第一項是利用項，第二項是探索項，兩項間有一個基本的平衡。當每個節點被訪問時，探索項的分母增加，從而減少其貢獻。另一方面，如果訪問了父節點的另一個子節點，那么分子就會增加，因此未訪問的兄弟節點的探索值也會增加。探索項確保每個子節點都有一個非零的選擇概率，這是必要的隨機性質。這也賦予了算法一個固有的重啟屬性，因為即使是低獎勵的子節點最終也能保證被選擇（如果給定足夠的時間），從而探索了不同的游戲路線。

參數可以進行調整以降低或增加探索的概率。一般取，因為這個值能以范圍為[0,1]的獎勵滿足Hoeffding ineqality。其他范圍的獎勵則需要不同的。

算法3展示了一種更有效的雙人零和博弈交替移動的備份方法。

?三、特點

1）啟發式：MCTS最重要的好處之一就是缺乏對特定領域的知識的需求，這使得它很容易適用于任何可以使用樹建模的領域?。

2）任何時間：MCTS立即反向傳播每個游戲的結果，確保在算法的每次迭代后所有值都是最新的，這允許算法在任何時候從根目錄返回一個操作。

3）不對稱：樹的選擇允許算法偏愛更有前途的節點（但不允許其他節點的選擇概率收斂到零），導致隨著時間的推移出現不對稱的樹，也就是說，部分樹的構建傾向于更有前途，即更重要的區域。

四、變化

傳統的游戲AI研究集中于有兩個玩家的零和游戲、交替回合、離散動作空間、確定性狀態轉換和完美信息。雖然MCTS已經廣泛應用于此類游戲，但它也被應用于其他領域類型，如單人游戲和規劃問題、多人游戲、實時游戲以及具有不確定性或同時移動的游戲。本節描述了MCTS適應這些領域的方法，以及那些采用來自MCTS的想法而不嚴格遵守其大綱的算法。

（我只選擇部分可能與課題相關的算法進行學習）

1.Learning in MCTS

MCTS可以被看作是一種強化學習算法，因此考慮它與時間差異學習（典型的RL算法）之間的關系。

時間差異學習（TDL）：時間差異學習（TDL）和MCTS都是學習基于狀態或狀態 - 行動對的值來采取行動的。在某些情況下，算法甚至可能是等價的，但TDL算法通常不構建樹，只有當所有狀態值都可以直接存儲在表中時，這種等價才成立。MCTS估計臨時狀態值，以決定下一步行動，而TDL學習每個狀態的長期值，然后指導未來的行為。

時間差異與蒙特卡洛（TDMC）：“一種新的方法使用獲勝概率代替非終端位置的獎勵”

2.多人 MCTS

極大極小搜索的中心假設是搜索玩家尋求最大化他們的獎勵，而對手則尋求最小化獎勵。在雙人零和游戲中，這相當于說每個玩家都尋求最大化自己的獎勵；然而，在兩個以上玩家的游戲中，這種等價性并不一定成立。

將MCTS應用于多人游戲的最簡單的方法是采用這樣的想法：每個節點存儲一個獎勵向量，并且選擇過程尋求最大化使用獎勵向量的適當成分計算出的UCB值。

?3.多代理MCTS

考慮擁有多個代理（即多個模擬策略）的影響，在這種情況下，不同的代理是通過給程序中使用的啟發式分配不同的優先級來獲得的。然而尋找具有正確屬性的代理集（即那些增加游戲強度的代理）是需要計算的。

?