Activité pratique

Durée2h30

Consignes globales

Cette activité pratique a pour but de vous préparer au projet PyRat. Elle consiste en deux grandes parties :

  • Vous allez installer le logiciel et écrire votre premier programme pour vous déplacer dans le labyrinthe. Vous allez également mettre en place un dépôt Git, afin de travailler efficacement en groupe.

  • Puis, vous serez guidé(e)s dans l’écriture de votre premier programme PyRat.

Cette mise en place peut être assez longue, mais elle est essentielle pour bien attaquer le projet. Si vous ne parvenez pas à tout faire dans la séance, terminez en dehors avant la prochaine.

N’oubliez pas que nous pouvons vous aider entre les séance via le serveur Discord du cours. Vous devriez dès à présent le rejoindre si ça n’est pas déjà fait.

Important

Pensez à bien suivre les étapes décrites sur cette page dans l’ordre, en particulier pour l’installation de PyRat et la mise en place du dépôt Git. Il y a parfois des petits détails importants qui, si vous lisez en diagonale, peuvent vous faire perdre beaucoup de temps.

À faire

Vous trouverez plus bas des boîtes “À faire” indiquant les étapes où vous devez agir.

Contenu de l’activité

1 — Où trouver PyRat ?

Le plus important à connaître est le site principal du logiciel PyRat, qui centralise tous les éléments de prise en main :

  • Documentation : Cette page regroupe les éléments de documentation sur comment installer et utiliser PyRat. La documentation présente aussi l’API PyRat, c’est à dire les fonctions fournies par la bibliothèque. Nous y avons également ajouté quelques tutoriels, qui constitueront la base de cette activité pratique.

    Information

    Comme pour la plupart des logiciels que vous rencontrerez dans votre vie, la documentation de PyRat est rédigée en anglais. Si vous passez par des outils de traduction automatique, il peut arriver d’observer des petites différences avec les termes utilisés dans le cours. N’hésitez pas à en discuter avec nous.

    Important

    Autre remarque, le code de PyRat est également rédigé en anglais. Dans ce projet, nous vous demandons de produire vos codes, commentaires et documentations en anglais également. C’est une pratique essentielle dans le métier d’ingénieur, où vous serez amené(e)s à travailler dans des contextes internationaux.

Voici également quelques liens secondaires, qui pourront vous être utiles plus tard :

  • PyPI : La page de référence pour l’installation de PyRat via pip.

  • GitHub : Ce dépôt GitHub contient les codes sources du logiciel PyRat. Quand nous travaillons à une nouvelle version du logiciel, c’est là que nos modifications sont publiées.

  • GitHub issues : Les issues GitHub sont une sorte de forum, où sont discutés les possibles problèmes rencontrés par les utilisateurs lors de l’installation ou l’utilisation du logiciel. C’est une bonne pratique de consulter cette page si vous rencontrez des difficultés.

2 — Préparer l’environnement du projet

Dans cette section, nous allons préparer l’environnement de travail pour le projet PyRat. Pour cela, nous allons créer l’arborescence de dossiers suivante.

ueinfos5                # Là où vous stockez vos fichiers du cours d'informatique (adaptez à votre organisation)
|_ projet               # Un sous-dossier pour le projet PyRat (à créer dès maintenant)
|_ |_ venv_projet       # L'environnement virtuel (créé en 2.1)
|_ |_ pyrat_workspace   # Le workspace PyRat (créé en 2.2)
|_ |_ |_ games
|_ |_ |_ players
|_ |_ |_ README.md      # Le fichier de description du projet (créé en 2.3.2)
|_ |_ |_ .gitignore     # Un fichier qui indique à Git quoi synchroniser (créé en 2.3.3)
|_ ...
À faire

Créez un dossier projet vide là où vous stockez vos fichiers de cours d’informatique. Puis, ouvrez un terminal et naviguez jusqu’à ce dossier.

Correction

C’est assez direct. Penser éventuellement à ne pas tout mettre en vrac sur le bureau. Voici une bonne arborescence :

IMT
|_ S5
|_ |_ info
|_ |_ |_ projet

Dans ce projet, nous allons travailler avec l’IDE VSCode. Vous pouvez en utiliser un autre si vous préférez, il vous suffira d’adapter les instructions.

1.1 — Créer un environnement virtuel Python

Afin de faciliter la séparation des dépendances d’un projet à l’autre, Python impose de passer par un environnement virtuel pour l’installation de bibliothèques logicielles. Nous allons installer PyRat dans un tel environnement.

À faire

En utilisant le terminal ouvert précédemment, créez un environnement virtuel Python dans le dossier projet (par exemple nommé venv_projet). Puis, activez cet environnement virtuel.

Correction

Pour créer l’environnement virtuel : python3 -m venv venv_projet (adapter python3 en python ou py si nécessaire).

Pour l’activer :

  • Sous Linux/Mac : source venv_projet/bin/activate.
  • Sous Windows (PowerShell) : .\venv_projet\Scripts\Activate.ps1.
  • Sous Windows (cmd) : .\venv_projet\Scripts\activate.bat.

2.2 — Télécharger et installer PyRat

À présent, nous allons installer la bibliothèque PyRat dans l’environnement virtuel venv_projet activé précédemment.

À faire

Trouvez la page décrivant l’installation dans la documentation de PyRat, et suivez les instructions.

Quelques remarques importantes :

  • Pensez à bien activer l’environnement virtuel venv_projet avant d’installer PyRat.
  • L’installation de PyRat ne s’arrête pas au pip install pyrat-game, il faut aussi créer le workspace PyRat. La commande correspondante est indiquée dans le guide d’installation.
  • Le workspace PyRat doit être créé dans le dossier projet, à côté de venv_projet (pas dedans).
  • La commande qui crée le dossier pyrat_workspace ajoute automatiquement ce dossier dans la variable d’environnement PATH de votre système. Cela permet aux codes Python que vous écrirez de s’importer facilement entre eux. Si vous déplacez ou renommez le dossier pyrat_workspace après sa création, vous devrez réparer cette variable d’environnement, comme expliqué dans cette issue.
Correction

C’est là : https://bastienpasdeloup.github.io/PyRat/install.html.

Faites bien attention aux remarques plus haut. En particulier, dans VSCode, ouvrez le dossier projet (pas pyrat_workspace). Sans ça, VSCode ne détectera pas l’environnement virtuel.

Une fois PyRat installé, démarrez VSCode, et ouvrez le dossier projet (celui qui contient venv_projet et pyrat_workspace). Via l’arborescence à gauche, ouvrez le fichier games/sample_game.py.

Comme venv_projet apparaît dans les dossiers ouverts, VSCode détectera votre environnement virtuel, et vous proposera de l’utiliser automatiquement, comme indiqué par la flèche dans la capture d’écran ci-dessous. S’il ne le fait pas, cliquez sur le numéro de version Python au bout de la flèche en bas à droite, et choisissez l’environnement virtuel venv_projet.

2.3 — Préparer le travail en groupe

Avant de démarrer cette activité pratique, vous avez dû former un trinôme. Si ça n’est pas le cas, faites le maintenant, et informez votre enseignant(e) de sa composition.

On suppose également que vous avez déjà tous créé un compte sur Gitlab ou Github, et créé une clé SSH. Si ça n’est pas le cas, revoilà le lien de la page sur le travail collaboratif avec Git vue en environnement.

2.3.1 — Mise en place du dépôt Git

À présent, nous allons faire en sorte que vous puissiez synchroniser votre dossier pyrat_workspace entre vous.

Avant de commencer, assurez -vous que chaque membre du groupe supprime un éventuel dossier __pycache__ dans pyrat_workspace/players. Ce dossier est créé automatiquement par Python pour stocker des fichiers temporaires, mais il ne doit pas être versionné avec Git.

À faire

Une fois votre trinôme constitué, choisissez l’un(e) d’entre vous (appelons cette personne “Boss” le temps de cette section pour vous motiver à prendre ce rôle :) ), puis suivez les instructions ci-dessous.

Correction

Juste suivre les instructions.

L’erreur la plus fréquente est que vous lisez trop vite, et que vous ne tapez pas exactement la bonne commande. Quand vous clonez le dépôt, assurez-vous que le dossier cloné s’appelle bien pyrat_workspace, et qu’il est au même endroit que l’ancien.

