Pyrat est un jeu consistant à se faire affronter deux joueurs qui doivent trouver plus de fromages que l'autre dans un labyrinthe. De la boue peut être présente entre des cases et cela fait ralentir le joueur. Par exemple, s'il est écrit 10 sur la boue, cela signifie que pendant que le joueur traverse la boue l'autre joueur peut parcourir 10 cases (si lui-même ne traverse aucune boue).
L'objectif de ce projet académique de 1ère année à l'IMT Atlantique est d'implémenter les fonctions associées aux joueurs en utilisant différentes stratégies pour gagner le plus rapidement possible.
Cette section détaille les différentes approches implémentées pour permettre au rat de naviguer et de collecter les fromages.
- Algorithmes de traversée (bas niveau) Ce sont les briques de base utilisées pour calculer les distances et explorer le labyrinthe.
DFS (DFS.py) : Exploration en profondeur. Utilisé pour parcourir le graphe de manière récursive et établir une table de routage de base.
Dijkstra (Dijkstra.py) : Algorithme de recherche de chemin optimal. Il garantit de trouver le chemin le plus court entre deux points en tenant compte du poids des arêtes.
- Stratégies de collecte (haut niveau) Ces scripts définissent comment le joueur choisit sa prochaine cible.
Glouton (tous les Greedy) :
Principe : Le joueur identifie le fromage le plus proche à chaque étape et s'y rend immédiatement.
Variantes : Les versions successives (Greedy1, 2, 3) optimisent la gestion du "meta-graphe" (un graphe complet représentant les distances entre tous les fromages).
Exhaustif (Exhaustive.py) :
Principe : Calcule toutes les permutations possibles de l'ordre de collecte des fromages pour trouver le chemin globalement le plus court.
Note : Très précis, mais coûteux en temps de calcul (limité par la complexité factorielle).
- Intelligence Artificielle Avancée (AI.py) Le fichier AI.py contient une logique plus complexe intégrant :
Analyse de l'adversaire : Utilisation de la méthode suivre() pour détecter si l'adversaire cible le même fromage que nous.
Prise de décision dynamique : Calcul de la rentabilité d'un déplacement en fonction de la position du joueur adverse et du score actuel.
Les fichiers ipynb visualize permettent de visualiser des parties entre les ordinateurs. Cependant certains visualize ne fonctionnent pas en l'état car la fonction get_neighbors fournie par l'école est obsolète.