INF4230 - Intelligence artificielle
Hiver 2017

TP2 - Algorithme minimax appliqué au jeu Planète_H

1. Objectifs

1. Implémenter et appliquer l'algorithme minimax avec élagage alpha-beta.
2. Élaborer et définir une fonction d'évaluation efficace.
3. Implémenter un algorithme de prise de décision en temps réel (profondeur itérative).

2. Planète_H : La bataille!

Vous devez programmer un joueur artificiel pour une variante du jeu Planète_H (un jeu avec adversaire à somme nulle). Il est fortement conseillé d'implémenter votre joueur artificiel à l'aide de l'algorithme minimax avec élagage alpha-beta (alpha-beta pruning) vu en classe.

2.1 Suite de l’histoire de la planète H

Après avoir échoué dans sa mission de faire exploser la planète grâce à l’efficacité de la stratégie de défense A* du Htepien, le méchant bonhomme a décidé de revenir en force. Cette fois, il veut pouvoir placer une série de bombes pour faire exploser la planète. Cependant, il faut en poser une série de 5 bombes dans des cases consécutives (en ligne, en colonne ou en diagonale) pour qu’une explosion soit possible. Informer de ce secret, le Htepien s’est donné une stratégie de contre-attaque (en se dotant de tuiles magiques  qu’il peut poser dans les cases) qui consiste non seulement à bloquer les tentatives du méchant bonhomme à placer ses 5 bombes consécutives, mais aussi à faire en sorte que 5 cases consécutives comportant des tuiles magiques (en ligne, en colonne ou en diagonale) inhiberaient définitivement l’action du bonhomme qui n’aura d’autre choix que d’abandonner.

 

Il vous est demandé de développer l’intelligence artificielle du Htepien pour préserver la planète H de cette bataille.

 

Les règles de bataille sont les suivantes :

• Les deux adversaires déposent chacun à son tour un objet dans une case (une tuile magique pour le Htepien) ou (une bombe pour l’autre).
• La bataille se passe dans un monde H (grille) de dimension fixée arbitrairement. Les tuiles magiques (vertes) et les bombes (rouges) doivent être déposées à l'intérieur des cases et non sur les intersections.
• Pour gagner, un des deux adversaires doit aligner exactement cinq (5) éléments (tuiles magiques ou bombes) à l'horizontale, à la verticale ou en diagonale.
• La bataille se termine lorsqu'il y a un gagnant ou lorsqu'il n'y a plus de placement possible (grille complète). Dans ce dernier cas, la bataille est déclarée nulle.

2.2 Interface graphique

Une interface graphique pour cette version du jeu Planète_H est fournie dans planeteH_2.jar. Le jeu peut être lancé en ligne de commande : «java –jar planeteH_2.jar».

 

Il y a 4 modes de jeu (combinaison des deux rôles Htepien et Poseur de bombe) offerts dans la boîte de configuration :

• Htepien humain – Poseur de bombe humain
• Htepien virtuel (IA) – Poseur de bombe humain
• Htepien humain – Poseur de bombe virtuel (IA)
• Htepien virtuel (IA) – Poseur de bombe virtuel (IA)

2.3 Temps de réflexion limité

Le temps de réflexion est exprimé en temps réel, ou plus précisément selon l'horloge de la machine sur lequel le jeu Planete_H est exécuté.

À partir d'une certaine taille de grille, il n'est pas possible de faire une exploration complète de l'arbre de recherche. Pour cette raison, votre joueur artificiel doit être capable de prendre des décisions imparfaites en temps réel afin de respecter le temps de réflexion alloué.

Pour cela, vous devrez élaborer une fonction d'évaluation permettant d'évaluer les feuilles des branches n'atteignant pas une partie complétée. Vous devez aussi modifier légèrement l'algorithme minimax avec élagage alpha-beta afin que votre joueur puisse prendre des décisions en temps réel. Référez-vous à la section 5.4 du livre de référence pour plus de détails. Cette section introduit une stratégie iterative deepening. D'autres stratégies y sont également mentionnées. Ces stratégies permettent à l'algorithme d'être anytime. Dans le jargon en intelligence artificielle, un algorithme anytime est un algorithme qui permet de trouver rapidement une première solution et de continuer sa recherche afin de l'améliorer. L'algorithme termine dès qu'on demande une réponse (ex.: temps alloué expiré) ou lorsque l'espace de recherche est entièrement visité (la solution optimale est trouvée). En d'autres mots, l'algorithme trouve une solution en tout temps, d'où le nom anytime.

3. Ressources offertes et interface du joueur artificiel

Votre programme sera évalué de façon automatique. Vous devez donc vous conformer à l'interface et ressources offertes. À défaut de vous y conformer, votre programme ne pourra pas réussir les tests de correction automatique et pourrait obtenir une note de zéro (0).

L'interface graphique du jeu (voir section 2.2) est accompagnée d'un joueur artificiel implémenté dans la classe JoueurArtificiel du package planeteH_2.ia.  L’implémentation actuelle (par défaut) du joueur artificiel correspond à un comportement aléatoire. Ce Joueur aléatoire dépose l’objet dans une case vide choisie aléatoirement pour poursuivre la bataille. Votre travail consiste à proposer un joueur artificiel qui améliore ce comportement par l’utilisation de stratégies appropriées. Pour utiliser l’interface graphique et pour accéder au code source initial de Planète-H, vous devez télécharger le fichier planeteH_2-src.zip. Ensuite, vous pouvez modifier la classe JoueurArtificiel (JoueurArtificiel.java). Vous pouvez ajouter d'autres fichiers sources dans le package planeteH_2.ia. Cependant, vous ne pouvez pas faire d'autres modifications au niveau du package planeteH_2. Lors de la correction, les fichiers à l'extérieur de planeteH_2.ia seront écrasés par les fichiers originaux. Par conséquent, vous ne pouvez pas modifier l'interface planeteH_2.Joueur.

