CSC 3101 – Algorithmique et langage de programmation

Commencez par créer un nouveau projet nommé pacman. Ensuite, créez un package tsp.pacman dans lequel nous mettrons toutes nos classes. Ajoutez une classe Position. Cette classe contiendra un point décrit par une coordonnée row et col. Elle devra implémenter ou surdéfinir les méthodes suivantes :

• Un constructeur public Position(int row, int col)
• Des getters getRow et getCol pour accéder aux attributs.
• Une méthode pour tester l'égalité de deux positions.
• Une méthode pour obtenir le hash d'une position. On pourra pour cela utiliser la méthode Integer.hashcode et faire l'opération hash(x) * 31 + hash(y) (on ne veut pas une opération symétrique).
• Une méthode qui permettra de transformer une position en String.
• Une méthode dist pour calculer la distance entre deux positions. La distance que nous utiliserons sera la distance de Manhattan, donnée par : $$dist(A,B)=|X_A-X_B|+|Y_A-Y_B|$$

Pour tester votre code, écrivez une méthode main dans Position, initialisez deux points à (1, 5) et (4, 3), affichez les, et vérifiez que la distance entre les deux est bien 5.

Nous allons maintenant nous pencher sur la représentation d'un état dans le monde de Pacman. Dans cet exercice, nous considérerons qu'un état est constitué de la position de Pacman, ainsi que du contenu de chaque case. Pour cela, nous utiliserons un double tableau de char. Dans ce tableau, les informations seront encodées de la manière suivante:

• % représente un mur.
• . représente une nourriture.
• Un espace représente une case vide.

Créez une classe PacmanState et écrivez un constructeur prenant en entrée le double tableau et la position de Pacman. Il initialisera les attributs de la classe. Le tableau sera appelé board et la position de Pacman pacmanPosition.

Comme définir des tableaux à la main peut-être assez pénible, nous allons implémenter un nouveau constructeur prenant en entrée une chaîne de caractères. En Java, il est possible de créer une String sur plusieurs lignes de la manière suivante: Dans cette représentation, nous représenterons Pacman avec le caractère P.
Écrivez un nouveau constructeur prenant en entrée une chaîne de caractères et initialisant correctement les attributs. Pour cela, nous aurons besoin des méthodes suivantes déjà implémentées en Java permettant de manipuler les String :

