Nếu bạn mới làm quen với AI hoặc mới học nhập môn AI tại trường thì có lẽ bài toán N-Puzzle không còn quá xa lạ với các bạn nữa!
|
| Đề tài: Ứng dụng thuật toán BFS và A* vào giải bài toán xếp hình N-Puzzle |
Giới thiệu
Đề tài
Ứng dụng thuật toán BFS và A* vào giải bài toán xếp hình N-Puzzle
Bài toán ban đầu đặt ra một ma trận vuông kích thước N*N với các ô số ngẫu nhiên, nhiệm vụ của người chơi là di chuyển ô trống sao cho đưa được tất cả các ô số về đúng trạng thái đích.
Tác giả
| Tên | Mã sinh viên |
|---|---|
| Phạm Văn Linh | 20194094 |
| Nguyễn Văn Đức | 20194023 |
| Bùi Tiến Đạt | 20194012 |
| Vũ Đức Anh | 20193985 |
Giáo viên hướng dẫn
PGS.TS. Lê Thanh Hương - SOICT - HUST
Tính năng
Các tính năng của trò chơi sẽ được chia thành 2 nhóm chứ năng đó là chắc năng người chơi và chức năng giải bằng AI
- Người chơi có thể sử dụng button Trộn để xáo các ô số trên màn hình.
- Có 2 chế độ dành cho người chơi: chơi bằng bảng ô số hoặc thêm ảnh từ thiết bị.
- Người chơi có thể chọn 3 mức độ chơi dễ, trung bình và khó tương đương với các kích thước 3*3, 4*4 và 5*5.
- Người chơi có thể tùy chọn 2 trạng thái đích.
- Khi chơi, người chơi thực hiện di chuyển các ô số thông qua các nút W, A, S, D trên bàn phím hoặc click chuột.
- Người chơi có thể để AI tự giải bằng button Giải, sau khi giải xong người chơi có thể lựa chọn tự chạy lời giải hoặc không.
- Chức năng thứ 2 đó là so sánh các Heuristic, AI sẽ tự chạy lần lượt các Heuristic để tìm lời giải sau đó so sánh kết quả các lần chạy.
Thuật toán
Trong trò chơi này bọn mình dùng 2 thuật toán để tìm lời giải đó là:
- Tìm kiếm theo chiều rộng - BFS
- Tìm kiếm với tri thức bổ sung - A* với 6 heuristic sẽ được giới thiệu ở phần sau.
Heuristic
6 heuristic được bọn mình sử dụng với thuật toán A* đó là:
- H1: Tổng số ô sai vị trí.
- H2: Khoảng cách Manhattan - Khoảng cách ngắn nhất để các ô về đúng vị trí đích.
- H3: Khoảng cách Euclid giữa các ô và vị trí đích(lấy phần nguyên).
- H4: Tổng số ô sai hàng cộng số ô sai cột.
- H5: Linear conflict - Khoảng cách manhattan + số ô linear conflict
- H6: H5 + số ô không thể về đích(các ô mà vị trí xung quanh trạng thái đích của nó đều đúng).
Demo
Video
Hình ảnh
Phụ lục
- Source code: https://github.com/phamvanlinhxyz/N-Puzzle-AI
- Báo cáo: https://drive.google.com/file/d/1gBWbTK4GK_m73iyomaOFbRzZ1Nv1EIkZ/view?usp=sharing
Lời kết
Trong bài viết này mình đã chia sẻ cho các bạn bài tập lớn nhập môn AI của bọn mình. Nếu có bất kì thắc mắc hay góp ý nào hãy để lại cho mình 1 comment ở bên dưới. Chúc các bạn một ngày tốt lành!
Copyright © Phạm Văn Linh