- Conception et Développement d’un moteur d’intelligence artificielle pour un jeu d’échecs multiplateformes. - 1.3 Projet du jeu vidéo Jingci. - Chapitre 1 État de l’art : Epreuves générales de la programmation de jeux d’échecs. - Description générale du jeu. - 2.3 Implémentation de la recherche de mouvement. - Figure 1-1 Arbre de positions du jeu Tictactoe [8. - Figure 1-2 Exemple de l’évaluation de l’heuristique [15. - Figure 1-4 Illustration de l’algorithme Minimax [9. - Figure 2-4 Portée de courses: pour le ballon et pour le joueur. - Figure 2-9 Initiation du jeu. - Figure 4-3 Architecture de l’application NDK [12. - Figure 4-8 Représentation de la surface de but. - Figure 4-11 Classe d’une position du jeu JingciNode. - Figure 4-20 Ecrans de la victoire et de l’échec. - 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. - 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 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.. - Evaluer et choisir une approche efficace de la programmation du jeu d’échecs. - Chapitre 1 État de l’art : Épreuves générales de la programmation de jeux d’échecs. - Figure 1-1 Arbre de positions du jeu Tictactoe [8]. - Pour le faire, on doit considérer d’une équation d’évaluation de mouvement. - Figure 1-2 Exemple de l’évaluation de l’heuristique [15]. - Les pièces de l’équipe Noir : le roi, la dame et 3 pions. - Les pièces de l’équipe Blanche : le roi, le tour, le cavalier et 2 pions. - Pour un jeu d’échecs, le nombre de mouvements est énorme. - Pour la modélisation d’espace de jeu, on peut considérer les mouvements du jeu comme l’arbre de décision. - À partir de la racine – le mouvement d’initiation du jeu, chaque nœud fils de l’arbre manifeste de mouvements possibles pour réagir contre le nœud parent. - Par conséquent, le fait d’examiner chacun des nœuds d’un jeu d’échec est impossible. - En fait, les gains d’un jeu d’échecs sont de victoire ou d’échec. - Figure 1-4 Illustration de l’algorithme Minimax [9]. - Le pseudocode de l’algorithme MiniMax [9]. - Le pseudocode de l’algorithme Alpha-Beta [9]. - Le redémarrage du jeu : pour le redémarrage du jeu, le ballon doit être déplacé sur le carré du centre.. - Le but : On dit qu’une équipe marque le but quand il peut tirer le ballon à un des carrés du but de l’adversaire.. - C’est pour arranger la formation de l’équipe avant le match.. - L’initiation du jeu : L’initiation est le premier mouvement du jeu. - Le temps de calcul : le temps de calcul d’un mouvement, pour le noyau AI doit ne pas passer 10 secondes. - L’utilisateur, maintenant, joue au rôle d’un entraineur d’équipe : il doit disposer la formation de son équipe : Son équipe va jouer avec combien d’attaquants ? Son équipe va jouer avec combien de défenseurs ? Quelle est la stratégie utile de l’équipe pour chaque match. - Par exemple, suivant l’étude de Shannon [12] (le nombre Shannon) pour le Jeu d’Echecs, il y a environ en moyenne 40 mouvements pour chaque match. - Cela veut dire que l’on a 40 mouvements pour le Noir et 40 mouvements pour le Blanc. - Pour le jeu d’échecs Jingci, on peut calculer brièvement les calculs possibles : Il y a 19 pièces (1 ballon, 2 gardiens de but, 16 joueurs). - En fait, le calcul d’un mouvement du jeu Jingci n’est pas égal à 19*25 = 475. - Pour le gardien de but : le nombre maximum est de 3*5 carrés (car il est limite dans la zone de goal). - Pour le ballon : le nombre maximum est de 5*5 - Pour les joueurs : le nombre maximum est de 16*5*5. - Le nombre de calcul pour le profondeur N = (72) N. - Pour éviter le phénomène d’explosion combinatoire, on peut seulement chercher les solutions pour quelques premiers niveaux de profondeur de l’arbre du jeu car les appareils portables ont besoin de long temps pour trouver une solution positive.. - Dans les parties suivantes, on va discuter des solutions pour diminuer l’espace de recherche et des tactiques de jouer pour le noyau IA.. - Notamment pour les téléphones portables de générations précédentes (qui ont moins de l’espace de stockage et de mémoire vive), la considération de ces demandes va faire que le jeu peut être exécuté ou non. - Alors, en face des difficultés réelles, on doit proposer des applications de l’algorithme Alpha-Beta et des tactiques de football (pour diminuer l’espace de recherche) et optimiser l’équation d’évaluation (pour augmenter l’efficacité de calcul) qui vont être présentées aux suivants.. - Pour les applications mobiles, le calcul de la profondeur de 1 en appliquant Minimax est faisable, néanmoins pour le niveau de profondeur de 2, ou 3 et plus, la recherche des nœuds de l’arbre sont impossible dans une période acceptable. - On a abordé la difficulté de calcul dans la partie précédente et pour ce jeu, pour chaque mouvement, on peut calculer environ des milliers fois de l’équation heuristique. - Mais le facteur de branchement maintenant n’est pas de 3 comme l’arbre ci-dessous, on doit imaginer d’un arbre de 40 branches pour chaque niveau de profondeur (il faut faire attention que le premier mouvement a maximum de 25 sous- branches car la règle de l’initiation, pour les mouvements suivants, chaque nœud a maximum de 40 de sous-branches – le nombre moyen de solutions):. - On doit utiliser ces attributs de façon flexible pour que le calcul de l’heuristique pour chaque mouvement ne soit pas très complexe et soit assez efficace.. - Pour faciliter comprendre le mécanisme de l’Alpha-Beta, on va analyser le sous arbre de A ci-dessus. - Pour le nœud B (du type MIN), on va choisir la valeur minimum parmi ses fils (c’est de 5). - Pour le nœud C (du type MIN), on va choisir la valeur minimum parmi ses fils (D, E, F). - A = B = 5 mais on ne doit pas examiner le F (et sous arbre de F s’il existe).. - Comme dans l’image illustrée [11] (figure 15 ci-dessus), les branches de l’arbre sont coupés car l’évaluation de ces branches n’est pas nécessaire. - En réalité, pour notre arbre de positions pour un jeu d’échecs comme. - D’un autre côté, on doit considérer aussi de l’heuristique d’un mouvement – d’une position du jeu. - Dans le domaine de la programmation de jeux d’échecs, on a des facteurs pour évaluer une solution, par exemple de la position des pièces, des poids des pièces ou des pièces existants encore sur le tableau du jeu (dans quelques jeux on peut tirer les pièces de l’adversaire et celui qui a plus de pièces que l’autre, a l’avantage). - Par exemple, pour le jeu d’échecs, le poids de roi est plus grand que de la dame (qui est plus grand que du fou, du tour, du cavalier et du pion). - Le jeu Jingci n’a pas de règles qui permettent à l’utilisateur de tirer les pièces de l’adversaire alors, pour notre jeu, on peut analyser ses caractéristiques pour que l’on puisse choisir entre eux les meilleurs facteurs qui peuvent nous aider à évaluer le mouvement.. - Le Ballon est très proche de goal de l’équipe Blanc (d_minWGoal est plus petite, d_minBGoal est plus grande). - L’idée d’ici est que l’on applique des tactiques du jeu football pour le noyau IA car on sait que elles sont très efficaces en réalité. - Dans la période de réalisation, on propose des tactiques faisables pour le noyau IA ci-dessous.. - Au contraire, quand on attaque le but de l’adversaire, on peut laisser passer les défenseurs qui sont loin du ballon ou loin du but de l’adversaire car la probabilité de ces pièces pour qu’elles puissent marquer le but est beaucoup moins que les attaquants.. - Dans ce cas-là, on peut diminuer le calcul d’un mouvement en évitant de calculer les mouvements possibles pour le gardien de but et pour les pièces les plus loin du goal d’adversaire. - Figure 4-3 Architecture de l’application NDK [12]. - Publication de l’application. - Cette partie aborde la conception du noyau de jeu : la conception de classes, et de l’implémentation des algorithmes pour réaliser les solutions proposées.. - On appelle notre noyau IA à partir du GUI du jeu, on propose une classe de l’interface de programme GameAPI. - Avec la classe JingciNode, on représente les états actuels du jeu : les statuts de droits utilises (le Pass, le Bound), les statuts de l’initiation, de la répétition ou le tour du Rouge ou du Bleu. - La représentation du tableau de jeu est faite dans le codage de l’espace du jeu qui se compose de 9x9 carrées. - Et aussi on utilise un tableau d’integer 5x5 pour le masque de la portée possible de carrées d’une pièce.. - Mais quand on utilise un masque de 5x5 pour comparer avec le tableau de positions de pièces, il y a quelques cas dans lesquels la comparaison est incorrecte car la violation de l’espace de mémoire.. - Toutes les autres cellules ayant valeur 0 sont disponibles pour le Joueur. - 2.1.3 Représentation d’un mouvement du jeu. - Les données de l’état actuel du jeu sont aussi stockées pour chaque instance de JingciNode.. - La vérification de l’initiation : il y a une vérification pour le mouvement d’initiation : pour cette étape, il y a seulement le ballon qui peut se déplacer. - La vérification de l’état de réinitialisation : pour éviter les jeux négatifs, par exemple l’utilisateur cherche toujours de déplacer le ballon dans un carrée, ensuite de déplacer ses joueurs pour bloquer le ballons. - La vérification de l’état de répétition. - Classe d’une position du jeu JingciNode. - La taille du tableau de jeu est de 9x9 alors, dans 2 mouvements parfaits, on peut approcher le but de l’ennemi. - Cette réduction de l’espace de recherche manifeste une efficacité visible. - 2.4.2 Amélioration de l’utilisation de la mémoire vive. - De cette façon, on peut diminuer l’allocation de l’espace de mémoire. - Par conséquence, on a diminué la taille de l’application et les ressources du système en marche.. - 5 Vérifier la répétition du jeu O O X O O. - On a déjà accueilli des nouvelles demandes du client : le déploiement de l’application de multi-langue, l’élargissement de niveau de difficulté de jeu, l’ajout d’un module d’entrainement des utilisateurs, etc.. - En cherchant les réponses pour les questions « comment on arrange la formation de l’équipe. - Le moteur de jeux Cocos2dx est un moteur puissant pour le développement des jeux vidéo. - l’application de l’algorithme Alpha-Beta pour l’élagage de l’espace de recherche de solutions possibles d’un noyau de jeu vidéo. - l’application des tactiques de réflexion proposées pour le noyau d’intelligence artificielle. - [15] Clotures du Jeu d’échecs, [online, page consultée en. - [16] Tablier du Jeu d’échecs, [online, page consultée en 11/2013] http://www.intuitor.com/chess/. - [17] Tablier du Jeu d’échecs chinois, [online, page consultée en 11/2013] http://ancientchess.com/page/04.htm. - [19] Talier du Jeu GO, [online, page consultée en