Luận văn thạc sĩ conception et développement dun moteur dintelligence artificielle pour un jeu déchecs multiplateformes luận văn ths công nghệ thông tin

Luận văn thạc sĩ về thiết kế và phát triển mô hình trí tuệ nhân tạo cho trò chơi cờ vua đa nền tảng trong lĩnh vực công nghệ thông tin

• Tác giả: Hoang Duc Viet
• Người hướng dẫn: Ho Tuong Vinh
• Trường học: L’institut De La Francophonie Pour L'informatique
• Chuyên ngành: Informatique
• Đề tài: Conception Et Développement D’un Moteur D’intelligence Artificielle Pour Un Jeu D’échecs Multiplateformes
• Loại tài liệu: Mémoire de fin d’études
• Năm xuất bản: 2014
• Địa điểm: Hanoi

Mục lục chi tiết

• 1. Chapitre 1: État de l’art : Épreuves générales de la programmation de jeux d’échecs
• 1.1. Représentation des données
• 1.2. Gestion des mouvements
• 1.2.1. Génération des mouvements
• 1.2.2. Evaluation de mouvements
• 1.2.3. Recherche de mouvements
• 1.3. Algorithmes de recherche (Minimax, Alpha-Beta)
• 1.3.1. Algorithme Minimax
• 1.3.2. Algorithme Elagage Alpha-Beta (Alpha-Beta pruning)
• 2. Chapitre 2: Épreuves du projet
• 2.1. Description générale du jeu
• 2.2. Spécifications d’exigences fonctionnelles
• 2.3. Spécifications d’exigences non-fonctionnelles
• 2.4. Capacité de réfléchir du noyau d’Intelligence artificielle
• 2.5. Difficultés de calcul
• 3. Chapitre 3: Solutions proposées
• 3.1. Arbres de positions
• 3.2. Stratégies de décisions
• 4. Chapitre 4: Réalisation et résultats
• 4.1. Ingénierie de développement
• 4.1.1. Méthode de développement
• 4.1.2. Langage de programmation et plateformes
• 4.1.3. Gestion de code et de changement
• 4.2. Conception et Développement
• 4.2.1. Représentation des données
• 4.2.2. Implémentation de règles et de contraintes
• 4.2.3. Implémentation de la recherche de mouvement

Tóm tắt

I. Cách giới thiệu tổng quan phát triển AI cho trò chơi cờ đa nền tảng

Phát triển AI cho trò chơi cờ đa nền tảng là lĩnh vực kết hợp giữa trí tuệ nhân tạo trong trò chơi cờ và công nghệ đa nền tảng nhằm tạo ra trải nghiệm chơi game thông minh, linh hoạt trên nhiều thiết bị khác nhau. Việc phát triển này không chỉ giúp nâng cao khả năng chơi cờ của máy mà còn mở rộng phạm vi tiếp cận người chơi trên các hệ điều hành như iOS, Android, Windows và Web. Trong bối cảnh công nghệ AI ngày càng phát triển, việc tích hợp thuật toán AI cho game cờ và áp dụng các mô hình học máy trong trò chơi cờ trở thành xu hướng tất yếu để tạo ra các sản phẩm game cờ thông minh, hấp dẫn và có tính cạnh tranh cao trên thị trường. Đồng thời, phát triển AI đa nền tảng giúp tối ưu hóa hiệu suất và trải nghiệm người chơi, đồng thời giảm thiểu chi phí phát triển và bảo trì phần mềm.

1.1. Tổng quan về trí tuệ nhân tạo trong trò chơi cờ và vai trò của AI đa nền tảng

Trí tuệ nhân tạo trong trò chơi cờ đóng vai trò quan trọng trong việc mô phỏng khả năng suy nghĩ, ra quyết định và phản ứng của máy như một đối thủ thực thụ. AI đa nền tảng cho phép phát triển một hệ thống AI có thể hoạt động hiệu quả trên nhiều thiết bị và hệ điều hành khác nhau, từ máy tính để bàn đến thiết bị di động. Việc này giúp mở rộng phạm vi người dùng và tăng tính linh hoạt trong trải nghiệm chơi cờ. Các công nghệ như mô hình AI cho cờ vua, cờ tướng và thuật toán như Minimax, Alpha-Beta pruning được áp dụng để tối ưu hóa khả năng suy nghĩ của AI.

1.2. Lịch sử và xu hướng phát triển AI chơi cờ thông minh đa nền tảng

Lịch sử phát triển AI chơi cờ bắt đầu từ các thuật toán cơ bản như Minimax và Alpha-Beta pruning, giúp máy tính có thể đánh giá và lựa chọn nước đi tối ưu. Với sự phát triển của công nghệ, AI đã được tích hợp các kỹ thuật học máy trong trò chơi cờ để nâng cao khả năng tự học và thích nghi. Xu hướng hiện nay tập trung vào phát triển AI đa nền tảng, cho phép game cờ chạy mượt mà trên nhiều thiết bị, đồng thời tích hợp các công nghệ mới như deep learning để cải thiện hiệu suất và trải nghiệm người chơi.

II. Hướng dẫn phân tích thách thức phát triển AI cho trò chơi cờ đa nền tảng

Phát triển AI cho trò chơi cờ đa nền tảng gặp nhiều thách thức kỹ thuật và thiết kế. Đầu tiên là vấn đề về hiệu suất tính toán khi AI phải xử lý lượng lớn nước đi có thể xảy ra trong không gian trò chơi rộng lớn. Ngoài ra, việc tối ưu hóa thuật toán để phù hợp với các thiết bị có cấu hình khác nhau như điện thoại, máy tính bảng hay PC cũng là một bài toán khó. Các giới hạn về bộ nhớ, thời gian phản hồi và khả năng xử lý song song cần được cân nhắc kỹ lưỡng. Thách thức tiếp theo là làm sao để tích hợp công nghệ AI trong game đa nền tảng một cách hiệu quả, đảm bảo tính nhất quán và đồng bộ giữa các phiên bản trên các nền tảng khác nhau. Cuối cùng, việc xây dựng một AI có khả năng phản ứng linh hoạt, tạo ra trải nghiệm người chơi tự nhiên và hấp dẫn cũng đòi hỏi sự kết hợp tinh tế giữa thuật toán và chiến thuật chơi cờ.

