Tài liệu Xây dựng trò chơi cờ tướng

ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA KHOA HỌC - KỸ THUẬT MÁY TÍNH LUẬN VĂN TỐT NGHIỆP ĐẠI HỌC XÂY DỰNG TRÒ CHƠI CỜ TƯỚNG Ngành: Khoa học Máy tính GVHD: Ths. Vương Bá Thịnh GVPB: Ths. Trần Giang Sơn —o0o— SVTH: Chung Minh Đệ - 1711020 TP. HỒ CHÍ MINH, THÁNG 7/2021 ĐẠI HỌC QUỐC GIA TP.HCM ---------TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA:KH & KT Máy tính_____ BỘ MÔN: KHMT____________ CỘNG HÒA Xà HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự do - Hạnh phúc NHIỆM VỤ LUẬN ÁN TỐT NGHIỆP HỌ VÀ TÊN: Chung Minh Đệ_________________________MSSV: 1711020________ NGÀNH: Khoa học máy tính_____________________LỚP: _______________________ 1. Đầu đề luận án: Game Cờ Tướng 2. Nhiệm vụ (yêu cầu về nội dung và số liệu ban đầu): - Tìm hiểu về cờ Tướng - Tìm hiểu về các giải thuật AI truyền thống - Tìm hiểu về Unity và Công nghệ AR - Thiết kế game phù hợp - Hiện thực sản phẩm có đánh giá 3. Ngày giao nhiệm vụ luận án: 01/02/2021 4. Ngày hoàn thành nhiệm vụ: 30/07/2021 5. Họ tên giảng viên hướng dẫn: Phần hướng dẫn: 1) Vương Bá Thịnh Nội dung và yêu cầu LVTN đã được thông qua Bộ môn. Ngày ........ tháng ......... năm .......... CHỦ NHIỆM BỘ MÔN GIẢNG VIÊN HƯỚNG DẪN CHÍNH (Ký và ghi rõ họ tên) (Ký và ghi rõ họ tên) PGS.TS. Huỳnh Tường Nguyên PHẦN DÀNH CHO KHOA, BỘ MÔN: Người duyệt (chấm sơ bộ):_________________________ Đơn vị:_________________________________________ Ngày bảo vệ:____________________________________ Điểm tổng kết:___________________________________ Nơi lưu trữ luận án:_______________________________ Vương Bá Thịnh 75ѬӠ1*ĈҤ,+Ӑ&%È&+.+2$ KHOA KH & KT MÁY TÍNH &Ӝ1*+Ñ$;­+Ӝ,&+Ӫ1*+Ƭ$9,ӊ71$0 ĈӝFOұS- 7ӵGR- +ҥQKSK~F ---------------------------Ngày 10 tháng 08 QăP 2021 3+,ӂ8&+Ҩ0%Ҧ29ӊ/971 'jQKFKRQJ˱ͥLK˱ͣQJG̳Q) +ӑYjWrQ69 Chung 0LQKĈӋ(MSSV: 1711020) Ngành (chuyên ngành): .KRDKӑFPi\WtQK ĈӅWjL *DPH&ӡ7ѭӟQJ +ӑWrQQJѭӡLKѭӟQJGүQ: 9ѭѫQJ%i7KӏQK 7әQJTXiWYӅEҧQWKX\ӃWPLQK 6ӕWUDQJ 6ӕFKѭѫQJ 6ӕEҧQJVӕOLӋX 6ӕKuQKYӁ 6ӕWjLOLӋXWKDPNKҧR 3KҫQPӅPWtQKWRiQ +LӋQYұWVҧQSKҭP 7әQJTXiWYӅFiFEҧQYӁ - 6ӕEҧQYӁ %ҧQ$ %ҧQ$ .KәNKiF - 6ӕEҧQYӁYӁWD\ 6ӕEҧQYӁWUrQPi\WtQK 1KӳQJѭXÿLӇPFKtQKFӫD/971 - 6LQKYLrQÿmWuPKLӇXYӅ&ӡ7ѭӟQJ - 7uPKLӇXFiFJLҧLWKXұW0LQLPD[KӑFPi\KӑFWăQJFѭӡQJ - Tìm KLӇXYӅ8QLW\F{QJQJKӋ$5 - 7KLӃWNӃTXkQFӡ' - Phân tích, WKLӃWNӃKӋWKӕQJ - 6ҧQSKҭPFyWKrPWUҧLQJKLӋPFKѫL$5 1KӳQJWKLӃXVyWFKtQKFӫD/971 - +jPOѭӧQJJLiFKѭDWӕW - *DPHFKѭDKҩSGүQ ĈӅQJKӏĈѭӧFEҧRYӋ† %әVXQJWKrPÿӇEҧRYӋ† 9. 0 FkXKӓL69SKҧLWUҧOӡLWUѭӟF+ӝLÿӗQJ ĈiQKJLiFKXQJEҵQJFKӳJLӓLNKi7% KhôQJÿѭӧFEҧRYӋ† ĈLӇP8.0 /10 .êWrQJKLU}KӑWrQ 9ѭѫQJ%i7KӏQK TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA KH & KT MÁY TÍNH CỘNG HÒA Xà HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự do - Hạnh phúc ---------------------------Ngày 11 tháng 08 năm 2021 PHIẾU CHẤM BẢO VỆ LVTN (Dành cho người phản biện) 1. Họ và tên SV: CHUNG MINH ĐỆ MSSV: 1711020 Ngành (chuyên ngành): 2. Đề tài: XÂY DỰNG TRÒ CHƠI CỜ TƯỚNG 3. Họ tên người phản biện: TRẦN GIANG SƠN 4. Tổng quát về bản thuyết minh: Số trang: 66 Số chương: 5 Số bảng số liệu: 13 Số hình vẽ: 29 Số tài liệu tham khảo: 15 Phần mềm tính toán: Hiện vật (sản phẩm) 5. Tổng quát về các bản vẽ: - Số bản vẽ: Bản A1: Bản A2: Khổ khác: - Số bản vẽ vẽ tay Số bản vẽ trên máy tính: 6. Những ưu điểm chính của LVTN: - Sinh viên đã tìm hiểu những kiến thức cơ sở để thực hiện luận văn như giải thuật MinMax, giải thuật Alpha-Beta. - Sinh viên đã tìm hiểu và sử dụng môi trường lập trình Unity để hiện thực chương trình. - Viết được chương trình cho phép người chơi cờ với máy trên điện thoại thông minh. 7. Những thiếu sót chính của LVTN: - Chương trình còn đơn giản, nước đi của máy tính không hiệu quả. Cần bổ sung thêm một số giải thuật và giải pháp để tăng độ thông minh cho chương trình. - Cần phải chỉnh sửa thêm hàm lượng giá. - Việc đưa nội dung thực tế tăng cường (AR) vào trò chơi là không cần thiết. 8. Đề nghị: Được bảo vệ  Bổ sung thêm để bảo vệ  Không được bảo vệ  9. 3 câu hỏi SV phải trả lời trước Hội đồng: - Em hãy đề xuất phương án để làm tăng độ thông minh cho chương trình. 10. Đánh giá chung (bằng chữ: giỏi, khá, TB): Điểm : 6 /10 Ký tên (ghi rõ họ tên) Trần Giang Sơn Lời cam đoan Các tài liệu, trang web mà chúng tôi tham khảo trong quá trình thực hiện đề cương luận văn đều được trích dẫn rõ ràng nguồn gốc được trình bày ở mục tài liệu tham khảo. Chúng tôi xin cam đoan rằng ngoài những trích dẫn tham khảo, toàn bộ nội dung báo cáo đều do chúng tôi tự soạn thảo từ những kết quả nghiên cứu do chúng tôi thực hiện và các kết quả của chúng tôi nghiên cứu dưới sự hướng dẫn của thầy Vương Bá Thịnh, không sao chép từ bất kỳ nguồn tài liệu nào khác. Tôi sẽ hoàn toàn chịu xử lý theo quy định nếu có bất cứ sai phạm nào với lời cam kết. Sinh viên thực hiện đề tài Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính Lời cảm ơn Để hoàn thành đề cương luận văn, tôi đã nhận được sự hướng dẫn, giúp đỡ quý báu của các thầy cô, các anh chị và các bạn xung quanh. Trước hết tôi xin trân trọng cảm ơn Ban giám hiệu, Phòng Đào tạo, các Bộ môn và các thầy cô giáo đã tận tình truyền đạt kiến thức và tạo điều kiện thuận lợi cho tôi trong suốt quá trình học tập và nghiên cứu tại trường. Với vốn kiến thức được tiếp thu trong quá trình học tập không chỉ là nền tảng cho quá trình viết luận văn mà còn là hành trang quý báu sẽ đi suốt cuộc đời và hỗ trợ rất nhiều cho công việc của tôi. Tôi xin gửi lời biết ơn sâu sắc và lời cảm ơn chân thành đến Ths Vương Bá Thịnh đã dành rất nhiều thời gian và tâm huyết hướng dẫn nghiên cứu và hoàn thành đề cương luận văn tốt nghiệp. Tôi xin gửi lời cảm ơn đến thầy cô của khoa Khoa học và Kỹ thuật Máy tính, đặc biệt các thầy cô đã tham gia giảng dạy các môn trong chương trình mà tôi theo học. Các thầy cô là người trang bị, trau dồi thêm cho tôi kiến thức nền tảng, kỹ năng nghiên cứu, kỹ năng tìm hiểu và giải quyết vấn đề trong học tập cũng như trong cuộc sống. Tôi xin gửi lời cảm ơn sâu sắc đến toàn thể gia đình, bạn bè, những người đã luôn bên cạnh tôi, tạo động lực để tôi phấn đấu trong học tập và trong cuộc sống. Cuối cùng, do những kiến thức còn hạn chế nên tôi khó tránh khỏi những sai sót nhỏ trong đề cương luận văn. Tôi rất hi vọng đó là những lỗi sai nhỏ và kính mong những đóng góp ý kiến từ các quý thầy cô. Sinh viên thực hiện đề tài Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 2/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính Tóm tắt đề tài Trò chơi điện thoại di động đang có bước phát triển vượt bậc và trở thành ngành công nghiệp giải trí lớn nhất thế giới. Bên cạnh đó sự phát triển của điện thoại di động ngày càng vượt trội hơn so với trước. Điển hình là sự xuất hiện của nhiều nhãn điện thoại di động mới trên thị trường. Với sự phát triển đó, hàng loạt trò chơi khác nhau với đa dạng các thể loại được ra đời. Trong đó có những sản phẩm có sự kết hợp câu chuyện thực tế và trò chơi giúp cho người chơi có cảm giác như đang xem một bộ phim và trải nghiệm bản thân là một nhân vật trong phim đó. Ngoài ra còn có những sản phẩm chuyển thể các trò chơi trong thực tế thành những trò chơi trên điện thoại di động giúp dễ dàng tham gia, sử dụng bất cứ nơi đâu và dễ dàng thao tác. Hiện nay, những trò chơi trực tuyến ngày càng phổ biến và chiếm được số lượng lớn người tham gia. Nhưng không vì vậy mà các trò chơi cổ điển ngày càng mất đi, số lượng tải và truy cập những trò chơi này vẫn còn rất nhiều. Tuy nhiên, với sự phát triển nhanh chóng của trò chơi trên điện thoại di động một số nhà phát triển đã có những chiến lược và thay đổi cũng như sáng tạo những trò chơi mới dựa trên những trò chơi cổ điển này. Nhầm mang lại những trải nghiệm mới hơn cho người chơi và thu hút thêm được số lượng người chơi. Sự kết hợp giữa trò chơi và trí tuệ nhân tạo đã và đang được phổ biến rộng rãi trên thị trường trò chơi điện tử ngày nay. Sự kết hợp này mang lại được những trải nghiệm mới mẻ hơn như trải nghiệm độ khó đa dạng, đưa ra những gợi ý bổ ích và nhu cầu của con người về những trò chơi chiến thuật, thông minh ngày càng cao. Nắm bắt được những nhu cầu đó, tôi đã thực hiện xây dựng trò chơi cờ tướng trên điện thoại di động. Trò chơi này mang lại cho người dùng cảm giác mới mẻ hơn về cờ tướng vì nó được xây dựng với sự kết hợp giữa cờ tướng cổ điển, trí tuệ nhân tạo và công nghệ thực tế tăng cường. Để hiện thực được đề tài này, tôi đã thực hiện những công việc sau: • Tìm hiểu về trò chơi cờ tướng cơ bản bao gồm lịch sử hình thành và phát triển, các quân cờ, bàn cờ và luật chơi của cờ tướng. • Tìm hiểu về giải thuật trí tuệ nhân tạo có thể áp dụng vào trò chơi cờ tướng. • Tìm hiểu các kiến thức nền tảng những công nghệ cần thiết để xây dựng trò chơi kết hợp với thực tế tăng cường. • Thực hiện từng bước các công việc theo sự chỉ dẫn của giáo viên hướng dẫn. Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 3/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính • Hoàn thành ứng dụng, kiểm tra lại ứng dụng và cải thiện những thiếu sót. • Tự đánh giá sản phẩm đã thực hiện về ưu điểm và nhược điểm, hướng phát triển trong tương lai và viết báo cáo. Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 4/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính Mục lục Lời cam đoan 1 Lời cảm ơn 2 Tóm tắt đề tài 3 Danh sách hình vẽ 7 Danh sách bảng 9 Thuật ngữ và từ viết tắt 10 1 Giới thiệu đề tài 11 1.1 Tổng quan đề tài . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 Mục tiêu và phạm vi của đề tài . . . . . . . . . . . . . . . . . . . . 11 1.3 Ý nghĩa thực tiễn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Cấu trúc luận văn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 Cơ sở lý thuyết 2.1 14 Giới thiệu cờ tướng . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.1 Lịch sử cờ tướng . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.2 Quân cờ và luật di chuyển của các quân cờ . . . . . . . . . . 14 2.2 Cây tìm kiếm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 Giải thuật tìm kiếm Minimax . . . . . . . . . . . . . . . . . . . . . 17 2.4 Giải thuật cắt tỉa Alpha-Beta . . . . . . . . . . . . . . . . . . . . . 18 2.5 Hàm lượng giá . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.6 Chuỗi FEN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.7 Thực tế tăng cường . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.8 Công cụ sử dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 5/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính 2.9 Các công trình liên quan . . . . . . . . . . . . . . . . . . . . . . . . 26 2.9.1 Các hướng khai thác chủ yếu . . . . . . . . . . . . . . . . . 26 2.9.2 Phần mềm cờ tướng Intella . . . . . . . . . . . . . . . . . . 26 2.9.3 Phần mềm cờ tướng CCBridge . . . . . . . . . . . . . . . . . 27 2.9.4 Alpha Zero . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3 Phân tích và thiết kế hệ thống 29 3.1 Phân tích độ phức tạp của cờ tướng . . . . . . . . . . . . . . . . . . 29 3.2 Hàm lượng giá 3.3 Giải thuật tìm kiếm Minimax . . . . . . . . . . . . . . . . . . . . . 34 3.4 Thiết kế hệ thống . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Đặc tả Usecase . . . . . . . . . . . . . . . . . . . . . . . . . 36 4 Hiện thực và kết quả 4.1 4.2 4.3 41 Trò chơi cờ tướng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.1.1 Xây dựng đồ họa và luật chơi . . . . . . . . . . . . . . . . . 41 4.1.2 Hiện thực . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.1.3 Khó khăn và giải pháp trong quá trình thực hiện . . . . . . 55 Kết hợp cờ tướng và thực tế tăng cường . . . . . . . . . . . . . . . 56 4.2.1 Tìm hiểu về một số công trình liên quan . . . . . . . . . . . 56 4.2.2 Hiện thực . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.2.3 Khó khăn và giải pháp trong quá trình hiện thực . . . . . . 62 Quản lý mã nguồn . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5 Tổng kết và kế hoạch phát triển 64 5.1 Kết quả đạt được . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.2 Hạn chế . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.3 Kế hoạch phát triển . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Tài liệu tham khảo Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 66 Trang 6/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính Danh sách hình vẽ 2.1 Cây tìm kiếm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Trạng thái bàn cờ bắt đầu trận . . . . . . . . . . . . . . . . . . . . 21 2.3 Sản phẩm của thực tế tăng cường . . . . . . . . . . . . . . . . . . . 23 2.4 Hình ảnh logo Unity . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.5 Hình ảnh logo Blender . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.6 Giao diện phần mềm Intella . . . . . . . . . . . . . . . . . . . . . . 27 2.7 Giao diện phần mềm CCbridge . . . . . . . . . . . . . . . . . . . . 28 3.1 Trường hợp AI xem quân Tướng như quân cờ thường . . . . . . . . 34 3.2 Usecase trò chơi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3 Class diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.1 Hình ảnh một số quân cờ . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2 Hình ảnh bàn cờ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3 Hình ảnh di chuyển quân cờ . . . . . . . . . . . . . . . . . . . . . . 43 4.4 Tạo quân cờ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.5 Hình ảnh quân cờ trong Blender . . . . . . . . . . . . . . . . . . . . 46 4.6 Main Camera trong Unity . . . . . . . . . . . . . . . . . . . . . . . 47 4.7 Board trong Unity . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.8 Directional Light trong Unity . . . . . . . . . . . . . . . . . . . . . 49 4.9 GameManager Light trong Unity . . . . . . . . . . . . . . . . . . . 50 4.10 Materials trong Unity . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.11 Prefab trong Unity . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.12 Script trong Unity . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.13 Config trong Unity . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.14 Thiết lập vị trí xe đen . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.15 Thiết lặp tên ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.16 Thiết lặp lõi AR trên Android . . . . . . . . . . . . . . . . . . . . . 59 4.17 Một số thiết lặp trên ứng dụng . . . . . . . . . . . . . . . . . . . . 59 Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 7/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính 4.18 Cài đặc các Package AR . . . . . . . . . . . . . . . . . . . . . . . . 60 4.19 Các thành phần trong Project . . . . . . . . . . . . . . . . . . . . . 62 Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 8/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính Danh sách bảng 2.1 Ký hiệu và số lượng quân cờ mỗi bên . . . . . . . . . . . . . . . . . 15 2.2 Ký hiệu quân cờ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1 Bảng số lượng nút phải xét trong thuật toán Minimax . . . . . . . . 29 3.2 Bảng số lượng nút phải xét trong thuật toán Minimax kết hợp với Alpha-Beta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3 Giá trị mỗi quân cờ . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4 Giá trị vị trí quân Xe . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.5 Giá trị vị trí quân Mã . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.6 Giá trị vị trí quân Pháo . . . . . . . . . . . . . . . . . . . . . . . . 33 3.7 Giá trị vị trí quân Tốt . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.8 Sử dụng camera AR . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.9 Di chuyển quân cờ . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.10 Kết quả trận đấu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.1 Số lượng quân cờ mỗi bên . . . . . . . . . . . . . . . . . . . . . . . 53 Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 9/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính Thuật ngữ & từ viết tắt AI - Artificial Intelligence AR - Augmented Reality VR - Virtual Reality FEN - Forsyth–Edwards Notation Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 10/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính 1 1.1 Giới thiệu đề tài Tổng quan đề tài Trong cuộc sống hiện nay nhu cầu giải trí của con người rất đa dạng sau những giờ học tập, lao động căng thẳng để lấy lại sức lực và tinh thần. Xã hội càng phát triển với nhịp sống của công nghiệp thì nhu cầu giải trí càng lớn và càng phong phú. Để đáp ứng được nhu cầu đó đòi hỏi tạo ra nhiều sân chơi phù hợp cho mọi lứa tuổi và mọi đối tượng. Công nghệ giải trí hiện nay khá đa dạng và phong phú: tham gia sinh hoạt văn hóa, thể thao, các sân chơi truyền hình, trò chơi điện tử... Tồn tại một trong số đó là nhu cầu giải trí về chơi cờ. Nó đã xuất hiện từ rất lâu và vẫn được nhiều người ưa thích cho đến hiện nay. Trên địa bàn thành phố Hồ Chí Minh có rất nhiều địa điểm chơi cờ khá nổi tiếng: Cafe cờ tướng Phan Xích Long, câu lạc bộ cờ tướng Nguyễn Trung Trực, Cafe Hội quán cờ... thu hút rất nhiều người đến chơi. Chúng ta ít nhiều cũng đã chứng kiến những hình ảnh về những ván cờ căng thẳng giữa những người lớn tuổi hoặc trung niên. Khi đất nước ngày càng phát triển làm cho nhu cầu giải trí cũng ngày càng tăng lên. Điều này dẫn tới sự phát triển và độ đa dạng của loại hình giải trí cũng tăng lên. Tuy nhiên sức hút của các bộ môn thể thao trí tuệ như cờ tướng hay cờ vua vẫn còn tồn tại. Nhưng hình thức chơi cờ đã có sự tăng lên. Chúng ta thường bắt gặp những hình ảnh của hai người đang ngồi chơi cờ ở một số quán cafe. Bên cạnh đó, sự phát triển của công nghệ đã tạo ra những sản phẩm thông minh và tiện lợi góp phần mang Internet đến gần hơn với mọi người. Do đó việc chơi cờ cũng trở nên thuận tiện hơn, không cần phải di chuyển đến địa điểm nên việc chơi cờ trở nên thuận tiện hơn. Để đáp ứng được nhu cầu giải trí của con người đòi hỏi phải có những sản phẩm ngày càng tốt hơn mang đến những trải nghiệm mới cho người dùng. Tôi đã vận dụng những kiến thức đã học trong khoảng thời gian ở trường và tìm hiểu những công nghệ mới hiện nay để tạo ra sản phẩm nhầm mục đích có thể phục vụ cho nhu cầu giải trí của con người và trau dồi thêm hiểu biết cho bản thân. 1.2 Mục tiêu và phạm vi của đề tài Đề tài nghiên cứu hướng tới mục tiêu là nghiên cứu các phương pháp giải quyết bài toán về sử dụng trí tuệ nhân tạo trong trò chơi cờ tướng kết hợp với thực tế tăng cường. Đối với bài toán này, có nhiều phương pháp để giải quyết như phương pháp tìm kiếm Minimax, học có giám sát (Supervised Learning), học tăng cường (Reinforcement Learning)... Mỗi phương pháp giải quyết mang lại độ hiểu quả Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 11/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính khác nhau. Đề tài nghiên cứu tập trung vào phương pháp tìm kiếm Minimax và kết hợp với thực tế tăng cường nhầm tạo cho người dùng trải nghiệm mới hơn. Đó là việc sử dụng thực tế tăng cường để thể hiện bàn cờ vào trong thực tế qua điện thoại di động. Đề tài tập trung vào quá trình phát triển trò chơi trên nền tảng Unity và ngôn ngữ C#. Cùng với đó là sử dụng các giải thuật tìm kiếm Minimax và cắt tỉa Alpha-Beta để tạo ra đối thủ trí tuệ nhân tạo. Bên cạnh đó còn sử dụng thực tế tăng cường để có thể tăng thêm độ sinh động cho trò chơi. Sản phẩm hướng đến tay người chơi thông qua Google Play hoặc AppStore. Và đối đượng được nhắm đến là những người có nhu cầu trải nghiệm cờ tướng mới trên điện thoại hoặc có sở thích chơi cờ tưởng và đối với mọi lứa tuổi. • Hiện thực quân cờ và bàn cờ để có thể thêm vào Unity. • Xây dựng trò chơi cờ tướng trên nền tảng Unity. • Kết hợp trò chơi cờ tướng với các giải thuật trí tuệ nhân tạo là tìm kiếm Minimax và cắt tỉa Alpha-Beta. • Tìm hiểu về thực tế tăng cường và thực hiện các ví dụ về thực tế tăng cường. • Thực hiện kết hợp giữa cờ tướng đã xây dựng ở trên và thực tế tăng cường. 1.3 Ý nghĩa thực tiễn Việc xây dựng một sản phẩm trò chơi cờ tướng đã góp phần mang ý nghĩa về mặt thực tiễn cũng như ý nghĩa về mặt khoa học. Về mặt thực tiễn, nhầm góp phần giải quyết nhu cầu của con người mang lại những trải nghiệm mới mẽ hơn cho người dùng. Về mặt khoa học, góp phần vào công cuộc nghiên cứu về vấn đề hiện thực trò chơi kết hợp với thực tế tăng cường. 1.4 Cấu trúc luận văn Luận văn được tổ chức theo cấu trúc như sau: • Chương 1: Giới thiệu và tổng quan đề tài. • Chương 2: Trình bày về cơ sở lý thuyết. • Chương 3: Phân tích và thiết kế hệ thống. Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 12/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính • Chương 4: Hiện thực và kết quả • Chương 5: Tổng kết những kết quả đạt được, những hạn chế và rút kinh nghiệm. Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 13/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính 2 Cơ sở lý thuyết 2.1 2.1.1 Giới thiệu cờ tướng Lịch sử cờ tướng Hiện nay, cờ tướng phổ biến nhất tại một số nước như: Trung Quốc, Việt Nam, ĐàiLoan, Singapore và nằm cùng thể loại với cờ vua, shogi, janggi. Trò chơi mô phỏng cuộc chiến giữa hai quốc gia, với mục tiêu là bắt được Tướng đối phương hoặc bao vây quân Tướng. Đầu tiên, chúng ta sẽ nói lịch sử hình thành nên cờ tướng. Cờ Ấn Độ du nhập vào Trung Quốc và trở thành tiền thân cờ tướng cũng như cờ Shogi của xứ Nhật Bản và khi cờ Trung Quốc du nhập vào Triều Tiên thì trở thành cờ Janggi. Trong khi đó, cờ Ấn Độ du nhập sang Tây phương trở thành cờ vua. Và cuối cùng, người Trung Quốc chuyển thành cờ tướng vào thời kỳ nhà Tống. Nhà sử học người Đức Peter Banaschak đã chỉ ra rằng cờ tướng Baoying, không có "Pháo" trong "Xuanguailu" do đó chưa có Pháo của Niu Sengru, ngài tể tướng của nhà Đường, là nguồn gốc thực sự của cờ tướng hiện đại tức là thời Đường đã manh nha trò chơi cờ tướng hiện đại hoàn toàn xuất hiện bởi người Trung Hoa vào thời kỳ nhà Đường. Tiếp theo, chúng ta đề cập đến bàn cờ. Về bàn cờ, có dạng là hình chữ nhật do 9 đường dọc và 10 đường ngang cắt nhau vuông góc tại điểm 90 tạo thành. Ở giữa bàn cờ có một khoảng trống được gọi là sông,chia bàn cờ thành hai phần đối xứng bằng nhau. Mỗi bên có một cung Tướng hình vuông do 4 ô hợp thành tại các đường dọc 4, 5, 6 kể từ đường ngang cuối của mỗi bên, trong 4 ô này có vẽ hai đường chéo. Mỗi ván cờ lúc bắt đầu phải có 32 quân cờ chia đều cho mỗi bên gồm 16 quân trắng và 16 quân đen, gồm 7 loại quân.Tuy tên quân cờ của mỗi bên có thể viết khác nhau (ký hiệu theo chữ Hán) nhưng giá trị và cách đi quân của chúng giống nhau hoàn toàn. 2.1.2 Quân cờ và luật di chuyển của các quân cờ Trong bàn cờ, mỗi quân cờ có một cách di chuyển khác nhau, chúng được di chuyển theo luật như sau: • Tướng: Đi từng ô một, đi ngang hoặc đi dọc. Tướng luôn trong phạm vi "cung" và không được ra ngoài. "Cung" tức là hình vuông 3x3 được đánh dấu bởi lằng chéo hình chữ X. Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 14/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính • Sĩ: Đi chéo 1 ô mỗi nước và phải luôn trong cung. Như vậy quân Sĩ có 5 vị trí hợp lệ và có chức năng bảo vệ tướng. • Tượng: Đi chéo 2 ô mỗi nước và không được vượt qua sông. Như vậy, trên bàn cờ, quân Tượng có 7 vị trí có thể đi được. • Xe: Đi ngang hoặc dọc trên bàn cờ miễn là đừng bị quân khác cản đường từ điểm đi đến điểm đến. • Pháo: Đi ngang hoặc dọc giống như quân Xe. Điểm khác biệt muốn ăn quân phải nhảy qua đúng 1 quân nào đó. Khi không ăn, tất cả những điểm từ điểm đi đến điểm đến không có quân nào cản. • Mã: Đi ngang 2 ô và dọc 1 ô (hay dọc 2 ô và ngang 1 ô). Nếu có quân cờ nào đó nằm ngay bên cạnh thì Mã bị cản, không được đi đường đó. • Tốt: Đi 1 ô mỗi nước. Nếu chưa qua sông, nó chỉ được tiến. Nếu qua sông thì được đi ngang hay tiến, không được lùi. Quân cờ Tướng Ký hiệu Số lượng 1 Sĩ 2 Tượng 2 Xe 2 Pháo 2 Mã 2 Tốt 5 Bảng 2.1: Ký hiệu và số lượng quân cờ mỗi bên Ngoài ra còn tồn tại những luật chơi khác trong trò chơi cờ tướng: • Lộ mặt tướng: Hai quân Tướng không được đối mặt nhau trên cùng một cột. Luôn luôn phải có một quân nào đó nằm giữa để che mặt. Nước đi để hai tướng đối mặt nhau là không hợp lệ. • An toàn của Tướng: Sau một nước đi, Tướng của bên đi không được để đối phương ăn ngay trong nước kế tiếp. Những nước để Tướng không an toàn là không hợp lệ. Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 15/66 Trường Đại Học Bách Khoa Tp.Hồ Chí Minh Khoa Khoa Học và Kỹ Thuật Máy Tính Ván đấu sẽ được kết thúc nếu xảy ra 1 trong những trường hợp sau đây: • Chiếu bí: Nếu một bên chiếu tướng, và đối thủ không có khả năng đỡ, bên chiếu tướng thắng. • Hết nước đi: Nếu bên tới phiên không có nước hợp để đi, bên đó thua. • Sau 120 nước đi của cả 2 bên, mà không có quân cờ nào bị ăn thì hòa nhau. • Cấm chiếu tướng liên tục 10 lần. • Ăn quân: Khi quân di chuyển đến 1 vị trí được giữ bởi quân đối phương, quân đối phương bị ăn và bị lấy ra khỏi bàn cờ. • Chống tướng: Hai quân Tướng trên bàn cờ không được nằm cùng nhau trên một cột dọc mà không có quân cản nào ở giữa. Nước đi để 2 quân Tướng trong vị trí chống tướng là không hợp lệ. 2.2 Cây tìm kiếm Trong lĩnh vực khoa học máy tính, cây tìm kiếm là cây cấu trúc dữ liệu dạng cây được sử dụng để định vị các khóa cụ thể từ bên trong một tập hợp. Để cây hoạt động như cây tìm kiếm, khóa cho mỗi nút phải lớn hơn bất kỳ khóa nào trong cây con bên trái và nhỏ hơn bất kỳ khóa nào trong cây con bên phải. Ưu điểm của cây tìm kiếm là hiệu quả về thời gian tìm kiếm của chúng do cây được cân bằng hợp lý, nghĩa là lá ở hai đầu có độ sâu tương đương. Các cấu trúc cây tìm kiếm khác nhau tồn tại, một số trong đó chép chèn và xóa các phần tử hiệu quả, mà các hoạt động đó duy trì sự cân bằng của cây. Cây tìm kiếm được sử dụng trong trò chơi cờ tướng cho việc lưu trữ trạng thái bàn cờ. Mỗi một nút trong cây là một trạng thái bàn cờ và các cạnh của nó tương ứng với nước đi. Số lượng các trạng thái có thể sinh ra từ một trạng thái là số con của nút đó trong cây. Khi bắt đầu vào là trạng thái bàn cờ, trò chơi sẽ tính toán các nước đi hợp lệ. Kết hợp với với trạng thái bàn cờ và nước đi hợp lệ sẽ tạo ra được trạng thái tiếp theo cho bàn cờ. Thực hiện tương tự như vậy ta có thể xây dựng được cây tìm kiếm từ đầu vào là trạng thái bàn cờ. Luận văn tốt nghiệp - HK202 - Năm học 2020 - 2021 Trang 16/66