Devoir 2 – Recherche multiagent dans Pac-Man

Université de Sherbrooke
IFT615 – Intelligence artificielle, Hiver 2017

Professeur: Froduald Kabanza
Auxiliaire d'enseignement: Mariane Maynard

Date de remise: 2017-03-09

Source: The Pac-Man Projects, University of California, Berkeley

Fichiers à télécharger

Introduction

Pour toute question concernant ce travail, envoyez un courriel à Mariane Maynard.

Ce travail doit fonctionner avec la version 2.6 ou 2.7 du langage Python. Voici quelques ressources sur le langage Python qui pourraient vous aider dans votre travail:

Labyrinthe (Source: UC Berkeley)

Pour ce travail, vous devrez implémenter des agents pour la version classique de Pac-Man, incluant les fantômes.

Dans les fichiers fournis pour ce travail, un correcteur automatique est inclus pour évaluer votre implémentation. Celui-ci peut être lancé par la commande: python autograder.py Veuillez noter que votre note finale peut être différente de la note que vous obtenez avec le correcteur automatique.

Le code de ce projet consiste en plusieurs fichiers Python. Seul le fichier multiAgents.py devra être modifié et remis; les autres fichiers peuvent être consultés au besoin, mais ne doivent pas être modifiés. De plus, seules les sections indiquées dans le fichier multiAgents.py doivent être modifiées; les noms des classes et des variables globales ainsi que les signatures des méthodes et des fonctions ne doivent pas être modifiés.

Générateur de nombres aléatoires

Vous pouvez utiliser l'option --fixRandomSeed (ou -f) pour utiliser un seed fixe ('cs188', voir pacman.py à la ligne 534) avec le générateur de nombre aléatoires, de façon à ce que les fantômes aléatoires aient toujours le même comportement d'une exécution à l'autre: python pacman.py -f -p ReflexAgent

Plagiat

Tout cas de plagiat sera sanctionné adéquatement. Voir le document informatif du Groupe de travail antiplagiat de l'Université de Sherbrooke à cet effet.

Agent réactif: 4 points

Lancez l'agent réactif dans multiAgents.py: python pacman.py -p ReflexAgent

Remarquez que cet agent ne se débrouille pas très bien, même dans des labyrinthes simples: python pacman.py -p ReflexAgent -l testClassic

Inspectez le code de cet agent (dans le fichier multiAgents.py) et validez votre compréhension du fonctionnement de cet agent.

Améliorez l'agent réactif dans la classe ReflexAgent du fichier multiAgents.py afin qu'il arrive à jouer de façon respectable. Le code fourni montre quelques exemples d'utilisation de la classe GameState pour obtenir de l'information sur l'état du jeu. Votre agent devrait être capable de compléter facilement et de manière fiable le labyrinthe testClassic: python pacman.py -p ReflexAgent -l testClassic

Les points seront alloués en fonction de certains critères sur 10 exécutions de votre agent dans le labyrinthe openClassic:

