蒙特卡洛搜索樹如何工作？

Question

嘗試使用YouTube視頻和論文來學習MCST。

http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/grand-challenge.pdf

但是我沒有多少運氣的理解超越了高層次的理論解釋的細節。以下是上述論文中的一些引用以及我有的問題。

1. 選擇階段：MCTS反覆選擇當前狀態的得分最高的子節點。如果當前狀態是根節點，那麼這些孩子從哪裏來的呢？難道你沒有一個只有一個根節點的樹開始？只有一個根節點，您是否馬上進入擴展和模擬階段？

2. 如果MCTS在選擇階段選擇得分最高的孩子節點，那麼您從來不會去探索其他孩子，甚至可能是一個全新的孩子，同時沿着樹的高度往下走？

3. 節點的擴展階段如何發生？在上圖中，爲什麼不選擇葉節點，而是決定將葉節點添加到葉節點？

4. 在模擬階段，使用隨機策略爲兩個玩家選擇合法移動，直到遊戲結束。這個隨機策略是一種硬編碼的行爲，你基本上在模擬中擲骰子，以便在每個玩家之間輪流選擇其中一種可能的動作，直到最後？

5. 我明白這一點的方法是從單個根節點開始，並通過重複上述步驟將樹構建到特定深度。然後你選擇第二級別中得分最高的孩子作爲下一步。你願意構建的樹的大小基本上是你的硬性AI響應要求嗎？由於在構建樹時，遊戲將停止並計算該樹。

Answer 1

基本上，蒙特卡羅是：隨機嘗試多次（*），然後保持導致大多數時間最佳結果的舉措。

（*）：次數和深度取決於您想要達到的決定的速度。

所以根節點永遠是當前的遊戲狀態與直接的孩子是你的可能的舉措。 如果你可以做2個動作（是/否，左/右，...），那麼你有2個子節點。

如果你不能做任何動作（這可能發生取決於遊戲），那麼你沒有任何決定，然後蒙特卡洛對此舉毫無用處。

如果您有X個可能的移動（國際象棋遊戲），那麼每個可能的移動都是直接的子節點。然後，（在2人遊戲中），evey等級是交替的「你的動作」，「對手動作」等等。

如何遍歷樹應該是隨機的（統一的）。

你的移動1

他移動4（隨機移動子級2）

你的移動3（子級1的隨機移動）（子級的隨機移動3） - >贏yay

選擇一個參考最大深度，並評估你贏或輸的次數（或者如果遊戲沒有在X深度之後完成，那麼有一個評估函數）。

你重複操作的y倍的（即相當大），並且選擇直接子節點（又名：你的舉動），導致你贏得大部分的時間。

這是評估哪些移動你應該做的現在。之後，對手移動，輪到你了。因此，您必須重新創建一棵樹，並將根節點作爲新的當前情況，並重新使用蒙特卡羅技術來猜測您最可能採取的行動。等等。

Answer 2

1. 選擇階段：MCTS反覆選擇當前狀態的得分最高的子節點。如果當前狀態是根節點，那麼這些孩子從哪裏來的呢？難道你沒有一個只有一個根節點的樹開始？只有一個根節點，您是否馬上進入擴展和模擬階段？

選擇步驟通常實施不實際這實際上存在於樹節點中選擇（已經通過擴展步驟中創建）。它通常被ipmlemented選擇匹配你當前節點的遊戲狀態的所有可能的後繼狀態。因此，在剛開始的時候，當你只有一個根節點時，你會希望你的選擇步驟仍然能夠從所有可能的後繼遊戲狀態中選擇一個（即使它們沒有匹配樹中的節點）。通常情況下，對於尚未訪問過的遊戲狀態（在樹中沒有節點），您需要非常高的分數（無限大，或者一些非常大的常數）。這樣，你的選擇步驟將總是隨機地在沒有匹配節點的狀態中進行選擇，並且只有在所有可能的遊戲狀態在樹中具有匹配節點的情況下才真正使用探索與利用權衡。

如果MCTS選擇在選擇階段得分最高的子節點，你永遠探索其他的孩子甚至可能是一個全新的孩子，而下降樹的水平？

的「」得分'使用選擇步驟通常應不只是模擬通過該節點的去所有結果的平均值。它通常應該是一個由兩部分組成的分數;一個「探索」部分，對於已經很少被訪問的節點來說是很高的，還有一個「開發」部分，對於目前看起來是很好的移動的節點來說是很高的（這裏很多仿真都以一個勝利結束對於允許選擇移動的玩家來說）。這在您鏈接的論文的第3.4節中有描述。 W(s, a)/N(s, a)是開發部分（簡單的平均分數），而B(s, a)是探索部分。

1. 節點的擴展階段如何發生？在上圖中，爲什麼不選擇葉節點，而是決定將葉節點添加到葉節點？

膨脹處理通常被實現簡單的添加相應於由選擇步驟選擇的最後一場比賽狀態的節點（以下是我回答你的第一個問題，在選擇步驟總是會選擇一個遊戲結束以前從未選擇的狀態）。

1. 在模擬階段，使用隨機策略爲兩個玩家選擇合法移動，直到遊戲結束。這個隨機策略是一種硬編碼的行爲，你基本上在模擬中擲骰子，以便在每個玩家之間輪流選擇其中一種可能的動作，直到最後？

最直接的（也可能是最常見的）實現的確是完全隨機播放。儘管如此，也可以做到這一點。例如，您可以使用啓發式方法爲某些操作創建偏向。通常，完全隨機播放速度更快，可以讓您在相同的處理時間內運行更多模擬。但是，它通常也意味着每個單獨的模擬信息都較少，這意味着您實際上需要運行更多的MCTS模擬才能發揮出色。

我明白這是你開始在一個根節點和通過重複上述相在構造樹到一定深度的方式。然後你選擇第二級別中得分最高的孩子作爲下一步。你願意構建的樹的大小基本上是你的硬性AI響應要求嗎？由於在構建樹時，遊戲將停止並計算該樹。

MCTS不統一探索樹的所有部分到相同的深度。它傾向於探索看起來比較有趣的部分（強烈的動作），比看起來沒有興趣的部分（弱動作）更深。所以，通常你不會真的使用深度限制。相反，您可以使用時間限制（例如，持續運行迭代，直到您花費1秒，5秒或1分鐘，或者您允許的任何處理時間量）或迭代次數限制（例如，允許它運行10K或50K或任意數量的仿真）。