Bất kỳ đề xuất thuật toán tìm kiếm cây song song được phân phối nào?

Question

Tôi đang viết bot Go/Gomoku được phân phối.

Về cơ bản, vấn đề là phân phối tìm kiếm cây lên nhiều máy tính. Với các thuật toán tìm kiếm cây cơ bản như DFS, điều này sẽ rất đơn giản, vì tôi chỉ có thể phân vùng không gian tìm kiếm thành các subtrees. Mặc dù tôi muốn có một cái gì đó hiệu quả hơn, như mini-max với việc cắt tỉa alpha-beta - nhưng từ sự hiểu biết của tôi thì nó hoàn toàn vô nghĩa nếu không có bất kỳ loại bộ nhớ chia sẻ nào. Vì vậy, tôi là loại bị mắc kẹt.

Bất kỳ ý tưởng nào tôi có thể sử dụng thuật toán nào hiệu quả và dễ phân phối? Và quan trọng hơn, nơi tôi có thể tìm thấy một số (giả) mã cho nó hoặc có thể thực hiện?

Cảm ơn,

Answer 1

Bạn cần phải đọc lên về Monte Carlo Tree Tìm kiếm, không phải vì nó vốn đã dễ dàng hơn để phân phối (nó không phải là dễ dàng hơn và cũng không khó so với tìm kiếm cây khác), nhưng vì đó là trạng thái của nghệ thuật và những người làm việc về vấn đề đang làm việc trên phiên bản phân tán của thuật toán đó.

Nếu bạn đang gặp rắc rối khi tạo thuật toán phân tán, không có lý do gì để bắt đầu bằng thuật toán ít hơn. Trừ khi bạn đang tạo thuật toán phân tán vì lý do giáo dục, trong trường hợp này, sẽ có một thứ gì đó mang tính giáo dục sâu sắc trong thử nghiệm phân phối thuật toán cơ bản và thấy nó hoạt động kém hơn thuật toán hiện đại không được phân phối :)

Some slides

các MoGo homepage

Hãy xem phần "phát triển gần đây" trong Wikipedia page on computer go.

Answer 2

DDS* và ABDADA 2 phân phối/song song các thuật toán minimax. Một số giao tiếp là cần thiết, nhưng điều này có thể được thực hiện bằng cách chuyển tiếp một số kết quả trở lại bộ điều khiển.

Cách tiếp cận dễ dàng hơn như bạn đã đề cập sẽ giống như bản đồ giảm với các gốc cây tìm kiếm khác nhau.

Là @Pascal Cuoq rightly mentions, Tìm kiếm cây Monte Carlo là công cụ tiên tiến trong Go.

Ở đây bạn có thể tìm thấy một lời giải thích tốt về thuật toán tìm kiếm MoGo và làm thế nào nó song song:

http://www.lri.fr/~gelly/paper/nips_exploration_exploitation_mogo.pdf

nút đó đang chơi với kết quả tốt hơn dựa trên vở kịch ngẫu nhiên được khai thác sâu hơn. Ở mỗi bước một nút lá được chọn để mở rộng một lớp. Điều này có thể được phân phối bằng cách mỗi máy chọn một chiếc lá khác nhau để mở rộng.

một cái nhìn tổng quan tốt của monte carlo tìm kiếm cây là ở đây:

http://sander.landofsand.com/publications/Monte-Carlo_Tree_Search_-_A_New_Framework_for_Game_AI.pdf

Answer 3

Thử phương pháp Giảm thiểu bản đồ. Ví dụ: xem

Breadth-First Search (BFS) & MapReduce