Vous pouvez tester votre agent dans le labyrinthe mediumClassic avec un ou deux fantômes (et sans animation pour accélérer l'affichage graphique): python pacman.py --frameTime 0 -p ReflexAgent -k 1
python pacman.py --frameTime 0 -p ReflexAgent -k 2
Votre agent mourra probablement souvent dans ce labyrinthe avec 2 fantômes, à moins que votre fonction d'évaluation soit très bonne.

Essayez d'utiliser des valeurs réciproques des informations importantes (e.g., la distance de Pac-Man aux gommes) plutôt qu'uniquement les informations elles-mêmes dans votre fonction d'évaluation.

Vous pouvez lancer votre algorithme dans les mêmes conditions que le correcteur automatique avec cette commande: python autograder.py -q q1 --no-graphics

Ne passez pas trop de temps sur cette question, le cœur du travail est dans les questions suivantes.

Minimax: 5 points

Implémentez l'algorithme minimax dans la classe MinimaxAgent du fichier multiAgents.py. Votre algorithme doit fonctionner avec un nombre arbitraire de fantômes, et doit donc être légèrement différent de l'algorithme standard. En particulier, l'arbre de recherche aura plusieurs couches min (une pour chaque fantôme) pour chaque couche max.

Votre algorithme doit étendre l'arbre de recherche jusqu'à une profondeur arbitraire (self.depth). Les feuilles de l'arbre doivent être évaluées avec la fonction self.evaluationFunction, qui correspond à scoreEvaluationFunction par défaut.

Le correcteur automatique déterminera si votre algorithme explore le bon nombre d'états de jeu. Celui-ci est très capricieux sur le nombre d'appels à la méthode GameState.getLegalActions; si vous l'appelez plus ou moins souvent que nécessaire, le correcteur automatique pourrait retourner des erreurs.

Vous pouvez évaluer votre code avec cette commange: python autograder.py -q q2 Vous pouvez aussi lancer l'algorithme sans affichage graphique avec l'option --no-graphics.

La bonne implémentation de l'algorithme minimax fera perdre la partie à Pac-Man dans certains tests; puisqu'il s'agit du résultat attendu, le test réussira.

La valeur minimax de l'état initial dans le labyrinthe minimaxClassic est 9, 8, 7, -492 pour les profondeurs 1, 2, 3 et 4, respectivement. Remarquez que l'agent gagnera souvent malgré la sinistre prédiction de la profondeur 4.

Dans des labyrinthes plus grands comme openClassic et mediumClassic, vous remarquerez que Pac-Man est plutôt bon pour éviter de mourir, mais plutôt mauvais pour gagner. Il se promènera souvent sans réellement faire de progrès; il se promènera peut-être même près de gommes sans les manger, parce qu'il ne sait pas ce qu'il ferait après avoir mangé les gommes. Ce comportement est normal; il sera réglé dans la question sur la fonction d'évaluation.

Lorsque Pac-Man croit que sa mort est inévitable, il tentera de terminer la partie le plus rapidement possible. Il ne s'agit pas toujours du meilleur comportement à adopter avec des fantômes aléatoires, mais les agents minimax assument toujours le pire cas: python pacman.py -p MinimaxAgent -l trappedClassic -a depth=3 Essayez de comprendre pourquoi Pac-Man s'élance vers le fantôme le plus proche dans cet exemple.

Élagage alpha-bêta (alpha-beta pruning): 5 points

Implémentez dans la classe AlphaBetaAgent un agent qui utilise l'élagage alpha-bêta pour explorer plus efficacement l'arbre minimax. Votre algorithme doit fonctionner avec un nombre arbitraire de fantômes, et donc être légèrement différent de l'algorithme standard.

Votre algorithme devrait être plus rapide que l'algorithme minimax. Idéalement, l'algorithme ne devrait pas prendre plus que quelques secondes par déplacement à une profondeur de recherche de 3 dans le labyrinthe smallClassic: python pacman.py -p AlphaBetaAgent -a depth=3 -l smallClassic

Les valeurs minimax trouvées par l'agent AlphaBetaAgent devraient être identiques à celles trouvées par l'agent MinimaxAgent; les actions peuvent être différentes si elles produisent des valeurs égales. Encore une fois, la valeur minimax de l'état initial dans le labyrinthe minimaxClassic est 9, 8, 7, -492 pour les profondeurs 1, 2, 3 et 4, respectivement.

Les états successeurs doivent être traités dans le même ordre qu'ils sont retournés par la méthode GameState.getLegalActions afin que le correcteur automatique évalue adéquatement votre code.

Vous ne devez pas élaguer un état si sa valeur est égale à alpha ou à bêta pour que votre algorithme explore les mêmes états que les solutions du correcteur automatique.

Vous pouvez tester votre code avec cette commande: python autograder.py -q q3

La bonne implémentation de l'algorithme d'élagage alpha-bêta fera perdre la partie à Pac-Man dans certains tests; puisqu'il s'agit du résultat attendu, le test réussira.

Expectimax: 5 points

Les algorithmes minimax et alpha-bêta assument que le joueur fait face à des adversaires qui prennent des décisions optimales, bien que cela ne soit cependant pas toujours le cas.

Implémentez, dans la classe ExpectimaxAgent, l'algorithme expectimax, capable de modéliser les comportements probabilistes des agents pouvant prendre des décisions sous-optimales. Vous pouvez tester votre algorithme sur des cas simples avec la commande suivante: python autograder -q q4

Une fois que votre algorithme fonctionne correctement dans ces cas simples, vous pouvez le tester dans Pac-Man pour vérifier qu'il s'y comporte bien. Les fantômes aléatoires ne sont bien sûr pas des agents minimax optimaux, et donc les modéliser avec un algorithme qui fait cette supposition n'est peut-être pas approprié. L'algorithme expectimax ne choisit pas la valeur minimale sur toutes les actions des fantômes, mais choisit plutôt l'espérance selon la modélisation du comportement des fantômes par l'agent. Pour simplifier votre code, assumez que votre agent sera confronté à un adversaire qui choisit ses actions aléatoirement de façon uniforme de l'ensemble retourné par getLegalActions.

Pour voir comment votre agent se comporte dans Pac-Man, lancez la commande suivante: python pacman.py -p ExpectimaxAgent -l minimaxClassic -a depth=3

Vous devriez voir que Pac-Man agit de façon plus cavalière lorsqu'il est près des fantômes. En particulier, si Pac-Man croît qu'il pourrait se faire prendre, mais pourrait arriver à s'échapper et à manger quelques gommes supplémentaires, il tentera sa chance. Vous pouvez observer les résultats dans deux scénarios: python pacman.py -p AlphaBetaAgent -l trappedClassic -a depth=3 -q -n 10
python pacman.py -p ExpectimaxAgent -l trappedClassic -a depth=3 -q -n 10
L'agent expectimax devrait gagner environ la moitié du temps, alors que l'agent alpha-bêta devrait perdre à tous les coups. Assurez-vous de comprendre pourquoi le comportement est différent du cas minimax.

La bonne implémentation de l'algorithme expectimax fera perdre la partie à Pac-Man dans certains tests; puisqu'il s'agit du résultat attendu, le test réussira.

Fonction d'évaluation: 6 points

Implémentez une meilleure fonction d'évaluation pour Pac-Man dans la fonction betterEvaluationFunction. La fonction d'évaluation devrait évaluer des états plutôt que des actions, comme le faisait la fonction d'évaluation de l'agent réactif. Vous pouvez utiliser tous les outils que vous voulez à votre disposition pour l'évaluation des états, incluant les algorithmes de recherche du TP1. Pour une profondeur de recherche de 2, votre fonction d'évaluation devrait réussir le labyrinthe smallClassic avec un fantôme aléatoire plus de la moitié du temps, et devrait prendre un temps raisonnable pour s'exécuter (pour avoir tous vos points, Pac-Man devrait avoir un pointage autour de 1000 lorsqu'il réussit un labyrinthe). Vous pouvez tester votre algorithme avec la commande suivante: python autograder.py -q q5

