Đào sâu lặp trong máy cờ

Giải thích

Đào sâu lặp khiến một ban đầu tìm với giới hạn nhỏ rồi lặp lại phân tích với các giới hạn ngày càng lớn. Trong cờ vua, độ sâu thường được đo bằng ply, trong đó một ply là một nước đi của một bên.

Thoạt nhìn, cách này có vẻ lãng phí vì các thế gần gốc được thăm lại nhiều lần. Tuy nhiên, những vòng trước tạo ra thông tin quý giá: nước tốt nhất tạm thời, biến chính, tức chuỗi hiện được xem là tốt nhất, các kết quả đã lưu và dữ liệu cho . Tìm các lựa chọn hứa hẹn trước trong vòng tiếp theo thường giúp nhiều nhánh dừng sớm hơn và bù phần lớn công việc lặp lại.

Lợi ích thực tế rõ nhất là quản lý thời gian. Nếu đồng hồ buộc máy cờ dừng giữa một vòng sâu hơn, nó vẫn có kết quả hoàn chỉnh từ vòng trước. Máy không phải đặt mọi thứ vào một tìm kiếm có thể không hoàn tất.

Đào sâu lặp không có nghĩa chỉ mở rộng một biến được ưa thích. Mỗi vòng trở lại thế ban đầu với giới hạn lớn hơn, dù các kỹ thuật chọn lọc có thể gán độ sâu cục bộ khác nhau trong cây. Nó cũng đẩy ra xa mà không loại bỏ được chân trời.

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

Giao diện thường hiển thị độ sâu của vòng hiện tại, nhưng chỉ một con số lớn hơn không chứng minh hai máy cờ khác nhau đã thực hiện lượng công việc tương đương.

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

Sự lặp lại vô ích

Công việc trước cung cấp thứ tự nước đi, biến chính và thông tin tìm kiếm đã lưu, nên vòng tiếp theo không thật sự bắt đầu từ con số không.

Đào sâu và mở rộng chọn lọc

Đào sâu lặp nâng giới hạn tổng thể giữa các lượt, còn mở rộng thêm tìm kiếm cục bộ vào những biến cụ thể.

Nguồn

1.Depth-first iterative-deepening: An optimal admissible tree search, Artificial Intelligence / Elsevier
2.Iterative Deepening, 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