<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

<b>BỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG ĐẠI HỌC KIẾN TRÚC</b>

<b>BÀI TẬP LỚN MƠN TRÍ TUỆ NHÂN TẠO</b>

<b>NGHIÊN CỨU VÀ XÂY DỰNG GHOST-PACMAN TRÊN THUẬT TOÁN DFS</b>

Giảng viên hướng dẫn: Nguyễn Thị HuệNhóm: 7

Sinh viên thực hiện: Lưu Việt Dương (Nhóm trưởng)Nguyễn Quốc Việt Hùng

Phạm Đức TrịnhĐỗ Vĩnh ĐạiĐỗ Anh Tuấn

<b>Hà Nội, tháng 10 năm 2023</b>

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

<b>MỤC LỤC</b>

<b>MỤC LỤC____________________________________________________________2DANH MỤC VIẾT TẮT________________________________________________4DANH MỤC HÌNH ẢNH_______________________________________________5LỜI NÓI ĐẦU________________________________________________________6CHƯƠNG 1. TỔNG QUAN VỀ ĐỀ TÀI___________________________________71.1. Tổng quan về trí tuệ nhân tạo____________________________________7</b>

1.1.1. Khái niệm________________________________________________________71.1.2. Lịch sử phát triển__________________________________________________71.1.3. Các lĩnh vực nghiên cứu và ứng dụng cơ bản____________________________81.1.4. Những vấn đề chưa được giải quyết____________________________________91.1.5. Các hướng phát triển_______________________________________________9

<b>1.2. Tổng quan về đề tài_____________________________________________9</b>

1.2.1 Ý tưởng__________________________________________________________91.2.2. Cách chơi_______________________________________________________101.2.3. Phương hướng___________________________________________________10

<b>1.3. Các công nghệ sử dụng trong đề tài_______________________________10</b>

1.3.1. Ngôn ngữ Python_________________________________________________101.3.2. Thư viện Time___________________________________________________111.3.3. Thư viện Imple Object Oriented Graphics______________________________11

<b>CHƯƠNG 2. ỨNG DỤNG THUẬT TOÁN DFS VÀO PACMAN_____________122.1. Thuật tốn DFS tổng qt______________________________________12</b>

2.1.1. Khái niệm.______________________________________________________122.1.2. Mơ tả thuật toán DFS qua đồ thị._____________________________________132.1.3. Ưu nhược điểm___________________________________________________14

<b>2.2. Áp dụng thuật toán vào dự án___________________________________14</b>

2.2.1. Trạng thái xuất phát_______________________________________________142.2.2. Thiết lập DFS____________________________________________________14

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

<b>CHƯƠNG 3: TRIỂN KHAI HỆ THỐNG_________________________________153.1. Thiết lập bộ khung cơ bản______________________________________153.2. Khởi tạo mơi trường hệ thống chính______________________________173.3. Thiết lập thuật tốn DFS_______________________________________19TÀI LIỆU THAM KHẢO______________________________________________24</b>

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

<b>DANH MỤC VIẾT TẮT</b>

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

<b>DANH MỤC HÌNH ẢNH</b>

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

<b>LỜI NĨI ĐẦU</b>

Trí tuệ nhân tạo hiện đang đóng vai trò rất quan trọng trong cuộc sống hoạt động mn màu mn vẻ của thế giới.

Vậy “Trí tuệ nhân tạo - AI” là gì? AI – Aritifical Intelligence hay cịn được gọilà trí tuệ nhân tạo là một ngành khoa học kỹ thuật liên quan đến máy móc thơng minh. Trí tuệ nhân tạo được thực hiện bằng cách nghiên cứu suy nghĩ của con người , các con người học hỏi, sự quyết định, cách làm việc khi gặp một vấn đề nào đó.

Thơng qua q trình nghiên cứu trên tạo thành một nền tảng quan trọng trong việc phát triển và tạo nên hệ thống máy móc thơng minh rồi áp dụng nó vào mục địch khác nhau trong cuộc sống của nhân loại.

Với trí tuệ nhân tạo, nhân loại đã có thể giải quyết nhiều vấn đề một cách tốt hơn. Để tìm hiểu sâu hơn về AI nói chúng cũng như các thuật tốn tìm kiếm nói riêng, nhóm xin triển khai việc nghiên cứu và xây dựng Ghost-Pacman dựa trên thuật toán DFS.

