Cấp phép YOLO
Quay lại Bảng thuật ngữ Ultralytics

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:

  1. 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ử.
  2. 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.
  3. 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ả.
  4. 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.

Khám phá các giải pháp

Thị giác máy tính trong thể thao

Thị giác máy tính trong thể thao

Khám phá cách Ultralytics YOLO thúc đẩy thị giác máy tính trong thể thao với khả năng theo dõi cầu thủ và bóng, phân tích hiệu suất, cung cấp thông tin chuyên sâu cho huấn luyện và hỗ trợ phục hồi cho vận động viên.
Tìm hiểu thêm
Thị giác máy tính cho ảnh hàng không

Thị giác máy tính cho ảnh hàng không

Chuyển hình ảnh từ drone và ảnh hàng không thành thông tin chuyên sâu theo thời gian thực cho nông nghiệp, nuôi trồng thủy sản, bảo tồn và phân tích không gian địa lý với Ultralytics YOLO.
Tìm hiểu thêm
Thị giác máy tính trong hàng không vũ trụ

Thị giác máy tính trong hàng không vũ trụ

Ứng dụng computer vision trong ngành hàng không vũ trụ với Ultralytics YOLO cho kiểm tra máy bay, phát hiện dị vật trên đường băng (FOD), vận hành mặt đất tại sân bay và phát hiện lỗi vật liệu composite.
Tìm hiểu thêm
Computer vision trong lĩnh vực an ninh

Computer vision trong lĩnh vực an ninh

Bảo vệ mọi địa điểm bằng model Ultralytics YOLO. Vision AI hỗ trợ giám sát vành đai, phát hiện mối đe dọa, nhận dạng biển số và an toàn nơi làm việc.
Tìm hiểu thêm
Computer vision trong robotics

Computer vision trong robotics

Tăng cường năng lực cho máy móc thông minh bằng model Ultralytics YOLO. Vision AI trong lĩnh vực robotics hỗ trợ điều hướng tự động, nhận thức, theo dõi đối tượng và điều khiển theo thời gian thực.
Tìm hiểu thêm
Thị giác máy tính trong logistics

Thị giác máy tính trong logistics

Tinh giản hoạt động logistics với các model Ultralytics YOLO. Vision AI hỗ trợ kiểm tra kiện hàng, phân loại, theo dõi phương tiện và giám sát an toàn kho hàng theo thời gian thực.
Tìm hiểu thêm
Thị giác máy tính trong bán lẻ

Thị giác máy tính trong bán lẻ

Định hình lại hoạt động bán lẻ với các model Ultralytics YOLO. Vision AI hỗ trợ theo dõi hàng tồn kho, giám sát kệ hàng, quản lý hàng chờ và phân tích khách hàng thông minh hơn.
Tìm hiểu thêm
Thị giác máy tính trong chăm sóc sức khỏe

Thị giác máy tính trong chăm sóc sức khỏe

Xây dựng các giải pháp chăm sóc sức khỏe với model Ultralytics YOLO. Vision AI trong chăm sóc sức khỏe hỗ trợ xử lý hình ảnh y tế nhanh hơn, chẩn đoán thông minh hơn và theo dõi bệnh nhân.
Tìm hiểu thêm
Thị giác máy tính trong sản xuất

Thị giác máy tính trong sản xuất

Tối ưu hóa sản xuất bằng các model Ultralytics YOLO. Vision AI thúc đẩy kiểm soát chất lượng, phát hiện lỗi, tuân thủ PPE và tự động hóa dây chuyền lắp ráp.
Tìm hiểu thêm
Thị giác máy tính trong ngành ô tô

Thị giác máy tính trong ngành ô tô

Ứng dụng thị giác máy tính trong ngành ô tô với các model Ultralytics YOLO. Vision AI nâng cao an toàn giao thông, hỗ trợ người lái và tự động hóa phương tiện để tạo nên những tuyến đường thông minh hơn.
Tìm hiểu thêm
Thị giác máy tính trong nông nghiệp

Thị giác máy tính trong nông nghiệp

Ứng dụng AI thị giác vào nông nghiệp thông minh với các model Ultralytics YOLO. Hỗ trợ giám sát cây trồng, theo dõi vật nuôi và canh tác chính xác để nâng cao năng suất một cách thông minh hơn.
Tìm hiểu thêm

Hãy cùng nhau kiến tạo tương lai của AI!

Bắt đầu hành trình hướng đến tương lai của machine learning