Ce sera automatique si vous avez bien nommé le dépôt pyrat_workspace. Si vous avez utilisé un nom différent, il faut absolument ajouter pyrat_workspace à la fin de la commande git clone, comme suit : git clone https://adresse.de.mon.depot.git pyrat_workspace.

En cas d’erreur comme quoi on ne peut pas importer players depuis un script dans games, c’est probablement que le workspace récupéré depuis Git n’est pas au même endroit que l’ancien, ou n’a plus le bon nom. Dans ce cas, consulter cette issue.

  1. Le/la boss crée un projet Git nommé pyrat_workspace (privé, sans README.md (décochez la case)), via Gitlab ou Github.

    Important

    Attention à bien nommer le projet pyrat_workspace. Si vous l’appelez autrement (par exemple mon_workspace), les autres étudiant(e)s du groupe risquent de créer un dossier mon_workspace au lieu de pyrat_workspace lors du clonage, ce qui empêchera les imports Python de fonctionner correctement.

  2. Le/la boss initialise ce dépôt grâce aux commandes suivantes :

    # Dans un terminal, placez vous dans le dossier pyrat_workspace
    # Adaptez avec le bon chemin
    cd \chemin\vers\pyrat_workspace
    
    # Initialisez Git dans le dossier courant
    git init --initial-branch=main
    
    # Ajoutez le dépôt existant
    # Adaptez avec la bonne adresse
    git remote add origin https://adresse.de.mon.depot.git
    
    # Ajoutez tous les fichiers du pyrat_workspace
    git add .
    
    # Créez un commit avec le nouveau contenu
    git commit -m "Initialisation du dépôt avec le workspace"
    
    # Poussez vers le serveur
    git push -u origin main
    # Dans un terminal, placez vous dans le dossier pyrat_workspace
    # Adaptez avec le bon chemin
    cd \chemin\vers\pyrat_workspace
    
    # Initialisez Git dans le dossier courant
    git init --initial-branch=main
    
    # Ajoutez le dépôt existant
    # Adaptez avec la bonne adresse
    git remote add origin https://adresse.de.mon.depot.git
    
    # Ajoutez tous les fichiers du pyrat_workspace
    git add .
    
    # Créez un commit avec le nouveau contenu
    git commit -m "Initialisation du dépôt avec le workspace"
    
    # Poussez vers le serveur
    git push -u origin main
    # Dans un terminal, placez vous dans le dossier pyrat_workspace
    # Adaptez avec le bon chemin
    cd /chemin/vers/pyrat_workspace
     
    # Initialisez Git dans le dossier courant
    git init --initial-branch=main
    
    # Ajoutez le dépôt existant
    # Adaptez avec la bonne adresse
    git remote add origin https://adresse.de.mon.depot.git
    
    # Ajoutez tous les fichiers du pyrat_workspace
    git add .
    
    # Créez un commit avec le nouveau contenu
    git commit -m "Initialisation du dépôt avec le workspace"
    
    # Poussez vers le serveur
    git push -u origin main
    # Dans un terminal, placez vous dans le dossier pyrat_workspace
    # Adaptez avec le bon chemin
    cd /chemin/vers/pyrat_workspace
     
    # Initialisez Git dans le dossier courant
    git init --initial-branch=main
    
    # Ajoutez le dépôt existant
    # Adaptez avec la bonne adresse
    git remote add origin https://adresse.de.mon.depot.git
    
    # Ajoutez tous les fichiers du pyrat_workspace
    git add .
    
    # Créez un commit avec le nouveau contenu
    git commit -m "Initialisation du dépôt avec le workspace"
    
    # Poussez vers le serveur
    git push -u origin main
  3. Le/la boss invite les autres étudiants du groupe comme collaborateurs du projet via l’interface de Gitlab ou Github.

    Information

    C’est fini pour le boss (jusqu’à l’étape 5) ! Passons aux autres étudiant(e)s du groupe.

  4. Chaque étudiant(e) non-boss supprime le dossier pyrat_workspace créé par PyRat pendant l’installation. Puis, chacun(e) clone le dépôt au même endroit avec les commandes suivante :

    # Dans un terminal, placez vous dans le dossier qui contenait le pyrat_workspace que vous venez de supprimer
    # Adaptez avec le bon chemin
    cd \chemin\vers\le\dossier\parent\de\pyrat_workspace
    
    # Clonez le dépôt
    # Adaptez avec la bonne adresse
    # Attention ! Gardez bien pyrat_workspace à la fin de la commande après le lien !
    git clone https://adresse.de.mon.depot.git pyrat_workspace
    # Dans un terminal, placez vous dans le dossier qui contenait le pyrat_workspace que vous venez de supprimer
    # Adaptez avec le bon chemin
    cd \chemin\vers\le\dossier\parent\de\pyrat_workspace
    
    # Clonez le dépôt
    # Adaptez avec la bonne adresse
    # Attention ! Gardez bien pyrat_workspace à la fin de la commande après le lien !
    git clone https://adresse.de.mon.depot.git pyrat_workspace
    # Dans un terminal, placez vous dans le dossier qui contenait le pyrat_workspace que vous venez de supprimer
    # Adaptez avec le bon chemin
    cd /chemin/vers/le/dossier/parent/de/pyrat_workspace
    
    # Clonez le dépôt
    # Adaptez avec la bonne adresse
    # Attention ! Gardez bien pyrat_workspace à la fin de la commande après le lien !
    git clone https://adresse.de.mon.depot.git pyrat_workspace
    # Dans un terminal, placez vous dans le dossier qui contenait le pyrat_workspace que vous venez de supprimer
    # Adaptez avec le bon chemin
    cd /chemin/vers/le/dossier/parent/de/pyrat_workspace
    
    # Clonez le dépôt
    # Adaptez avec la bonne adresse
    # Attention ! Gardez bien pyrat_workspace à la fin de la commande après le lien !
    git clone https://adresse.de.mon.depot.git pyrat_workspace

    Cette commande devrait créer un nouveau dossier pyrat_workspace là où se trouvait celui que vous avez supprimé.

    Important

    Attention à ce que ce nouveau dossier soit bien au même endroit et s’appelle bien pyrat_workspace. La raison est que ce chemin a été ajouté dans le PATH par PyRat, ce qui permettra à vos codes Python de s’importer facilement.

    Information

    C’est tout pour les non-boss ! Les instructions restantes concernent tout le monde.

  5. Vérifiez que vous avez bien le bon pyrat_workspace dans votre workspace VSCode. Pour vous en rendre compte, cliquez sur le menu Source control à gauche. Vous devriez voir que VSCode a automatiquement détecté votre dépôt Git, et vous propose de gérer vos add, commit, push, etc. directement via son interface.

  6. Vérifiez que PyRat marche bien. Démarrez le script sample_game.py dans le dossier pyrat_workspace/games et exécutez le. Vous devriez voir une partie de PyRat se lancer, comme précédemment.

2.3.2 — Ajout d’un fichier README.md

Dans tout projet informatique, il est important d’avoir un petit fichier qui explique succinctement (ou pas) à quoi sert le projet. On appelle ce fichier un “README”, et on y trouve généralement les adresses de contact des auteurs, les instructions d’utilisation du projet, etc.

Sur les dépôts Git, ce fichier s’appelle classiquement README.md, car on rédige son contenu en Markdown, un langage permettant de formater du texte. Si vous avez déjà utilisé des outils comme Discord, (ou Mattermost, Slack, etc.), c’est généralement ce langage qui est utilisé pour mettre du texte en gras, italique, etc.

À faire

Choisissez l’un(e) d’entre vous qui n’était pas le/la Boss, et appelons cet étudiant(e) “Big Boss” (le temps de cette section, ne prenez pas la grosse tête tout de suite). Puis, suivez les instructions ci-dessous.

Correction

Le/la Big Boss fait un add et un commit du fichier README.md, puis un push. Les autres font un pull.

N’hésitez pas à tout faire via l’interface VSCode si vous préférez.

  1. Le/la Big Boss crée un fichier README.md dans son workspace PyRat, comme indiqué plus haut.

  2. Une fois le fichier créé, le/la Big Boss y copie-colle le texte suivant (changez les éléments entre <...> par le bon contenu), et sauvegarde le fichier.

    # Description
    
    This is the repository of a PyRat workspace created following instructions [https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical](provided here).
    It is used to store the codes developed during the PyRat project by the aforementioned students during year 1 at IMT Atlantique.
    
    - <First name> <Name> <mail@imt-atlantique.fr>
    - <First name> <Name> <mail@imt-atlantique.fr>
    - <First name> <Name> <mail@imt-atlantique.fr>
    
    # Repository documentation
    
    <You can write stuff here later>

