tailieunhanh - Giáo trình Trí tuệ Nhân tạo part 7

Trong các hàm đệ quy trên, f(u) là giá trị của hàm kết cuộc tại đỉnh kết thúc u. Sau đây là thủ tục chọn nước đi cho trắng tại đỉnh u. Trong thủ tục Minimax(u,v), v là biến lưu lại trạng thái mà Trắng đã chọn đi tới từ u. procedure Minimax(u, v); Thủ tục chọn nước đi như trên gọi là chiến lược Minimax, bởi vì Trắng đã chọ được nước đi dẫn tới đỉnh con có giá trị là max của các giá trị các đỉnh con, và Đen đáp lại bằng nước đi tới đỉnh có. | Trong các hàm đệ quy trên f u là giá trị của hàm kết cuộc tại đỉnh kết thúc u. Sau đây là thủ tục chọn nước đi cho trắng tại đỉnh u. Trong thủ tục Minimax u v v là biến lưu lại trạng thái mà Trắng đã chọn đi tới từ u. procedure Minimax u v begin val -X for mỗi w là đỉnh con của u do if val MinVal w then val Min Val w v w end Thủ tục chọn nước đi như trên gọi là chiến lược Minimax bởi vì Trắng đã chọ được nước đi dẫn tới đỉnh con có giá trị là max của các giá trị các đỉnh con và Đen đáp lại bằng nước đi tới đỉnh có giá trị là min của các giá trị các đỉnh con. Thuật toán Minimax là thuật toán tìm kiếm theo độ sâu ở đây ta đã cài đặt thuật toán Minimax bởi các hàm đệ quy. Bạn đọc hãy viết thủ tục không đệ quy thực hiện thuật toán này. Về mặt lí thuyết chiến lược Minimax cho phép ta tìm được nước đi tối ưu cho Trắng. Song nó không thực tế chúng ta sẽ không có đủ thời gian để tính được nước đi tối ưu. Bởi vì thuật toán Minimax đòi hỏi ta phải xem xét toàn bộ các đỉnh của cây trò chơi. Trong các trò chơi hay cây trò chơi là cực kỳ lớn. Chẳng hạn đối với cờ vua chỉ tính đến độ sâu 40 thì cây trò chơi đã có khoảng 10120 đỉnh Nếu cây có độ cao m và tại mỗi đỉnh có b nước đi thì độ phức tạp về thời gian của thuật toán Minimax là O bm . Để có thể tìm ra nhanh nước đi tốt không phải là tối ưu thay cho việc sử dụng hàm kết cuộc và xem xét tất cả các khả năng dẫn tới các trạng thái kết thúc chúng ta sẽ sử dụng hàm đánh giá và chỉ xem xét một bộ phận của cây trò chơi. Hàm đánh giá Hàm đánh giá eval ứng với mỗi trạng thái u của trò chơi với một giá trị số eval u giá trị này là sự đánh giá độ lợi thế của trạng thái u. Trạng thái u càng thuận lợi cho Trắng thì eval u là số dương càng lớn u càng thuận lợi cho Đen thì eval u là số âm càng nhỏ eval u 0 đối với trạng thái không lợi thế cho ai cả. Chất lượng của chương trình chơi cờ phụ thuộc rất nhiều vào hàm đánh giá. Nếu hàm đánh giá cho ta sự đánh giá không chính xác về các trạng thái nó có thể hướng dẫn ta đi tới trạng thái được xem