Tìm kiếm cây Monte Carlo hoặc các thuật toán khác cho trò chơi thẻ ngẫu nhiên?

Question

Tôi hiện đang làm việc để triển khai trò chơi bài đánh bài và chơi bài 2 người, tương tự như 66 hoặc Schnapsen. Về cơ bản bạn cần phải thu thập điểm bằng cách chiến thắng thủ đoạn và trong khi có thẻ trong gói, cả hai người chơi rút ra một thẻ sau mỗi vòng.

Tôi đang ở thời điểm lập trình một AI tốt cho trò chơi không gian lận, nhưng thực sự tính toán di chuyển tốt nhất bằng cách chỉ sử dụng thông tin ở trạng thái trò chơi đã cho. Tôi bị mắc kẹt khi quyết định thuật toán hoặc logic nào là tốt nhất để sử dụng. Tôi quyết định chống lại các thuật toán như cắt tỉa Alpha-Beta vì có quá nhiều thông tin ẩn đặc biệt là vào đầu trò chơi. Tôi đọc nhiều điều thú vị về Tìm kiếm cây Monte Carlo và tìm kiếm UCT liên quan, nhưng vì trò chơi có các yếu tố ngẫu nhiên, nên cây cần tìm kiếm sẽ phát triển rất lớn trong một thời gian ngắn.

Thuật toán hoặc phương pháp nào sẽ là cách tốt nhất để sử dụng?

Answer 1

MCTS chắc chắn sẽ tốt hơn. Bất kể bạn chọn ai, bạn sẽ phải đối phó với thông tin không đầy đủ là vấn đề trọng tâm ở đây.

Answer 2

Here là một liên kết tới ứng dụng của UCT tới Klondike Solitaire. MCTS là hoàn toàn phù hợp cho vấn đề vì nó có thể đối phó tốt với tính ngẫu nhiên.

Bạn có thể xem phương pháp thưa thớt được mô tả bên trong giấy để biết cách giới hạn chiều rộng của cây.