• String strip(): Permet de retirer les espaces et retours à lignes pouvant être présents au début et à la fin d'une String. Cela est utile, car souvent, quand nous avons une String sur plusieurs lignes, il est plus lisible de rajouter des espaces.
• String[] split(String c): Permet de séparer une String en sous-chaînes de caractères en utilisant le caractère c (donné sous forme d'un String) comme délimiteur. C'est par exemple utile pour séparer les lignes en utilisant le caractère de retour à la ligne \n.
• char charAt(int index): Obtient le caractère à un index donné.
• int length(): Donne la longueur de la chaîne de caractères.

Voici un exemple de code utilisant ces fonctions :

Vous allez devoir utiliser strip une première fois pour retirer les sauts de lignes potentiels au début et à la fin de la String. Ensuite, vous devez faire un split("\n") pour obtenir un tableau de String ou chaque ligne est séparée. Il faudra alors itérer sur cette ligne et itérer sur chaque caractère de cette ligne pour utiliser charAt(int index). Le caractère à la ligne i et à l'index j sera dans this.board[i][j]. On prendra garde de traiter le cas avec Pacman à part.
Pour initialiser le tableau, vous pourrez utiliser le nombre de lignes et la longueur de la première ligne (il y a toujours au moins une ligne).

Ajouter des méthodes int getWidth() et int getHeight() qui retourne la hauteur et la largeur du tableau.

Écrivez une méthode char get(Position position) et void set(Position position, char value) permettant respectivement d'obtenir le caractère à une position donnée et d'affecter un caractère à une position donnée.

Écrivez une méthode pour obtenir la représentation textuelle d'un état. Vérifiez que vous retrouvez bien la représentation donnée en exemple plus haut.
Pour tester votre code, vous pouvez créer une méthode main dans la classe PacmanState.
Pour la représentation textuelle, vous devez redéfinir la méthode toString. Vous pouvez soit utiliser la concaténation de String avec + ou la classe StringBuilder donnée par Java qui est plus rapide.
N'oubliez pas d'afficher Pacman !

Écrivez une méthode Position findPacman() donnant la position de Pacman et une méthode List<Position> findFoods() donnant la position de toutes les nourritures. Cette dernière méthode devra retourner une ArrayList.
Testez votre code dans le main.
Nous rappelons que ArrayList est une classe générique définie par Java qui correspond aux tableaux extensibles. Pour rajouter un élément à cette liste, vous pouvez utiliser la méthode add. Pour accéder à un élément, vous pouvez utiliser la méthode get (et non les crochets !).

Dans son monde, Pacman ne peut se diriger que dans quatre directions (haut, bas, gauche, droite) à condition qu'il n'y ait pas de murs.
La liste des positions où Pacman peut se rendre dans l'état actuel constitue les actions disponibles à Pacman. En règle générale, une IA doit choisir une action étant donné un état du système. Par exemple, les actions aux échecs sont la liste des coups légaux. Pour une IA qui génère du texte comme ChatGPT, l'état est la liste des mots précédents de la conversation et les actions sont la liste des mots de son vocabulaire.
Écrivez une méthode List<Position> findPossibleMoves(Position position) qui nous donne toutes les positions où un Pacman à la position position peut se déplacer légalement. Le résultat sera une ArrayList en interne.
Comme cette méthode sera souvent utilisée avec la position de Pacman en argument, on définira une méthode List<Position> findPossibleMoves() qui retournera le résultat de findPossibleMoves appelé sur pacmanPosition.
Vérifiez dans le main que pour notre exemple, il n'y a qu'une seule action légale.

Le succès d'une IA dépend grandement de la capacité à simuler les états suivants du système. Autrement dit, étant donné un état et une action, il nous faut créer l'état suivant. Cette simulation peut être exacte (Pacman, échecs) mais aussi approximative (poser un robot sur Mars en simulant la physique).
Quand nous simulons les successeurs d'un état, il est très important de ne pas modifier l'état actuel ! Comme nous le verrons par la suite, nous aurons besoin d'y revenir. Pour cela, nous allons devoir copier notre tableau interne. Implémentez une méthode char[][] copyBoard() qui copie le tableau.
Attention de ne pas copier des références !
Pour la copie, il faut recréer un nouveau tableau avec la bonne taille et faire une double boucle.

Une fois cette copie effectuée, implémentez une méthode PacmanState move(Position to) qui, étant donné une position, simule l'état suivant sans modifier l'état actuel. On considèrera que quand Pacman quitte une position, il laisse derrière lui une case vide. On rappelle qu'il faut créer un nouvel état et ne pas modifier l'état actuel.
Pour tester votre code, faites bouger Pacman en (3, 7) et vérifiez qu'il a maintenant deux actions légales.

Pour qu'une IA existe, il faut qu'elle ait un objectif. Cet objectif peut prendre plusieurs formes. Dans des cas précis comme Pacman, il est possible de définir ce qu'est un état final que l'on veut atteindre. Par exemple, un état final est un état tel qu'il n'y ait plus de nourritures à manger. Dans d'autres cas, l'état final n'existe pas et il nous faut donc une métrique pour mesurer notre succès. Par exemple, ChatGPT essaie de maximiser la probabilité que sa réponse soit correcte avec un nombre de mots limités.
Écrivez une méthode boolean isFinalState() déterminant si nous avons atteint un état final.
Tester que notre exemple n'est pas un état final et que, si l'on enlève la seule nourriture, il devient final.
Vous pouvez utiliser la méthode findFoods écrite plus haut.

Manger toutes les nourritures est certes l'objectif principal, mais un objectif secondaire consiste à le faire en un minimum d'étapes. Ajoutez un attribut int score qui compte le nombre déplacements de Pacman. Ce nombre sera augmenté de 1 à chaque appel à la méthode move pour le nouvel état créé.
On écrira également une fonction getScore permettant d'obtenir le score d'un état.
Testez que l'état initial a bien un score de 0 et l'état après un déplacement un score de 1.
N'oubliez pas de modifier move !

Finalement, nous allons utiliser notre PacmanState dans des structures de données ayant besoin de vérifier l'égalité de deux états, mais aussi de calculer des hashs d'états. Écrivez ces fonctions. Pour cela, les méthodes suivantes peuvent vous faciliter la vie:

• Arrays.deepEquals : Permet de vérifier l'égalité de tableaux imbriqués.
• Arrays.deepHashCode : Permet de calculer le hash de tableaux imbriqués.

Nous rappelons qu'il faut redéfinir les méthodes boolean equals(Object o) et int hashCode().

Nous allons créer un simulateur complet pour notre IA. Pour cela, créez l'interface Pacman qui devra n'avoir d'une seule méthode Position chooseAction(PacmanState state). Toutes nos IA devront implémenter cette interface.

Notre simulateur de Pacman va devoir gérer l'exécution d'une partie. Pour cela, il va devoir implémenter une "Game Loop" (boucle de jeu) simplifiée. Une game loop est un concept classique dans les jeux videos : il s'agit d'une boucle se répétant à l'identique pendant toute la partie et guidant tous les événements à chaque instant du jeu.
Pour notre Pacman, notre boucle va s'exécuter jusqu'à ce que nous ayons atteint un état final. À chaque étape de la boucle, notre simulateur :

• Demande à notre IA de choisir une action pour l'état actuel.
• Remplace l'état actuel par l'état suivant l'action.
• Met à jour l'affichage. Pour cela, il faut appeler la fonction update(state) de PacmanVisualizer.
• Patiente un certain laps de temps (pour pouvoir humainement voir ce qui se passe). Pour cela, vous pouvez utiliser la fonction System.currentTimeMillis() qui donne le temps actuel en millisecondes et une boucle while vide.

Commencez par créer une classe PacmanSimulator avec un constructeur prenant en entrée l'état initial (PacmanState state), l'IA (Pacman pacman) et la période de rafraichissement en millisecondes (int refreshPeriod). Le constructeur devra également créer un attribut PacmanVisualizer pv. Toutes ces variables sont à stocker dans des attributs.
Implémentez ensuite la boucle de jeu dans une méthode void gameLoop() et affichez le score une fois la partie finie.

Écrivez une méthode main dans la classe PacmanSimulator. Dans cette classe, créez un état initial en utilisant l'exemple donné plus haut. Ensuite, créez un Pacman qui se déplace de manière aléatoire. Pour cela, utilisez une classe anonyme. Ensuite, initialisez un PacmanSimulator et visualiser que votre Pacman n'est pas encore intelligent. On prendra une période de rafraichissement de 500ms (que l'on pourra adapter selon les besoins).
Pour obtenir un index aléatoire dans une ArrayList, on peut faire (int)(Math.random() * positions.size()).

Nous allons visualiser les algorithmes de parcours à l'aide de notre simulateur. Pour cela, nous supposerons que Pacman peut se téléporter. De plus, chaque position visitée par Pacman sera marquée de la lettre V : modifiez la méthode move pour que ce soit le cas.
Testez votre code avec le Pacman aléatoire et remarquez que toutes les positions visitées deviennent vertes.

Dans le CI5, nous avons implémenté un parcours en profondeur. Maintenant que nous avons accès aux collections de Java, nous allons voir que notre travail est grandement simplifié. Nous rappelons qu'un parcours en profondeur consiste à privilégier les états loins de l'état initial. En d'autres termes, les états découverts récemment dans l'exploration seront exploités en premier.
Quelle structure de données vous semble la plus adaptée pour cet algorithme, c'est-à-dire à accéder aux nouveaux éléments en premier ? Vous pouvez consulter une liste de structures de données et d'algorithmes ici.
Les différents parcours utilisent soit Stack (pile), soit Queue (une file, à travers LinkedList), soit PriorityQueue (une file de priorité).

Créez une nouvelle classe PacmanDFSTeleport qui met en œuvre Pacman. Implémentez la recherche en profondeur dans chooseAction. On pourra initialiser la structure choisie à la question précédente dans le constructeur. À chaque fois qu'un nouvel état est exploité (c'est-à-dire, que l'on appelle findPossibleMoves) dans la recherche, nous considérons que Pacman s'y déplace en se téléportant. Nous rappelons que, pour l'instant, Pacman peut se téléporter.
Il est important que PacmanDFSTeleport se souvienne des positions déjà visitées. Il faudra pour cela utiliser la structure de données idoine et l'initialiser dans le constructeur.
Visualizer votre recherche en créant un nouveau Pacman.
Vous allez devoir utiliser un HashSet. Il vous faut initialiser deux champs dans le constructeur : HashSet<Position> visited et Stack<Position> toVisit. Voici le pseudo code de l'algorithme dans chooseAction:

* Pour chaque action légale: * Si la position suivante n'a pas été vue dans le passé: * Marquez la position comme vue (dans visited). * Rajouter la position dans la Stack toVisit (push). * Retourner le prochain élément de la Stack toVisit (pop).

À l'opposé de la recherche en profondeur, la recherche en largeur privilégie les positions non visitées les plus proches du point de départ. En d'autres termes, il s'agit des états rencontrés et non visités les plus vieux.
Quelle structure de données vous semble la plus adaptée pour cet algorithme ?
Les différents parcours utilisent soit Stack (pile), soit Queue (une file, à travers LinkedList), soit PriorityQueue (une file de priorité).

Créez une nouvelle classe PacmanBFSTeleport qui met en œuvre Pacman. Implémentez la recherche en largeur. Le code devrait être très similaire à celui de PacmanDFSTeleport, seule la structure de données change.
Visualizer votre recherche.

Nous allons maintenant implémenter un algorithme appelé A* (A étoile ou A star). Il s'agit d'un algorithme d'exploration comme la recherche en profondeur et la recherche en largeur. La différence est que le système de priorité n'est pas donné par l'ordre de visite des positions, mais par une fonction appelée heuristique. Une heuristique est une approximation de la distance (dans le monde de Pacman) d'une position à la position finale. Meilleure est l'estimation, plus rapide sera l'algorithme.
Commencez par créer une classe PacmanAStarTeleport qui met en œuvre Pacman.
Dans cet exercice, nous considèrerons que la priorité d'une position dans l'exploration est donnée par sa distance de Manhattan avec l'état final + le coût déjà payé pour atteindre la position actuelle (c'est-à-dire le score implémenté plus haut). Comme la priorité dépend de la position de la nourriture, nous devons transmettre l'état initial au constructeur.
Pour nous rappeler du coût pour atteindre une position, nous allons utiliser une champ cout de type HashMap<Position,Integer> que nous allons initialiser dans le constructeur. De plus, on précisera que le coût de la position initiale de Pacman est 0.
Dans le constructeur, initialisez aussi une file à priorité PriorityQueue (qui sera un champ et que vous appellerez toVisit) pour que la priorité soit donnée par la distance de Manhattan additionnée au coût de la position (HashMap créer au-dessus). Pour utiliser une PriorityQueue, nous allons utiliser son constructeur qui demande en paramètre une référence sur un objet qui met en œuvre l'interface Comparator: @FunctionalInterface public interface Comparator<T> { int compare(T o1, T o2); } Pour cela trois possibilités s'offrent à vous :

• Écrire une nouvelle classe qui met en œuvre l'interface Comparator, et créer un objet de cette classe, puis passer la référence sur cet objet en paramètre du constructeur de PriorityQueue
• Passer en paramètre du constructeur de PriorityQueue la référence obtenue par la création d'une classe anonyme qui met en œuvre l'interface Comparator
• Passer en paramètre du constructeur PriorityQueue la référence obtenue par une expression lambda qui met en œuvre l'interface Comparator

Dans cet exercice, nous vous proposons d'utiliser une expression lambda pour implémenter un Comparator . Pour implémenter la méthode int compare(T o1, T o2); du comparateur, la méthode Integer.compare vous sera utile. Vous pouvez aussi utiliser Comparator.comparingInt().

Votre lambda expression sera de la forme: (position1, position2) -> Integer.compare(valeur heuristique position1, valeur heuristique position2) Donc les instructions pour créer la PriorityQueue auront la forme suivante : toVisit = new PriorityQueue( (position1, position2) -> Integer.compare(valeur heuristique position1, valeur heuristique position2)); );

