Bài tập lớn Tìm hiểu thuật A* áp dụng cho trò chơi 8 số

LỜI MỞ ĐẦU Trí tuệ nhân tạo là một ngành của khoa học máy tính_ nghiên cứu xử lý thông tin bằng máy tính , do đó trí tuệ nhân tạo đặt ra mục tiêu nghiên cứu: làm thế nào thể hiện được các hành vi thông minh bằng thuật toán, rồi nghiên cứu các phương pháp cài đặt các chương trình có thể thực hiện được các hành vi thông minh bằng thuật toán, tiếp theo chúng ta chỉ cần chỉ ra tính hiệu quả, tính khả thi của thuật toán thực hiện một nhiệm vụ và đưa ra các phương pháp cài đặt. Trong bài tập lớn lần này chúng em tìm hiểu thuật A* áp dụng cho trò chơi 8 số. Ngôn ngữ chúng em lựa chọn để cài đặt thuật toán này là Visual C#. Trong quá trình tìm hiểu còn nhiều vấn đề thiếu sót, mong thầy và các bạn góp ý.  Giới thiệu bài toán. Một bảng 3x3 với các ô trong đó có số từ 1 ->8 và 1 ô trống, các ô được đặt ở các vị trí ngẫu nhiên, ô trống và ô số có thể đổi chỗ cho nhau, tìm cách di chuyển các ô sao cho các con số về đúng thứ tự, bài toán đặt ra ở đây là tìm phương án tối ưu sao cho số lần di chuyển là ít nhất. Trạng thái ban đầu Trạng thái đích có thể có 2 trường hợp có thể xảy ra: và Với mỗi trạng thái ban đầu, chỉ tìm được 1 trạng thái đích có thể đạt tới Điều đầu tiên cần phải quan tâm để giải bài toán này là xác định trạng thái đích. Trạng thái đích được xác định dựa trên trạng thái ban đầu. Vậy trạng thái đích được xác định như thế nào. Đầu tiên hãy thử tính có bao nhiêu số bé hơn 8 ở sau ô chứa giá trị 8. Kết quả nhận được là 6 (những ô màu vàng) Làm tương tự như vậy với ô có giá trị 6. Dễ thấy trong 3 ô (4,7,5) có 2 giá trị nhỏ 6 là 4,5. Làm như trên từ ô đầu tiên (2) tới ô cuối cùng (5) và cộng dồn các giá trị nhận được: N = 1+6+1+0+2+0+1+0=11 Nếu N là số lẻ thì chúng ta chỉ có thể có đáp án là trạng thái A, ngược lại là trạng thái B A B Chúng ta đã xác định được trạng thái đích cần đạt được, bây giờ bắt đầu tìm kiếm giải thuật để tìm ra đích. Các thuật toán giải quyết bài toán. Tìm kiếm theo chiều rộng (Breadth-first search algorithm) Tìm kiếm theo chiều sâu (Depth-first search algorithm) Tìm kiếm lặp sâu dần (cải tiến từ giải thuật tìm kiếm theo chiều sâu) 4. A* (a sao) (cải tiến từ thuật toán Dijkstra) (minh họa bằng giải thuật này) Giới thiệu thuật toán A* Thuật toán A* là thuật toán tìm kiếm có tính heuristic trên không gian trạng thái dựa vào hàm f, được định nghĩa như sau: f=g(n)+h’(n) g(n): chi phí thực sự đi từ nút đầu đến nút n h’(n): chi phí ước lượng đi từ nút n đến trạng thái đích Để cài đặt giải thuật A* ta dùng hai danh sách để chứa các trạng thái, danh sách Open chứa các trạng thái chưa xét, danh sách Close chứa các trạng thái đã xét. Giải thuật A* cho bài toán ta canh Trò chơi 8 số ở mức độ khó vừa phải nên là một trò chơi rất thú vị. một giải pháp điển hình gồm khoảng 20 bước, mặc dù con số này biến đổi phụ thuộc vào trạng thái đầu. Hệ số rẽ nhánh khoảng bằng 3 (khi ô trống ở giữa, có bốn khả năng di chuyển; khi nó ở góc có hai khả năng di chuyển; và khi nó ở trên các cạnh, có ba khả năng đi). Để giải bài toán này ta cần tìm một hàm Heuristic tốt. Ta có hai hàm ước lượng: H1 = số lượng các số sai vị trí H2 = tổng số khoảng cách của các số so với vị trí mục tiêu, là tổng khoảng cách theo chiều ngang và theo chiều dọc. Bài toán tacanh khi được giải bằng thuật toán A* sẽ thực hiện theo các bước sau: Từ trạng thái ban đầu ta xác định được trạng thái đích. Gọi G là số bước đã di chuyển ô trống H là hàm heuristic, ước tính số hao tổn để tới trạng thái đích, tính bằng tổng các quãng đường của các ô ở vị trí sai để về tới vị trí đúng F=G+H. Có hai danh sách Open và Close, Open chứa các trạng thái chưa xét, danh sách Close chứa các trạng thái đã xét. Ban đầu ta thêm trạng thái khởi đầu vào Open, sau đó chọn trạng thái có f = g + h nhỏ nhất, lúc này danh sách Open chứa duy nhất trạng thái khởi đầu nên ta lấy trạng thái khởi đầu khỏi Open, và đưa vào danh sách Close các trạng thái đã xét. Từ trạng thái đang xét ta xác định được trạng thái tiếp theo, dựa vào các hướng di chuyển của ô trống. Đưa tất cả các trạng thái mới mà chưa có trong Close và Open vào danh sách Open. Ta tiếp tục chọn trạng thái có f = g + h nhỏ nhất khỏi Open như bước đầu tiên cho đến khi tìm ra trạng thái đích thì dừng lại. Từ trạng thái đích vừa tìm được đi ngược lại danh sách ta sẽ tìm được đường đi từ trạng thái khởi đầu đến trạng thái đích. Ví dụ: cho hình sau: N= 1+6+1+2+1=11 nên trạng thái đích là Các bước giải bài toán như sau: Đầu tiên ta xác định trạng thái tiếp theo của bài toán trên: Có ba trường hợp xảy ra: 1 2 3 Đối với trường hợp 1 có g= 1, h= 4,f= h+g=5 Đối với trường hợp 2 có g= 1, h= 5,f= h+g=6 Đối với trường hợp 2 có g= 1, h= 6,f= h+g=7 So sánh các f với nhau ta thấy f của trường hợp 1 nhỏ nhất nên trạng thái tiếp theo là trạng thái 1. Từ 1 ta có ba trạng thái: 1.1 1.2 1.3 Đối với trường hợp 1.1 có g= 2, h= 3,f= h+g=5 Đối với trường hợp 1.2 có g= 2, h= 5,f= h+g=7 Đối với trường hợp 1.3 có g= 2, h= 5,f= h+g=7 So sánh các f với nhau ta thấy f của trường hợp 1 nhỏ nhất nên trạng thái tiếp theo là trạng thái 1.1 Từ 1.1 có hai trạng thái: 1.1.1 1.1.2 Đối với trường hợp 1.1.1 có g= 3, h= 2,f= h+g=5 Đối với trường hợp 1.1.2 có g= 3, h= 4,f= h+g=7 So sánh các f với nhau ta thấy f của trường hợp 1 nhỏ nhất nên trạng thái tiếp theo là trạng thái 1.1.1 Từ 1.1.1 có một trạng thái: Từ trạng này có: g= 4, h=1, f= 5. Ta có trạng thái đích: Cài đặt thuật toán: Ta tiến hành cài đặt thuật toán trên ngôn ngữ Visual C#. Ta xây dựng các class sau: Class Node: xác định thuộc tính mỗi trạng thái của bài toán. Trong lớp này ta xây dựng hàm HeuristicFunction() để xác định độ ước lượng h. Class Puzzles: có các thành phần là các danh sách Open và Close kiểu LinkedNode: ngoài ra lớp này còn có các phương thức để thực hiện thuật toán A*: Hàm GetSmallListNode(): để lấy trạng thái nhỏ nhất khỏi danh sách Open. Hàm Open.Remove(SmallestNode): để xóa trạng thái nhỏ nhất vừa được chọn khỏi Open. Hàm Close.AddFirst(SmallestNode) để thêm trạng thái nhỏ nhất đã được xét vào Close. Hàm AddNodeToOpen(): thêm các trạng thái chưa được xét vào Open. Ta dùng vòng lặp while(Open!= null) để duyệt danh sách Open và chọn ra trạng thái nhỏ nhất. Danh sách Open được duyệt đến khi tìm được trạng thái đích. Ngoài ra chương trình còn có class giao diện dùng để xây dựng giao diện trực quan cho bài toán.