2.1. Thách thức về thuật toán AI và giới hạn tài nguyên trên thiết bị đa nền tảng

Thuật toán AI cho game cờ như Minimax hay Alpha-Beta pruning đòi hỏi nhiều tài nguyên tính toán để duyệt cây nước đi và đánh giá vị trí. Trên các thiết bị di động, giới hạn về CPU, RAM và pin khiến việc thực thi các thuật toán này trở nên khó khăn. Cần có các phương pháp tối ưu như cắt tỉa Alpha-Beta, giới hạn độ sâu tìm kiếm, hoặc áp dụng các mô hình đơn giản hơn để đảm bảo thời gian phản hồi dưới 10 giây, phù hợp với trải nghiệm người dùng.

2.2. Vấn đề đồng bộ và tương thích khi phát triển AI đa nền tảng

Phát triển AI đa nền tảng yêu cầu đảm bảo tính tương thích và đồng bộ giữa các hệ điều hành và thiết bị khác nhau. Mỗi nền tảng có đặc thù riêng về kiến trúc phần cứng, hệ điều hành và ngôn ngữ lập trình. Việc lựa chọn công nghệ phát triển như C++ với Cocos2d-x giúp giảm thiểu sự khác biệt này, nhưng vẫn cần xử lý các vấn đề về giao diện người dùng, hiệu suất và quản lý bộ nhớ sao cho AI hoạt động ổn định và nhất quán trên mọi nền tảng.

III. Phương pháp tối ưu phát triển AI chơi cờ thông minh đa nền tảng hiệu quả

Để phát triển AI chơi cờ thông minh trên đa nền tảng, cần áp dụng các phương pháp tối ưu thuật toán và kiến trúc phần mềm. Sử dụng thuật toán Alpha-Beta pruning giúp giảm đáng kể không gian tìm kiếm so với Minimax truyền thống, từ đó tiết kiệm thời gian và tài nguyên. Việc xây dựng mô hình dữ liệu hiệu quả như sử dụng bảng 2D mở rộng với sentinels giúp tránh lỗi truy cập bộ nhớ và tăng tốc độ xử lý. Ngoài ra, áp dụng các chiến thuật chơi cờ như tấn công và phòng thủ giúp AI có khả năng phản ứng linh hoạt và tự nhiên hơn. Việc lựa chọn ngôn ngữ lập trình C++ kết hợp với engine Cocos2d-x hỗ trợ phát triển đa nền tảng, giúp tái sử dụng mã nguồn và giảm chi phí phát triển.

3.1. Ứng dụng thuật toán Alpha Beta và mô hình AI cho cờ vua cờ tướng

Thuật toán Alpha-Beta pruning là kỹ thuật cắt tỉa cây tìm kiếm giúp loại bỏ các nhánh không cần thiết, giảm số lượng trạng thái cần đánh giá. Trong phát triển AI cho trò chơi cờ, thuật toán này giúp tăng tốc độ suy nghĩ của AI mà vẫn đảm bảo tìm ra nước đi tối ưu. Mô hình AI cho cờ vua, cờ tướng được xây dựng dựa trên cấu trúc cây vị trí (JingciNode) lưu trữ trạng thái bàn cờ, các quyền đặc biệt như PASS và BOUND, cùng với các cờ hiệu trạng thái như bóng bị kẹt hay lặp lại nước đi. Việc kết hợp thuật toán Alpha-Beta với mô hình dữ liệu này giúp AI có thể suy nghĩ sâu hơn trong thời gian giới hạn.

3.2. Phương pháp tích hợp công nghệ AI và học máy trong trò chơi cờ đa nền tảng

Ngoài thuật toán tìm kiếm, việc tích hợp các kỹ thuật học máy giúp AI cải thiện khả năng đánh giá vị trí và dự đoán nước đi của đối thủ. Các mô hình học sâu có thể được huấn luyện trên dữ liệu trận đấu để tạo ra các hàm đánh giá phức tạp hơn so với các hàm heuristic truyền thống. Khi phát triển đa nền tảng, cần thiết kế kiến trúc phần mềm tách biệt rõ ràng giữa lõi AI và giao diện người dùng, sử dụng các API chuẩn để dễ dàng tích hợp và bảo trì. Việc này cũng giúp tận dụng tối đa sức mạnh phần cứng của từng nền tảng mà không làm ảnh hưởng đến logic AI.

3.3. Bí quyết áp dụng chiến thuật tấn công và phòng thủ trong AI chơi cờ

Chiến thuật tấn công và phòng thủ được áp dụng để giảm không gian tìm kiếm và tăng tính thực tế cho AI. Khi AI ở thế tấn công, nó tập trung tính toán các nước đi của các quân cờ gần bóng và mục tiêu ghi bàn, giảm tải việc tính toán cho các quân cờ xa hơn. Ngược lại, khi phòng thủ, AI ưu tiên di chuyển các quân cờ gần bóng của đối thủ để ngăn chặn tấn công. Việc áp dụng các chiến thuật này giúp AI phản ứng nhanh hơn, giảm thời gian suy nghĩ và tạo ra các nước đi có tính chiến thuật cao, mang lại trải nghiệm chơi cờ thông minh và tự nhiên.