À présent, votre objectif est de manipuler Git (via l’interface VSCode ou la ligne de commande) pour que :

  • Le fichier README.md apparaisse sur le dépôt.
  • Chaque étudiant du groupe ait une vue locale à jour du dépôt dans son workspace.
2.3.3 — Ajout d’un fichier .gitignore

Quand on réalise un projet avec Git, il faut uniquement versionner les fichiers intéressants (le code, la documentation, éventuellement certaines données, etc.), mais pas les fichiers qui permettent l’exécution du projet (environnement virtuel, fichiers temporaires, etc.).

Pour cela, on peut mettre à la racine du dépôt un fichier nommé .gitignore, dans lequel on liste tous les fichiers et dossiers à ignorer par Git.

À faire

L’étudiant(e) qui n’a pas encore dirigé le groupe devient le/la Méga Boss. Puis, suivez les instructions ci-dessous.

Correction

Le/la Méga Boss fait un add et un commit du fichier .gitignore, puis un push. Les autres font un pull.

N’hésitez pas à tout faire via l’interface VSCode si vous préférez.

  • Le/la Méga Boss télécharge ce fichier .gitignore standard pour Python, le place dans son dossier pyrat_workspace, comme indiqué plus haut, puis le renomme en .gitignore.

  • Puis, en vous inspirant de ce que vous avez fait pour le fichier README.md plus haut, arrangez vous pour que :

    • Le fichier .gitignore apparaisse sur le dépôt.
    • Chaque étudiant du groupe ait une vue locale à jour du dépôt dans son workspace.

3 — C’est parti !

3.1 — Se familiariser avec PyRat

A ce stade, tout est prêt pour commencer le projet ! Découvrons à présent en quoi consiste le logiciel PyRat. Avant d’attaquer la création de programmes PyRat, étudiez les liens suivants :

  • Découverte de PyRat : Ce lien présente PyRat dans les grandes lignes, à savoir le contenu de pyrat_workspace et de la bibliothèque Python pyrat-game, les élements de jeu, etc.

  • Tutoriels de base : Sur cette page, nous vous proposons quelques tutoriels à suivre, qui détaillent les programmes PyRat fournis par défaut dans le pyrat_workspace, et vous expliquent comment customiser les éléments de jeu.

3.2 — Votre premier programme PyRat

L’objectif de cette activité pratique est d’écrire vos premiers codes PyRat, c’est à dire :

  • Un joueur, sous la forme d’un fichier héritant de la classe Player, décrit dans un fichier du dossier pyrat_workspace/players.
  • Un script, qui lance une partie avec votre joueur, décrit dans un fichier du dossier pyrat_workspace/games.
3.2.1 — Description de la stratégie

Le programme que nous allons écrire est une amélioration de Random4, décrit dans le tutoriel sur les programmes RandomX.

L’un des problèmes de Random4 (que Random3 avait déjà) est que, si le rat arrive dans une zone du labyrinthe où il a visité toutes les cases voisines, il tente de rejoindre une case non visitée en se déplaçant aléatoirement. À partir de là, le rat reprend sa stratégie d’exploration.

On pourrait améliorer cet aspect du programme en gardant en mémoire notre trajectoire, c’est à dire la suite de cases parcourues jusqu’au tour en cours. Ainsi, en arrivant sur une case dont on a déjà visité toutes les cases voisines, il suffirait de revenir en arrière le long de la trajectoire parcourue. Si on arrive sur une case dont on a déjà visité tous les voisins, on recommence, etc. À un moment, à force de revenir sur ses pas, le rat finira par arriver sur une case ayant au moins une case voisine inexplorée, et pourra reprendre sa quête de fromage.

3.2.2 — Création du joueur
À faire

Faites une copie du fichier Random4.py (dans le dossier players), et renommez le nouveau fichier Random5.py (dans le même dossier). Faites toutes les modifications nécessaires pour que ce nouveau fichier décrive une classe nommée Random5.

Correction

Pour le moment, juste copier Random4.py en Random5.py et renommer la classe. Penser à adapter la doc aussi éventuellement.

Ne vous préoccupez pas du comportement du joueur pour le moment, on cherche juste à créer un programme utilisable qui ne crashe pas.

3.2.3 — Création de la partie
À faire

Créez un fichier visualize_random5.py dans le dossier games de votre pyrat_workspace. Ce fichier doit effectuer les opérations détaillées ci-dessous.

Correction

Le programme devrait ressembler à ça :

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import pprint

# PyRat imports
from pyrat import Game
from players.Random5 import Random5

##########################################################################################
######################################### SCRIPT #########################################
##########################################################################################

if __name__ == "__main__":

    # Instantiate a game with a few arguments
    game_config = {"mud_percentage": 0.0,
                   "maze_width": 13,
                   "maze_height": 10,
                   "nb_cheese": 1,
                   "random_seed": 42,
                   "trace_length": 1000}

    # Instantiate a game with specified arguments
    game = Game(**game_config)

    # Instantiate the player
    player = Random5()
    game.add_player(player)

    # Start the game
    stats = game.start()
    pprint.pprint(stats)

##########################################################################################
##########################################################################################
  1. Importer la classe Random5 que vous venez de créer.

  2. Créer une partie de PyRat (une instance de la classe Game), contenant 1 morceau de fromage. Pensez aussi à mettre une valeur élevée à l’argument trace_length pour vérifier plus tard que le rat revient bien sur ses traces.

  3. Instancier un joueur de la classe Random5, et l’ajouter à la partie.

  4. Démarrer la partie.

Information

Inspirez vous des tutoriels PyRat, ainsi que des exemples donnés par défaut dans pyrat_workspace/games.

3.2.4 — Implémentez la stratégie
À faire

Maintenant que vous avez un script visualize_random5.py qui lance une partie de PyRat avec le joueur Random5, adaptez le code de Random5.py pour que le rat suive la stratégie décrite plus haut.

Correction

Le programme devrait ressembler à ça :

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import random

# PyRat imports
from pyrat import Player, Maze, GameState, Action

##########################################################################################
######################################### CLASSES ########################################
##########################################################################################