Do thời gian hạn chế cũng như việc kỹ năng có thể thiếu sót trong hiểu biết về xây dựng phần mềm và trí tuệ nhân tạo, nghiên cứu và xây dựng của nhóm vẫn sẽ cịn nhiều hạn chế. Rất mong nhận được sự đóng góp ý kiến từ thầy cơ.

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

<b>CHƯƠNG 1. TỔNG QUAN VỀ ĐỀ TÀI</b>

<b>1.1. Tổng quan về trí tuệ nhân tạo</b>

Thuật ngữ “Trí tuệ nhân tạo” (Artificial Intelligence - AI) được thiết lập bởiJohn McCarthy tại Hội thảo đầu tiên về chủ đề này vào mùa hè năm 1956. Đồng thời,ông cũng đề xuất ngơn ngữ lập trình Lisp – một trong những ngơn ngữ lập trình hàmtiêu biểu, được sử dụng trong lĩnh vực AI. Sau đó, Alan Turing đưa ra "Turing test"như là một phương pháp kiểm chứng hành vi thông minh.

Thập kỷ 60, 70 Joel Moses viết chương trình Macsyma - chương trình tốnhọc sử dụng cơ sở tri thức đầu tiên thành công. Marvin Minsky và Seymour Papert đưara các chứng minh đầu tiên về giới hạn của các mạng nơ-ron đơn giản. Ngơn ngữ lậptrình logic Prolog ra đời và được phát triển bởi Alain Colmerauer. Ted Shortliffe xâydựng thành công một số hệ chuyên gia đầu tiên trợ giúp chẩn đoán trong y học, các hệthống này sử dụng ngôn ngữ luật để biểu diễn tri thức và suy diễn.

Vào đầu những năm 1980, những nghiên cứu thành công liên quan đến AInhư các hệ chuyên gia (expert systems) – một dạng của chương trình AI mơ phỏng trithức và các kỹ năng phân tích của một hoặc nhiều chuyên gia con người

Vào những năm 1990 và đầu thế kỷ 21, AI đã đạt được những thành tựu to lớnnhất, AI được áp dụng trong logic, khai phá dữ liệu, chẩn đoán y học và nhiều lĩnh vựcứng dụng khác trong công nghiệp. Sự thành công dựa vào nhiều yếu tố: tăng khả năngtính tốn của máy tính, tập trung giải quyết các bài toán con cụ thể, xây dựng các mốiquan hệ giữa AI và các lĩnh vực khác giải quyết các bài toán tương tự, và một sự

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

chuyển giao mới của các nhà nghiên cứu cho các phương pháp tốn học vững chắc vàchuẩn khoa học chính xác.

<b>1.1.3. Các lĩnh vực nghiên cứu và ứng dụng cơ bản</b>

Lập luận, suy diễn tự động: Khái niệm lập luận (reasoning), và suy diễn(reference) được sử dụng rất phổ biến trong lĩnh vực AI. Lập luận là suy diễn logic,dùng để chỉ một tiến trình rút ra kết luận (tri thức mới) từ những giả thiết đã cho (đượcbiểu diễn dưới dạng cơ sở tri thức). Như vậy, để thực hiện lập luận người ta cần có cácphương pháp lưu trữ cơ sở tri thức và các thủ tục lập luận trên cơ sở tri thức đó.

Biểu diễn tri thức: Muốn máy tính có thể lưu trữ và xử lý tri thức thì cần cócác phương pháp biểu diễn tri thức. Các phương pháp biểu diễn tri thức ở đây bao gồmcác ngôn ngữ biểu diễn và các kỹ thuật xử lý tri thức. Một ngôn ngữ biểu diễn tri thứcđược đánh giá là “tốt” nếu nó có tính biểu đạt cao và các tính hiệu quả của thuật tốnlập luận trên ngơn ngữ đó. Tính biểu đạt của ngơn ngữ thể hiện khả năng biểu diễn mộtphạm vi rộng lớn các thông tin trong một miền ứng dụng. Tính hiệu quả của các thuậttốn lập luận thể hiện chi phí về thời gian và không gian dành cho việc lập luận. Tuynhiên, hai yếu tố này dường như đối nghịch nhau, tức là nếu ngơn ngữ có tính biểu đạtcao thì thuật tốn lập luận trên đó sẽ có độ phức tạp lớn (tính hiệu quả thấp) và ngượclại (ngơn ngữ đơn giản, có tính biểu đạt thấp thì thuật tốn lập luận trên đó sẽ có hiệuquả cao). Do đó, một thách thức lớn trong lĩnh vực AI là xây dựng các ngơn ngữ biểudiễn tri thức mà có thể cân bằng hai yếu tố này, tức là ngơn ngữ có tính biểu đạt đủ tốt(tùy theo từng ứng dụng) và có thể lập luận hiệu quả.

