Monte Carlo Tree Search (MCTS)
Tìm kiếm cây Monte Carlo (MCTS) chọn hành động bằng cách mở rộng cây tìm kiếm từ các lượt mô phỏng, tập trung vào những nước đi tiềm năng. Phương pháp này được dùng trong AlphaGo và robot.
Tìm kiếm cây Monte Carlo (MCTS) là thuật toán lập kế hoạch chọn hành động tiếp theo bằng cách mở rộng cây gồm các tương lai khả dĩ từ nhiều lượt mô phỏng, dành nhiều ngân sách hơn cho các nước đi có vẻ hứa hẹn nhất. Thuật toán chỉ cần cách tạo nước đi và kết quả hợp lệ, chẳng hạn luật chơi hoặc trình mô phỏng, không cần hàm đánh giá được viết thủ công. Đây cũng là thuật toán anytime: dừng ở bất kỳ thời điểm nào cũng trả về nước đi tốt nhất tìm được cho đến lúc đó, và thêm thời gian sẽ cho kết quả tốt hơn. Rémi Coulom đặt tên cho phương pháp này vào năm 2006, cùng năm Levente Kocsis và Csaba Szepesvári công bố UCT, quy tắc lựa chọn trở thành dạng tiêu chuẩn của phương pháp. MCTS đã làm thay đổi cờ vây trên máy tính chỉ trong vài năm, sau đó hỗ trợ AlphaGo và AlphaZero, và hiện được dùng để lập kế hoạch hành vi của robot và phương tiện, cũng như tìm kiếm các bước suy luận trong mô hình ngôn ngữ lớn (LLM).
MCTS hoạt động như thế nào#
Quá trình tìm kiếm duy trì một cây có gốc là trạng thái hiện tại; các nút lưu số lần được thăm và số lần những lượt thăm đó dẫn đến chiến thắng. Mỗi vòng lặp có bốn giai đoạn:
- Lựa chọn: Bắt đầu từ nút gốc, đi xuống qua các nút đã được khám phá đầy đủ bằng cách chọn nút con có điểm UCT cao nhất, cân bằng giữa tỷ lệ thắng cao và các nước đi hiếm khi được thử.
- Mở rộng: Tại nút đầu tiên có nước đi chưa được thử, thêm nước đi đó làm nút con mới.
- Mô phỏng: Chơi tiếp từ nút con mới đến hết ván, theo cách cổ điển là dùng các nước đi ngẫu nhiên, để thu được kết quả.
- Lan truyền ngược: Đi ngược lên theo đường đi và cập nhật số lượt thăm cùng tổng số lần thắng của từng nút theo kết quả.
Khi hết ngân sách, thuật toán chọn nút con được thăm nhiều nhất của nút gốc, đây là lựa chọn ổn định hơn nút có giá trị trung bình cao nhất.
Cân bằng giữa khám phá và khai thác#
UCT xem lựa chọn tại mỗi nút như một bài toán bandit đa nhánh và áp dụng công thức UCB1: điểm của một nút con bằng tỷ lệ thắng w/n cộng c·√(ln N / n), trong đó n là số lượt thăm của nút con, N là số lượt thăm của nút cha, còn c là hằng số khám phá—về lý thuyết là √2 và được tinh chỉnh trong thực tế. Số hạng thứ hai giảm khi một nước đi được thử thường xuyên hơn, nhờ đó một nước đi có vài chiến thắng may mắn không thể lấn át các nước đi còn lại và nước đi bị bỏ quên cuối cùng cũng được xem xét lại.
Ví dụ Python sau chạy MCTS trên một trò chơi nhỏ: người chơi lần lượt lấy từ một đến ba viên đá khỏi đống 10 viên, và người lấy viên cuối cùng sẽ thắng.
import math
import random
# Game: players take 1-3 stones in turn, and whoever takes the last stone wins
random.seed(0)
N, W = {(10,): 0}, {} # visits and wins per node; a node is the sequence of pile sizes from the root
def rollout(stones):
"""Play random moves to the end and return 1 if the player to move wins."""
turn = 0
while stones:
stones -= random.randint(1, min(3, stones))
turn ^= 1
return turn
def search(node):
"""Run one MCTS iteration below a node and return 1 if the player to move there wins."""
if node[-1] == 0:
return 0 # the opponent took the last stone
children = [(*node, node[-1] - k) for k in (1, 2, 3) if k <= node[-1]]
unvisited = [c for c in children if c not in N]
if unvisited: # expansion, then simulation
child = random.choice(unvisited)
N[child], W[child] = 0, 0
result = 1 - rollout(child[-1])
else: # selection by UCT, balancing win rate against how rarely a child was tried
child = max(children, key=lambda c: W[c] / N[c] + 1.4 * math.sqrt(math.log(N[node]) / N[c]))
result = 1 - search(child)
N[child] += 1 # backpropagation, with wins counted for the player who moved into the child
W[child] += result
return result
for _ in range(2000):
search((10,))
N[(10,)] += 1
for take in (1, 2, 3):
child = (10, 10 - take)
print(f"Take {take}: {N[child]} visits, win rate {W[child] / N[child]:.2f}")Lấy hai viên đá nhận được 1,889 trong tổng số 2,000 lượt thăm và thắng 91% số lần mô phỏng, so với 68 lượt thăm khi lấy một viên và 43 lượt khi lấy ba viên. Đây là nước đi chiến thắng: để lại 8 viên, là bội số của 4, cho phép người chơi đi trước đáp lại mọi nước đi bằng cách lấy sao cho số viên còn lại là bội số của 4, cho đến khi đống đá cạn. Quá trình tìm kiếm tìm ra nước đi này chỉ từ các lượt mô phỏng ngẫu nhiên và thống kê lượt thăm, không cần mã hóa chiến lược.
Từ AlphaGo đến AlphaZero và MuZero#
Hệ số phân nhánh trung bình của cờ vây là khoảng 250 nước đi hợp lệ, so với khoảng 35 trong cờ vua, khiến việc tìm kiếm vét cạn vượt quá khả năng; MCTS đã thúc đẩy bước tiến về sức mạnh cờ vây trên máy tính từ cuối thập niên 2000 trở đi. AlphaGo của DeepMind hướng dẫn MCTS bằng mạng chính sách đề xuất các nước đi có khả năng xảy ra và đánh giá trạng thái bằng cả mạng giá trị lẫn các lượt mô phỏng nhanh; tháng 3 năm 2016, hệ thống đánh bại Lee Sedol với tỷ số 4–1. AlphaZero và MuZero tiến xa hơn. AlphaZero loại bỏ hoàn toàn các lượt mô phỏng, chấm điểm trạng thái ở nút lá bằng mạng giá trị và huấn luyện mạng đó trên các ván đấu với chính nó, sử dụng số lượt thăm từ mỗi lần tìm kiếm làm mục tiêu cho mạng chính sách, qua đó biến MCTS thành một bước cải thiện chính sách bên trong học tăng cường. MuZero chạy cùng quá trình tìm kiếm bên trong một model môi trường đã học, nhờ đó có thể chơi cờ vây, cờ vua, shogi và các trò Atari mà không cần được cung cấp luật chơi.
MCTS dùng cho lập kế hoạch và suy luận#
Robot và phương tiện tự hành dùng MCTS để lập kế hoạch trong các tình huống không chắc chắn như nhập làn giao thông; các biến thể như POMCP mở rộng phương pháp này sang quy trình quyết định Markov có thể quan sát một phần bằng cách theo dõi phân phối niềm tin trên các trạng thái ẩn. Một quá trình tìm kiếm lập kế hoạch từ đầu vào camera cần có trạng thái gốc: chẳng hạn, một cánh tay robot chơi cờ vua có thể dùng model Ultralytics YOLO26 được huấn luyện trên ảnh bàn cờ để xác định vị trí từng quân cờ, rồi dùng trạng thái bàn cờ khôi phục làm gốc của quá trình tìm kiếm.
Trong suy luận của LLM, mỗi nút là một lời giải từng phần và mỗi cạnh là một bước suy luận; model thưởng cho quá trình hoặc bước kiểm tra câu trả lời sẽ chấm điểm các nhánh. rStar-Math của Microsoft sử dụng MCTS cùng model ưu tiên quá trình để nâng Qwen2.5-Math-7B từ 58,8% lên 90,0% trên benchmark MATH. Tree of Thoughts thay vào đó tìm kiếm qua các bước suy luận bằng thuật toán tìm kiếm theo chiều rộng hoặc chiều sâu. MCTS khó áp dụng hơn trong quá trình huấn luyện: DeepSeek liệt kê phương pháp này trong số những nỗ lực không thành công đối với DeepSeek-R1, vì không gian chuỗi token lớn hơn nhiều so với không gian của một trò chơi bàn cờ và model giá trị hướng dẫn việc tìm kiếm rất khó huấn luyện; thay vào đó, R1 được huấn luyện bằng học tăng cường với phần thưởng có thể xác minh.