class Random5 (Player):

    """
    *(This class inherits from* ``Player`` *).*

    This player is an improvement of the ``Random4`` player.
    A limitation of ``Random4`` is that it gets stuck in areas when all neighbors have been visited.
    To avoid this, we keep track of the trajectory of the player, and when we are stuck, we go back to the last cell in the trajectory.
    """

    ##################################################################################
    #                                   CONSTRUCTOR                                  #
    ##################################################################################

    def __init__ ( self,
                   *args:    object,
                   **kwargs: object
                 ) ->        None:

        """
        Initializes a new instance of the class.
        Here, in addition to the attributes developed in the ``Random4`` player, we also create an attribute for our trajectory.

        Args:
            args:   Arguments to pass to the parent constructor.
            kwargs: Keyword arguments to pass to the parent constructor.
        """

        # Inherit from parent class
        super().__init__(*args, **kwargs)

        # We create an attribute to keep track of visited cells
        # We will initialize it in the ``preprocessing()`` method to allow the game to be reset
        # Otherwise, the set would keep the cells visited in previous games
        self.visited_cells = None

        # We also create an attribute for the reduced maze
        self.reduced_maze = None

        # We create an attribute for the player's trajectory
        self.trajectory = None

    ##################################################################################
    #                                  PYRAT METHODS                                 #
    ##################################################################################

    def preprocessing ( self,
                        maze:       Maze,
                        game_state: GameState,
                      ) ->          None:
        
        """
        *(This method redefines the method of the parent class with the same name).*

        This method is called once at the beginning of the game.
        Here, we use it to create a reduced maze that contains only the cells that are not dead-ends.
        We define a dead-end as a cell that has only one neighbor and does not contain cheese or the player.
        Note that this is not the best way to define a dead-end, but it is a simple one.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        """

        # Initialize visited cells
        self.visited_cells = set()

        # Reduce the maze
        my_location = game_state.player_locations[self.get_name()]
        self.reduced_maze = self.remove_dead_ends(maze, [my_location] + game_state.cheese)

        # Initialize the trajectory
        self.trajectory = [my_location]

    ##################################################################################

    def turn ( self,
               maze:       Maze,
               game_state: GameState,
             ) ->          Action:

        """
        *(This method redefines the method of the parent class with the same name).*

        It is called at each turn of the game.
        It returns an action to perform among the possible actions, defined in the ``Action`` enumeration.
        We also update the set of visited cells at each turn.
        Now, we work with the reduced maze to find the next action.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        
        Returns:
            One of the possible actions.
        """

        # Mark current cell as visited
        my_location = game_state.player_locations[self.get_name()]
        if my_location not in self.visited_cells:
            self.visited_cells.add(my_location)

        # Add current location to trajectory
        self.trajectory.append(my_location)

        # Return an action
        action = self.find_next_action(self.reduced_maze, game_state)
        return action
    
    ##################################################################################
    #                                  OTHER METHODS                                 #
    ##################################################################################

    def find_next_action ( self,
                           maze:       Maze,
                           game_state: GameState,
                         ) ->          Action:

        """
        This method returns an action to perform among the possible actions, defined in the ``Action`` enumeration.
        Here, the action is chosen randomly among those that don't hit a wall, and that lead to an unvisited cell if possible.
        If no such action exists, we come back to the last cell in the trajectory and pop it.
        
        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.

        Returns:
            One of the possible actions that leads to a valid neighbor.
        """

        # Go to an unvisited neighbor in priority
        my_location = game_state.player_locations[self.get_name()]
        neighbors = maze.get_neighbors(my_location)
        unvisited_neighbors = [neighbor for neighbor in neighbors if neighbor not in self.visited_cells]
        if len(unvisited_neighbors) > 0:
            neighbor = random.choice(unvisited_neighbors)
            
        # If there is no unvisited neighbor, go back in the trajectory
        # We pop the last cell in the trajectory, which is the current cell
        # Then, we pop again to get the previous cell, which is where we want to go back
        else:
            self.trajectory.pop()
            neighbor = self.trajectory.pop()
        
        # Retrieve the corresponding action
        action = maze.locations_to_action(my_location, neighbor)
        return action
    
    ##################################################################################

    def remove_dead_ends ( self,
                           maze:              Maze,
                           locations_to_keep: list[tuple[int, int]]
                         ) ->                 Maze:
        
        """
        This method returns a new maze that contains only the cells that are not dead-ends.
        A dead-end is defined as a cell that has only one neighbor and does not contain cheese or the player.

        Args:
            maze:              An object representing the maze in which the player plays.
            locations_to_keep: A list of locations to keep in the reduced maze.

        Returns:
            A new maze with only the cells that are not dead-ends.
        """

        # Initialize the reduced maze as the original one
        # We do not need to make a copy of the maze, as the game sends a copy of the maze at each turn.
        updated_maze = maze
        
        # Iteratively remove dead-ends from the maze
        # We still keep dead ends that contain locations to keep
        removed_something = True
        while removed_something:
            removed_something = False
            for vertex in updated_maze.get_vertices():
                if len(updated_maze.get_neighbors(vertex)) == 1 and vertex not in locations_to_keep:
                    updated_maze.remove_vertex(vertex)
                    removed_something = True

        # Return the updated maze
        return updated_maze

##########################################################################################
##########################################################################################

N’hésitez pas à lancer régulièrement votre script visualize_random5.py, par exemple pour afficher la trajectoire parcourue, ou pour vérifier que votre code ne crashe pas.

Vous devriez obtenir un rat qui se comporte comme suit. En particulier, il ne devrait pas aller dans des culs de sac (amélioration apportée par Random4), et devrait revenir sur ses pas quand toutes les cases voisines sont déjà visitées.

3.2.5 — Évaluez la stratégie

Maintenant que vous avez une nouvelle stratégie, il faut se poser la question de si elle est vraiment efficace. Pour cela, une approche possible est de la comparer à d’autres méthodes.

À faire

Adaptez le script evaluate_random_players.py fourni à la fin du tutoriel pour ajouter votre joueur Random5 aux quatre autres.

Quelles conclusions tirez-vous ? Discutez-en avec votre enseignant(e) !

Correction

Voici une adaptation du script evaluate_random_players.py. Nous prenons un peu d’avance en incluant également les programmes développés plus bas.

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import tqdm.auto as tqdm
import matplotlib.pyplot as pyplot
import scipy.stats as scstats

# PyRat imports
from pyrat import Game, GameMode
from players.Random1 import Random1
from players.Random2 import Random2
from players.Random3 import Random3
from players.Random4 import Random4
from players.Random5 import Random5
from players.Random6 import Random6
from players.Random7 import Random7

##########################################################################################
######################################### SCRIPT #########################################
##########################################################################################

if __name__ == "__main__":

    # Determines how many games will be played for each player
    nb_games = 1000

    # Customize the game elements
    game_config = {"mud_percentage": 0.0,
                   "nb_cheese": 1,
                   "game_mode": GameMode.SIMULATION}

    # Run the games for each player class
    players = [Random1(), Random2(), Random3(), Random4(), Random5(), Random6(), Random7()]
    results = {player.get_name(): [] for player in players}
    for player in players:
        for seed in tqdm.tqdm(range(nb_games), desc=player.get_name()):

            # Make the game with given seed
            game = Game(random_seed=seed, **game_config)
            game.add_player(player)
            stats = game.start()

            # Store the number of turns needed
            results[player.get_name()].append(stats["turns"])

    # Visualization of cumulative curves of numbers of turns taken per program
    max_turn = max([max(results[player]) for player in results])
    pyplot.figure(figsize=(10, 5))
    for player in results:
        turns = [0] + sorted(results[player]) + [max_turn]
        games_completed_per_turn = [len([turn for turn in results[player] if turn <= t]) * 100.0 / nb_games for t in turns]
        pyplot.plot(turns, games_completed_per_turn, label=player)
    pyplot.title("Comparison of turns needed to complete all %d games" % (nb_games))
    pyplot.xlabel("Turns per game")
    pyplot.ylabel("% of games completed")
    pyplot.xscale("log")
    pyplot.legend()
    pyplot.savefig("evaluate_random_players.png")

    # Formal statistics to check if these curves are statistically significant
    for i, player_1 in enumerate(results):
        for j, player_2 in enumerate(results):
            if j > i:
                test_result = scstats.mannwhitneyu(results[player_1], results[player_2], alternative="two-sided")
                print("Mann-Whitney U test between turns of program '%s' and of program '%s':" % (player_1, player_2), test_result)

##########################################################################################
##########################################################################################

En exécutant ce script, on obtient le graphique suivant :

Comparaison des performances des différents programmes aléatoires

Et on obtient les résultats suivants pour les tests statistiques :

Mann-Whitney U test between turns of program 'Random1' and of program 'Random2':
MannwhitneyuResult(statistic=np.float64(629444.0), pvalue=np.float64(1.193805368295762e-23))

Mann-Whitney U test between turns of program 'Random1' and of program 'Random3':
MannwhitneyuResult(statistic=np.float64(777997.5), pvalue=np.float64(8.474324515868948e-103))

Mann-Whitney U test between turns of program 'Random1' and of program 'Random4':
MannwhitneyuResult(statistic=np.float64(803477.5), pvalue=np.float64(3.946294369720488e-122))

Mann-Whitney U test between turns of program 'Random1' and of program 'Random5':
MannwhitneyuResult(statistic=np.float64(896372.5), pvalue=np.float64(6.578900822721211e-207))

Mann-Whitney U test between turns of program 'Random1' and of program 'Random6':
MannwhitneyuResult(statistic=np.float64(974073.0), pvalue=np.float64(3.710534971663599e-295))

Mann-Whitney U test between turns of program 'Random1' and of program 'Random7':
MannwhitneyuResult(statistic=np.float64(971377.0), pvalue=np.float64(8.137790587846432e-292))

Mann-Whitney U test between turns of program 'Random2' and of program 'Random3':
MannwhitneyuResult(statistic=np.float64(675221.0), pvalue=np.float64(6.101481042673725e-42))

Mann-Whitney U test between turns of program 'Random2' and of program 'Random4':
MannwhitneyuResult(statistic=np.float64(709365.5), pvalue=np.float64(4.059310828048741e-59))

Mann-Whitney U test between turns of program 'Random2' and of program 'Random5':
MannwhitneyuResult(statistic=np.float64(830148.5), pvalue=np.float64(3.563466221925198e-144))