Implémentez maintenant Position chooseAction(PacmanState state) de PacmanAStarTeleport. Le code devrait être très similaire à la recherche en profondeur et en largeur.
Visualizer votre recherche.
N'oubliez pas de mettre à jour cost quand on rencontre un état pour la première fois.

Maintenant que nous avons visualisé nos algorithmes, nous pouvons remettre la fonction move comme elle l'était à l'origine. Faites en sorte que ce soit le cas.

En vous inspirant du code que vous avez implémenté pour A*, écrivez une fonction List<Position> goTo(Position from, Position to) dans PacmanState qui nous donne le chemin optimal entre deux positions.
Pour cela, les champs que nous avons utilisés deviendront des variables. Nous devrons aussi nous rappeler comment chaque Position a été atteinte, c'est-à-dire conserver une HashMap nous indiquant la position précédente dans l'exploration de chaque position.
Précédemment, chooseAction était appelée à chaque fois que nous voulions explorer une nouvelle position. Maintenant, il va falloir faire une boucle qui continue tant qu'il y a des états à explorer (!toVisit.isEmpty()) et que nous n'avons pas atteint la position finale.
Après la boucle, il va falloir reconstituer un chemin de la position initiale à la position finale. On pourra pour cela utiliser une LinkedList.

Nous allons reprendre l'algorithme A* vu plus haut pour créer un plan d'actions nous permettant de manger toutes les nourritures le plus rapidement possible. Pour cela, créer une classe PacmanAStar qui met en œuvre Pacman.
Comme précédemment, nous avons besoin d'une heuristique pour évaluer non plus une position, mais un état. Écrivez une fonction int calculateHeuristic(PacmanState state) qui pour l'instant retourne le nombre de nourritures restant.