IV. Ứng dụng thực tiễn và kết quả nghiên cứu phát triển AI cho trò chơi cờ đa nền tảng

Dự án phát triển AI cho trò chơi cờ Jingci đã thành công trong việc xây dựng một hệ thống AI đa nền tảng với khả năng suy nghĩ và phản ứng như người chơi thực thụ. Ứng dụng được phát triển trên nền tảng Cocos2d-x với ngôn ngữ C++, cho phép triển khai trên iOS, Android và Windows/Linux mà không cần viết lại mã nguồn. Kết quả thử nghiệm cho thấy AI có thể suy nghĩ trong thời gian dưới 10 giây, đáp ứng yêu cầu về trải nghiệm người dùng. Việc áp dụng thuật toán Alpha-Beta pruning và các chiến thuật tấn công, phòng thủ giúp giảm đáng kể không gian tìm kiếm và tăng hiệu quả tính toán. Ngoài ra, các cải tiến về quản lý bộ nhớ và lựa chọn ngẫu nhiên trong các nước đi giúp tránh tình trạng lặp lại và giảm tiêu thụ tài nguyên. Sản phẩm đã được phát hành trên Google Play và App Store, nhận được phản hồi tích cực từ người dùng và khách hàng.

4.1. Kết quả thực nghiệm về hiệu suất và trải nghiệm người chơi AI đa nền tảng

Thử nghiệm trên nhiều thiết bị di động và máy tính để bàn cho thấy AI có thể xử lý các nước đi phức tạp trong thời gian hợp lý, dưới 10 giây cho mỗi lượt đi. Việc áp dụng thuật toán Alpha-Beta pruning giúp giảm số lượng trạng thái cần đánh giá, từ hàng trăm nghìn xuống còn vài nghìn, tiết kiệm tài nguyên và tăng tốc độ phản hồi. Trải nghiệm người chơi được cải thiện nhờ AI có khả năng phản ứng linh hoạt, áp dụng các chiến thuật tấn công và phòng thủ phù hợp với tình huống trên bàn cờ.

4.2. Ứng dụng công nghệ AI và phát triển phần mềm đa nền tảng trong dự án Jingci

Dự án Jingci sử dụng ngôn ngữ C++ và engine Cocos2d-x để phát triển phần mềm đa nền tảng, giúp giảm thiểu công sức chuyển đổi mã nguồn giữa các hệ điều hành. Việc quản lý mã nguồn bằng SVN, sử dụng TestFlight cho thử nghiệm beta và Google Drive để chia sẻ tài liệu giúp quy trình phát triển hiệu quả và chuyên nghiệp. Các kỹ thuật tối ưu bộ nhớ và xử lý đồ họa cũng được áp dụng để giảm kích thước ứng dụng và tăng hiệu suất trên thiết bị di động.

4.3. Đánh giá và phản hồi từ người dùng về AI chơi cờ thông minh

Phản hồi từ người dùng cho thấy AI trong trò chơi Jingci có khả năng tạo ra các nước đi hợp lý, thách thức người chơi và mang lại trải nghiệm thú vị. Người chơi đánh giá cao tính đa dạng trong chiến thuật của AI và khả năng thích nghi với các phong cách chơi khác nhau. Một số đề xuất cải tiến bao gồm mở rộng mức độ khó, thêm chế độ huấn luyện và đa ngôn ngữ, thể hiện tiềm năng phát triển tiếp theo của dự án.

V. Phương hướng tương lai và kết luận phát triển AI cho trò chơi cờ đa nền tảng

Phát triển AI cho trò chơi cờ đa nền tảng là một lĩnh vực đầy tiềm năng với nhiều cơ hội và thách thức. Trong tương lai, việc tích hợp sâu hơn các kỹ thuật học máy trong trò chơi cờ như deep learning và reinforcement learning sẽ giúp AI trở nên thông minh và linh hoạt hơn. Đồng thời, mở rộng khả năng đa nền tảng sang các thiết bị mới như VR/AR sẽ tạo ra trải nghiệm chơi game đột phá. Việc cải tiến thuật toán, tối ưu hóa hiệu suất và nâng cao trải nghiệm người dùng sẽ tiếp tục là trọng tâm. Kết luận, dự án phát triển AI cho trò chơi cờ đa nền tảng không chỉ nâng cao chất lượng game mà còn góp phần thúc đẩy sự phát triển của công nghệ AI trong lĩnh vực giải trí số.

5.1. Xu hướng phát triển AI chơi cờ đa nền tảng với học máy và công nghệ mới

Xu hướng phát triển AI trong trò chơi cờ đang chuyển dịch từ các thuật toán tìm kiếm truyền thống sang các mô hình học sâu và học tăng cường, giúp AI tự học và cải thiện qua thời gian. Việc áp dụng các công nghệ mới như mạng nơ-ron sâu, học tăng cường sâu sẽ giúp AI có khả năng dự đoán và phản ứng chính xác hơn. Đồng thời, phát triển đa nền tảng sẽ mở rộng sang các thiết bị thực tế ảo, tăng cường trải nghiệm người chơi.

5.2. Kết luận về vai trò và tiềm năng của AI trong trò chơi cờ đa nền tảng

AI đóng vai trò trung tâm trong việc nâng cao trải nghiệm chơi cờ, giúp trò chơi trở nên hấp dẫn và thử thách hơn. Phát triển AI đa nền tảng không chỉ giúp tiếp cận nhiều người chơi hơn mà còn tối ưu hóa hiệu suất và chi phí phát triển. Tiềm năng ứng dụng AI trong game cờ còn rất lớn, đặc biệt khi kết hợp với các công nghệ mới và chiến thuật thông minh, mở ra nhiều hướng phát triển sáng tạo trong ngành công nghiệp game.

Nội dung chính

Tổng quan nghiên cứu