Lập kế hoạch: khả năng suy ra các mục đích cần đạt được đối với các nhiệmvụ đưa ra, và xác định dãy các hành động cần thực hiện để đạt được mục đích đó.

Học máy: là một lĩnh vực nghiên cứu của AI đang được phát triển mạnh mẽ vàcó nhiều ứng dụng trong các lĩnh vực khác nhau như khai phá dữ liệu, khám phá trithức, …

Xử lý ngôn ngữ tự nhiên: là một nhánh của AI, tập trung vào các ứng dụngtrên ngôn ngữ của con người. Các ứng dụng trong nhận dạng tiếng nói, nhận dạng chữviết, dịch tự động, tìm kiếm thơng tin, …

Hệ chun gia: cung cấp các hệ thống có khả năng suy luận để đưa ra nhữngkết luận. Các hệ chuyên gia có khả năng xử lý lượng thông tin lớn và cung cấp các kếtluận dựa trên những thơng tin đó. Có rất nhiều hệ chuyên gia nổi tiếng như các hệchuyên gia y học MYCIN, đoán nhận cấu trúc phân tử từ công thức hóa họcDENDRAL…

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

<b>1.1.4. Những vấn đề chưa được giải quyết</b>

Mặc dù đạt được nhiều thành tựu và có nhiều ứng dụng đáng kể, các hệ thốngtrí tuệ nhân tạo hiện nay chưa đạt được mức độ trí tuệ nhân tạo mạnh (strong AI) haytrí tuệ nhân tạo tổng quát (Artificial General Intelligence). Đây cũng được coi là vấnđề khó nhất và chưa được giải quyết. Trí tuệ nhân tạo mạnh là khái niệm để chỉ khảnăng của máy tính thực hiện bất cứ cơng việc trí tuệ nào mà con người có thể thựchiện. Khái niệm trí tuệ mạnh được sử dụng để phân biệt với trí tuệ nhân tạo yếu (weakAI) hay trí tuệ nhân tạo ứng dụng (applied AI), tức là dùng máy tính để giải quyết từngbài tốn ra quyết định hay lập luận đơn lẻ. Như vậy, trí tuệ nhân tạo mạnh địi hỏi giảiquyết đầy đủ các cơng việc trí tuệ như người trong khi trí tuệ nhân tạo yếu giải quyếtbài tốn cụ thể.

Các khó khăn để đạt được trí tuệ nhân tạo tổng quát bao gồm khả năng thịgiác máy, xử lý ngôn ngữ tự nhiên, khả năng xử lý các tình hướng mới, tình huốngkhơng ngờ tới khi giải quyết các bài tốn thực tế. Đây là những lĩnh vực mà máy tínhcịn thua kém con người. Các hệ thống trí tuệ nhân tạo hiện nay có thể giải quyết tốtbài tốn đặt ra trong một phạm vi hẹp. Tuy nhiên, khi gặp vấn đề thực tế ở phạm virộng hơn, hệ thống trí tuệ nhân tạo thường khơng thể xử lý được các tình huống mới,vượt ra ngồi ngữ cảnh ban đầu của bài tốn. Ngược lại, con người có khả năng xử lýtốt hơn nhiều những trường hợp như vậy do có hiểu biết rộng về thế giới xung quanh.Việc trang bị cho máy tính lượng tri thức như con người hiện vẫn là vấn đề chưa đượcgiải quyết

<b>1.1.5. Các hướng phát triển</b>

