Báo cáo đồ án trí tuệ nhân tạo: Xây dựng chương trình giải quyết bài toán không gian trạng thái của trò chơi cờ vua theo phương pháp cắt tỉa Anpha-Beta

Học viện Kỹ thuật quân sự Khoa CNTT Đồ án Nhập môn trí tuệ nhân tạo Không gian trạng thái là trò chơi cờ vua. Xây dựng chương trình giải quyết bài toán theo phương pháp cắt tỉa Anpha-Beta Họ và tên: Đặng Minh Sang Lớp: Tin học 5A I. Lời nói đầu Năm 1950, Claude Shannon đã viết chương trình chơi cờ đầu tiên. Đó là hành động đầu tiên đánh dấu việc nguyên cứu Trí tuệ nhân tạo và đưa nó vào chơi cờ. Điều này là một bằng chứng rõ ràng về khả năng máy tính có thể làm được những công việc đòi hỏi trí thông minh của con người. Ngày này, việc nguyên cứu Trí tuệ nhân tạo và đưa nó vào các ứng dụng thực tế đang ngày càng nhiều, và ngày càng chứng tỏ được thế mạnh của mình trong các công việc đòi hỏi khả năng suy nghĩ và tính toán giống như con người. Trong đó, vấn đề Tìm kiếm có đối thủ đang được áp dụng rất rộng rãi trong các trò chơi đối kháng, tất nhiên, tuân theo những tiêu chuẩn nhất định. Bản đồ án này được xây dựng, cũng nằm một trong số đó. Áp dụng lí thuyết Trí tuệ nhân tạo, kết hợp với các hàm đánh giá, từ đó xây dựng một chương trình cờ vua mang tính chất minh họa thuật toán hơn là xây dựng một chương trình có tính ứng dụng cao trong thực tế. II. Cơ sở lí thuyết Vấn đề chơi cờ có thể xem xét như vấn đề tìm kiếm trong không gian trạng thái. Mỗi trạng thái là một tình thế (cách bố trí các quân cờ trên bàn cờ). - Trạng thái ban đầu là sự sắp xếp các quân cờ của hai bên lúc bắt đầu chơi. - Các toán tử là các nước đi hợp lệ. - Các trạng thái kết thúc là các tình thế mà cuộc chơi dừng, thường được xác định bởi một điều kiện dừng nào đó. - Một hàm kết cuộc ứng mỗi trạng thái kết thúc với một giá trị nào đó. Tư tưởng của thuật toán cắt cụt Anpha-beta như sau: nhớ lại rằng, chiến lược tìm kiếm Minimax là chiến lược tìm kiếm theo độ sâu. Giả sử trong quá trình tìm kiếm, ta đi xuống đỉnh A là đỉnh trắng, đỉnh A có người anh em V đã được đánh giá. Giả sử cha của đỉnh A là B và B có người anh em U đã được đánh giá, và giả sử cha của B là C. Khi đó ta có giá trị đỉnh C ít nhất là giá trị của U, giá trị của đỉnh B nhiều nhất là giá trị V. Do đó, nếu eval (U)>eval(V), ta không cần đi xuống để đánh giá đỉnh A nữa mà không ảnh hưởng gì đến đánh giá đỉnh C. Hay nói cách khác, ta có thể cắt bỏ cây con gốc A. Lập luận tương tự cho trường hợp đỉnh A là đen, trong trường hợp này, nếu eval (U)