Monte Carlo Tree Search (MCTS)

Monte Carlo Tree Search (MCTS) là một thuật toán tìm kiếm heuristic được sử dụng cho các quy trình ra quyết định phức tạp, chủ yếu trong học máy và trí tuệ nhân tạo. Như đã nêu trong định nghĩa trên Wikipedia, MCTS kết hợp độ chính xác của các thuật toán tìm kiếm cây với sức mạnh của lấy mẫu ngẫu nhiên (mô phỏng Monte Carlo) để đánh giá các nước đi hứa hẹn nhất trong một không gian trạng thái nhất định. Vốn được phổ biến nhờ thành công trong các trò chơi bàn cờ phức tạp, thuật toán này hiện là thành phần nền tảng của các AI agent hiện đại và các hệ thống lý luận tiên tiến, bao gồm các Large Language Models (LLMs) hàng đầu.

Link to this sectionCách thức hoạt động của Monte Carlo Tree Search#

MCTS xây dựng cây tìm kiếm một cách gia tăng bằng cách khám phá các hành động hứa hẹn nhất. Hoạt động theo Quy trình quyết định Markov, thuật toán lặp lại bốn giai đoạn liên tục cho đến khi đạt đến ngân sách tính toán hoặc giới hạn thời gian:

1. Lựa chọn (Selection): Bắt đầu từ nút gốc, thuật toán duyệt xuống cây bằng cách chọn các nút con cân bằng giữa khám phá (thử các đường đi mới) và khai thác (ưu tiên các đường đi có phần thưởng cao trong quá khứ). Công thức Upper Confidence Bound applied to Trees (UCT) là một phương pháp tiêu chuẩn được sử dụng để quản lý sự cân bằng này.

2. Mở rộng (Expansion): Trừ khi nút được chọn kết thúc quá trình mô phỏng, một hoặc nhiều nút con được thêm vào để mở rộng cây tìm kiếm sang các trạng thái chưa được khám phá.

3. Mô phỏng (Simulation/Rollout): Một quá trình mô phỏng nhanh, thường là ngẫu nhiên, được chạy từ nút mới mở rộng đến cuối kịch bản để dự đoán kết quả.

4. Lan truyền ngược (Backpropagation): Kết quả của quá trình mô phỏng được lan truyền ngược lên cây, cập nhật số liệu thống kê thành công và giá trị của tất cả các nút đã duyệt qua để cung cấp thông tin cho các lựa chọn trong tương lai.

Link to this sectionCác ứng dụng thực tế trong AI#

Một khảo sát toàn diện về các phương pháp Monte Carlo Tree Search nêu bật tính linh hoạt của nó trong việc giải quyết các bài toán với không gian tìm kiếm khổng lồ và không thể tính toán được.

• Game Playing: MCTS achieved global recognition when Google DeepMind used it to power AlphaGo, creating the first AI to defeat a human world champion in the game of Go. By pairing MCTS with neural networks, the system could effectively evaluate board states that were too vast for traditional brute-force search.
• Lý luận LLM và Agentic AI: Trong năm 2024 và 2025, các nhà nghiên cứu ngày càng tích hợp MCTS với LLMs để tăng cường khả năng tư duy và logic "System 2". Ví dụ, nghiên cứu gần đây về thiết kế heuristic tự động chứng minh cách MCTS giúp các LLMs điều hướng các tối ưu hóa phức tạp. Tương tự, việc kết hợp MCTS với LLMs cải thiện đáng kể hiệu suất trong trả lời câu hỏi dựa trên cơ sở tri thức và lý luận toán học bằng cách đánh giá nhiều lộ trình logic tiềm năng trước khi đưa ra câu trả lời. Các tổ chức như OpenAI tận dụng các cơ chế suy luận dựa trên tìm kiếm trong các mô hình tiên tiến của họ, chẳng hạn như OpenAI's o1, để cải thiện đáng kể độ chính xác trong việc giải quyết vấn đề.
• Robotics và Lập kế hoạch tự hành: MCTS được sử dụng trong tối ưu hóa logistics và định tuyến, phương tiện tự hành và action chunking cho robot để mô phỏng các trạng thái tương lai và điều hướng an toàn trong các môi trường vật lý phức tạp.

Link to this sectionMCTS so với các khái niệm liên quan#

Để hiểu đầy đủ về MCTS, việc phân biệt nó với các kỹ thuật AI liên quan sẽ rất hữu ích:

• Reinforcement Learning (RL): Trong khi RL đào tạo các mô hình theo thời gian để học một chính sách toàn cục, MCTS thường là một thuật toán lập kế hoạch được sử dụng trong quá trình real-time inference để tìm ra hành động tức thời tốt nhất từ một trạng thái cụ thể. Tuy nhiên, cả hai thường được kết hợp với nhau; các mô hình RL có thể cung cấp giá trị heuristic cho các nút MCTS.
• Tree of Thoughts (ToT): ToT là một framework nhắc lệnh (prompting framework) được thiết kế rõ ràng cho các LLMs. Nó được truyền cảm hứng mạnh mẽ từ MCTS, cấu trúc việc tạo ngôn ngữ như một cái cây, nơi mỗi nút đại diện cho một "suy nghĩ". MCTS là nền tảng thuật toán rộng hơn mà ToT và các framework tương tự xây dựng dựa trên đó.

Link to this sectionTích hợp Vision AI vào MCTS#

Trong AI thực thể hoặc các hệ thống tự hành, nhận thức thị giác thường đóng vai trò là bộ đánh giá trạng thái cho một nút MCTS. Bằng cách tận dụng Ultralytics YOLO26, một agent có thể đánh giá nhanh chóng một môi trường để tính toán điểm heuristic trong giai đoạn mô phỏng.

Dưới đây là một ví dụ khái niệm cho thấy cách bạn có thể sử dụng một mô hình Ultralytics YOLO để tính toán phần thưởng nút đơn giản trong quá trình rollout của MCTS.

from ultralytics import YOLO

# Load an Ultralytics YOLO26 model for state evaluation
model = YOLO("yolo26n.pt")


def evaluate_mcts_state(image_state):
    # Run inference to evaluate the visual environment
    results = model(image_state, verbose=False)

    # Example heuristic: Reward the MCTS path if an 'obstacle' is successfully avoided
    # Assume class 0 is 'obstacle'. Reward is 1 if path is clear, 0 if blocked.
    obstacle_detected = any(box.cls == 0 for box in results[0].boxes)
    return 0 if obstacle_detected else 1


# Simulate a rollout step
reward = evaluate_mcts_state("path_simulation_view.jpg")
print(f"MCTS Rollout Reward: {reward}")

Đối với các nhà phát triển muốn mở rộng các agent thông minh như vậy, Ultralytics Platform cung cấp các công cụ mạnh mẽ để đào tạo và triển khai các mô hình thị giác nền tảng. Điều này giúp việc tích hợp nhận thức nhanh chóng, đáng tin cậy vào các kiến trúc tìm kiếm phức tạp được xây dựng bằng các thư viện toán học tiêu chuẩn hoặc các framework học máy như PyTorch và TensorFlow trở nên dễ dàng hơn đáng kể.