Trong những năm gần đây, sự phát triển nhanh chóng của công nghệ phần cứng và thuật toán đã thúc đẩy sự bùng nổ trong lĩnh vực phát triển trò chơi video, đặc biệt là các trò chơi chiến thuật như cờ vua và mô phỏng thể thao. Một trong những thách thức nổi bật của các nhà phát triển là thiết kế các hệ thống trí tuệ nhân tạo (AI) có khả năng suy luận và đưa ra quyết định chiến thuật hiệu quả trong không gian trạng thái đồ sộ. Luận văn tập trung vào việc nghiên cứu và phát triển một động cơ AI cho trò chơi Jingci, một trò chơi chiến thuật mô phỏng bóng đá trên một bàn cờ 9x9, với mục tiêu tối ưu hiệu quả tính toán trên thiết bị di động đa nền tảng (iOS và Android).

Mục tiêu chính của nghiên cứu là thiết kế và triển khai một động cơ AI sử dụng thuật toán cắt tỉa Alpha-Beta nhằm giảm thiểu không gian tìm kiếm các nước đi, đồng thời tích hợp các chiến thuật bóng đá thực tiễn để nâng cao khả năng phản ứng và tư duy của AI. Phạm vi nghiên cứu tập trung vào các giai đoạn phát triển tại công ty Newwave (Việt Nam) trong thời gian sáu tháng, với mục tiêu phát triển lõi AI và triển khai trên nền tảng Cocos2d-x cho đa nền tảng di động.

Việc phát triển động cơ AI này đóng vai trò quan trọng trong việc phổ biến và nâng cao trải nghiệm chơi Jingci, đồng thời góp phần mở rộng kiến thức về lập trình game chiến thuật kết hợp AI hiệu suất cao trong điều kiện tài nguyên hạn chế. Kết quả của luận văn được đánh giá qua thời gian phản hồi của AI không quá 10 giây, khả năng đa nền tảng linh hoạt và độ chính xác trong lựa chọn nước đi chiến thuật.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai lý thuyết cơ bản trong lập trình trí tuệ nhân tạo cho game chiến thuật:

1. Thuật toán Minimax – Mô hình này được sử dụng để mô phỏng quá trình lựa chọn nước đi tối ưu trong trò chơi hai người có tổng bằng không (zero-sum game). Minimax duyệt toàn bộ cây tìm kiếm các trạng thái tương lai, tìm mức tối đa hóa lợi ích của người chơi AI trong khi đối thủ chơi một cách tối ưu.

2. Thuật toán cắt tỉa Alpha-Beta (Alpha-Beta Pruning) – Là một cải tiến của Minimax nhằm loại bỏ các nhánh không cần thiết trong cây tìm kiếm khi giá trị của chúng không thể ảnh hưởng đến quyết định cuối cùng. Alpha-Beta sử dụng hai thông số alpha (giá trị tốt nhất hiện tại của nút MAX) và beta (giá trị tốt nhất hiện tại của nút MIN) để cắt tỉa hiệu quả, giúp giảm thời gian tính toán mà không làm giảm độ chính xác.

Các khái niệm chính bao gồm:

• Không gian trạng thái và cây vị trí (game tree): Mỗi nút biểu diễn trạng thái hiện tại của bản đồ game (bàn chơi 9x9) với vị trí của các quân cờ, thông tin lượt chơi, quyền sử dụng các quyền ưu tiên (PASS và BOUND).
• Hàm đánh giá (heuristic function): Phân tích các yếu tố như khoảng cách giữa bóng và cầu môn, khoảng cách giữa bóng và người chơi, quyền sử dụng đặc biệt, nhằm xác định ưu thế tương đối của một vị trí trong trạng thái.
• Chiến thuật tấn công và phòng thủ: Tích hợp kiến thức bóng đá thực tiễn qua các chiến thuật quyết định việc lựa chọn tập hợp quân cờ ưu tiên di chuyển nhằm giảm độ phức tạp tính toán và nâng cao hiệu quả AI.

Phương pháp nghiên cứu

Luận văn triển khai nghiên cứu và phát triển động cơ AI theo các phương pháp sau:

• Nguồn dữ liệu và công cụ: Dữ liệu về luật chơi Jingci, cùng mô hình hành vi bóng đá mô phỏng được thu thập và phân tích. Mã nguồn được phát triển trên ngôn ngữ C++ và nền tảng Cocos2d-x, hỗ trợ đa hệ điều hành (Windows, Linux, iOS, Android).

• Cỡ mẫu và timeline nghiên cứu: Thực hiện trong 6 tháng với sự phân chia nhiệm vụ rõ ràng: Sprint 1 – xây dựng lõi AI cơ bản, Sprint 2 – mở rộng khả năng và phát triển đồ họa, Sprint 3 – tích hợp hệ thống, Sprint 4 – kiểm thử và triển khai.

• Phương pháp chọn mẫu: Nghiên cứu tập trung trên các trạng thái khả thi (khoảng 72 ô khả dụng trên bàn) trong quá trình tìm kiếm nước đi, tập trung ưu tiên vào quân cờ gần bóng hoặc có khả năng tạo ra nước đi lợi thế cao.

• Phân tích và đánh giá kết quả: Sử dụng thuật toán Alpha-Beta kết hợp các chiến thuật bóng đá giúp giảm số lượng nhánh tìm kiếm từ trung bình 40 xuống còn 4-6 quân cờ cần tính toán, từ đó cải tiến hiệu suất và giảm thời gian suy luận AI xuống dưới 10 giây.