Mann-Whitney U test between turns of program 'Random2' and of program 'Random6':
MannwhitneyuResult(statistic=np.float64(954534.5), pvalue=np.float64(1.642204139083212e-271))

Mann-Whitney U test between turns of program 'Random2' and of program 'Random7':
MannwhitneyuResult(statistic=np.float64(950008.5), pvalue=np.float64(3.715566915390973e-266))

Mann-Whitney U test between turns of program 'Random3' and of program 'Random4':
MannwhitneyuResult(statistic=np.float64(543162.0), pvalue=np.float64(0.0008304016572701611))

Mann-Whitney U test between turns of program 'Random3' and of program 'Random5':
MannwhitneyuResult(statistic=np.float64(691584.0), pvalue=np.float64(8.519425633784984e-50))

Mann-Whitney U test between turns of program 'Random3' and of program 'Random6':
MannwhitneyuResult(statistic=np.float64(925934.5), pvalue=np.float64(1.0825651827569589e-238))

Mann-Whitney U test between turns of program 'Random3' and of program 'Random7':
MannwhitneyuResult(statistic=np.float64(916785.0), pvalue=np.float64(1.2737098944078e-228))

Mann-Whitney U test between turns of program 'Random4' and of program 'Random5':
MannwhitneyuResult(statistic=np.float64(644933.5), pvalue=np.float64(3.1172422904019286e-29))

Mann-Whitney U test between turns of program 'Random4' and of program 'Random6':
MannwhitneyuResult(statistic=np.float64(916347.0), pvalue=np.float64(3.6742404350271064e-228))

Mann-Whitney U test between turns of program 'Random4' and of program 'Random7':
MannwhitneyuResult(statistic=np.float64(905822.5), pvalue=np.float64(7.305777365442017e-217))

Mann-Whitney U test between turns of program 'Random5' and of program 'Random6':
MannwhitneyuResult(statistic=np.float64(891258.5), pvalue=np.float64(9.574270851465981e-202))

Mann-Whitney U test between turns of program 'Random5' and of program 'Random7':
MannwhitneyuResult(statistic=np.float64(877888.0), pvalue=np.float64(2.5564688168315526e-188))

Mann-Whitney U test between turns of program 'Random6' and of program 'Random7':
MannwhitneyuResult(statistic=np.float64(468236.5), pvalue=np.float64(0.01379698799921949))

D’après la courbe et les tests, on observe que Random5 prend significativement ($p \ll 0.01$) moins de tours en moyenne que les autres programmes. C’est donc une amélioration pertinente du point de vue des résultats.

Cela dit, on n’a pas mesuré les impacts en terme de temps de calcul et de coût énergétique, donc il faudrait pousser un peu plus les analyses pour voir si c’est à garder.

Pour aller plus loin

4 — Le joueur Random6

4.1 — Description de la stratégie

Quand Random5 arrive à un croisement amenant à plusieurs cases voisines non visitées, le rat choisit une case aléatoirement parmi celles-ci et s’y dirige.

Imaginons le cas trivial où il n’y a aucun mur, on se dit alors que les directions se rapprochant le plus du fromage (à vol d’oiseau) sont les plus intéressantes. Comme en PyRat on bouge sur une grille, mieux vaut aller vers le nord ou l’est si le fromage est au nord-est. Une stratégie intéressante serait alors de trier les cases voisines non visitées par ordre croissant de distance au fromage, et de privilégier la première.

À faire

Quel est l’impact du nombre de murs sur cette stratégie et son intérêt par rapport à une orientation aléatoire ?

Correction

Plus on a de murs, plus il faudra faire des chemins détournés pour aller au fromage. Donc la stratégie deviendra probablement moins efficace.

4.2 — Implémentez et évaluez la stratégie

À faire

En vous inspirant de ce que vous avez fait pour Random5, créez un joueur Random6 (et un script dans games pour le tester), qui implémente la stratégie guidée par l’emplacement du fromage.

Correction

Le programme devrait ressembler à ça :

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# PyRat imports
from pyrat import Player, Maze, GameState, Action

##########################################################################################
######################################### CLASSES ########################################
##########################################################################################

class Random6 (Player):

    """
    *(This class inherits from* ``Player`` *).*

    This player is an improvement of the ``Random5`` player.
    A limitation of ``Random5`` is that it gives equal importance to all unvisited neighbors.
    However, some may reduce the distance to the cheese, while others may increase it.
    """

    ##################################################################################
    #                                   CONSTRUCTOR                                  #
    ##################################################################################

    def __init__ ( self,
                   *args:    object,
                   **kwargs: object
                 ) ->        None:

        """
        Initializes a new instance of the class.

        Args:
            args:   Arguments to pass to the parent constructor.
            kwargs: Keyword arguments to pass to the parent constructor.
        """

        # Inherit from parent class
        super().__init__(*args, **kwargs)

        # We create an attribute to keep track of visited cells
        # We will initialize it in the ``preprocessing()`` method to allow the game to be reset
        # Otherwise, the set would keep the cells visited in previous games
        self.visited_cells = None

        # We also create an attribute for the reduced maze
        self.reduced_maze = None

        # We create an attribute for the player's trajectory
        self.trajectory = None

    ##################################################################################
    #                                  PYRAT METHODS                                 #
    ##################################################################################

    def preprocessing ( self,
                        maze:       Maze,
                        game_state: GameState,
                      ) ->          None:
        
        """
        *(This method redefines the method of the parent class with the same name).*

        This method is called once at the beginning of the game.
        Here, we use it to create a reduced maze that contains only the cells that are not dead-ends.
        We define a dead-end as a cell that has only one neighbor and does not contain cheese or the player.
        Note that this is not the best way to define a dead-end, but it is a simple one.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        """

        # Initialize visited cells
        self.visited_cells = set()

        # Reduce the maze
        my_location = game_state.player_locations[self.get_name()]
        self.reduced_maze = self.remove_dead_ends(maze, [my_location] + game_state.cheese)

        # Initialize the trajectory
        self.trajectory = [my_location]

    ##################################################################################

    def turn ( self,
               maze:       Maze,
               game_state: GameState,
             ) ->          Action:

        """
        *(This method redefines the method of the parent class with the same name).*

        It is called at each turn of the game.
        It returns an action to perform among the possible actions, defined in the ``Action`` enumeration.
        We also update the set of visited cells at each turn.
        Now, we work with the reduced maze to find the next action.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        
        Returns:
            One of the possible actions.
        """

        # Mark current cell as visited
        my_location = game_state.player_locations[self.get_name()]
        if my_location not in self.visited_cells:
            self.visited_cells.add(my_location)

        # Add current location to trajectory
        self.trajectory.append(my_location)

        # Return an action
        action = self.find_next_action(self.reduced_maze, game_state)
        return action
    
    ##################################################################################
    #                                  OTHER METHODS                                 #
    ##################################################################################

    def find_next_action ( self,
                           maze:       Maze,
                           game_state: GameState,
                         ) ->          Action:

        """
        This method returns an action to perform among the possible actions, defined in the ``Action`` enumeration.
        Here, the action is chosen by prioritizing unvisited neighbors that reduce the distance to the closest cheese.
        If no such action exists, we come back to the last cell in the trajectory and pop it.
        
        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.

        Returns:
            One of the possible actions that leads to a valid neighbor.
        """

        # Go to an unvisited neighbor in priority
        # We sort the unvisited neighbors by their Euclidean distance to the closest cheese
        my_location = game_state.player_locations[self.get_name()]
        neighbors = maze.get_neighbors(my_location)
        unvisited_neighbors = [neighbor for neighbor in neighbors if neighbor not in self.visited_cells]
        if len(unvisited_neighbors) > 0:

            # Find the closest cheese in case there are multiple
            my_x, my_y = maze.i_to_rc(my_location)
            distances_player_cheese = {}
            for cheese in game_state.cheese:
                cheese_x, cheese_y = maze.i_to_rc(cheese)
                distances_player_cheese[cheese] = ((my_x - cheese_x) ** 2 + (my_y - cheese_y) ** 2) ** 0.5
            closest_cheese = min(distances_player_cheese, key=distances_player_cheese.get)
            closest_cheese_x, closest_cheese_y = maze.i_to_rc(closest_cheese)

            # Compute distances to the closest cheese for each unvisited neighbor
            distances_neighbor_cheese = {}
            for neighbor in unvisited_neighbors:
                neighbor_x, neighbor_y = maze.i_to_rc(neighbor)
                distances_neighbor_cheese[neighbor] = ((neighbor_x - closest_cheese_x) ** 2 + (neighbor_y - closest_cheese_y) ** 2) ** 0.5

            # Choose the neighbor that reduces the distance to the closest cheese the most
            neighbor = min(distances_neighbor_cheese, key=distances_neighbor_cheese.get)

        # If there is no unvisited neighbor, go back in the trajectory
        # We pop the last cell in the trajectory, which is the current cell
        # Then, we pop again to get the previous cell, which is where we want to go back
        else:
            self.trajectory.pop()
            neighbor = self.trajectory.pop()
        
        # Retrieve the corresponding action
        action = maze.locations_to_action(my_location, neighbor)
        return action
    
    ##################################################################################

    def remove_dead_ends ( self,
                           maze:              Maze,
                           locations_to_keep: list[tuple[int, int]]
                         ) ->                 Maze:
        
        """
        This method returns a new maze that contains only the cells that are not dead-ends.
        A dead-end is defined as a cell that has only one neighbor and does not contain cheese or the player.

        Args:
            maze:              An object representing the maze in which the player plays.
            locations_to_keep: A list of locations to keep in the reduced maze.

        Returns:
            A new maze with only the cells that are not dead-ends.
        """

        # Initialize the reduced maze as the original one
        # We do not need to make a copy of the maze, as the game sends a copy of the maze at each turn.
        updated_maze = maze
        
        # Iteratively remove dead-ends from the maze
        # We still keep dead ends that contain locations to keep
        removed_something = True
        while removed_something:
            removed_something = False
            for vertex in updated_maze.get_vertices():
                if len(updated_maze.get_neighbors(vertex)) == 1 and vertex not in locations_to_keep:
                    updated_maze.remove_vertex(vertex)
                    removed_something = True

        # Return the updated maze
        return updated_maze

