TRƯỜNG ĐH SƯ PHẠM KỸ THUẬT TP. HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN TIỂU LUẬN CUỐI KỲ Môn học: TRÍ TUỆ NHÂN TẠO ĐỀ TÀI: XÂY DỰNG GAME GIẢI MÊ CUNG DÙNG CÁC THUẬT TOÁN TRONG VIỆC TÌM ĐƯỜNG ĐI TỐI ƯU Giảng viên: PGS. Hoàng Văn Dũng Danh sách sinh viên thực hiện Mã số Họ và tên Mức độ đóng góp (%) SV 21110837 Nguyễn Quốc Lân 100% 21110822 Võ Minh Đạt 100% 21110154 Trần Đình Duy 100% TP. Hồ Chí Minh, tháng 11 năm 2023 MỤC LỤC PHẦN 1.Phát biểu bài toán.Mục đích, yêu cầu cần thực hiện.1Môi trường lập trình.2Thư viện chính sử dụng.Giải thuật BFS.Mô tả trong code.Giải thuật DFS.Mô tả trong code.Giải thuật UCS.Mô tả trong code.Giải thuật Greedy Search.Mô tả trong code.Mô tả trong code.Giải thuật ID.Mô tả trong code.Giải thuật Beam Search.Mô tả trong code.
PHÂN TÍCH, THIẾT KẾ GIẢI PHÁP.Thiết kế giao diện.Giao diện trang chủ.Giao diện người chơi.Giao diện AI.Các chức năng khác:.Dừng khẩn cấp. THỰC NGHIỆM, PHÂN TÍCH, ĐÁNH GIÁ KẾT QUẢ.Thuật toán BFS.Thuật toán DFS.Thuật toán UCS.Thuật toán Greedy.Thuật toán ID.Thuật toán Beam.Phân tích chi phí cho nhiều map và trung bình.Đánh giá kết quả các thuật toán.Đánh giá kết quả thực hiện.Hướng phát triển. 36 TÀI LIỆU THAM KHẢO. 38 DANH MỤC HÌNH ẢNH Hình 1.
Code cho thuật toán BFS. Code cho thuật toán DFS. Code cho thuật toán UCS. Code cho thuật toán Greedy.
Code cho thuật toán Astar. Code cho thuật toán ID. Code cho thuật toán Beam. Giao diện trang chủ.
Giao diện chế độ người chơi. Giao diện chế độ AI chơi. Dừng khẩn cấp. Demo thuật toán BFS.
Demo thuật toán DFS. Demo thuật toán UCS. Demo thuật toán Greedy. Demo thuật toán A*.
Demo thuật toán ID. Demo thuật toán Beam.31 DANH MỤC BẢNG Bảng 1. Bảng so sánh tổng số nút duyệt. Bảng so sánh số bước di chuyển.
Bảng so sánh tổng thời gian thực thi.34 DANH MỤC BIỂU ĐỒ Biểu đồ 1. Biểu đồ cột so sánh số nút duyệt giữa các thuật toán. Biểu đồ cột so sánh số bước di chuyển giữa các thuật toán. Biểu đồ cột so sánh thời gian chạy giữa các thuật toán.
Biểu đồ so sánh tổng hợp các thuật toán.35 DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Từ đầy đủ BFS Breadth First Search DFS Depth First Search UCS Uniform Cost Search ID Iterative Deepening A* A-star AI Artificial Intelligence Avg Average PHẦN 1.1 Lời nói đầu Ngày nay cùng với sự phát triển về khoa học và kỹ thuật là sự phát triển mạnh mẽ của nền công nghệ thông tin. Trong công nghiệp, nghiên cứu khoa học thì công nghệ thông tin đống vai trò rất quan trong trong sự phát triển của đât nước cũng như toàn thế giới Trên thế giới cũng như ở Việt Nam, công nghệ thông tin đã trở thành một ngày công nghiệp mũi nhọn, nó là một ngày khoa học kỹ thuật không thể thiếu trong việc áp dụng vào các hoạt động xã hội và khoa học. Nền công nghiệp hiện nay mang tính chất tự động hóa cao kèm theo đó là sự đòi hỏi về việc ứng dụng công nghệ thông tin cho lĩnh vực này. Vậy để có thể đáp ứng tốt những yêu cầu của ngày càng cao hơn trong lĩnh vực tự động hóa người ta đã tiến hành lập trình cho những cỗ máy, những người máy có thể tư duy như con người nhằm giảm bớt các gánh nặng công việc.
Việc ứng dụng trí tuệ nhân tạo đã tạo ra một cuộc cách mạng lớn trong việc tìm hiểu và chinh phục những điều mà con người không dám mơ tới. Đó là những robot thông minh, những cỗ máy thông minh có thể thay thế con người làm việc trong những môi trường khắc nghiệt hay chinh phục không gian bao la.Và bên cạnh đó là việc ứng dụng những thành tựu đó vào lĩnh vực giải trí của con người. Đó là những con vật robot, những trò chơi. Đó là những ứng dụng lớn lao của trí tuệ nhân tạo vào của sống của con người.
Trong bài tập lớn này chúng em sử dụng những thuật toán đã học cùng với giao diện trực quan mô tả cách thức hoạt động của các thuật toán AI để sinh viên dể dàng hiểu được cũng như vận dụng chúng cho chính công việc của họ sau này. Mặc dù rất cố gắng để hoàn thành công việc, xong thời gian có hạn và kiến thức chưa nhiều nên việc chương trình còn nhiều thiếu sót cần được bổ xung. Vì vậy chúng em mong nhận được những đóng góp của thầy cô và bạn bè để chương trình ngày càng hoàn thiện hơn và giúp ích được nhiều hơn.2 Phát biểu bài toán Bài toán đặc ra là dùng các giải thuật đã học trong trí tuệ nhân tạo để giải mã một mê cung và tìm đường đi đến vị trí chìa khóa và vị trí cửa cuối cùng.3 Mục đích, yêu cầu cần thực hiện Mục đích của đề tài này là dùng giao diện trực quan mô tả quá quá trình giải mã các thuật toán AStar, Breadth First Search, Depth First Search, Uniform-Cost Search, Greedy Search, Iterative Deepening Search, Beam Search đồng thời tính toán thời gian thực thi của từng thuật toán cho từng không gian trạng thái khác nhau. Bài toán tìm đường đi trong một mê cung dùng để mô phỏng đánh giá các thuật toán trong việc giải mã các mê cung khác nhau, từ đó đưa ra nhận xét và kết luận về việc giải mã mê cung, đánh giá không gian trạng thái cũng như tính toán thời gian thực hiện thuật toán để xác định với mỗi không gian trạng thái khác nhau thì ta cần sử dụng thuật toán nào để tối ưu hóa nhất có thể.
Đồ án học phần này có giá trị như một phần mô phỏng phục vụ cho mục đích giáo dục sau này.1 Môi trường lập trình Với bài tập lớn này chúng em sử dụng Python làm ngôn ngữ chính để viết code với trình soạn thảo code Visual Studio Code và trình biên dịch spyder (anaconda3) 2.2 Thư viện chính sử dụng Thư viện chính được nhóm chúng em sử dụng là pygame. Đây là thư viện mã nguồn mở trên ngôn ngữ Python dùng để lập trình video game. Pygame chứa đầy đủ các công cụ hỗ trợ lập trình game như đồ họa, hoạt hình, âm thanh, và sự kiện điều khiển. Pygame cũng đồng thời cung cấp các công cụ tích hợp hiệu ứng âm thanh cũng như nhạc nền cho game.
Cuối cùng, các sự kiện điều khiển từ bàn phím, chuột cũng được Pygame hỗ trợ một cách hiệu quả. Trong đề tài này, nhóm chúng em sử dụng Pygame để xây dựng giao diện và mô phỏng chuyển động thuật toán. Đầu mỗi file, khai báo thư viện pygame qua câu lệnh ‘import pygame’.3 Giải thuật BFS Thuật toán duyệt đồ thị ưu tiên chiều rộng là thuật toán tìm kiếm mù mà những đỉnh gần với đỉnh gốc sẽ được duyệt trước. Ý tưởng Với đồ thị không trọng số và đỉnh nguồn s.
Đồ thị này có thể là đồ thị có hướng hoặc vô hướng, điều đó không quan trọng đối với thuật toán. Đầu tiên ta thăm đỉnh nguồn s. Việc thăm đỉnh s sẽ phát sinh thứ tự thăm các đỉnh (u1 , u2 ,…up) kề với s (những đỉnh gần s nhất). Tiếp theo, ta thăm đỉnh u1, khi thăm đỉnh u1 sẽ lại phát sinh yêu cầu thăm những đỉnh (v1, v2, …, vp) kề với u1.
Nhưng rõ ràng những đỉnh v này “xa” s hơn những đỉnh uu nên chúng chỉ được thăm khi tất cả những đỉnh uu đều đã được thăm. Tức là thứ tự thăm các đỉnh sẽ là: s, u1 , u2, …, up , v1, v2, …, vp. Mô tả trong code def bfs(GUI, Grid, start, end): Grid.append((count, start)) states_history = {start} came_from = {} while len(states) != 0: if abortCatch(): return (0, 0) current = states.pop(0)[1] if current == end: came_from.pop(start) return came_from, count for nei in Grid.neighbors[flat(current, Grid.size)]: if (nei in came_from): if (came_from[nei] not in came_from): came_from[nei] = current else: came_from[nei] = current if nei not in states_history: count += 1 states.append((count, nei)) states_history.add(nei) if nei != end: simulate(GUI, nei) return 0, 0 Hình 1. Code cho thuật toán BFS 4 2.4 Giải thuật DFS Thuật toán tìm kiếm theo chiều sâu là một thuật toán duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị.
Thuật toán khởi đầu tại gốc (hoặc chọn một đỉnh nào đó coi như gốc) và phát triển xa nhất có thể theo mỗi nhánh.1 Ý tưởng Đây là thuật toán tìm các đỉnh bằng cách duyệt theo chiều sâu. Đầu tiên ta thăm đỉnh nguồn s. Xuất phát từ 1 đỉnh và đi cho đến khi không thể đi tiếp, sau đó đi về lại đỉnh đầu. Trong quá trình quay lại: Nếu gặp đường đi khác thì đi cho đến khi không đi tiếp được nữa.
Nếu không tìm ra đường đi nào khác thì ngừng việc tìm kiếm. Trong quá trình đi đến đỉnh khác, thuật toán sẽ lưu lại đỉnh cha vừa đi qua để khi đi ngược lại từ đỉnh Kết thúc đến đỉnh Xuất phát, ta có thể xem được đường đi từ đỉnh Kết thúc đến đỉnh Bắt Đầu (có thể số lần đi không ít nhất, các bạn có thể tham khảo thuật toán BFS).2 Mô tả trong code def dfs(GUI, Grid, start, end): Grid.append((count, start)) states_history = {start} came_from = {} while len(states) != 0: if abortCatch(): return (0, 0) current = states.pop()[1] if current == end: came_from.pop(start) 5 return came_from, count neis = Grid.neighbors[flat(current, Grid.shuffle(neis) for nei in neis: if (nei in came_from): if (came_from[nei] not in came_from): came_from[nei] = current else: came_from[nei] = current if nei not in states_history: count += 1 states.append((count, nei)) states_history.add(nei) if nei != end: simulate(GUI, nei) return 0, 0 Hình 2.