En vous inspirant de l'implémentation de la fonction goTo de l'exercice précédent, écrivez la fonction chooseAction implémentant A* pour trouver un plan optimal. Rappelez-vous que maintenant, les positions sont des états et que nous nous déplaçons d'un état à l'autre avec move.
Attention, un plan est toujours constitué d'une séquence de positions, même si l'on raisonne à l'échelle des états.

Comme calculer un plan peut-être assez long et que, dans notre cas, le monde est statique (à part Pacman), vous pouvez sauvegarder votre plan dans un attribut et le réutiliser dans les appels suivants. Implémentez cette sauvegarde.
Voici quelques exemples de mondes sur lesquels tester votre code: Votre score devrait être de 27 et 34 (le score devrait être affiché à la fin de la boucle de jeu).

La vitesse de A* va dépendre du nombre d'états explorés. Ajoutez un compteur à votre fonction chooseAction qui s'incrémente à chaque état exploré, c'est-à-dire sur lequel on a appelé findPossibleMoves. Testez votre code sur le monde suivant: Vous devriez explorer moins de 15,000 états et avoir un score de 60.

(optionnel, difficile) Comme mentionné plus haut, l'efficacité de A* dépend de son heuristique. Modifiez la fonction calculateHeuristic pour essayer d'accélérer A*. L'objectif ultime serait de descendre en dessous de 7,000 états explorés !
Pour concevoir une bonne heuristique, essayez de voir quels sont les critères ou les métriques qui donnent une idée si un état est meilleur qu'un autre.
Idées de métriques : La distance minimale à une nourriture, la distance maximale entre deux nourritures.