##########################################################################################
##########################################################################################

Vous devriez observer quelque chose comme ça :

À faire

Puis, complétez le script evaluate_random_players.py pour ajouter votre joueur Random6 aux cinq autres. Un avis sur les résultats observés ?

Correction

Le programme devrait ressembler à ça :

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import pprint

# PyRat imports
from pyrat import Game
from players.Random6 import Random6

##########################################################################################
######################################### SCRIPT #########################################
##########################################################################################

if __name__ == "__main__":

    # Instantiate a game with a few arguments
    game_config = {"mud_percentage": 0.0,
                   "maze_width": 13,
                   "maze_height": 10,
                   "nb_cheese": 1,
                   "random_seed": 42,
                   "trace_length": 1000}

    # Instantiate a game with specified arguments
    game = Game(**game_config)

    # Instantiate the player
    player = Random6()
    game.add_player(player)

    # Start the game
    stats = game.start()
    pprint.pprint(stats)

##########################################################################################
##########################################################################################

D’après la courbe et les tests, on observe que Random6 prend significativement ($p \ll 0.01$) moins de tours en moyenne que Random5. C’est donc une amélioration pertinente du point de vue des résultats.

4.3 — Les cas limites

On se posait précédemment la question de si le nombre de murs pouvait poser problème.

À faire

Faites varier ce nombre pour évaluer la densité au delà de laquelle Random6 n’est pas significativement meilleur que Random5. Le plus efficace est de créer un script dans le dossier games pour tester ça dans une boucle qui augmente progressivement la densité de murs.

Correction

Voici un script qui permet d’étudier l’impact du pourcentage de murs sur les performances relatives de Random5 et Random6 :

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import tqdm.auto as tqdm
import matplotlib.pyplot as pyplot
import scipy.stats as scstats

# PyRat imports
from pyrat import Game, GameMode
from players.Random5 import Random5
from players.Random6 import Random6

##########################################################################################
######################################### SCRIPT #########################################
##########################################################################################

if __name__ == "__main__":

    # Determines how many games will be played for each player
    nb_games = 1000

    # Define the wall percentages to test
    wall_percentages = [0.0, 10.0, 20.0, 30.0, 40.0, 50.0, 60.0, 70.0, 80.0, 90.0, 100.0]

    # Customize the game elements
    game_config = {"mud_percentage": 0.0,
                   "nb_cheese": 1,
                   "game_mode": GameMode.SIMULATION}

    # Run the games for each player class
    players = [Random5(), Random6()]
    results = {walls: {player.get_name(): [] for player in players} for walls in wall_percentages}
    for walls in wall_percentages:
        print(f"Wall percentage: {walls}%")
        for player in players:
            for seed in tqdm.tqdm(range(nb_games), desc=player.get_name()):

                # Make the game with given seed
                game = Game(random_seed=seed, wall_percentage=walls, **game_config)
                game.add_player(player)
                stats = game.start()

                # Store the number of turns needed
                results[walls][player.get_name()].append(stats["turns"])

    # Visualization of cumulative curves of numbers of turns taken per program
    max_turn = max([max(results[walls][player]) for walls in results for player in results[walls]])
    pyplot.figure(figsize=(10, 5))
    for (i_player, player) in enumerate(results[walls]):
        for (i_walls, walls) in enumerate(results):
            turns = [0] + sorted(results[walls][player]) + [max_turn]
            games_completed_per_turn = [len([turn for turn in results[walls][player] if turn <= t]) * 100.0 / nb_games for t in turns]
            pyplot.plot(turns,
                        games_completed_per_turn,
                        label="%s (walls=%.1f%%)" % (player, walls),
                        linestyle="-" if i_player == 0 else "--",
                        color=pyplot.cm.viridis(i_walls / (len(results) - 1)))
    pyplot.title("Comparison of turns needed to complete all %d games" % (nb_games))
    pyplot.xlabel("Turns per game")
    pyplot.ylabel("% of games completed")
    pyplot.xscale("log")
    pyplot.legend(bbox_to_anchor=(1.05, 1), loc="upper left", ncol=2)
    pyplot.tight_layout()
    pyplot.savefig("walls_impact_on_random5_random6.png")

    # Plot statistical significance as a function of wall percentage
    p_values = []
    for walls in results:
        stat, p_value = scstats.mannwhitneyu(results[walls]["Random5"], results[walls]["Random6"], alternative="greater")
        p_values.append(p_value)
    pyplot.figure(figsize=(10, 5))
    pyplot.plot(wall_percentages, p_values, marker='o')
    pyplot.axhline(y=0.05, color='r', linestyle='--', label='Significance threshold (0.05)')
    pyplot.title("Statistical significance of Random6 vs Random5")
    pyplot.xlabel("Wall percentage")
    pyplot.ylabel("p-value (Mann-Whitney U test)")
    pyplot.yscale("log")
    pyplot.legend()
    pyplot.savefig("walls_impact_on_random5_random6_p_values.png")

##########################################################################################
##########################################################################################

On observe les courbes suivantes en sortie, pour 1000 parties jouées par programme et par pourcentage de murs :

Le script affiche également la significativité statistique des différences observées entre les deux programmes en fonction du pourcentage de murs :

On observe que le script Random6 est significativement meilleur que Random5 dans à peu près toutes les configurations, même si l’écart diminue avec le pourcentage de murs qui augmente.

On avait déjà parlé de significativité dans le tutoriel, n’hésitez pas à relire cette partie.

4.4 — Remarques

Si vous avez suivi toutes les étapes, vous devriez vous rendre compte que votre programme ne comporte plus d’aléatoire du tout !

À faire

Pensez à faire un peu de ménage dans les dépendances de votre fichier Random6.py (qui est du coup assez mal nommé) en enlevant import random.

Correction

Normalement, on n’a plus besoin de import random dans Random6.py, donc on peut l’enlever. Idéalement, on devrait aussi renommer le fichier et la classe pour refléter le fait que ce n’est plus un programme aléatoire.

Une autre remarque est que la distance Euclidéenne utilisée pour trier les voisins non visités ne prend pas en compre la topologie du labyrinthe, ni la boue. Cela s’observe dans la vidéo plus haut, où on voit bien que la portion de chemin 82 -> 95 -> 94 aurait été plus courte que 82 -> 81 -> 94. Il faudra donc passer à des stratégies plus intelligentes pour trouver des chemins plus courts.

Pour aller encore plus loin

5 — Le joueur Random7

