Tôi đã nghĩ về một số số phỏng đoán cho trò chơi tic-tac-toe lớn (kích thước cao hơn). Làm cách nào để kiểm tra xem thực tế nào trong số đó thực tế là nhất quán?Trong lập trình trò chơi, làm thế nào tôi có thể kiểm tra xem liệu một heuristic được sử dụng là phù hợp hay không?
Điều gì có nghĩa là nhất quán anyways?
CHỈNH SỬA: Câu trả lời nhầm lẫn về sự chấp nhận và nhất quán này. Tôi đã sửa chữa nó để chỉ sự chấp nhận, nhưng câu hỏi ban đầu là về sự nhất quán, và câu trả lời này không trả lời đầy đủ câu hỏi.
Bạn có thể làm điều đó một cách phân tích, bằng cách phân biệt tất cả các trường hợp khác nhau và do đó chứng minh rằng phỏng đoán của bạn thực sự được chấp nhận.
Để tìm kiếm thông tin, một phỏng đoán có thể chấp nhận được với sự cố tìm kiếm (ví dụ: tìm kiếm di chuyển tốt nhất trong trò chơi) nếu và chỉ khi nó đánh giá thấp khoảng cách 'đến trạng thái phù hợp.
VÍ DỤ: Tìm tuyến đường ngắn nhất đến thành phố mục tiêu thông qua mạng lưới đường cao tốc giữa các thành phố. Ở đây, người ta có thể sử dụng khoảng cách Eucidean như một heuristic: chiều dài của một đường thẳng đến mục tiêu luôn luôn ngắn hơn hoặc bằng nhau dài hơn cách tốt nhất có thể.
Khả năng chấp nhận được yêu cầu bởi các thuật toán như A*, sau đó kiểm dịch bạn là tối ưu (nghĩa là họ sẽ tìm thấy 'tuyến đường' tốt nhất đến trạng thái mục tiêu nếu có).
Tôi khuyên bạn nên xem chủ đề này theo số AI textbook.
Có một sự khác biệt giữa các chẩn đoán thừa nhận và nhất quán, mặc dù tất cả các chẩn đoán nhất quán đều được chấp nhận. Chấp nhận có nghĩa là heuristic đánh giá thấp tổng chi phí đường dẫn và nó phù hợp nếu heuristic giảm không quá chi phí bước sau khi đi qua một bước. –
Heuristics sản xuất một số loại giá trị chi phí cho một trạng thái nhất định. Tính nhất quán trong bối cảnh này có nghĩa là ước tính cho một tiểu bang cộng với chi phí chuyển sang tiểu bang tiếp theo nhỏ hơn hoặc bằng với ước tính cho tiểu bang mới đó. Nếu điều này không đúng thì nó sẽ ngụ ý rằng - nếu heuristic là chính xác - việc chuyển từ trạng thái này sang trạng thái khác có thể phải chịu chi phí âm, thường không thể hoặc không chính xác. Điều này là trực quan để chứng minh khi nói đến pathfinding, như bạn mong đợi mỗi bước dọc theo con đường để mất một thời gian, do đó, các ước tính ở bước 1 phải thấp hơn so với ước tính ở bất kỳ bước 2. Nó có thể nhiều hơn một chút phức tạp cho tic-tac-toe vì bạn có thể phải tự ý quyết định cái gì cấu thành 'chi phí' trong hệ thống của bạn. Nếu heuristic của bạn có thể đi cả lên hoặc xuống như là kết quả của việc chơi một động thái - ví dụ. bởi vì bạn mã hóa những động thái tốt với những con số dương và những động thái xấu với những con số âm - thế thì heuristic của bạn không thể nhất quán.
Tuy nhiên, thiếu phương pháp phỏng đoán nhất quán không phải lúc nào cũng là vấn đề. Bạn có thể không được đảm bảo đạt được một giải pháp tối ưu mà không có một giải pháp, nhưng nó vẫn có thể tăng tốc độ tìm kiếm so với tìm kiếm trạng thái vũ phu.
Đây là câu hỏi thực sự. –
Hai người đã gắn cờ trang này để đóng 'không phải là một câu hỏi thực tế'. Tôi cũng không đồng ý với họ. – Kylotan