Hiện nay trí tuệ nhân tạo có thể mang lại nhiều cơ hội phát triển theo nhiềukhuynh hướng khác nhau chẳng hạn như Tìm kiếm trong khơng gian, học máy, hệchuyên gia, nhân dạng và xử lý tiếng nói… Khơng chỉ dừng lại ở đó trí tuệ nhân tạongày càng phát triển mang lại nhiều khuynh hướng phát triển hơn nữa bên cạnh đó cácngành phát triển từ trí tuệ nhân tạo cũng ngày càng khó khăn hơn khi tìm kiếm tuyểnchọn người nội dung khắt khe hơn…

<b>1.2. Tổng quan về đề tài1.2.1 Ý tưởng</b>

Pacman là một trò chơi nổi tiếng khắp thế giới vào những năm đầu thập niên1980, ngày nay dù đã khơng cịn nổi tiếng như ngày đó nhưng vẫn khơng thể khơngcơng nhận sự thú vị trong trò chơi này.

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

Nhằm lưu giữ lấy một trò chơi thế kỷ dựa vào thuật tốn hiện đại DFS hyvọng có thể mang lại sự sống mới cho trò chơi tuyệt vời này.

<b>1.2.2. Cách chơi</b>

Với mục đích thiết kế thuật tốn tìm kiếm đường đi cho nhân vật Ghost, thiếtkế trò chơi sẽ cho thấy rõ ràng phương pháp tìm kiếm đường đi của nhân vật Ghost khiđịnh vị vị trí của Pacman trên bản đồ.

Lý do lựa chọn ngôn ngữ do các ưu điểm tối ưu của ngôn ngữ như sau:

Đơn giản, dễ học: Python có cú pháp rất đơn giản, rõ ràng. Nó dễ đọc và viếthơn rất nhiều khi so sánh với những ngơn ngữ lập trình khác như C++, Java, C#.Python làm cho việc lập trình trở nên thú vị, cho phép bạn tập trung vào những giảipháp chứ không phải cú pháp.

Miễn phí, mã nguồn mở: Bạn có thể tự do sử dụng và phân phối Python, thậmchí là dùng cho mục đích thương mại. Vì là mã nguồn mở, bạn khơng những có thể sửdụng các phần mềm, chương trình được viết trong Python mà cịn có thể thay đổi mãnguồn của nó. Python có một cộng đồng rộng lớn, khơng ngừng cải thiện nó mỗi lầncập nhật.

Khả năng di chuyển: Các chương trình Python có thể di chuyển từ nền tảngnày sang nền tảng khác và chạy nó mà khơng có bất kỳ thay đổi nào. Nó chạy liềnmạch trên hầu hết tất cả các nền tảng như Windows, macOS, Linux.

Khả năng mở rộng và có thể nhúng: Giả sử một ứng dụng đòi hỏi sự phức tạprất lớn, bạn có thể dễ dàng kết hợp các phần code bằng C, C++ và những ngơn ngữkhác (có thể gọi được từ C) vào code Python. Điều này sẽ cung cấp cho ứng dụng của

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

bạn những tính năng tốt hơn cũng như khả năng scripting mà những ngơn ngữ lập trìnhkhác khó có thể làm được.

Ngôn ngữ thông dịch cấp cao: Không giống như C/C++, với Python, bạnkhơng phải lo lắng những nhiệm vụ khó khăn như quản lý bộ nhớ, dọn dẹp những dữliệu vơ nghĩa,... Khi chạy code Python, nó sẽ tự động chuyển đổi code sang ngơn ngữmáy tính có thể hiểu. Bạn không cần lo lắng về bất kỳ hoạt động ở cấp thấp nào.

Thư viện tiêu chuẩn lớn để giải quyết những tác vụ phổ biến: Python có mộtsố lượng lớn thư viện tiêu chuẩn giúp cho công việc lập trình của bạn trở nên dễ thởhơn rất nhiều, đơn giản vì khơng phải tự viết tất cả code. Ví dụ: Bạn cần kết nối cơ sởdữ liệu MySQL trên Web server? Bạn có thể nhập thư viện MySQLdb và sử dụng nó.Những thư viện này được kiểm tra kỹ lưỡng và được sử dụng bởi hàng trăm người. Vìvậy, bạn có thể chắc chắn rằng nó sẽ khơng làm hỏng code hay ứng dụng của mình.