La plupart du temps, le fromage va se trouver en diagonale par rapport au rat (par exemple au nord-ouest). Conceptuellement, dans un labyrinthe sans murs, ça ne change pas grand chose d’aller au nord puis à l’ouest, ou d’aller à l’ouest puis au nord. La boue dans le labyrinthe change toutefois cette équivalence. C’est un phénomène que nous avons décrit dans les remarques sur Random6 plus haut.

On pourrait donc améliorer Random6 comme suit : si deux actions réduisent la distance au fromage, on privilégie celle qui amène à la case suivante en un minimum de tours.

À faire

Comme précédemment, créez un joueur Random7 qui implémente cette stratégie, ainsi qu’un script pour lancer une partie avec.

Correction

Le programme devrait ressembler à ça :

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# PyRat imports
from pyrat import Player, Maze, GameState, Action

##########################################################################################
######################################### CLASSES ########################################
##########################################################################################

class Random7 (Player):

    """
    *(This class inherits from* ``Player`` *).*

    This player is an improvement of the ``Random6`` player.
    A limitation of ``Random6`` is that it can enter mud by goint north then west, while going west then north would avoid the mud.
    We improve this by checking weights leading to cells that reduce the distance to the closest cheese.
    """

    ##################################################################################
    #                                   CONSTRUCTOR                                  #
    ##################################################################################

    def __init__ ( self,
                   *args:    object,
                   **kwargs: object
                 ) ->        None:

        """
        Initializes a new instance of the class.

        Args:
            args:   Arguments to pass to the parent constructor.
            kwargs: Keyword arguments to pass to the parent constructor.
        """

        # Inherit from parent class
        super().__init__(*args, **kwargs)

        # We create an attribute to keep track of visited cells
        # We will initialize it in the ``preprocessing()`` method to allow the game to be reset
        # Otherwise, the set would keep the cells visited in previous games
        self.visited_cells = None

        # We also create an attribute for the reduced maze
        self.reduced_maze = None

        # We create an attribute for the player's trajectory
        self.trajectory = None

    ##################################################################################
    #                                  PYRAT METHODS                                 #
    ##################################################################################

    def preprocessing ( self,
                        maze:       Maze,
                        game_state: GameState,
                      ) ->          None:
        
        """
        *(This method redefines the method of the parent class with the same name).*

        This method is called once at the beginning of the game.
        Here, we use it to create a reduced maze that contains only the cells that are not dead-ends.
        We define a dead-end as a cell that has only one neighbor and does not contain cheese or the player.
        Note that this is not the best way to define a dead-end, but it is a simple one.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        """

        # Initialize visited cells
        self.visited_cells = set()

        # Reduce the maze
        my_location = game_state.player_locations[self.get_name()]
        self.reduced_maze = self.remove_dead_ends(maze, [my_location] + game_state.cheese)

        # Initialize the trajectory
        self.trajectory = [my_location]

    ##################################################################################

    def turn ( self,
               maze:       Maze,
               game_state: GameState,
             ) ->          Action:

        """
        *(This method redefines the method of the parent class with the same name).*

        It is called at each turn of the game.
        It returns an action to perform among the possible actions, defined in the ``Action`` enumeration.
        We also update the set of visited cells at each turn.
        Now, we work with the reduced maze to find the next action.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        
        Returns:
            One of the possible actions.
        """

        # Mark current cell as visited
        my_location = game_state.player_locations[self.get_name()]
        if my_location not in self.visited_cells:
            self.visited_cells.add(my_location)

        # Add current location to trajectory
        self.trajectory.append(my_location)

        # Return an action
        action = self.find_next_action(self.reduced_maze, game_state)
        return action
    
    ##################################################################################
    #                                  OTHER METHODS                                 #
    ##################################################################################

    def find_next_action ( self,
                           maze:       Maze,
                           game_state: GameState,
                         ) ->          Action:

        """
        This method returns an action to perform among the possible actions, defined in the ``Action`` enumeration.
        Here, the action is chosen by prioritizing unvisited neighbors that reduce the distance to the closest cheese.
        If no such action exists, we come back to the last cell in the trajectory and pop it.
        
        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.

        Returns:
            One of the possible actions that leads to a valid neighbor.
        """

        # Go to an unvisited neighbor in priority
        # We sort the unvisited neighbors by their Euclidean distance to the closest cheese
        my_location = game_state.player_locations[self.get_name()]
        neighbors = maze.get_neighbors(my_location)
        unvisited_neighbors = [neighbor for neighbor in neighbors if neighbor not in self.visited_cells]
        if len(unvisited_neighbors) > 0:

            # Find the closest cheese in case there are multiple
            my_x, my_y = maze.i_to_rc(my_location)
            distances_player_cheese = {}
            for cheese in game_state.cheese:
                cheese_x, cheese_y = maze.i_to_rc(cheese)
                distances_player_cheese[cheese] = ((my_x - cheese_x) ** 2 + (my_y - cheese_y) ** 2) ** 0.5
            closest_cheese = min(distances_player_cheese, key=distances_player_cheese.get)
            closest_cheese_x, closest_cheese_y = maze.i_to_rc(closest_cheese)

            # Compute distances to the closest cheese for each unvisited neighbor
            distances_neighbor_cheese = {}
            for neighbor in unvisited_neighbors:
                neighbor_x, neighbor_y = maze.i_to_rc(neighbor)
                distances_neighbor_cheese[neighbor] = ((neighbor_x - closest_cheese_x) ** 2 + (neighbor_y - closest_cheese_y) ** 2) ** 0.5
            
            # Among neighbors that reduce the distance to the closest cheese, choose the closest one from current location
            # If no neighbor reduces the distance to the closest cheese, we do as Random6
            valid_neighbors = {neighbor: maze.get_weight(my_location, neighbor) for neighbor in unvisited_neighbors if distances_neighbor_cheese[neighbor] < distances_player_cheese[closest_cheese]}
            if len(valid_neighbors) > 0:
                neighbor = min(valid_neighbors, key=valid_neighbors.get)
            else:
                neighbor = min(distances_neighbor_cheese, key=distances_neighbor_cheese.get)

        # If there is no unvisited neighbor, go back in the trajectory
        # We pop the last cell in the trajectory, which is the current cell
        # Then, we pop again to get the previous cell, which is where we want to go back
        else:
            self.trajectory.pop()
            neighbor = self.trajectory.pop()
        
        # Retrieve the corresponding action
        action = maze.locations_to_action(my_location, neighbor)
        return action
    
    ##################################################################################

    def remove_dead_ends ( self,
                           maze:              Maze,
                           locations_to_keep: list[tuple[int, int]]
                         ) ->                 Maze:
        
        """
        This method returns a new maze that contains only the cells that are not dead-ends.
        A dead-end is defined as a cell that has only one neighbor and does not contain cheese or the player.

        Args:
            maze:              An object representing the maze in which the player plays.
            locations_to_keep: A list of locations to keep in the reduced maze.

        Returns:
            A new maze with only the cells that are not dead-ends.
        """

        # Initialize the reduced maze as the original one
        # We do not need to make a copy of the maze, as the game sends a copy of the maze at each turn.
        updated_maze = maze
        
        # Iteratively remove dead-ends from the maze
        # We still keep dead ends that contain locations to keep
        removed_something = True
        while removed_something:
            removed_something = False
            for vertex in updated_maze.get_vertices():
                if len(updated_maze.get_neighbors(vertex)) == 1 and vertex not in locations_to_keep:
                    updated_maze.remove_vertex(vertex)
                    removed_something = True

        # Return the updated maze
        return updated_maze

##########################################################################################
##########################################################################################
À faire

Puis, complétez le script evaluate_random_players.py pour l’ajouter aux autres. Est-ce que cet ajout améliore significativement les performances moyennes par rapport à Random6 ?

Correction

Le programme devrait ressembler à ça :

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import pprint

# PyRat imports
from pyrat import Game
from players.Random7 import Random7

##########################################################################################
######################################### SCRIPT #########################################
##########################################################################################

if __name__ == "__main__":

    # Instantiate a game with a few arguments
    game_config = {"mud_percentage": 0.0,
                   "maze_width": 13,
                   "maze_height": 10,
                   "nb_cheese": 1,
                   "random_seed": 42,
                   "trace_length": 1000}

    # Instantiate a game with specified arguments
    game = Game(**game_config)

    # Instantiate the player
    player = Random7()
    game.add_player(player)

    # Start the game
    stats = game.start()
    pprint.pprint(stats)

##########################################################################################
##########################################################################################