Phương pháp luận này mang đến một quy trình phát triển Agile với sự tương tác giữa nhóm phát triển gồm 4 thành viên, phối hợp chặt chẽ để đảm bảo tiến độ và chất lượng của sản phẩm cuối cùng.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả của thuật toán cắt tỉa Alpha-Beta
   Việc áp dụng Alpha-Beta pruning đã giúp cắt giảm số lượng trạng thái cần đánh giá đến hơn 50% so với thuật toán Minimax truyền thống. Cụ thể, ở độ sâu tìm kiếm 2, số nước đi có thể lên tới 5184, nhưng sau cắt tỉa giảm xuống còn khoảng một phần ba, qua đó giảm rất nhiều thời gian tính toán.

2. Giảm không gian tìm kiếm nhờ chiến thuật bóng đá
   Sự tích hợp các chiến thuật tấn công và phòng thủ giúp hạn chế phạm vi quân cờ cần xem xét trong mỗi lượt đi từ con số trung bình 40 xuống còn 4-6 quân cờ, tiết kiệm tài nguyên tính toán và cải thiện thời gian phản hồi AI xuống dưới 10 giây.

3. Tối ưu về bộ nhớ và ổn định trên thiết bị đa nền tảng
   Kiến trúc phần mềm sử dụng biến con trỏ và quản lý bộ nhớ hiệu quả giúp giảm mức tiêu thụ RAM tối đa từ 140MB xuống còn dưới 75MB trong thời gian hoạt động, đảm bảo tương thích và hoạt động mượt mà trên các thiết bị di động phổ biến.

4. Đa dạng hóa lựa chọn nhằm giảm lặp lại và làm phong phú trận đấu
   Việc mở rộng lựa chọn nhiều nước đi gần tối ưu và áp dụng chọn ngẫu nhiên có trọng số đã giảm hẳn hiện tượng AI lặp lại các nước đi giống nhau, giúp trải nghiệm người chơi hấp dẫn hơn với các kết quả trận đấu phong phú và tự nhiên hơn.

Thảo luận kết quả

Nguyên nhân thành công của kết quả trên nằm ở việc kết hợp sáu yếu tố: thuật toán Alpha-Beta cùng các chiến thuật bóng đá, cấu trúc dữ liệu hiệu quả (như bảng kích thước 13x13 với sentinels tránh lỗi truy cập bộ nhớ), chương trình quản lý bộ nhớ chặt chẽ, và phương pháp phân tích chiến thuật hợp lý nhằm giảm độ phức tạp.

So với các nghiên cứu về lập trình AI cho các trò chơi cờ vua hoặc Go, dự án Jingci với môi trường bàn cờ 9x9 cùng luật chơi riêng đòi hỏi tối ưu riêng biệt về không gian tìm kiếm. Một nghiên cứu gần đây trong lĩnh vực lập trình game chiến thuật cũng chỉ ra tầm quan trọng của việc tích hợp chiến thuật thực tiễn để lọc các nước đi không cần thiết, điều này hoàn toàn phù hợp với kết quả đề xuất trong luận văn.

Tất cả dữ liệu phân tích có thể được trình bày trực quan thông qua biểu đồ cột thể hiện số lượng trạng thái được xử lý trước và sau khi cắt tỉa Alpha-Beta, cùng với biểu đồ tròn phản ánh phân bố lượt chạy trên các loại quân cờ theo các chiến thuật tấn công và phòng thủ.

Đề xuất và khuyến nghị

1. Cải tiến độ sâu tìm kiếm động
   Áp dụng kỹ thuật tìm kiếm động với độ sâu có thể thay đổi dựa trên tình huống thực tế của trận đấu nhằm tối ưu thời gian phản hồi và độ chính xác của nước đi, hướng tới nâng cao độ khó AI một cách linh hoạt.

2. Mở rộng các mức độ chiến thuật
   Phát triển thêm các chiến thuật phức tạp như chiến thuật phản công, chiến thuật tiền vệ để tăng tính đa dạng và chiều sâu cho AI, giúp trò chơi hấp dẫn và sát thực hơn.

3. Tối ưu hóa về tài nguyên đa nền tảng
   Khuyến nghị nhóm phát triển tiếp tục tối ưu bộ nhớ và bộ xử lý cho các thiết bị đời thấp để mở rộng tệp khách hàng, bao gồm việc áp dụng các kỹ thuật nén hình ảnh và âm thanh hiệu quả hơn.

4. Triển khai mô-đun huấn luyện và nâng cao người chơi
   Thiết kế các chế độ huấn luyện có sự tương tác nâng cao giúp người chơi làm quen và nâng cao kỹ năng, đồng thời thu thập dữ liệu để tinh chỉnh các tham số AI phù hợp.

Đề xuất trên nên được thực hiện trong vòng 12 tháng tiếp theo, dưới sự phối hợp giữa nhóm phát triển phần mềm và đội ngũ thiết kế trải nghiệm người dùng nhằm đảm bảo sự thành công và phù hợp với nhu cầu thị trường.

Đối tượng nên tham khảo luận văn

1. Nhà phát triển game trí tuệ nhân tạo
   Luận văn cung cấp các kiến thức về thuật toán Alpha-Beta pruning, cách ứng dụng thực tế cho các game chiến thuật có không gian trạng thái lớn, hỗ trợ nâng cao kỹ năng phát triển AI hiệu suất cao trên nền tảng di động.

2. Nghiên cứu sinh và sinh viên ngành khoa học máy tính
   Đây là tư liệu tham khảo giá trị về phát triển hệ thống AI đa nền tảng, nghiên cứu sâu về kỹ thuật tối ưu thuật toán tìm kiếm, cũng như thiết kế mô hình đánh giá chiến lược trong lĩnh vực trò chơi.

3. Doanh nghiệp phát triển phần mềm game di động
   Các công ty muốn mở rộng lĩnh vực sản phẩm, đặc biệt trong thể loại game mô phỏng chiến thuật và thể thao có thể học hỏi phương pháp phát triển agile, tối ưu tài nguyên và quản lý dự án từ nghiên cứu.

