← 回首頁

蒙地卡羅樹搜尋 MCTS/UCB(賽局樹逐迭代成長)

下棋時想找出最好的一步,把每種走法都算到底其實算不完——分支多到天文數字。蒙地卡羅樹搜尋(MCTS) 換個懶人思路:與其窮舉,不如「隨手挑幾種走法,各自在腦中亂玩到分出勝負」很多遍,哪種走法贏的次數多就傾向選它, 同時偶爾也試試還沒玩過的走法,免得錯過好棋。這種「多試幾次、用結果回頭修正判斷」的探索與利用取捨, 正是 AlphaGo 打敗人類、以及今天 AI agent 規劃多步行動時共用的核心招式。下面你會看到它把一個小遊戲反覆模擬, 並和事先精確算出的必勝步同場對照,看「隨機估計」怎麼慢慢逼近「真值」。

MCTS(Monte Carlo Tree Search)反覆執行「選擇(UCB1)→ 擴展 → 模擬(rollout)→ 回傳(backpropagation)」 四個階段:選擇沿樹下降,未曾建立子節點的動作視為無限優先,已完全展開的節點則用 UCB1(Upper Confidence Bound,信賴上界—— 在「選目前已知勝率較高的」和「去試還沒試幾次的」之間取平衡,勝率 + 探索項)取捨; 擴展在選擇止步處建立一個新節點作為本次模擬起點;模擬從該節點以決定性隨機政策反覆走子直到終局,記錄勝者; 回傳沿本次選擇路徑逐節點更新造訪次數與勝場。反覆 N 次後,以「造訪次數最多」的子節點作為最終推薦動作—— 這是用大量隨機模擬的統計逼近精確解,而非窮舉。本頁把賽局縮到 Nim 單堆(pile=5,每步取 1 或 2,取走最後 一顆者勝),因為這個規模小到可以用 minimax 精確算出必勝步,讓「MCTS 估計」與「真值」能夠同幀並列對照。

為什麼 AI 時代重要

AlphaGo/AlphaZero 用 MCTS + 神經網路價值/策略估計取代窮舉搜尋,在圍棋這種狀態空間大到無法窮舉的賽局中 找出接近最優的落子;今日的 LLM agent 規劃(多步工具呼叫、程式生成的候選路徑搜尋、對話策略規劃)同樣借用 「選擇最有希望的分支 → 模擬到底看結果 → 用結果回頭修正判斷」這套模式,本質上都是「用隨機模擬的統計取代 精確計算」的模擬式決策——UCB1 的探索/利用權衡(explore/exploit trade-off)也是 agent 規劃、推薦系統、 A/B 測試等場景反覆出現的核心思想。

它是賽局理論與隨機化的延伸

MCTS 的樹搜尋建立在賽局理論的必勝判定之上:本頁的 minimax 精確解沿用 雜項頁的 Nim 賽局必勝盤面判定(輸盤面 = 3 的倍數),只是 MCTS 刻意不直接呼叫這個精確解,而是用隨機模擬去逼近它,藉此展示「估計 vs 真值」的收斂過程。模擬(rollout) 階段的決定性隨機政策則沿用 取樣演算法頁同一顆 LCG(線性同餘產生器,burn-in 3 步、高位取值)—— 同一套決定性偽隨機機制,一個用於串流抽樣維持代表性樣本,一個用於賽局模擬逼近最優策略。

MCTS(四相迭代:選擇 UCB1 → 擴展 → 模擬 rollout → 回傳)

每個節點代表「走到此盤面所需的完整路徑」(同一顆數在樹的不同分支各自成一個節點)。選擇迴圈:終局節點 直接停止;否則若有未曾建立子節點的合法動作,取索引最小者(未訪動作的 UCB1 值視為無限,恆優先);否則以 UCB1 = 對手視角換算後的勝率 + c·√(ln(parent 造訪次數)/child 造訪次數) 取最大值(c=√2,平手取索引小)。 模擬(rollout)從擴展節點以固定種子的 LCG 反覆走子至終局;若擴展節點本身已是終局(終局捷徑),不擲骰、 不消耗亂數,勝者由盤面直接決定。

固定資料:Nim 單堆 pile=5,每步取 1 或 2;UCB1 探索係數 c=√2;rollout LCG 種子 seed=4; 迭代數 N=16;minimax 精確解最佳步 = 取 2(留 3,逼對手進入必敗盤面)。
迭代:0 / 16 rollout 模擬次數:0(終局捷徑不擲骰,不計入) 目前推薦:(尚無子節點)
階段:初始化
賽局樹:節點內數字為該盤面剩餘顆數(pile),節點上方 v=?/w=? 為該節點目前的 造訪次數/勝場——wins 視角提醒:w 統計的是「站在這個節點、輪到誰走」的那一方之後贏了幾次, 不是走到這個節點那步棋所屬玩家的勝場;下方對照表的 winRate 已換算成 父節點視角 (1 − w/v),才能跟 minimax 的「對自己最有利」直接對照,兩邊數字看起來不同並非錯誤。 橘色(current)=當下選擇/擴展/模擬所在節點;藍色外框(frontier)=本次迭代新建立的節點; 紫色(visited)=本次選擇路徑走訪過的既有節點;綠色(finalized)=本次回傳更新的路徑,或終幀的 推薦獲勝路徑。
誠實揭露 1——收斂但非保證:本頁固定種子(seed=4)跑 16 次迭代後,root 推薦動作收斂到 minimax 的精確解「取 2」,但這是這個種子、這個迭代數下的實測結果,換一顆種子或迭代數不夠,MCTS 完全可能收斂到錯誤動作或根本不收斂——MCTS 本質是統計逼近,不是精確演算法,不保證任何單次執行都 收斂到真值。
誠實揭露 2——過程並非單調收斂:本頁推薦動作的逐迭代序列是 [取1, 取1, 取2, 取2, 取2, 取1, 取2, 取2, 取2, 取2, 取2, 取2, 取2, 取2, 取2, 取2]——第 6 次 迭代(iter5)一度從「取 2」搖擺回「取 1」(小樣本下單次 rollout 結果的雜訊),第 7 次迭代起才穩定 收斂在「取 2」。這正是「估計」的真實面貌:即使最終收斂,過程未必單調,教學上刻意保留這個搖擺, 不做美化。
誠實揭露 3——rollout 次數 ≠ 迭代數:上方「rollout 模擬次數」最終停在 8,而不是迭代數 16——因為每次迭代若選擇止步於既有終局節點(終局捷徑),勝者由盤面直接決定,不需要、也不會擲骰 模擬,本頁誠實地不把這種情況計入 rollout 次數。
教學縮尺:本頁選用可用 minimax 精確解算出來的小型 Nim(pile=5),只為了讓「MCTS 估計 vs 真值」的對照可行;MCTS 真正的優勢場景是圍棋/西洋棋/agent 規劃等狀態空間大到無法窮舉精確解的 賽局——那些場景根本沒有 minimax 精確解可供對照,本頁能對照全靠賽局刻意縮小,這是教學上的簡化, 不是 MCTS 規模優勢的示範。

root 子節點統計 vs minimax 精確解對照

走法visitswins(父視角)winRate(父視角)minimax 對照

已執行操作紀錄(opLog)

(空)