D’après la courbe et les tests, on observe une petite dégradation, mais le test statistique ne permet pas de conclure que c’est significativement moins bon ($p > 0.01$). Ça vaudrait le coup de tester ce que ça donne avec plus de boue et moins de murs, il est possible que ça change un peu les conclusions.

6 — Suivre le mur

On dit parfois que quand on est perdu dans un labyrinthe, il suffit de poser une main sur un mur, et d’avancer sans jamais décoller sa main. On teste ?

À faire

Prenez quelques minutes pour essayer d’imaginer les cas où cette stratégie peut fonctionner, pour partir d’une case et arriver au morceau de fromage.

Une fois que vous avez identifié ce qui marche, créez un script dans games pour créer ce contexte, puis créez un joueur pour réaliser cette stratégie.

Correction

Pour que la stratégie fonctionne, il faut qu’il existe un mur continu entre la position initiale et le fromage. C’est par exemple le cas si on se place sur le bord du labyrinthe et que le fromage touche le bord.

Au contraire, on aura des soucis si le fromage est au milieu du labyrinthe, sans mur adjacent. Idem pour le joueur qui, s’il commence sans mur adjacent ou touchant un mur qui n’amène pas au fromage, ne pourra jamais le trouver.

Testons en forçant les positions des joueurs et du fromage. Voici un script de jeu qui crée un labyrinthe sans trous (pour garantir que la case 0 existe) et en plaçant le joueur en bas à droite et le fromage en haut à gauche :

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import pprint

# PyRat imports
from pyrat import Game, StartingLocation
from players.WallFollower import WallFollower

##########################################################################################
######################################### SCRIPT #########################################
##########################################################################################

if __name__ == "__main__":

    # Instantiate a game with a few arguments
    game_config = {"mud_percentage": 0.0,
                   "wall_percentage": 70.0,
                   "cell_percentage": 100.0,
                   "fixed_cheese": [0],
                   "maze_width": 13,
                   "maze_height": 10,
                   "random_seed": 42,
                   "trace_length": 1000}

    # Instantiate a game with specified arguments
    game = Game(**game_config)

    # Instantiate the player
    player = WallFollower()
    game.add_player(player, location=StartingLocation.BOTTOM_RIGHT)

    # Start the game
    stats = game.start()
    pprint.pprint(stats)

##########################################################################################
##########################################################################################

Et voici un joueur qui suit le mur à sa droite :

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# PyRat imports
from pyrat import Player, Maze, GameState, Action

##########################################################################################
######################################### CLASSES ########################################
##########################################################################################

class WallFollower (Player):

    """
    *(This class inherits from* ``Player`` *).*

    This player follows a wall by always keeping its right hand on the wall.
    """

    ##################################################################################
    #                                   CONSTRUCTOR                                  #
    ##################################################################################

    def __init__ ( self,
                   *args:    object,
                   **kwargs: object
                 ) ->        None:

        """
        Initializes a new instance of the class.

        Args:
            args:   Arguments to pass to the parent constructor.
            kwargs: Keyword arguments to pass to the parent constructor.
        """

        # Inherit from parent class
        super().__init__(*args, **kwargs)

        # We remember the previous action performed
        self.previous_action = Action.NOTHING

    ##################################################################################
    #                                  PYRAT METHODS                                 #
    ##################################################################################

    def preprocessing ( self,
                        maze:       Maze,
                        game_state: GameState,
                      ) ->          None:
        
        """
        *(This method redefines the method of the parent class with the same name).*

        This method is called once at the beginning of the game.
        Here, we initialize the previous action to one that leads to a wall.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        """

        # Initialize last action to one that leads to a wall
        my_location = game_state.player_locations[self.get_name()]
        for action in [Action.EAST, Action.NORTH, Action.WEST, Action.SOUTH]:
            if self.action_hits_wall(maze, my_location, action):
                self.previous_action = action
                break

    ##################################################################################

    def turn ( self,
               maze:       Maze,
               game_state: GameState,
             ) ->          Action:

        """
        *(This method redefines the method of the parent class with the same name).*

        It is called at each turn of the game.
        It returns an action to perform among the possible actions, defined in the ``Action`` enumeration.
        We return an action that allows to keep the wall on the right.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        
        Returns:
            One of the possible actions.
        """

        # Actions order depends on the last action performed
        actions_order = []
        if self.previous_action == Action.NORTH:
            actions_order = [Action.EAST, Action.NORTH, Action.WEST, Action.SOUTH]
        elif self.previous_action == Action.EAST:
            actions_order = [Action.SOUTH, Action.EAST, Action.NORTH, Action.WEST]
        elif self.previous_action == Action.SOUTH:
            actions_order = [Action.WEST, Action.SOUTH, Action.EAST, Action.NORTH]
        elif self.previous_action == Action.WEST:
            actions_order = [Action.NORTH, Action.WEST, Action.SOUTH, Action.EAST]

        # Test actions in an order that allows to keep the wall on the right
        my_location = game_state.player_locations[self.get_name()]
        for action in actions_order:
            if not self.action_hits_wall(maze, my_location, action):
                self.previous_action = action
                return action
            
        # If all actions hit a wall, we don't move
        return Action.NOTHING
    
    ##################################################################################
    #                                  OTHER METHODS                                 #
    ##################################################################################

    def action_hits_wall ( self,
                           maze:             Maze,
                           current_location: int,
                           action:           Action,
                         ) ->                bool:

        """
        This method indicates whether the given action from the current location hits a wall.
        
        Args:
            maze:             An object representing the maze in which the player plays.
            current_location: The current location of the player.
            action:           The action to perform.

        Returns:
            True if the action hits a wall, False otherwise.
        """

        # Check where the action would lead
        current_location_row, current_location_col = maze.i_to_rc(current_location)
        target_location_row, target_location_col = current_location_row, current_location_col
        if action == Action.NORTH:
            target_location_row -= 1
        elif action == Action.SOUTH:
            target_location_row += 1
        elif action == Action.WEST:
            target_location_col -= 1
        elif action == Action.EAST:
            target_location_col += 1

        # If the target exists, check if we can go there
        if maze.rc_exists(target_location_row, target_location_col):
            target_location = maze.rc_to_i(target_location_row, target_location_col)
            return not maze.has_edge(current_location, target_location)

        # Target does not exist, so we hit a wall
        return True

##########################################################################################
##########################################################################################

Vous devriez observer un comportement comme celui-ci :

7 — Factoriser tout ça

Maintenant que vous avez codé 7 programmes aléatoires, vous devez vous apercevoir qu’il y a un certain nombre de redondances dans vos codes. En particulier, la fonction remove_dead_ends(...) introduite à partir de Random4 apparaît probablement dans tous les fichiers développés par la suite, vu que ce pré-traitement est relativement indépendant de la stratégie de déplacement.

Maintenant, imaginons que vous découvriez une erreur dans le code de cette fonction. Pour la corriger, il va falloir fouiller dans tous vos fichiers pour changer toutes les copies de remove_dead_ends(...). C’est problématique, car vous allez perdre du temps, et peut-être introduire de nouvelles erreurs sans faire exprès…

À faire

Prenez un moment pour réfléchir aux contenus de vos programmes aléatoires. Comment pourriez-vous exploiter le paradigme orienté objet pour mieux organiser tout ça ? Est-ce que votre nouvelle organisation permet également de factoriser des éléments développés pour le programme qui suit le mur ?

Correction

Pour mieux organiser :

  • Créer une classe Random, si possible abstraite (hériter de abc.ABC), et y mettre les éléments communs aux programmes aléatoires.

  • Changer la relation d’héritage des programmes 1 à 7 pour hériter de Random.

  • Comme la simplification de labyrinthe par remove_dead_ends() est plus liée au labyrinthe qu’au joueur, ça pourrait être bien de définir une classe MazeWrapper. Cette classe aurait un attribut maze initialisé avec ce qui est reçu lors de l’appel de preprocessing() (pas un héritage, car le maze reçu par preprocessing est une instance d’une classe enfant de Maze, et il y en a plusieurs possibles). Ensuite, mettre remove_dead_ends() dans MazeWrapper et adapter les codes.

Et pour suivre le mur :

  • Ça pourrait valoir le coup de créer une classe MyPlayer qui agrège les éléments communs à tous les programmes développés en cours. Pas dit que ça serve tout de suite, mais peut-être plus tard, si on définit des trucs communs à tous les joueurs.