Tóm tắt đồ án Ứng dụng trí tuệ nhân tạo để lập trình trò chơi caro giữa người và máy

Nội dung text: Tóm tắt đồ án Ứng dụng trí tuệ nhân tạo để lập trình trò chơi caro giữa người và máy

1. TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN HỮU NGHỊ VIỆT - HÀN KHOA CÔNG NGHỆ THÔNG TIN  ỨNG DỤNG TRÍ TUỆ NHÂN TẠO ĐỂ LẬP TRÌNH TRÒ CHƠI CARO GIỮA NGƢỜI VÀ MÁY TÓM TẮT ĐỒ ÁN TỐT NGHIỆP NGÀNH: LẬP TRÌNH MÁY TÍNH HSSV thực hiện : Lê Hữu Hùng MÃ HSSV : CCLT17A003 Cán bộ hƣớng dẫn : TS. Lê Tân Khóa đào tạo : 2017 - 2020 Đà Nẵng, 01/2020
2. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy MỞ ĐẦU 1. Lý do chọn đề tài Từ lâu con người đã có suy nghĩ muốn tạo ra một cỗ máy có thể tự suy nghĩ và hành động. Chính vì thế, trí tuệ nhân tạo (AI) trở thành một một lĩnh vực mới trong thời đại công nghệ thông tin ngày nay. Các ngành nghề trong xã hội đang có xu hướng xử dụng AI để khiến máy móc thông minh hơn. Trong giải trí, trong y tế, hay cả trong giáo dục, rất nhiều robot thông minh được tạo ra có thể thay thế con người dạy học, giúp đỡ người già, thực hiện các công đoạn trong công nghiệp, Vì những ứng dụng hữu ích của nó, em xin trình bày một ứng dụng của AI trong game caro giữa người và máy dựa trên các thuật toán cơ bản hay dùng trong trí tuệ nhân tạo. Mong muốn thông qua game này, em sẽ có những cái nhìn cụ thể về đề tài AI, từ đó mở rộng để nghiên cứu và phát triển thêm. 2. Mục tiêu và nhiệm vụ nghiên cứu Mục tiêu: Tìm hiểu định nghĩa, lịch sử phát triển của trí tuệ nhân tạo Tìm hiểu cấu trúc, các thuật toán và cách hoạt động của AI Nhiệm vụ: Ứng dụng nghiên cứu để lập trình game caro mà máy tính có thể tự đưa ra bước đi 3. Đối tƣợng và phạm vi nghiên cứu Đối tượng nghiên cứu: Lĩnh vực AI Phạm vi nghiên cứu: Trong game caro giữa người và máy SVTH: Lê Hữu Hùng – Lớp CCLT17A 1
3. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy 4. Phƣơng pháp nghiên cứu Nghiên cứu dựa trên: Tài liệu Tham khảo từ giáo viên hướng dẫn Thực hành viết mã trên máy tính bằng ngôn ngữ java 5. Dự kiến kết quả Đạt được mục tiêu đã nêu ra, lập trình thành công game caro giữa người và máy. Dự kiến hoàn thành trong khoảng 1 tháng. 6. Ý nghĩa khoa học và thực tiễn Ý nghĩa khoa học: Tìm hiểu về các thuật toán được sử dụng trong công nghệ AI. Có được nền tảng để mở rộng phạm vi nghiên cứu ở những mặt ứng dụng khác của trí tuệ nhân tạo Thực tiễn: Lập trình game caro phục vụ cho giải trí và nâng cao khả năng lập trình. 7. Nội dung đồ án tốt nghiệp Ngoài phần mở đầu, kết luận và tài liệu tham khảo, nội dung đồ án gồm có 2 chương: Chương 1: Giới thiệu về AI Chương 2: Ứng dụng AI để lập trình game caro giữa người và máy SVTH: Lê Hữu Hùng – Lớp CCLT17A 2
4. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy CHƢƠNG I: GIỚI THIỆU VỀ AI 1.1. GIỚI THIỆU VỀ AI 1.1.1. Tìm hiểu khái niệm 1.1.2. Lịch sử phát triển 1.1.3. Các lĩnh vực nghiên cứu của AI 1.1.4. Ứng dụng của AI 1.2. NHỮNG VẤN ĐỀ CHƢA ĐƢỢC GIẢI QUYẾT CỦA TRÍ TUỆ NHÂN TẠO 1.3. NHỮNG ƢU ĐIỂM VÀ RỦI RO CỦA AI HIỆN TẠI 1.3.1. Ƣu điểm 1.3.2. Rủi ro SVTH: Lê Hữu Hùng – Lớp CCLT17A 3
5. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy CHƢƠNG II: ỨNG DỤNG AI ĐỂ LẬP TRÌNH GAME CARO GIỮA NGƢỜI VÀ MÁY 2.1. CÁC CHƢƠNG TRÌNH CHƠI CỜ VÀ LỊCH SỬ GAME CARO 2.1.1. Sơ lƣợc về lịch sử các chƣơng trình chơi cờ 2.1.2. Lịch sử của game caro 2.1.3. Sự phát triển của game caro 2.2. PHÂN TÍCH BÀI TOÁN nh 2.4. Cây tìm kiếm của trò chơi 2.3. PHƢƠNG PHÁP GIẢI QUYẾT 2.3.1. Các thuật toán tìm kiếm 2.3.2. Phân tích và lựa chọn thuật toán cho game Sau khi đã t m hiểu các thuật toán trên, dễ thấy rằng giải thuật tìm kiếm minimax kết hợp cắt tia alpha-beta rất phù hợp để tìm kiếm nước đi tốt cho máy. Vì vậy trong game caro giữa người và máy em sẽ sử dụng thuật toán này. Game bao gồm một vùng 20x20 ô, khi bắt đầu game, sẽ có 2 trường hợp người đánh trước hoặc máy đánh trước. Khi máy được tùy chỉnh để đánh trước, máy sẽ đánh vào ô trung tâm, ngược lại, khi người chơi đánh trước sẽ khởi chạy thuật toán minimax và cắt tỉa alpha-beta để tìm kiếm nước đi cho máy. SVTH: Lê Hữu Hùng – Lớp CCLT17A 4
6. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy nh 2.15. Sơ đồ hàm alphabeta SVTH: Lê Hữu Hùng – Lớp CCLT17A 5
7. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy nh 2.16. Sơ đồ hàm maxvalue àm maxvalue đầu tiên sẽ gọi hàm Giatribanco() để tính toán giá trị của các ô. Sau đó sẽ lấy ra ô có giá trị lớn nhất, nghĩa là ô này là ô lợi thế cho máy. Kiểm tra xem đã chạm tới giới hạn độ sâu chưa, v như đã nói ở thuật toán minimax phần trước, chúng ta chỉ xét cây trò chơi trong một độ sâu nhất định. Nếu đã đạt tới độ sâu MAXDEPTH thì trả về giá trị của ô lợi thế. Ngược lại thì lấy ra MAXMOVE (ở đây là 4) ô có giá trị lớn nhất. Sau đó cho máy đánh thử vào các ô tạo thành một trạng thái bàn cờ mới (node mới) rồi áp dụng hàm minvalue cho node đó. Cứ lặp lại như thế đến khi đạt đến MAXDEPTH thì trả về giá trị của ô lớn nhất, hoặc tìm thấy trạng thái chiến thắng cho máy thì trả về giá trị max và gán nước đi tiếp theo bestmove cho nước đi đang xét (nước đi dẫn đến chiến thắng). SVTH: Lê Hữu Hùng – Lớp CCLT17A 6
8. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy nh 2.17. Sơ đồ hàm minvalue àm min cũng tương tự như hàm max Với hàm Giatribanco() chúng ta sẽ tính giá trị của các ô trống trên bàn cờ dựa theo các chiều dựa trên hàm danhgia(). Hàm danhgia xét một khối gồm 5 ô liên tiếp theo chiều dọc, ngang và 2 đường chéo. Nếu tìm thấy một khối chỉ có 1 loại quân (hoặc chỉ có X hoặc chỉ có O) thì ta sẽ tính giá trị của các ô trống còn lại trong khối đó như sau: Nếu đến lượt người có loại quân như trong khối thì các ô trống sẽ nhận giá trị theo mảng Diemtancong[] dựa trên số quân đang có trong khối, càng nhiều quân điểm càng cao. Ngược lại đến lượt của đối thủ thì ô trống sẽ nhận giá trị theo mảng Diemphongthu[]. SVTH: Lê Hữu Hùng – Lớp CCLT17A 7
9. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy Ngược lại đối với khối chỉ có toàn quân địch thì giá trị các ô trống sẽ giảm dần theo 2 mảng trên. nh 2.18. Hàm GiaTriBanCo() Hàm danhgia () bên dưới là hàm sẽ tính giá trị cho từng ô theo các chiều khác nhau SVTH: Lê Hữu Hùng – Lớp CCLT17A 8
10. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy nh 2.19. Khởi tạo tọa độ bắt đầu và kết thúc tùy theo phương duyệt Đầu tiên hàm đánh giá sẽ dựa vào thông số đưa vào là phuongduyet để gán các giá trị cho tọa độ bắt đầu (gh_cot1; gh_dong1), và tọa độ kết thúc duyệt (gh_cot2; gh_dong2). Nếu xét theo chiều ngang, phần bàn cờ được xét sẽ là toàn bộ bàn cờ trừ đi phần 4 cột bên phải bàn cờ, nếu xét theo chiều dọc phần bàn cờ được xét là toàn bộ bàn cờ trừ đi phần 4 cột ngoài cùng bên trái, tương tự với 2 đường chéo sẽ là trừ đi phần 4 cột phải và 4 dòng dưới cùng, hoặc là trừ đi 4 cột trái và 4 dòng cuối cùng SVTH: Lê Hữu Hùng – Lớp CCLT17A 9
11. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy Hình 2.21 Thực hiện tính toán giá trị cho các ô trống trong hàm danhgia() Tiếp theo trong hàm đánh giá, chúng ta duyệt một mảng 2 chiều gồm các ô trong phần bảng đã chọn tùy theo phuongduyet. Trong một lần duyệt của 2 vòng lặp, nó sẽ thực hiện những điều sau đây: Từ vị trí ô đang duyệt, thực hiện xét một khối gồm 5 ô liền kề rồi đếm xem trong 5 ô đó có bao nhiêu quân cờ của máy và bao nhiêu quân cờ của người. Ở đây hàm tangbiendem() sẽ giúp ta tăng các biến i và j trong vòng lặp for tùy theo phương duyệt, ví dụ nếu duyệt theo phương dọc, tangbiendem() sẽ chỉ tăng j, khi duyệt theo phương ngang th tangbiendem() sẽ chỉ tăng i, khi duyệt theo đường SVTH: Lê Hữu Hùng – Lớp CCLT17A 10
12. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy chéo từ trái sang phải thì tangbiendem() sẽ tăng cả i và j thêm 1, khi duyệt theo đường chéo từ phải qua trái thì sẽ tăng j và giảm i. nh 2.15. Hàm tangbiendem() Tiếp theo sẽ kiểm tra trong khối 5 ô liên tiếp đó có thỏa mãn: Hoặc chỉ chứa toàn quân của máy, hoặc chứa toàn quân của người nh 2.22. Xét 5 ô chỉ có một loại cờ SVTH: Lê Hữu Hùng – Lớp CCLT17A 11
13. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy Nếu thỏa mãn điều kiện ở bước thứ 2, kiểm tra tiếp lượt đánh là của người hay máy, nếu khối 5 ô chỉ chứa toàn quân của máy mà lại đến lượt của người chơi th giảm giá trị của ô đó theo mảng Diemphongthu[], ngược lại nếu tới lượt máy th tăng giá trị ô đó theo mảng Diemtancong[]. Vậy sau khi kết thúc hàm GiaTriBanCo() ta sẽ được một mảng 2 chiều các đối tượng Oco gồm các thuộc tính như quân cờ với giá trị 1 nếu là quân của máy, -1 nếu là quân của người, 0 nếu là ô trống. Thuộc tính giá trị chứa các giá trị mà ta vừa tính xong bằng hàm GiaTriBanCo(). nh 2.24. Đối tượng OCo Ở trên là cách thức hoạt động của hàm minimax để đưa ra nước đi tiếp theo cho máy. Phần tiếp theo, ta tìm hiểu cách xây dựng giao diện và cơ chế chiến thắng của game 2.3.3. Tạo giao diện và các cơ chế game a) Giao diện game Giao diện game được chia làm 2 phần, xây dựng dựa trên các thành phần của thư viện java.swing và thư viện Graphics: SVTH: Lê Hữu Hùng – Lớp CCLT17A 12
14. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy Hình 2.25 Giao diện game caro  Vùng chơi game: Gồm 20x20 ô được tạo thành bởi thành phần Jbutton của thư viện java.swing nh 2.26.Vùng chơi game SVTH: Lê Hữu Hùng – Lớp CCLT17A 13
15. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy Khi khởi chạy game, khi người chơi bấm vào nút New Game hoặc khi kết thúc ván chơi hàm createBox sẽ được gọi để vẽ lại 20x20 ô trên JPanel Gamearea. nh 2.27. Sơ đồ tạo giao diện chơi game Ở đây ta khởi tạo và gán cho Jbutton các sự kiện để khi click vào nó sẽ setIcon cho Jbutton đó theo biểu tượng tương ứng với quân cờ người hoặc máy đánh. Vùng thông báo và tùy chỉnh game: Gồm một hình minh họa game, một dòng String vẽ bởi thành phần Graphic thông báo luật chơi, và các nút Jbutton để điều chỉnh game SVTH: Lê Hữu Hùng – Lớp CCLT17A 14
16. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy nh 2.28. Menu game b) Cơ chế game Khi người hoặc máy có 5 quân liên tiếp sẽ có thông báo chiến thắng. Mỗi khi có một quân cờ được đánh, máy sẽ duyệt theo 4 hướng ngang, dọc và 2 đường chéo xem quân đó có tạo thành 5 quân liên tiếp không bằng hàm isEnd(), hàm này sẽ kiểm tra các hàm doc(), ngang(), cheo1(), cheo2(), nếu một trong các hàm này mang giá trị True thì thông báo kết thúc ván cờ SVTH: Lê Hữu Hùng – Lớp CCLT17A 15
17. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy nh 2.29. Kiểm tra chiến thắng Kiểm tra theo hàng dọc: máy sẽ duyệt từ vị trí quân vừa đánh theo 2 hướng lên trên và xuống dưới, nếu gặp một quân có cùng quân với ô vừa đánh, tăng biến đếm thêm 1, ngược lại thì dừng, không đếm nữa. Nếu biến đếm lớn hơn hoặc bằng 5 thì thông báo chiến thắng nh 2.30. Duyệt theo chiều dọc Tương tự với chiều ngang, 2 đường chéo SVTH: Lê Hữu Hùng – Lớp CCLT17A 16
18. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy nh 2.31. Duyệt theo chiều ngang nh 2.32. Duyệt đường chéo từ trái qua phải SVTH: Lê Hữu Hùng – Lớp CCLT17A 17
19. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy nh 2.33. Duyệt đường chéo từ phải qua trái 2.3.4. Các công cụ, thành phần sử dụng để thực hiện lập trình game. SVTH: Lê Hữu Hùng – Lớp CCLT17A 18
20. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy KẾT LUẬN 3.1. KẾT QUẢ ĐẠT ĐƢỢC Sau khi hoàn thành việc lập trình game caro dựa trên việc ứng dụng thuật toán minimax kết hợp với cắt tỉa alpha beta em đã đạt được một số kết quả sau:  Tìm hiểu được khái niệm trí tuệ nhân tạo và các lĩnh vực, ứng dụng của trí tuệ nhân tạo trong cuộc sống  Biết được sự hình thành và phát triển của trí tuệ nhân tạo mà ứng dụng cụ thể là trong các trò chơi chiến lược trên máy tính  Tìm hiểu các thuật toán tìm kiếm hay sử dụng trong trí tuệ nhân tạo  Áp dụng thuật toán minimax và cắt tỉa alpha-beta để xây dựng được hàm tính toán nước đi cho máy tính trong game caro giữa người và máy. 3.2. HƢỚNG PHÁT TRIỂN TRONG TƢƠNG LAI Vì vậy em xây dựng Game Caro này cũng có 1 mục đích bước đầu tìm hiểu về mảng Trí tuệ nhân tạo. Tiếp tục tìm hiểu và xây dựng Game Caro với 1 số tính năng như: máy có thể học cách đi của người, đưa ra phán đoán về nước đi .Và để Game có thể được nhiều người biết tới, em sẽ cố gắng tích hợp vào di động hay đưa lên website bằng cách sử dụng công cụ khác để xây dựng. Trong thời gian làm đồ án, em đã cố gắng hết m nh để hoàn thành đồ án tốt nhất. Nhưng với khả năng hiện tại và kinh nghiệm còn hạn chế, đồ án sẽ không tránh khỏi những thiếu sót. Em mong quý thầy cô cùng bạn bè thông cảm và đóng góp ý kiến để em hoàn thiện thêm kiến thức cho m nh và đồ án đạt hiệu quả cao hơn. 3.3. BÀI HỌC RÚT RA SVTH: Lê Hữu Hùng – Lớp CCLT17A 19
21. Ứng dụng trí tuệ nhân tạo để lập trình game caro giữa người và máy 3.3.1. Bài học kinh nghiệm Việc xây dựng game caro giữa người và máy giúp em có thêm hiểu biết về các thuật toán tìm kiếm hay dùng trong trí tuệ nhân tạo, điều này cũng giúp kĩ năng lập trình của em được cải thiện 3.3.2. Bài học thực tế Qua quá trình thực hiện đồ án, em nhận thấy lĩnh vực trí tuệ nhân tạo mở ra một kỉ nguyên mới trong việc giải phóng sức lao động, khi mà máy móc có thể làm được nhiều hơn, thậm chí vượt trội hơn trong một số lĩnh vực so với con người. Thêm nữa, đây cũng là một cơ hội để em khám phá và có thể đi sâu hơn vào lĩnh vực này, là cơ hội để học hỏi và làm việc. 3.3.3. Kết luận Cuối cùng em xin cảm ơn thầy Lê Tân đã tạo điều kiện để em được tìm hiểu và hoàn thành đồ án. Cảm ơn các thầy cô đã tận t nh giúp đỡ em trong các năm học tại trường, kết quả lớn nhất vẫn là những kiến thức thầy cô đã dạy trong gần 4 năm học. SVTH: Lê Hữu Hùng – Lớp CCLT17A 20