Essayez maintenant votre Pacman sur le monde suivant:
Que remarquez-vous ? Pourquoi ?

Implémentez un Pacman non optimal PacmanClosest qui va manger la nourriture la plus proche.

Nous allons stocker la position de tous nos fantômes dans un tableau de positions. Créez ce nouvel attribut Position[] ghostPositions dans PacmanState. Ensuite, créez un nouveau constructeur prenant en entrée le monde de Pacman sous forme de tableau, la position de Pacman, et la position des fantômes. Modifiez ensuite les deux autres constructeurs de la manière suivante:

• Pour le constructeur avec uniquement la position de Pacman et le monde, on considère qu'il n'y a pas de fantôme.
• Pour le constructeur lisant à partir d'une String, nous introduisons un nouveau caractère pour les fantômes: G.

Modifiez la fonction qui donne la représentation textuelle d'un état pour prendre en compte les fantômes. Testez votre code sur le monde suivant :

Écrivez une fonction Position[] findGhosts() donnant la position de tous les fantômes.

Ajoutez les fantômes impacte un certain nombre de méthodes. Modifiez les méthodes :

• findPossibleMoves pour qu'un déplacement sur un fantôme ne soit plus permis.
• move pour bien copier les fantômes dans le nouvel état.
• isFinalState qui doit maintenant retourner vrai quand Pacman meurt, c'est-à-dire quand il est sur la même case qu'un fantôme.
• equals qui doit prendre en compte les fantômes pour l'égalité entre états.
• hashCode qui doit ajouter le hash des positions des fantômes.