Hướng đối tượng: Mọi thứ trong Python đều là hướng đối tượng. Lập trìnhhướng đối tượng (OOP) giúp giải quyết những vấn đề phức tạp một cách trực quan.Với OOP, bạn có thể phân chia những vấn đề phức tạp thành những tập nhỏ hơn bằngcách tạo ra các đối tượng.

<b>1.3.2. Thư viện Time</b>

Thư viện Time trong Python cung cấp nhiều cách biểu diễn thời gian trongcode, chằng hạn như đối tượng, số, chuỗi… Thư viện này cũng cung cấp chức năngkhác ngoài việc đại diện cho thời gian như chờ đợi trong quá trình thực thi đoạn mã,đo lường độ hiệu quả của mã.

Mặc dù thư viện này ln có sẵn nhưng khơng phải tất cả các chức năng đềucó sẵn trên tất cả các nền tảng khác nhau. Hầu hết các hàm được định nghĩa trong thưviện Time đều gọi các hàm thư viện nền tảng C có cùng tên. Đơi khi có thể hữu ích khitham khảo tài liệu nền tảng vì ngữ nghĩa của các chức năng này khác nhau giữa cácnền tảng.

Ngồi ra thư viện này cịn cho phép tạm dừng việc thực thi mã của mình trongmột số giây nhất định. Điều này có thể hữu ích để tạo độ trễ hoặc tạm dừng trongchương trình.

<b>1.3.3. Thư viện Imple Object Oriented Graphics</b>

Thư viện đồ họa hướng đối tượng đơn giản được thiết kế để giúp những ngườimới lập trình có thể dễ dàng thử nghiệm đồ họa máy tính phương thức hướng đốitượng. Thư viện này được viết bởi John Zelle để sử dụng cùng với cuốn sách " Python

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

Programming: An Introduction to Computer Science – Tạm dịch: Lập trình Python:Giới thiệu về Khoa học máy tính" (Franklin, Beedle & Associates).

Thư viên này là phần mềm mã nguồn mở được phát hành theo các điều khoảncủa GPL. Thư viện này là một trình bao bọc xung quanh Tkinter và sẽ chạy trên bất kỳnền tảng nào có Tkinter. Nguyên tắc sử dụng đặt tệp “graphics.py” nơi Python có thểthấy.

Thư viện này chứa hai loại đối tượng trong thư viện. Lớp GraphWin triển khaimột cửa sổ nơi có thể thực hiện việc vẽ và cung cấp nhiều GraphicsObject khác nhauđể có thể vẽ vào GraphWin.

Các đối tượng được triển khai trong từ lớp GraphWin hỗ trợ chuyển đổi tọa độthông qua phương thức setCoords và các phương thức tương tác chuột và bàn phím.

Thư viện cung cấp các đối tượng đồ họa sau: Point (Điểm), Line (Đường),Circle (Hình trịn), Oval (Hình bầu dục), Rectangle (Hình chữ nhật), Polygon (Đagiác), Text (Văn bản), Entry (Nhập văn bản), Image (Hình ảnh).

Các thuộc tính khác nhau của các đối tượng đồ họa có thể được đặt như màuđường viền, màu tô và độ rộng. Các đối tượng đồ họa cũng hỗ trợ di chuyển và ẩn nấpđể tạo hiệu ứng hoạt ảnh.

<b>CHƯƠNG 2. ỨNG DỤNG THUẬT TOÁN DFS VÀO PACMAN</b>

<b>2.1. Thuật toán DFS tổng quát</b>

<b>2.1.1. Khái niệm.</b>

Thuật toán DFS là một dạng thuật tốn tìm kiếm trên đồ thị nút điểm hay cây.Trong lý thuyết khoa học máy tính, thuật tốn DFS nằm trong chiến lượng tìm kiếmmù (tìm kiếm khơng có định hướng, khơng chú ý đến giá trị thơng tin, giá trị đượcduyệt).

Ý tưởng thuật tốn triển khai thuật toán DFS cơ bản:

Duyệt xa nhất theo từng nhánh, khi nhánh đã duyệt hết, lùi về tìm và duyệtnhững nhánh tiếp theo. Quá trình duyệt đỉnh chỉ dừng lại khi đã tìm thấy mục tiêuhoặc khi đã duyệt qua hết tất cả các đỉnh

</div>