Cắt tỉa alpha-beta trong máy cờ

Giải thích

Cắt tỉa alpha-beta tăng tốc quá trình tìm kiếm của một , tức chương trình so sánh các nước đi và lời đáp. Có thể hình dung tìm kiếm như một cây: mỗi nút là một thế cờ và mỗi nhánh là một nước hợp lệ. Nếu không cắt tỉa, chương trình phải xem xét nhiều biến mà cuối cùng được chứng minh là không liên quan.

Phương pháp duy trì hai giới hạn trong lúc tìm kiếm. Alpha là kết quả tốt nhất mà một bên đã có thể bảo đảm trên đường hiện tại. Beta là giới hạn do một phương án mà đối thủ đã có sẵn tạo ra. Khi một biến trở nên tệ đến mức người chơi hợp lý sẽ không bao giờ chọn, việc tìm sâu thêm không thể thay đổi quyết định ở nút cao hơn.

Nhánh bị dừng vì một giới hạn logic trong cây, không chỉ vì nước đi trông kém hấp dẫn. Ở cùng độ sâu và với cùng các đánh giá tại giới hạn tìm kiếm, alpha-beta trả về cùng lựa chọn như một tìm kiếm đầy đủ giả định cả hai bên đều đáp trả tối ưu.

Mức tiết kiệm phụ thuộc nhiều vào thứ tự nước đi. Thử các nước mạnh trước sẽ thiết lập giới hạn hữu ích sớm hơn và cho phép nhiều nhánh dừng mà không cần xem sâu. Một , gán ước lượng số cho một thế cờ, cung cấp giá trị ở nơi tìm kiếm hữu hạn kết thúc.

Cách dùng và ngữ cảnh

Alpha và beta không phải hai đánh giá cố định của bàn cờ. Chúng là các giới hạn thay đổi khi thuật toán khám phá một biến.

Những nhầm lẫn thường gặp

Cắt tỉa và loại bỏ tùy tiện

Alpha-beta chỉ bỏ qua một nhánh sau khi chứng minh rằng nhánh đó không thể thay đổi lựa chọn theo các giới hạn hiện tại.

Cắt tỉa nhiều hơn tự động đồng nghĩa mạnh hơn

Sức mạnh còn phụ thuộc vào thứ tự nước đi, chất lượng đánh giá, độ sâu tìm kiếm và nhiều kỹ thuật khác của máy cờ.

Nguồn

1.An analysis of alpha-beta pruning, Artificial Intelligence / Elsevier
2.Alpha-Beta, Chess Programming Wiki
3.search.cpp, Stockfish

Giải thích

Cách dùng và ngữ cảnh

Những nhầm lẫn thường gặp

Nguồn

Thuật ngữ liên quan