MCTS (Monte Carlo Tree Search) hay Monte Carlo Tree Search là một giải thuật tìm kiếm trên cây sử dụng lấy mẫu ngẫu nhiên để đưa ra quyết định. Được phát triển từ những năm 1990 và áp dụng thành công bởi AlphaGo vào năm 2016, MCTS trở thành nền tảng của các hệ thống AI chơi trò chơi và ra quyết định phức tạp.
Tại sao cần MCTS cho trò chơi phức tạp?
Trong nhiều trò chơi hoặc bài toán tối ưu, số lượng trạng thái có thể là vô hạn hoặc rất lớn. Ví dụ với trò Go 19×19, số lượng bước đi khả dĩ lên tới 10170 — một con số khổng lồ hơn số nguyên tử trong vũ trụ quan sát được.
Các giải thuật truyền thống như minimax với alpha-beta pruning không thể duyệt hết không gian trạng thái trong thời gian hợp lý. MCTS giải quyết vấn đề này bằng cách:
- Mẫu hóa ngẫu nhiên: Thay vì duyệt toàn bộ cây, MCTS lấy mẫu ngẫu nhiên các nhánh hứa hẹn nhất.
- Dần dần xây dựng cây: Chỉ mở rộng những nút (node) được đánh giá là quan trọng qua nhiều lần mô phỏng.
- Kết hợp neural network: Trong AlphaGo, MCTS kết hợp với CNN (mạng nơ-ron tích chập) để dự đoán xác suất thắng và ưu tiên nhánh tìm kiếm.
4 bước cốt lõi của MCTS
Quá trình tìm kiếm MCTS diễn ra theo vòng lặp 4 bước, được lặp lại nhiều lần cho đến khi hết thời gian:
- Selection (Lựa chọn): Từ gốc cây, đi xuống theo chính sách UCT (Upper Confidence Trees) để cân bằng khai thác (exploitation) và khám phá (exploration). Công thức UCT:
w���/n��� + c��(ln N/n���). - Expansion (Mở rộng): Khi đến nút chưa được thăm, thêm một hoặc nhiều nút con tương ứng với các nước đi hợp lệ.
- Simulation (Mô phỏng): Từ nút mới, chơi ngẫu nhiên (hoặc theo policy network) cho đến khi kết thúc ván. Trước 2006 dùng playout ngẫu nhiên thuần túy; sau này dùng heuristics hoặc policy network để mô phỏng thông minh hơn.
- Backpropagation (Lan truyền ngược): Cập nhật thống kê thắng/thua và số lần thăm cho tất cả nút trên đường đi từ lá về gốc.
AlphaGo: MCTS kết hợp Deep Learning
Đột phá của AlphaGo (DeepMind, 2016) là kết hợp MCTS với hai mạng nơ-ron sâu:
- Policy Network (Mạng chính sách): Dự đoán xác suất chọn nước đi tốt, giảm không gian tìm kiếm.
- Value Network (Mạng giá trị): ��ớc lượng xác suất thắng từ một vị trí bàn cờ, thay thế playout ngẫu nhiên.
Kết quả: AlphaGo đánh bại Fan Hui (5-0, tháng 10/2015), Lee Sedol (4-1, tháng 3/2016) và Ke Jie (3-0, tháng 5/2017) — lần đầu tiên AI vượt qua kỳ thủ chuyên nghiệp cao nhất trên bàn cờ 19×19 đầy đủ.
AlphaGo Zero và AlphaZero: Tự học hoàn toàn
Sau AlphaGo, DeepMind phát hành AlphaGo Zero (2017) — không dùng dữ liệu ván cờ người, chỉ tự chơi (self-play) từ đầu. AlphaZero mở rộng ra cờ Vua, Shōgi và Go, đạt cấp siêu nhân chỉ sau vài giờ tự học.
Điểm mới so với AlphaGo gốc:
- Mạng duy nhất thay vì hai: Policy và Value được chia sẻ các tầng dưới.
- Không có rollout ngẫu nhiên — Value network thay thế hoàn toàn.
- MCTS dùng UCT với
c_puctđiều chỉnh bởi policy network.
��ng dụng thực tế vượt ra ngoài trò chơi
MCTS không chỉ dùng cho Go/Cờ Vua. Các ứng dụng thực tế:
| Lĩnh vực | ��ng dụng |
|---|---|
| Robotics | Lập kế hoạch chuyển động, điều khiển robot tự chủ |
| Tối ưu hóa | Lộ trình logistics, lịch trình sản xuất |
| Sinh học tính toán | Thiết kế protein, dự đoán cấu trúc RNA |
| Tài chính | Tối ưu danh mục đầu tư, định giá quyền chọn |
| Video game | AI đối thủ trong Total War, Civilization, F.E.A.R. |
So sánh MCTS với các giải thuật khác
| Giải thuật | ��u điểm | Nhược điểm |
|---|---|---|
| Minimax + Alpha-Beta | Tối ưu trong không gian nhỏ, có hàm đánh giá tốt | Bùng nổ tổ hợp, cần heuristic mạnh |
| MCTS thuần túy | Không cần hàm đánh giá, xử lý không gian lớn | Chậm hội tụ, cần nhiều mô phỏng |
| MCTS + Neural Network (AlphaZero) | Tự học, siêu nhân, tổng quát hóa tốt | Yêu cầu GPU/TPU lớn, huấn luyện tốn kém |
Thử thách và hạn chế của MCTS
Mặc dù mạnh, MCTS vẫn có những giới hạn:
- Độ trễ: Cần nhiều mô phỏng để hội tụ — không phù hợp real-time khắt khe.
- Khó khăn với không gian hành động khổng lồ: Nếu số nước đi hợp lệ quá lớn, Selection/Expansion trở nên chậm.
- Phụ thuộc phần cứng: AlphaZero cần hàng nghìn TPU để huấn luyện trong vài ngày.
Tóm tắt
MCTS là giải thuật tìm kiếm cây dựa trên lấy mẫu Monte Carlo, cân bằng khám phá và khai thác thông qua UCT. Khi kết hợp với Deep Learning (Policy/Value Network), MCTS đạt hiệu suất siêu nhân ở Go, Cờ Vua, Shōgi và mở ra ứng dụng rộng lớn trong robotics, tối ưu hóa, sinh học và tài chính. Hiểu MCTS là chìa khóa để nắm bắt cách AI hiện đại ra quyết định trong môi trường phức tạp, không xác định.
Nguồn tham khảo: Wikipedia – Monte Carlo tree search, Wikipedia – AlphaGo, DeepMind AlphaGo
