又是一個本來要棄賽的一天，還好明天颱風假救了我，又多一天可以趕稿了。

今天要來介紹非常有名的Monte Carlo Tree Search (MCTS)，因為內容實在太多所以我會拆成兩篇來介紹。

Pure Monte Carlo Search

如果我們直接把Monte Carlo Method套用在對局上，步驟如下：

1. 對每個可能的下一步棋進行模擬。
2. 從該步開始隨機進行多場遊戲，並記錄每場比賽的結果。
3. 計算該棋步的平均得分。
4. 選擇平均得分最高的棋步。

這樣會產生一些問題

• 浪費資源
  有可能浪費大量的模擬資源，因為它對每個子節點進行相同數量的模擬，而沒有考慮提前終止較差分支的可能性，應該要分配更多資源在那些較佳的節點上。
• 好的節點被稀釋掉
  用來評估棋步價值的分數是該棋步為根的子樹中葉節點的平均分數，因此真正最佳棋步就有可能被其他分支較低的分數稀釋，進而被低估並忽略，如下圖，Minimax會選擇左邊的節點，而Pure Monte Carlo Search會選擇右邊的節點。

Monte Carlo Tree Search

以下是大家熟悉的MCTS四個步驟。

• Selection：
  選擇要進行展開下一層的葉節點。
• Expansion：
  展開一個或多個子節點。這些新的子節點代表潛在的下一步行動，並為後續模擬提供新的分支。
• Simulation (playout、rollout)：
  從當前節點進行隨機模擬，直到遊戲結束。這一過程不需要額外的策略，僅依賴隨機選擇。其目的是估計該節點的潛在勝率。
• Backpropagation ：
  Simulation結束後，根據結果更新節點的評價。從模擬終局節點開始，將結果向上回傳至根節點，更新沿途所有節點的勝率和遊戲次數統計資訊。

接著為了解決上面的問題，我們要先對Selection進行優化。

Multi-armed Bandit Problem

Multi-armed Bandit Problem (多臂吃角子老虎機問題)

圖片來源吃角子老虎機，沒去過賭場也沒看過的吃角子老虎機的可以先點進去看看介紹。

假設你週末想去澳門翻身旅遊，到了一家賭場，前面有多台吃角子老虎機，每台機器的回報率(中獎率)是未知的，而且各自不同。你每次只能選擇拉其中一台機器，每拉一次，你會根據該機器的隨機回報機率得到一個獎勵。

假設有 A 跟 B 兩台機器，A 機器的回報率是 80%，B 機器的回報率是 40%，但是你事先並不知道這兩台機器的回報率。這時選擇拉哪一台機器就變得非常重要。如果能夠選擇到回報率更高的機器，當然能夠在有限次數內獲得最大的回報，那如何在不知道回報率的情況下做出最佳決策呢？

隨機選擇

如果每次操作都隨機選擇一台機器，那麼這顯然不是最佳策略。因為這樣你不能有效地利用先前的結果來推斷出哪台機器更有可能給你帶來更高的回報。隨機選擇意味著你完全依賴運氣，無法積累經驗以改善未來的決策。

經驗法則

一種常見的策略是基於過去的經驗來進行決策。例如先試了一次 A 機器，但沒中獎，然後試了一次 B 機器，結果中獎了。根據這樣的經驗，你可能會認為 B 機器更容易中獎，因此在後續的操作中，你會更傾向於選擇 B 機器。
這種情況聽起來合理，但卻隱藏著一個重大風險。如果你恰巧在第一次嘗試 A 機器時沒中，而 B 機器在你第一次嘗試時中獎，這可能會誤導你一直偏向於選擇 B 機器。 雖然 B 的回報率其實只有 40%，但因為它曾經中獎過，你可能會持續選擇它，而忽略了回報率更高的 A 機器。
因為你曾經在 B 機器上中過一次獎，你會產生一種錯覺，認為它更「幸運」，從而持續使用它，即使後來 B 機器再也沒中獎，但在你嘗試的次數中，B 的歷史平均回報始終比 A 的零回報要高。這樣一來，你會錯過回報率更高的 A 機器，僅僅因為初期的運氣不佳，沒有足夠的探索去發現 A 機器實際上有更高的回報率。

但我覺得這種忽略了理性分析，過度依賴於一次偶然的正面經驗，其實還蠻符合人性的XD。

在嘗試新的機器與繼續使用過往經驗表現較佳的機器，這就是「多臂吃角子老虎機問題」中的exploration (探索) 與exploitation (開發利用) 的平衡難題，尤其是當你面對更多台機器時，你需要在探索新機器和利用現有的最好機器之間做出選擇。

再舉一個比較日常的例子，比如每天中午我都會不知道要吃什麼，不知道大家有沒有相同的煩惱，到底要去踩雷呢，還是要吃平常吃過的那些，如果每天都去踩雷那就有可能每天都吃到難吃的，每天吃平常吃過覺得不錯的食物，就有可能錯過許多美食。

ε-Greedy Algorithm

此時使用 ε-Greedy Algorithm 就是一個簡單又有效方法，預先設定一個機率 ε，有 ε 的機率會從全部機台選擇一個機台（exploration），另外的 1 - ε 機率直接選過去表現最好的機台（exploitation）。

在這個過程中，隨著你拉機器次數的增加，你會對每台機器的回報率有越來越多的了解，你可以逐步降低 ε 的值，當你對每台機器有更多了解時，探索的頻率會逐漸減少，轉而專注於使用高回報的機器。

比如你已經分別在 A 與 B 機器拉了100次，假設分別中獎次數為81、39，明顯可以看出 A 機器的回報率更高，那就可以降低 ε，更專注於 A 機器了，甚至可以考慮不再使用 B 機器。

UCB (Upper Confidence Bound)

$$
a_t = \underset{a}{\mathrm{argmax}} \left( \hat{Q}(a) + U(a) \right)
$$

UCB 策略基於「樂觀地探索未知」，會根據每台機器的平均回報和不確定性來決定下一步的動作。

具體來說，每台機器 $a$ 的回報是通過以下公式來計算的：

$$
Q(a) + U(a) = \text{回報平均值} + \sqrt{\frac{2 \log t}{N(a)}}
$$

其中：

• $Q(a)$ 是目前已知的回報平均值。
• $U(a)$ 是不確定性的量度，這部分會隨著你玩某一台機器的次數 $N(a)$ 增加而減少，這意味著你會逐漸更多地關注高回報且已經嘗試過多次的機器。

UCB 策略確保了當你還沒有充分了解某台機器時，你會偏向於更多地探索它。隨著你對不同機器的理解變得更好，UCB 策略會自動轉向利用那些確定性較高且回報較高的機器。

Reference

• 電腦對局導論
• Monte-Carlo Tree Search
• Multi-armed Bandit Problem
• UCT (UCB applied to Trees) - Bandit Based Monte-Carlo Planning