4. Chuyên gia phân tích và thiết kế hệ thống đa nền tảng
   Với ứng dụng cụ thể về tích hợp C++ và Cocos2d-x cùng Android NDK, luận văn làm minh chứng thực tiễn cho kỹ thuật phát triển phần mềm đa nền tảng với hiệu quả cao, giảm thiểu chi phí chuyển đổi mã nguồn.

Từng nhóm trên có thể áp dụng những kinh nghiệm cũng như giải pháp sáng tạo được trình bày trong luận văn cho các dự án tương tự nhằm tăng tốc phát triển và chất lượng sản phẩm.

Câu hỏi thường gặp

1. Tại sao chọn Alpha-Beta pruning thay vì Minimax thuần túy?
   Alpha-Beta pruning giúp loại bỏ các nhánh con không cần duyệt trong cây trò chơi, giảm đáng kể số trạng thái phải đánh giá. Điều này giúp AI phản hồi nhanh hơn, phù hợp với giới hạn thời gian vài giây trên thiết bị di động.

2. Làm thế nào để tránh AI rơi vào vòng lặp lặp đi lặp lại các nước đi?
   Luận văn áp dụng kỹ thuật chọn ngẫu nhiên trong số các nước đi tốt nhất với xác suất phân phối nhằm đa dạng hóa hành động, qua đó hạn chế tình trạng AI lặp lại các nước đi giống nhau gây nhàm chán.

3. Chiến thuật bóng đá được tích hợp như thế nào trong AI?
   Các chiến thuật như tấn công tập trung quân cờ gần bóng hoặc phòng thủ chặt chẽ gần cầu môn được mô hình hóa và ưu tiên trong thuật toán tìm kiếm, giảm tải lượng trạng thái phải đánh giá mà vẫn đảm bảo tính chiến thuật.

4. Động cơ AI có thể mở rộng nâng cao độ khó không?
   Hoàn toàn có thể. Bằng cách tăng độ sâu tìm kiếm, bổ sung thêm chiến thuật phức tạp hoặc cải tiến hàm đánh giá, động cơ có thể được nâng cấp để phù hợp với nhiều cấp độ người chơi khác nhau.

5. Có giới hạn gì khi triển khai trên các nền tảng di động?
   Thiết bị di động có giới hạn về bộ nhớ và CPU so với máy tính để bàn. Vì vậy, luận văn tập trung tối ưu bộ nhớ, sử dụng kỹ thuật cắt tỉa tìm kiếm và chiến thuật giới hạn số quân cờ cần đánh giá nhằm cải thiện hiệu năng và trải nghiệm người dùng.

Kết luận

• Đã phát triển thành công động cơ AI cho trò chơi Jingci sử dụng thuật toán cắt tỉa Alpha-Beta giúp hiệu quả tính toán vượt trội trên thiết bị di động.
• Các chiến thuật bóng đá được tích hợp thành công, giúp AI thể hiện tư duy phù hợp, nâng cao trải nghiệm người chơi.
• Giải pháp tối ưu bộ nhớ và khả năng đa nền tảng đảm bảo ứng dụng hoạt động mượt mà trên hệ điều hành iOS và Android.
• Kết quả test cho thấy thời gian phản hồi AI dưới 10 giây, tiêu thụ bộ nhớ thấp nhất đạt 40 MB, cao nhất không quá 75 MB.
• Các đề xuất phát triển tiếp theo hướng tới nâng cao độ sâu tìm kiếm, mở rộng chiến thuật và phát triển tính năng huấn luyện người chơi.

Đây là bước tiến thiết thực cho lĩnh vực phát triển trò chơi chiến thuật tích hợp AI trên di động, mở đường cho các ứng dụng tương lai đa dạng và thông minh hơn. Khuyến khích các nhà phát triển và nghiên cứu tiếp tục khai thác kiến thức và kinh nghiệm từ luận văn để phát triển các dự án game trí tuệ nhân tạo hiệu quả hơn.

Trích đoạn nội dung tài liệu

MEMOIRE DE FIN D’ETUDES MASTER D’INFORMATIQUE Conception et Développement d’un moteur d’intelligence artificielle pour un jeu d’échecs multiplateformes Étudiant : HOANG Duc Viet Superviseurs : HO Tuong Vinh NGUYEN Duc Thinh Hanoi, Juin 2014 TIEU LUAN MOI download : [e-mail] Table de matières Table de matières. 2 Table de figures. Contexte du stage .3 Projet du jeu vidéo Jingci. Motivation et objectif du stage.

8 Chapitre 1 État de l’art : Epreuves générales de la programmation de jeux d’échecs. Représentation des données. Gestion des mouvements .1 Génération des mouvements .2 Evaluation de mouvements .3 Recherche de mouvements. Algorithmes de recherche (Minimax, Alpha-Beta) .2 Algorithme Elagage Alpha-Beta (Alpha-Beta pruning).

16 Chapitre 2 Épreuves du projet. Description générale du jeu. Spécifications d’exigences fonctionnelles. Spécifications d’exigences non-fonctionnelles.

Capacité de réfléchir du noyau d’Intelligence artificielle. Difficultés de calcul. 24 Chapitre 3 Solutions proposées. Arbres de positions.

Stratégies de décisions. 30 2 TIEU LUAN MOI download : skknchat@gmail. 31 Chapitre 4 Réalisation et résultats. Ingénierie de développement .1 Méthode de développement .2 Langage de programmation et plateformes .3 Gestion de code et de changement.

