1. Trang chủ
  2. Câu hỏi và trả lời
  3. Thuật toán tốt nhất được biết đến hiện nay cho cờ vua máy tính?

Thuật toán tốt nhất được biết đến hiện nay cho cờ vua máy tính?

2010-01-08 25 views

Trả lời

3

Minimax

Nếu bạn cần một kiến ​​thức chuyên sâu về các thuật toán AI, tôi nghĩ "artificial intelligence modern approach" cuốn sách là nguồn tốt nhất.

Nguồn

2010-01-08 08:21:42

+2

Đó sẽ là * một phần * của thuật toán chơi cờ. Tuy nhiên, minimax không phải là một thuật toán cờ vua. – Tarydon

1

Wikipedia là đặt cược an toàn làm điểm xuất phát. Bạn có nhìn ở đó không?

Rybka dường như là ứng cử viên.

Nguồn

2010-01-08 08:21:57 Tarydon

+0

Tôi đồng ý Wikipedia là một nơi tốt để xem nhưng Rybka là nguồn đóng nên có lẽ không giúp được gì nhiều –

+0

@Dave: Đúng, nhưng nó giải quyết vấn đề anarhikos * chỉ muốn học tên thuật toán *. – Tarydon

+1

@Tarydon - Rybka là tên của một động cơ _chess_. Vì nó là nguồn đóng không ai (ngoài tác giả) biết thuật toán nào sử dụng nó. –

20

Chiến lược chung trong thuật toán trò chơi là chiến lược minimax, được tăng cường với alpha-beta pruning. Thuật toán minimax tìm ra động thái tốt nhất, và việc cắt tỉa alpha-beta ngăn không cho nó đi vào các nhánh của cây trò chơi mà không thể tạo ra kết quả tốt hơn các nhánh trước đó đã có.

Tuy nhiên, cây trò chơi cờ vua quá lớn để được kiểm tra toàn bộ. Đó là lý do tại sao máy tính cờ vua động cơ chỉ kiểm tra cây lên đến một độ sâu nhất định, và sau đó sử dụng các phương pháp khác nhau để đánh giá các vị trí. Nhiều người trong số các phương pháp này được dựa trên chẩn đoán. Ngoài ra, một chương trình chơi cờ tướng nghiêm túc sẽ có một thư viện mở để nó có thể chơi ngay từ đầu bằng cách chỉ tham khảo thư viện đó và không phải kiểm tra cây trò chơi. Cuối cùng, nhiều trò chơi kết thúc được giải quyết hoàn toàn và chúng cũng được lập trình dưới dạng thư viện.

Nguồn

2010-01-08 08:34:34 JaakkoK

+0

Tương đương với minimax được gọi là negamax. Sự khác biệt là điểm số được phủ nhận ở mỗi thay đổi độ sâu trong cây. Bằng cách này, cả hai người chơi đang cố gắng để tối đa hóa số điểm (trong đó trong minimax một là cố gắng để giảm thiểu nó). Tôi không chắc chắn điều này làm gì với cửa sổ alpha/beta. Liệu nó có trở thành một giá trị duy nhất không? – phkahler

+2

cần lưu ý rằng chức năng đánh giá vị trí có lẽ là khía cạnh quan trọng nhất của động cơ cờ khi xác định sức mạnh của nó. Trong thực tế, nó có lẽ là khu vực duy nhất mà có sự mới lạ trong hầu hết các động cơ cờ vua bây giờ adays. Ví dụ, chức năng đánh giá vị trí Rybka được thiết kế trên 5 năm (nếu irc) bởi những người chơi rất mạnh. Trong một nghĩa nào đó, chức năng đánh giá là điều mang lại trực giác máy tính về vị trí cờ vua, một phần cơ bản quan trọng của bất kỳ trò chơi cờ vua nào và trực giao với các vấn đề khác như chiến thuật trong trò chơi. – ldog

+0

@gmatt - chỉ đúng một phần ... cắt tỉa tích cực là một phần của những gì làm cho Rybka trở nên mạnh mẽ, và nghiên cứu trong đó không quá cũ. Mở rộng cắt xén vô hạn, hạn chế razoring, và thích ứng di chuyển null cắt tỉa đã được nhà nước của nghệ thuật ít hơn một thập kỷ trước – tbischel

0

Hãy xem một số mã nguồn cờ miễn phí, ví dụ Crafty hoặc thậm chí tốt hơn về Trái cây? Nó chơi khá nhiều gần như cùng sức mạnh của Rybka. Nhưng có rất nhiều thuật toán mới ngoài kia. Ngày sẽ đến khi người chơi cờ vua sẽ phải nói rằng tôi không chơi vs động cơ này, và bài viết này khá nhiều tiền nó lên ->http://www.mychessblog.com/man-versus-machine-when-a-computer-will-become-world-chess-champion/

Nguồn

2010-01-08 23:54:33 chessplayer

0

Rất nhiều thuật toán được sử dụng trong lập trình cờ được mô tả trên trang web http://chessprogramming.wikispaces.com/ . Có một số chương trình nguồn mở có sẵn đang triển khai các thuật toán này.

Nguồn

2010-01-11 08:54:08

Các vấn đề liên quan

 Các vấn đề liên quan