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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.