Conception et Développement .1 Représentation des données .2 Implémentation de règles et de contrains .3 Implémentation de la recherche de mouvement. 57 3 TIEU LUAN MOI download : [e-mail] Table de figures Figure 1-1 Arbre de positions du jeu Tictactoe [8]. 11 Figure 1-2 Exemple de l’évaluation de l’heuristique [15]. 12 Figure 1-3 Jeux de deux à somme nulle: Echecs[16], Echecs chinoises[17], Tictactoe[18], Go[19], Othello[20], Gomoku[21].

13 Figure 1-4 Illustration de l’algorithme Minimax [9]. 14 Figure 1-5 Algorithme Minimax pour trouver la solution de Tictactoe [8]. 15 Figure 1-6 Algorithme Alpha-Beta [9]. 16 Figure 2-1 Terrain du football [13].

19 Figure 2-2 Tablier de jeu. 20 Figure 2-3 Pièces de jeu: Ballon, Joueurs, Gardiens (de goal). 20 Figure 2-4 Portée de courses: pour le ballon et pour le joueur. 20 Figure 2-5 Portée de pièce et de ballon selon le cas.

21 Figure 2-6 Illustration du cas de répétition de jeu. 21 Figure 2-7 Illustration du cas de ballon bloqué 1. 22 Figure 2-8 Illustration du cas de ballon bloqué 2. 22 Figure 2-9 Initiation du jeu.

23 Figure 3-1 Elagage Alpha-Beta [14]. 27 Figure 3-2 Exemple de la coupure Alpha [14]. 28 Figure 3-3 Facteurs d’évaluation d’une position de jeu. 29 Figure 3-4 Tactique défensive.

31 Figure 3-5 Tactique offensive. 31 Figure 4-1 Diagramme Gantt du projet Jingci. 34 Figure 4-2 Plan de réalisation du Jingci. 35 Figure 4-3 Architecture de l’application NDK [12].

37 Figure 4-4 Structure de codage du projet Jingci. 38 Figure 4-5 Diagramme de classes du noyau IA. 39 Figure 4-6 Représentation de tablier dans le mémoire. 40 Figure 4-7 Représentation de tablier et des sentinelles.

41 Figure 4-8 Représentation de la surface de but. 41 Figure 4-9 Représentation de la zone de gardien de but. 42 Figure 4-10 Classe Piece. 42 Figure 4-11 Classe d’une position du jeu JingciNode.

43 Figure 4-12 Algorithme de trouver les carres disponibles. 44 Figure 4-13 Algorithme de décision. 46 Figure 4-14 Tactique offensive. 47 Figure 4-15 Tactique défensive.

48 Figure 4-16 Ecran du programme Jingci et écran d’étape d’initiation. 51 Figure 4-17 Ecrans d’étape de préparation. 52 Figure 4-18 Ecrans de mouvement du jeu. 52 Figure 4-19 Ecrans du tir au goal.

53 Figure 4-20 Ecrans de la victoire et de l’échec. 53 4 TIEU LUAN MOI download : [e-mail] Remerciements Je remercie mes collègues dans la société Newwave, pour m’avoir permis d’effectuer ce stage dans les meilleures conditions possibles, qui ont pris du temps pour me guider dans mon stage. J’ai eu l’opportunité de pouvoir travailler pendant 6 mois en tant que stagiaire au sein de la société Newwave où j’ai reçu un accueil chaleureux de la part de toutes les personnes présentes dans cette entreprise. Je remercie également mes professeurs d’informatique à l’IFI pour m’avoir enseigné les connaissances nécessaires.

Mes sincères remerciements à mes professeurs de français pour m’avoir accompagné dans l’apprentissage du français nécessaire pour mes études à l’IFI en particulier et mon métier en général. Je remercie également M. Nguyen Van Tuan et Mme Nguyen Thi Hong Loan pour leurs aides concernant les procédures administratives pendant mon Master a l’IFI. Je tiens à remercier mes parents pour leur mobilisation, l’encouragement constant et pour leur aide financière.

Ils m’ont permis de réaliser mes études et mon stage dans de bonnes conditions. Enfin, je remercie amicalement mes amis vietnamiens et mes amis français qui sont toujours à côté de moi pour partager des difficultés et m’encourager à effectuer les études à IFI et ce stage. 5 TIEU LUAN MOI download : [e-mail] Résumé Ces dernières années, le domaine des jeux vidéo s’est développé sans cesse grâce au développement de matériel et d’algorithmes. En simulant le football, Jingci est un nouveau jeu du type d’échecs et nous voulons construire un jeu vidéo multiplateforme pour présenter ses intérêts.

Dans le projet Jingci, nous nous concentrons dans le but de développer un moteur d’intelligence artificielle afin d’attirer les utilisateurs à étudier les règles et jouer au jeu. Malgré la croissance des performances des appareils portables, la programmation de jeux d’échecs est tournée vers la recherche de solution dans un espace contenant énormément de positions. Des algorithmes ont été inventés pour résoudre le problème, par exemple Minimax, Alpha-Beta, etc. En évaluant les contraintes de temps de traitement et la limitation de ressource des appareils portables pendant la durée de réalisation, nous avons décidé d’appliquer l’Alpha-Beta pour implémenter un jeu vidéo qui soit déployé sur la plateforme mobile.

Dans le cadre de ce mémoire, nous allons exposer les problématiques, l’analyse et les solutions d’application l’algorithme d’élagage Alpha-Beta et les tactiques de football. Enfin, nous allons présenter le résultat et l’évaluation de la bonne efficacité en appliquant l’élagage Alpha-Beta pour réduire l’espace de recherche de solution et des stratégies de réflexion pour le moteur d’intelligence artificiel proposé pendant la réalisation. Mots-clés : intelligence artificielle, moteur de jeu vidéo, jeux mobiles, jeux d’échecs, jeux à somme nulle, élagage alpha-beta 6 TIEU LUAN MOI download : skknchat@gmail. Contexte du stage 1.1 IFI L’Institut de la Francophonie pour l'Informatique [23] est un institut international d’études supérieures en informatique située à Hanoi (Vietnam) et appuyée par l’Agence Universitaire de la Francophonie (AUF) et par l’Université Nationale du Vietnam.

