PHƯƠNG PHÁP CẢI TIẾN HIỆU QUẢ CÂY TÌM KIẾM MONTE CARLO

Abstract

Chess playing is an area of research in artificial intelligence. Traditional programs were built by using Minimax, Alpha-Beta with any heuristic evaluation function based on knowledge of chess players. It is difficult to design a good state evaluation function. Moreover, A traditional tree search is suitable for the games that their branch factor is low. Monte Carlo Tree Search is a novel framework, and very effective in some high branch factors such as Go. The Monte Carlo Tree Search model is combined from Tree search, Reinforcement learning, and Monte Carlo simulation. In our view, we can improve the performance of Monte Carlo Tree Search by studying how to improve the performance of reinforcement learning, or to improve the Monte Carlo simulation. This paper compacts the most efficient way of Monte Carlo Tree Search improvement and shows its efficiency based on the experimental results.

Tóm tắt

Các chương trình đánh cờ là một phần nghiên cứu của ngành Trí tuệ nhân tạo. Các chương trình truyền thống được xây dựng trên cây tìm kiếm Minimax, Alpha-Beta với hàm lượng giá được xây dựng dựa trên tri thức của người chơi cờ. Việc thiết kế một hàm lượng giá trạng thái tốt thường rất khó, hơn nữa các cây tìm kiếm truyền thống chỉ phù hợp với những trò chơi có hệ số phân nhánh thấp. Cây tìm kiếm Monte Carlo là một hướng tiếp cận hiện đại và hiệu quả trên nhiều trò chơi có hệ số phân nhánh cao như cờ Vây. Mô hình cây tìm kiếm Monte Carlo được kết hợp từ Cây tìm kiếm, Học tăng cường và giả lập Monte Carlo. Với cách tiếp cận này, ta có thể cải tiến hiệu suất của cây tìm kiếm Monte Carlo bằng cách tìm hiểu phương pháp cải tiến Học tăng cường và cải tiến giả lập Monte Carlo. Bài báo này nghiên cứu các thành phần chính của cây tìm kiếm Monte Carlo và xác định hướng cải tiến hiệu quả nhất cũng như thực nghiệm đã chứng minh tính hiệu quả.