Các nguyên lý cơ bản của khám phá đồ thị Monte Carlo
- Monte Carlo Tree Search (MCTS) khi được áp dụng lên đồ thị có hướng thay vì cây sẽ trở thành "Monte Carlo Graph Search" ("MCGS"), và đôi khi bị xem là khó hiện thực.
- Các tài liệu học thuật hiện có thường theo mô tả "tiêu chuẩn" của MCTS trên cây, nên việc khái quát hóa sang đồ thị khá khó nắm bắt về mặt khái niệm.
- Tài liệu này đưa ra một cách giải thích được xem là trực quan hơn, về bản chất là tương đương nhưng gọn gàng hơn, và suy ra từ các nguyên lý nền tảng vì sao việc khám phá đồ thị cần phải hoạt động theo cách này.
Giới thiệu / bối cảnh
- Trong các ứng dụng khám phá cây trò chơi hoặc các bài toán khám phá cây khác, có thể tồn tại nhiều chuỗi nước đi hay hành động khác nhau dẫn đến cùng một trạng thái.
- Ví dụ, trong cờ vua,
1. d4 d5 2. Nf3 dẫn đến cùng một thế cờ như 1. Nf3 d5 2. d4.
- Khi những tình huống như vậy có thể xảy ra trong trò chơi, số khả năng tăng theo cấp số nhân cùng với độ sâu tìm kiếm, khiến việc tìm kiếm sâu trở nên tốn kém hơn mức cần thiết.
- Lý tưởng nhất là ta muốn các nhánh tìm kiếm như vậy chia sẻ cùng phần tính toán.
- Tuy nhiên, các cách hiện thực MCTS tiêu chuẩn coi trò chơi như một cây phân nhánh và tái khám phá một cách kém hiệu quả các vị trí trùng lặp trong cây.
Cách giải thích phổ biến về MCTS - cây của các thống kê chạy
- MCTS thường được mô tả là một thuật toán theo dõi các thống kê chạy của các playout đi qua các nút của cây.
- Mỗi nút biểu diễn một trạng thái duy nhất của trò chơi, và theo dõi số lần được thăm (N) cùng giá trị trung bình chạy (Q) của các giá trị utility được lấy mẫu bởi các playout.
- Một vòng lặp đơn hoặc một playout của MCTS bao gồm việc đi xuống dọc theo cây để lấy mẫu hành động tiếp theo cần khám phá, mở rộng cây khi chạm đến một trạng thái mới, ước lượng utility U của trạng thái mới đó, rồi đi ngược lên cây trong khi tăng N ở mỗi nút và cập nhật trung bình Q bằng utility U mới được lấy mẫu.
Điều gì sai khi đưa lên đồ thị?
- Nếu áp dụng nguyên xi thuật toán trên cho một đồ thị có hướng không chu trình thay vì cây, thuật toán có thể trở nên không chính xác.
- Điều này là do MCTS thường được giải thích dưới góc nhìn các thống kê chạy của playout, như một phần mở rộng của các phương pháp dựa trên multi-armed bandit.
- Czech, Korus và Kersting đã giải quyết vấn đề này và đi đến một thuật toán sound, nhưng cũng có một cách tiếp cận thay thế nhìn MCTS từ góc độ học chính sách trực tuyến.
- Trong cách giải thích thay thế này, việc khái quát hóa sang đồ thị xuất hiện tương đối tự nhiên.
Nhìn lại MCTS như tối ưu hóa chính sách đã chuẩn hóa
- Khi MCTS cập nhật thống kê ở các nút khác nhau, về thực chất nó đang thực hiện một dạng học chính sách trực tuyến.
- Phân phối lượt thăm của MCTS xấp xỉ một chính sách "hậu nghiệm" dần cải thiện chính sách tiên nghiệm P từ mạng nơ-ron để tối đa hóa utility kỳ vọng.
Thực hiện Monte Carlo Graph Search đúng cách
- Mọi vấn đề phát sinh khi mở rộng MCTS sang đồ thị đều bắt nguồn từ giả định rằng việc thăm nút con chỉ đến từ một nút cha.
- Lý thuyết đảm bảo rằng số lần chọn hành động tích lũy do PUCT chọn sẽ cung cấp một chính sách hậu nghiệm xấp xỉ chính sách tối ưu hóa π, nên đây mới là thứ cần được theo dõi.
- Nếu dùng cách diễn giải rằng giá trị Q do một nút báo cáo là giá trị kỳ vọng của chính sách hậu nghiệm, ta có thể áp dụng công thức Q đệ quy mà không cần bàn đến cách tính từng playout riêng lẻ.
Thảo luận về các lựa chọn hiện thực
- Thuật toán được trình bày trong tài liệu này rất giống với thuật toán của Czech, Korus và Kersting, nhưng có một vài lựa chọn hiện thực và một số khác biệt nhỏ.
- Có nhiều cách có thể chọn để đơn giản hóa việc hiện thực, chẳng hạn như chiến lược giảm độ "cũ" của các giá trị Q hoặc dùng các cập nhật đồng nhất thay vì cập nhật tăng dần.
Ý kiến của GN⁺
- Bài viết này có thể thu hút những người quan tâm đến trí tuệ nhân tạo và lý thuyết trò chơi khi trình bày độ phức tạp của Monte Carlo Graph Search (MCGS) cùng một cách tiếp cận mới để hiểu nó.
- Các thuật toán như MCTS đóng vai trò quan trọng trong những trò chơi chiến lược phức tạp như cờ vua hay cờ vây, đồng thời góp phần vào sự phát triển của AI cho các trò chơi này.
- Tuy nhiên, nội dung của bài viết có thể hơi khó với các kỹ sư phần mềm mới vào nghề và đòi hỏi nền tảng lý thuyết nhất định.
- Một điểm cần cân nhắc khi hiện thực MCGS là làm sao cân bằng giữa hiệu quả và độ chính xác của thuật toán, vì điều này có thể ảnh hưởng lớn đến hiệu năng trong môi trường trò chơi thực tế.
- Một dự án hoặc sản phẩm khác có chức năng tương tự là AlphaZero của DeepMind, hệ thống đã đạt đến trình độ vượt qua các kỳ thủ hàng đầu thế giới ở cờ vua, cờ vây và shogi.
1 bình luận
Ý kiến trên Hacker News
Khám phá đồ thị là điều cần thiết cho sự tiến bộ của suy luận trong AI, và chỉ riêng các LLM đơn giản sẽ thất bại. Trong liên kết có nhiều tài liệu tham khảo hay, bao gồm cả Zobrist hashing cho bảng trò chơi. Cần tìm được cách băm tốt cho các mô tả trạng thái dựa trên ngôn ngữ để việc khám phá đồ thị không bùng nổ về mặt tính toán. Tài liệu đáng đọc về tìm kiếm trên cây gồm Thinking Fast and Slow và Teaching Large Language Models to Reason with Reinforcement Learning; chúng so sánh cách tiếp cận MCTS với các chiến lược RL hiện nay khác.
Chỉ từ URL HN là tôi đã nhận ra nhà phát triển thiên tài của KataGo. Các bài đăng cbaduk của anh ấy trên Reddit lúc nào cũng rất xuất sắc.
Về cái tên "Monte-Carlo Tree Search", độc giả nên nhận ra rằng trong thuật toán được nhắc tới không hề có phần "Monte-Carlo" và nó hoàn toàn mang tính quyết định. Việc MCTS thường được triển khai theo cách quyết định như vậy thật lạ. Tôi cứ tưởng có tính ngẫu nhiên trong việc lấy mẫu.
Bài báo được nhắc tới đã hoàn toàn nằm ngoài tầm chú ý của tôi khi tìm hiểu về MCTS. Sẽ rất thú vị nếu thử biến thể này vào dịp tới.
Kiến thức nền: