Thuật toán tìm kiếm trên cây Monte Carlo (MCTS)

Tìm kiếm Cây Monte Carlo (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 lĩnh vực học máy và trí tuệ nhân tạo. Như được 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 trên 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. Ban đầu đượ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 tác nhân AI hiện đại và các hệ thống suy luận tiên tiến, bao gồm cả các Mô hình Ngôn ngữ Lớn (LLMs) tiên tiến nhất.

Cách thức hoạt động của thuật toán Tìm kiếm trên cây Monte Carlo

MCTS xây dựng cây tìm kiếm theo từng bước bằng cách khám phá các hành động có triển vọng nhất. Hoạt động dựa trên 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 giới hạn tài nguyên tính toán hoặc thời gian:

1. Quy trình lựa chọn: Bắt đầu từ nút gốc, thuật toán di chuyển xuống cây bằng cách chọn các nút con để cân bằng giữa việc khám phá (thử các đường đi mới) và khai thác (ưu tiên các đường đi đã mang lại phần thưởng cao trong quá khứ). Công thức Giới hạn tin cậy trên áp dụng cho cây (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: 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 sẽ đượ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 (Rollout): Một mô phỏng nhanh, thường được thực hiện ngẫu nhiên, được chạy từ nút vừa được mở rộng đến cuối kịch bản để dự đoán kết quả.
4. Truyền ngược: Kết quả mô phỏng được truyền ngược lên cây, cập nhật thống kê thành công và giá trị của tất cả các nút đã đi qua để làm cơ sở cho các lựa chọn tiếp theo.

Ứng dụng thực tế trong AI

Một nghiên cứu toàn diện về các phương pháp Tìm kiếm Cây Monte Carlo đã chỉ ra khả năng ứng dụng linh hoạt của phương pháp này trong việc giải quyết các bài toán có không gian tìm kiếm khổng lồ và không thể xử lý bằng các phương pháp tính toán thông thường.

• Chơi trò chơi: MCTS đã được công nhận trên toàn cầu khi Google sử dụng thuật toán này để phát triển AlphaGo, tạo ra hệ thống trí tuệ nhân tạo đầu tiên đánh bại nhà vô địch thế giới của loài người trong trò chơi cờ vây. Bằng cách kết hợp MCTS với mạng nơ-ron, hệ thống có thể đánh giá hiệu quả các tình huống trên bàn cờ vốn quá phức tạp để áp dụng phương pháp tìm kiếm thử hết mọi khả năng truyền thống.
• Suy luận của LLM và Trí tuệ nhân tạo có khả năng hành động: Trong năm 2024 và 2025, các nhà nghiên cứu ngày càng tích hợp MCTS với LLM để nâng cao khả năng tư duy và logic thuộc "Hệ thống 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 mô hình ngôn ngữ lớn (LLMs) xử lý 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ở kiến thức và suy luận toán học bằng cách đánh giá nhiều đường dẫn 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 giải quyết vấn đề.
• Robot học và Lập kế hoạch tự động: MCTS được ứng dụng trong tối ưu hóa logistics và định tuyến, xe tự hành, và phân chia hành động của robot để mô phỏng các trạng thái trong tương lai và di chuyển an toàn trong các môi trường vật lý phức tạp.

MCTS so với các khái niệm liên quan

Để hiểu rõ 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:

• Học tăng cường (RL): Trong khi RL huấn luyện các mô hình theo thời gian để học được một chính sách tổng thể, thì MCTS thường là một thuật toán lập kế hoạch được sử dụng trong quá trình suy luận thời gian thực để tìm ra hành động tức thời tối ưu từ một trạng thái cụ thể. Tuy nhiên, hai phương pháp này 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.
• Cây Suy nghĩ (ToT): ToT là một khung công cụ gợi ý được thiết kế riêng cho các mô hình ngôn ngữ lớn (LLMs). Khung công cụ này chịu ảnh hưởng sâu sắc từ MCTS, tổ chức quá trình tạo ngôn ngữ dưới dạng một cây, trong đó mỗi nút đại diện cho một "suy nghĩ". MCTS là nền tảng thuật toán rộng lớn hơn mà ToT và các khung công cụ tương tự được xây dựng dựa trên đó.

Tích hợp Trí tuệ nhân tạo thị giác vào MCTS

Trong lĩnh vực trí tuệ nhân tạo có cơ thể (embodied AI) hoặc các hệ thống tự chủ, 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 sử dụng Ultralytics , một tác nhân có thể nhanh chóng đánh giá 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ụ minh họa cách bạn có thể sử dụngYOLO Ultralytics để tính toán phần thưởng nút đơn giản trong quá trình triển khai 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 quy mô các tác nhân thông minh như vậy, Ultralytics cung cấp các công cụ mạnh mẽ để huấn luyện và triển khai các mô hình thị giác cơ bản. Điều này giúp việc tích hợp khả năng nhận thức nhanh chóng và đá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 khung học máy như PyTorch và TensorFlow.