L’Université de La Rochelle [24] est partenaire depuis plusieurs années avec l’IFI. L’IFI offre deux formations Master et une double diplomation franco-vietnamienne pour ses étudiants: Systèmes Intelligence & Multimédia et Réseaux & Systèmes Communiquant. Pour ma part j’ai suivi le Master Systèmes Intelligences & Multimédia qui est enseigné totalement en français.2 Société Newwave Newwave est une jeune société vietnamienne [25]. Elle a été créée en 2011 par un groupe d’ingénieurs chaleureux et ambitieux.

Ils étaient 3 ingénieurs au début. En développement constant, la société se compose en ce moment de plus de 30 jeunes membres. Plusieurs projets ont été menés avec la satisfaction du client. Etant membre de l’association de logiciel du Vietnam, la société se concentre sur le domaine informatique, particulièrement dans le service outsourcing pour le marché japonais et le marché à domicile.

Dans son élan de développement, la société est en train de chercher le chemin afin de participer au marché européen avec des solutions et des productions techniques de hauts niveaux. Ayant des bonnes expériences avec les ressources libres (SugarCRM, CMSMS, vTiger, Apache LAMP, etc.) et des technologies modernes (HTML5, PHP/Javascript) et des plateformes (Microsoft, Java, iOS, 7 TIEU LUAN MOI download : [e-mail] Android), l’orientation en terme de développement est tourné vers des services informatiques principaux : - Développement de Logiciels personnalisés ; - Développement d’Applications Mobiles ; - Externalisation de Logiciels (Software Outsourcing) ; - Maintenance de Logiciels.3 Projet du jeu vidéo Jingci Jingci est un jeu du type stratégique qui a été inventé par un auteur japonais il y a quelques années. C’est un jeu du type jeu d’échecs simulant le football avec deux adversaires qui essayent toujours de marquer le but l’un de l’autre adversaire. Actuellement, ce jeu n’est pas connu au Japon ou dans le monde d’entier.

Pour intéresser les joueurs aux caractéristiques et au potentiel, notre client décide de développer un jeu vidéo sur la plateforme mobile, particulièrement sur iOS et sur Android. Pour ce fait, la difficulté de l’intelligence artificielle du programme est une grande épreuve, mais c’est aussi une occasion pour la société Newwave de surmonter cette épreuve pour prouver au client son efficacité. Ce stage a été effectué dans le cadre du projet Jingci, plus précisément dans le développement du noyau de l’intelligence artificielle. Motivation et objectif du stage Jingci est un nouveau jeu qui est maintenant en période d’être commercialisé.

La motivation principale du projet est d’élargir l’utilisation du jeu. Autrement dit, on veut populariser le jeu Jingci. C’est pourquoi on construit la première version du jeu vidéo ayant pour le but de présenter les règles, les contraintes et comment on joue à ce jeu pour montrer les intérêts du jeu. Le défi du projet est que l’on doit construire un programme complet qui doit avoir le noyau ayant capacités humaines : - Capacité de réagir : déplacer les pièces d’échecs suivant les règles ; - Capacité de réfléchir : calculer les mouvements les plus dangereux (qui peuvent vaincre l’utilisateur).

Le processus de développement de ce jeu vidéo se compose en plusieurs étapes: analyse des exigences, conception, implémentation de GUI, implémentation de noyau IA, intégration du noyau IA au GUI et déploiement. L’objectif principal du stage se concentre sur l’implémentation du noyau d’intelligence artificielle. Pour réaliser ce but, on doit passer plusieurs étapes: - Evaluer et choisir une plateforme utile de développement de jeux vidéo pour périphériques portables ; - Evaluer et choisir une approche efficace de la programmation du jeu d’échecs ; - Implémenter d’un noyau IA qui a la capacité de réfléchir ; - Tester et améliorer le noyau IA ; - Participer à la publication du jeu sur la plateforme mobile (l’intégration au GUI, le déploiement sur iOS et sur Android, etc. Contribution En participant au développement d’un projet complet, à partir de zéro jusqu’à un programme accompli, mes contributions vont se porter sur plusieurs points : 8 TIEU LUAN MOI download : [e-mail]  Premièrement, j’ai effectué une étude des langages et des moteurs de développement de jeux vidéo.

 Deuxièmement, j’ai étudié des solutions et des algorithmes actuels dans le domaine de programmation de jeux d’échecs.  Troisièmement, j’ai implémenté le noyau IA.  Finalement, j’ai collaboré avec notre équipe pour intégrer notre noyau IA à notre GUI et puis déployer une application complète. 9 TIEU LUAN MOI download : [e-mail] Chapitre 1 État de l’art : Épreuves générales de la programmation de jeux d’échecs Dans ce chapitre, on va faire des études sur les approches connues dans le domaine de programmation de jeux d’échecs.

Représentation des données Représentation des données est une mission importante de développement de jeux vidéo car si on peut bien modéliser le monde du jeu par des types utiles de données, le programme peut être marche efficacement et peut économiser mieux les ressources du système. Pour un jeu d’échecs, la représentation de données concerne directement la représentation du tableau de jeu, des pièces de jeu et des états de jeu. Dans cette partie, on va concentrer sur l’analyse de la représentation de tableau de jeu car elle influence indirectement la présentation des caractères de pièces et d’états du jeu. Cette partie va aborder le problème suivant : comment le tablier de jeu est représenté dans la mémoire du programme.

La structure de données qui présente le tableau de jeu et les pièces, est un facteur important pour l’efficacité de traitement du programme.