4. Indices

L'écriture d'une bonne fonction d'évaluation est difficile. Pour le jeu de tic-tac-toe, une fonction d'évaluation n'est pas vraiment utile, car il est possible d'explorer les 9!=362880 nœuds de l'arbre très rapidement. En fait, 362880 nœuds est une estimation conservatrice, car il y a moins que ce nombre de nœuds dans l'arbre si on considère que des parties se terminent en moins de 9 coups.

Dans le livre et les diapositives du cours, on donne tout de même une idée d'une fonction d'évaluation pour le jeu de tic-tac-toe. Il est proposé de compter le nombre de possibilités restantes pour gagner le jeu.

4.1 Fonction d'évaluation proposée pour Planète-H

Dans le jeu Planète_H, on peut compter le nombre de «groupes» de 1, 2, 3, 4 et 5 objets (bombes ou tuiles magiques) d'aligner, et ce, pour chaque joueur. La figure ci-dessous montre un arbre de jeu où le Htepien (qui place les objets verts) doit prendre une décision (3e tour). La grille g0 représente la situation actuelle, à partir de laquelle il y a 41 actions possibles. Donc 41 grilles à évaluer à l'aide d'une fonction d'évaluation si on limite la profondeur à 1 action. Par exemple, dans la première grille à gauche (g1), il y a un groupe de 1 objet pour chaque joueur et 1 groupe de 2 objets pour chaque joueur. Pour chaque taille de groupe (1 à 5), on calcule la différence entre la quantité pour le joueur actuel et la quantité pour l’adversaire. Ensuite, on peut calculer un score à l'aide d'une somme pondérée. Par exemple, on peut attribuer 1 point pour 1 objet, 10 points pour 2 objets, 100 points pour 3, 1000 pour 4 et 10000 pour 5. Dans l'exemple ci-dessous, les grilles g14 et g15 représentent les grilles résultantes suite aux deux «meilleurs» coups possibles avec 89 points. Évidemment, il s'agit d'une estimation et non d'une valeur exacte.

5. Contraintes

5.1 Langage de programmation autorisé, bibliothèque permise et taille des équipes

Vous devez utiliser le langage Java et vous assurer que vos programmes soient compilables, exécutables et corrigibles dans l'environnement de correction (voir section 5.4). Vous devez utiliser l’API de Java. Vous ne devez pas utiliser d'autres bibliothèques. Ce travail peut se faire en équipe d’au plus 3 étudiants.

5.2 Limitations techniques

• Votre programme ne peut utiliser qu'un seul fil d'exécution (thread) pour le calcul d'une décision. Les threads du garbage collector ne sont pas considérés.
• Votre joueur ne peut pas effectuer des calculs entre deux requêtes. Il doit être en mode d'attente.
• Votre joueur ne doit pas conserver d'informations en mémoire entre deux requêtes. D'ailleurs, les joueurs seront exécutés avec une limite de mémoire de 1 Go. Cette limite sera configurée à l'aide de l'option java -Xmx1g en Java et par la commande ulimit du shell Bash sous Linux.

Tout non-respect de ces limitations techniques peut entraîner un mauvais fonctionnement du correcteur automatique et mener à une disqualification au critère C décrit plus bas.

5.3 Restrictions de réutilisation de code de tierces parties

Vous devez programmer votre propre algorithme minimax avec élagage alpha-beta. Ainsi, vous ne pouvez pas réutiliser du code que vous retrouver dans Internet, et ce, même si ce code est correctement référencé.

6. Remise

Date de remise : 22 mars 2017 à 24h00 (23 mars à 00h00).

Consignes de remise : 

1)      Archivez uniquement les fichiers sources du répertoire planeteH_2/ia dans un seul fichier que vous appellerez tp2.zip.  Vous n'avez donc pas à inclure dans l’archive les fichiers source dans planeteH_2 qui étaient fournis dans planeteH_2-src.zip, car ces fichiers source seront de toute façon écrasés par leur version originale.

2)      Soumettez tp2.zip sous oto : $ oto rendre_tp nkambou_r INF4230-TP2 CODE00000001,CODE00000002 tp2.zip

7. Évaluation

Ce travail pratique vaut 15 % de la note finale.  Le tableau ci-dessous récapitule les critères qui seront considérés pour l’évaluation.

 

Critère	Description	Pondération
A.	Respect des règles du jeu. Ce test vérifie si votre joueur artificiel joue correctement, c'est-à-dire dans des cases vides.	3
B.	Réactions adéquates à diverses configurations de jeu. Votre joueur artificiel sera testé sur des cas simples afin de vérifier s'il répond correctement. Voir programme DemoCorrecteurB.java pour des exemples de test.	5
C.	Qualité des décisions prises par le joueur artificiel et capacité de répondre à l'intérieur des délais alloués.	6
D.	Respect des directives pour la remise. Fichiers sources seulement, aucun fichier binaire. Respect des directives Java (planeteH_2.ia). Compilable sans modifications. Exécutable sans modifications.	1
Total		/15