Maintenant qu'il y a deux manières de terminer le jeu et d'atteindre un état final (en mourant ou en ramassant toutes les nourritures), nous devons discriminer les états finaux gagnants des états finaux perdants. Écrivez les méthodes boolean isWon() et boolean isLost() qui nous disent si nous avons gagné ou perdu.

Écrivez une méthode PacmanState moveGhost(Position from, Position to) permettant de déplacer un fantôme. Attention, tout comme move, vous ne devez pas modifier l'état actuel, mais en créer un nouveau.
En réalité, il faut seulement modifier le tableau des positions des fantômes. Parcourez ce tableau et modifier la position du premier fantôme à la position from pour qu'il soit à la position to.

Finalement, nous voulons savoir quel est le prochain agent (c'est-à-dire IA ici) à jouer. Nous allons considérer que Pacman joue toujours en premier, puis chaque fantôme bouge à tour de rôle en fonction de leur position dans la structure interne de l'état implémentée plus haut.
Nous allons représenter le joueur actuel avec un entier. L'entier 0 représente Pacman, et l'entier i représente le fantôme i - 1. Ajoutez cet attribut currentPlayer et modifiez les constructeurs pour l'initialiser. Écrivez ensuite un getter (getCurrentPlayer).
Enfin, vous devez modifier les méthodes move et moveGhost pour mettre à jour le joueur actuel.

Tout comme pour Pacman, créez une classe abstraite Ghost avec une seule méthode : Position chooseAction(PacmanState state, Position position). Notez que cette fois, nous devons passer la position du fantôme qui doit choisir son action.
Créer un nouveau constructeur de PacmanSimulator permettant de prendre en plus des autres arguments un Ghost que l'on stockera dans les attributs.

Modifiez ensuite la boucle de jeu pour y ajouter les fantômes. On considère que pendant une boucle, Pacman et tous les fantômes bougent exactement une fois, et que l'affichage est mis à jour après tous les déplacements. En détails, vous devez :

• Demander à tour de rôle à chaque fantôme de bouger et modifier à chaque fois l'état actuel.
• Quand on sort de la boucle après avoir atteint un état final, nous devons afficher le score si nous avons gagné. Sinon, nous afficherons un message nous disant que nous avons perdu ainsi que le nombre de nourritures restantes.

Nous pouvons maintenant tester notre nouveau simulateur. Pour cela, créez un RandomGhost se déplaçant aléatoirement. Gardez votre PacmanClosest pour les tests. Vous devriez observer que Pacman a un peu plus de mal et meurt souvent, même si les fantômes ne font rien de très intelligent.

Pour ajouter du piquant au jeu, nous allons implémenter un fantôme directionnel qui, à chaque intersection choisit une direction (haut, bas, gauche, droite) et la suit jusqu'à la prochaine intersection ou jusqu'à être obligé de changer de direction (dans un virage par exemple). Il évitera toutefois de faire des demi-tours si possible.
Implémenter un fantôme direction GhostDirectional.
On fera attention que, dans notre cas, il faudra que GhostDirectional se souvienne de la direction précédente de chaque fantôme séparément.
Vérifiez le comportement de vos fantômes.

Les algorithmes que nous allons voir explorent les états jusqu'à une certaine profondeur et utilisent une fonction d'évaluation pour noter les états. Minimax fait cela de manière uniforme pour toutes les actions et alterne Pacman et fantômes.
L'idée de l'algorithme Minimax est que nous avons deux types d'agents : les agents max qui cherche à maximiser le score (Pacman) et les agents min qui cherchent à le diminuer (les fantômes). Cela signifie qu'un agent max choisira toujours l'action qui mène vers l'état avec le score le plus haut alors qu'un agent min choisira l'action qui mène vers l'état avec le score le plus bas. Le schéma suivant illustre le processus.




Pour commencer, créez une classe PacmanMinimax qui met en œuvre Pacman et dont le constructeur prend la profondeur en argument. En vous inspirant de la fonction implémentée pour A*, écrivez une fonction calculateHeuristic qui retourne le score d'un état, sachant que plus le score est haut, meilleur est l'état. De plus, on fera attention de donner des scores très hauts en cas de victoire et des scores très bas en cas de défaite.

Voici le pseudo-code de Minimax: Implémentez la méthode minimax puis utilisez cette méthode dans chooseAction.
Testez votre Pacman Minimax avec différente profondeur. Il devrait mieux survivre maintenant.
Pourquoi le temps de calcul augmente-t-il avec la profondeur ? Donnez la complexité en fonction de la profondeur.
Trouvez une profondeur donnant des temps de calculs raisonnables.

Minimax peut être optimisé en supprimant des branches non prometteuses. Imaginons que nous sommes un agent max Pacman. Plus haut dans la recherche, un agent min (un fantôme) connait déjà un chemin avec une valeur v. Cela signifie que si notre agent trouve un état avec une valeur supérieur à v, tout son travail va être ignoré, car le fantôme plus tôt dans l'exploration ne choisira pas les explorations actuelles. Le même raisonnement s'applique aux agents min.
Cela nous permet de dériver un algorithme appelé l'élagage AlphaBeta qui est une optimisation de Minimax. En voici le pseudo-code:

Au début, alpha et beta sont initialisés à Integer.MIN_VALUE et Integer.MAX_VALUE.
Implémentez dans une classe PacmanAlphaBeta alphabeta puis utilisez cette méthode dans chooseAction.
Quelle est la complexité de alphabeta ? Observez-vous une plus grande vitesse de calcul par rapport à Minimax pour des profondeurs identiques ?

Le dernier algorithme que nous allons voir est celui utilisé par la plupart des IAs aujourd'hui pour le genre de jeu qui nous intéresse. En particulier, AlphaZero l'utilise. Il s'agit de la Recherche arborescente Monte-Carlo (Monte-Carlo Tree Search, MCTS). L'idée de cette méthode est de lancer de nombreuses simulations aléatoires qui vont nous permettre d'évaluer au mieux la valeur d'un état. Plus nous auront de simulations, plus la valeur sera précise. Le fait d'utiliser des simulations aléatoires va d'une part nous faire moins dépendre de la fonction de score, et d'autre part, nous permettra d'explorer des profondeurs plus élevées que Minimax.
En réalité, MCTS ne consiste pas uniquement en des simulations aléatoires. Nous avons aussi un arbre "dur" d'états pour lesquels nous avons une estimation du score. À chaque itération de l'algorithme, nous allons choisir une feuille de l'arbre des états à partir de laquelle nous allons faire les simulations. Ce choix est un compromis entre explorer de nouveaux nœuds ou essayer d'affiner davantage l'évaluation du score. Ensuite, pour ce nœud, nous ajoutons tous ses fils à l'arbre et exécutons une simulation aléatoire. La simulation s'exécute jusqu'à un état final ou une profondeur maximale. L'état est alors évalué et son score est propagé dans l'arbre.
Un arbre MCTS est illustré dans la figure suivante :

Commencez par créer un nœud de cet arbre appelé MCTSNode. Son constructeur prendra soit uniquement un état (nœud racine) que l'on stockera dans un champ PacmanState state;, soit un état et le nœud parent, que l'on stockera dans un champ MCTSNode parent. Ensuite, la classe contiendra deux attributs pour calculer le score moyen : double totalScore et int totalVisits. Initialisez-les.

Nous allons mettre en place la procédure de mise à jour du score. Lorsqu'une simulation est finie, nous mettons à jour le score moyen du nœud source de la simulation, ainsi que de tous les parents. Écrivez une fonction void addScore(double score) mettant à jour tous les scores. Cette étape s'appelle la backpropagation.

Le score moyen est donné par totalScore / numberVisits.
Le nœud racine n'a pas de parent, c'est-à-dire l'attribut parent est null.

Pour sélectionner un nœud source de la simulation, nous devons utiliser une métrique appelée UCB : $$\frac{totalScore}{totalVisits}+C*\sqrt{\frac{log(totalVisitsParent)}{totalVisists}}$$
Cette métrique est composée de deux parties : La première est simplement le score moyen du nœud. La deuxième permet de contrôler l'exploration de nœuds moins visités à l'aide de la constante C.
Pour sélectionner le nœud source de la simulation, on sélectionne successivement le fils avec le plus fort UCB (en fonction de C), jusqu'à atteindre une feuille. Par contre, nous considérerons que le score est totalScore si l'agent actuel est Pacman et -totalScore sinon (comme pour Minimax, les fantômes choisissent la pire action pour Pacman).
Commencez par rajouter un attribut List<MCTSNode> sons à MCTSNode. Celui-ci vaut null pour une feuille. Ensuite, écrivez une fonction MCTSNode selectLeaf(double C) qui implémente ce mécanisme de sélection.

Implémentons maintenant l'expansion d'un nœud. Celle-ci consiste à agrandir l'arbre pour rajouter les fils du nœud actuel.
Écrivez la méthode void generateSons() qui va rajouter les fils au nœud actuel en fonction de l'agent actuel. On modifiera l'attribut sons créé plus haut.
N'hésitez pas à créer des sous-fonctions List<MCTSNode> getSonsPacman() et List<MCTSNode> getSonsGhosts(Position positionGhost).

La dernière fonction de MCTS à implémenter est la simulation. Cette dernière va se faire en choisissant les actions de manière aléatoire jusqu'à ce qu'un état final soit atteint ou jusqu'à une profondeur maximale. Une fois finie, nous calculons le score du dernier état qui sera défini par:

• Le nombre de nourritures restantes * -1 pour un état non final.
• Le score pour une victoire.
• Le nombre de nourritures restantes * -2 pour une défaite.

On évite de prendre des valeurs trop grandes pour ne pas perturber trop les moyennes.
Quand nous avons le score, nous pouvons mettre à jour le score du nœud actuel avec la méthode addScore.
Écrivez une méthode void runSimulation(int maxDepth) effectuant la simulation et mettant à jour les scores.
N'oubliez pas de faire jouer Pacman et les fantômes.

Pour visualiser votre arbre, écrivez une fonction void printTree(int depth) qui affiche l'arbre jusqu'à une profondeur donnée maximale. Chaque nœud de l'arbre sera indentée en fonction de sa profondeur et pour chaque nœud, nous voulons afficher totalVisits, totalScore et l'UCB (avec C=1).

Finalement, écrivez PacmanMCTS qui met en œuvre Pacman. Cette classe prendra trois arguments dans son constructeur : le temps maximum d'exécution (MCTS a l'avantage pour pouvoir plus facilement contrôler les temps de calcul), la profondeur maximale des simulations et le paramètre C de UCB.
Dans chooseAction, on crée un nouvel arbre et tant qu'il reste du temps, on sélectionne une feuille, on l'étend, et on lance une simulation depuis un des fils.
chooseAction retourne la position de Pacman de l'état du fils de la racine avec la meilleure moyenne.

Testez votre code en essayez de trouver une bonne valeur pour C. Afficher l'arbre peut-être utile.

Les simulations effectuées lorsque l'on choisit une action pour Pacman ne sont pas toutes à jeter. La branche qui correspond à la réalité peut-être récupérée pour accélérer les futurs calculs. Écrivez une fonction de mémorisation qui permettra de conserver les calculs d'un appel de chooseAction à l'autre.
On pourrait avoir un HashMap<PacmanState, MCTSNode> stateToNode dans les attributs et faire attention de supprimer le parent du nouveau nœud racine.

Vous pouvez continuer d'améliorer votre algorithme en modifiant par exemple l'heuristique de notation de l'état final lors de la simulation.