Tìm kiếm cây Monte Carlo

Tìm kiếm cây Monte Carlo, viết tắt là MCTS, không cố xem mọi biến đến cùng một độ sâu. Nó phát triển cây dần dần và dùng các kết quả tích lũy để chọn nơi dành phần tính toán tiếp theo. Một nước được thăm nhiều không tự động là nước tốt, nhưng ước lượng của nó thường được hỗ trợ bởi nhiều tìm kiếm hơn.

Một chu kỳ MCTS

1. Lựa chọn: bắt đầu từ thế ban đầu và đi theo các nhánh đã có, cân bằng giữa những nước đã tỏ ra mạnh và những nước vẫn chưa chắc chắn.
2. Mở rộng: thêm vào cây một thế cờ hoặc nước đi chưa được phát triển.
3. Đánh giá: ước tính kết quả từ thế mới. Phương pháp cổ điển có thể hoàn thành các ván mô phỏng, còn hệ thống hiện đại có thể dùng mạng nơ-ron, một mô hình được huấn luyện để nhận dạng mẫu, nhằm đánh giá thế cờ.
4. Lan truyền ngược: đưa kết quả trở lại theo đường đã đi và cập nhật số lần thăm cùng các ước lượng.

Lặp chu kỳ này tạo sự cân bằng giữa khai thác và khám phá. Khai thác nghĩa là dành thêm công sức ở nơi bằng chứng đã thuận lợi. Khám phá nghĩa là thử các phương án chưa chắc chắn để không loại một bất ngờ quá sớm. Quy tắc cân bằng chính xác phụ thuộc vào cách triển khai.

Khác với minimax, MCTS thường quyết định mức độ điều tra một nhánh dựa trên bằng chứng thu được trong quá trình tìm kiếm, thay vì chỉ dựa vào một độ sâu đồng đều. Trong một số chương trình cờ vua dựa trên mạng nơ-ron, mạng cung cấp một policy, gợi ý các nước có khả năng cao, và một value, ước tính kết quả. Value có vai trò liên quan đến hàm đánh giá, dù toàn bộ quá trình tìm kiếm khác nhau.