minimax cho tic-tac-toe

Question

Tôi đang cố gắng giải quyết tic-tac-toe bằng thuật toán minimax đơn giản. Đơn giản, nhưng phải bao gồm rất nhiều ngôn ngữ. Những gì tôi có cho đến thời điểm này:

Bảng được biểu diễn dưới dạng một mảng gồm 9 biến (không liên kết) được đặt thành x hoặc o.

Điều kiện giành chiến thắng sau đó về cơ bản là: win(Player, [X1,X2,X3|_]) :- X1==Player,X2==Player,X3==Player. v.v ... cho tất cả tám biến thể. vẽ chỉ là một kiểm tra đơn giản cho dù tất cả các biến bị ràng buộc.

Điều khoản di chuyển cũng đơn giản: move(Player, [X|_], 0, 0) :- var(X), X=Player., một lần nữa cho tất cả các vị trí có thể (tôi sẽ để lại mã tái sử dụng mở cho chương trình sau :)).

Bây giờ tôi có thể tạo tất cả các bước di chuyển đơn giản: move(Player, Board, X, Y). về cơ bản là tất cả những gì tôi cần cho minimax (rõ ràng là một hàm tiện ích đơn giản trả về 1 nếu máy tính thắng, 0 trong trường hợp hòa và -1 nếu chiến thắng của con người, thật dễ dàng). Tôi chỉ không có ý tưởng làm thế nào để thực hiện nó và tất cả các ví dụ tôi tìm thấy trên mạng là khá phức tạp và không giải thích tốt.

Lưu ý Tôi ổn với hành vi thời gian chạy^^ hoặc tệ hơn - nó thực sự không hiệu quả. Và vâng tôi biết cách viết minimax trong lisp, python, java - không có ý tưởng làm thế nào để "port" mã đó thành prolog.

Answer 1

Vâng, như bạn đã có di chuyển của bạn/4 vị, tôi sẽ bắt đầu với việc thu thập tất cả các động thái đó có thể xảy ra:

findall(X-Y, move(Player, Board, X, Y), Moves)

Và sau đó nó chỉ đơn giản là vấn đề của việc đánh giá mỗi di chuyển, chứ không phải là nó? Cho rằng tôi sẽ viết một vị ngữ như board_player_move_value/4 rằng, cho một bảng và một động thái của một người chơi nhất định, xác định mức độ di chuyển tốt cho người chơi này. Đó là vị từ này có khả năng phụ thuộc vào các động thái tiếp theo có thể xảy ra (đối với người chơi khác) ở giai đoạn này, và đây là nơi minimax xảy ra. Ví dụ, nếu di chuyển này thắng trò chơi, đó là một động thái tốt. Nếu người chơi khác có thể thắng trong lần di chuyển tiếp theo, đó là một động thái xấu vv. Tôi sẽ sử dụng vị từ này để xây dựng một tập hợp các điều khoản của biểu mẫu Value-Move, sử dụng keysort/2 để sắp xếp chúng và sau đó chọn một trong các bước với giá trị tốt nhất, nơi "tốt nhất" phụ thuộc vào việc liệu tôi có đang cố gắng tìm một động thái để thu nhỏ hoặc tối đa hóa trình phát hay không.