Les points seront alloués en fonction de certains critères sur 10 exécutions de votre agent dans le labyrinthe smallClassic:

Comme pour l'agent réactif, essayez d'utiliser des valeurs réciproques des informations importantes (e.g., la distance de Pac-Man aux gommes) plutôt qu'uniquement les informations elles-mêmes dans votre fonction d'évaluation.

Une façon d'implémenter la fonction d'évaluation est d'utiliser une combinaison linéaire de plusieurs paramètres, c'est-à-dire de calculer la valeur de différents paramètres que vous considérez importants, de les multiplier par des facteurs déterminant leur importance relative, puis de les combiner en les additionnant.

Bonus: 2 points

Malgré les 2 points bonus, la note maximale pour ce travail sera 25/25, ramenée sur 10 points. Les points supplémentaires ne seront pas rapportés sur les travaux futurs.

Dans cette question, les fantômes seront plus intelligents qu'auparavant: ils pourchasseront Pac-Man au lieu de se mouvoir aléatoirement. Le labyrinthe comportera des impasses, mais aussi plus de gommes pour donner une chance à Pac-Man.

Implémentez un agent dans la classe ContestAgent. Vous pouvez utiliser la procédure de recherche, la profondeur et la fonction d'évaluation de votre choix. Le seul critère est que les parties doivent durer au plus 3 minutes.

Les points seront alloués en fonction de certains critères:

Vous pouvez tester votre agent avec la commande suivante: python autograder.py -q extra

Soumission

Le travail doit être remis par turnin sur le site opus.dinf.usherbrooke.ca au plus tard le 9 mars 2017 à 23:59:59. Remettez uniquement le fichier: multiAgents.py.

Écrivez votre nom, votre matricule et votre adresse courriel en commentaire dans l'entête de chaque fichier.