Activité pratique

Consignes globales

L’objectif de cette activité est d’écrire des programmes pour guider votre rat à travers le labyrinthe grâce à des algorithmes de parcours. Nous allons tout d’abord nous placer dans un cas simple :

• Un seul joueur.
• Un seul morceau de fromage à attraper.
• Pas de boue dans le labyrinthe.

Contenu de l’activité

1 — Parcours en profondeur (DFS)

1.1 — Préparation

Tout d’abord, nous allons créer un joueur et un script pour visualiser son comportement.

• players/DFS.py – Inspirez vous de ce que vous avez fait en séance 1 pour créer un joueur DFS héritant de Player, et ayant :

  • Un constructeur __init__(...).

  • Une méthode preprocessing(...).

  • Une méthode turn(...).

  Dans un premier temps, ne vous préoccupez pas du comportement de votre joueur, créez juste le strict minimum pour pouvoir lancer une partie avec votre joueur DFS sans que ça crashe.

• games/visualize_DFS.py – Créez un fichier qui lancera une partie avec un joueur DFS, dans un labyrinthe respectant les critères listés plus haut. Vous pouvez éventuellement définir une random_seed (pour toujours travailler avec le même labyrinthe) et une trace_length (pour suivre la trajectoire de votre joueur). Inspirez-vous des autres fichiers du sous-dossier games que vous avez rencontrés lors de la séance précédente.

1.2 — La méthode traversal(...)

1.2.1 — Implémentation

Comme vous avez pu l’étudier dans vos cours de programmation et d’algorithmique, la clé pour écrire un bon programme est de bien décomposer les tâches à effectuer en fonctions. Pour cela, au lieu d’effectuer directement le parcours dans une des méthodes du joueur, on vous demande d’écrire une méthode traversal(...) qui effectuera le parcours en profondeur, et renverra la table de routage correspondante.

def traversal ( self,
                graph:  Graph,
                source: int
              ) ->      tuple[dict[int, int], dict[int, int | None]]:

    """
    This method performs a DFS traversal of a graph.
    It returns the explored vertices with associated distances.
    It also returns the routing table, that is, the parent of each vertex in the traversal.
    
    Args:
        graph:  The graph to traverse.
        source: The source vertex of the traversal (we type it as int here because we will only manipulate mazes, but Graph uses Hashable as a more generic type).

    Returns:
        A tuple containing:
        - The distances from the source to each explored vertex.
        - The routing table, that is, the parent of each vertex in the traversal (None for the source).
    """

    # Your code here

1.2.2 — Tests

Avez-vous bien pensé à vérifier que votre méthode traversal(...) fonctionne ? On peut souvent faire des erreurs en écrivant du code, que ça soit un détail de raisonnement oublié, un cas un peu inhabituel pas géré, ou juste une erreur de syntaxe. Par défaut, une bonne position est de partir du principe que tout code non testé est faux.

Vous avez vu en séance 2 de programmation comment exécuter des tests unitaires, et verrez en séance 3 comment en concevoir. Pour le moment, nous allons vous fournir un fichier de tests pour vérifier votre implémentation de traversal(...). Dans les prochaines séances de PyRat, vous aurez à créer vos propres tests.

• tests/test_DFS.py.

Ce fichier présuppose que vous avez bien suivi les instructions jusqu’à présent, c’est-à-dire que votre joueur s’appelle bien DFS dans un fichier DFS.py, que traversal(...) a bien le prototype de la méthode donnée plus haut, etc.

Si vous avez bien compris l’algorithme de parcours en profondeur, vous devriez constater qu’il existe de nombreuses solutions possibles, selon l’ordre dans lequel les sommets voisins sont explorés. Pour cette raison, nous ne pouvons pas créer directement un test qui vérifierait que, pour un graphe donné, on obtient une table de routage particulière fixée à l’avance. À la place, nous allons évaluer des propriétés de la solution produite par la méthode traversal(...) sur un certain nombre de labyrinthes générés aléatoirement :

• Les sorties sont des types attendus.

• Tous les sommets sont visités (présuppose que le graphe le permet).

• La table de routage forme un arbre, dont la racine correspond au sommet de départ du parcours.

• Les distances trouvées sont valides, c’est-à-dire strictement positives et croissantes, sauf pour le sommet de départ qui doit être égal à 0.

En exécutant ce fichier, vous devriez obtenir la sortie suivante dans le terminal :

test_traversal (__main__.DFS_Tests.test_traversal)
This method tests the ``traversal(...)`` method. ... ok

----------------------------------------------------------------------
Ran 1 test in 1.603s

OK

1.3 — Utiliser la table de routage

1.3.1 — Implémentation

Maintenant que vous avez un algorithme de parcours qui marche (et testé !), écrivons une méthode qui exploite la table de routage pour renvoyer la série de cases à suivre pour atteindre une case donnée.

def find_route ( self,
                 routing_table: dict[int, int | None],
                 source:        int,
                 target:        int
               ) ->             list[int]:

    """
    This method finds the route from a source vertex to a target vertex using a routing table.

    Args:
        routing_table: The routing table, that is, the parent of each vertex in the traversal (None for the source).
        source:        The source vertex.
        target:        The target vertex.

    Returns:
        The route from the source to the target as a list of vertices.
    """

    # Your code here

1.3.2 — Tests

Maintenant que nous avons écrit une nouvelle méthode, ajoutons quelques tests. Notez ici que, pour une table de routage donnée, avec des sommets source et cible fixés, il n’existe qu’une seule solution possible. Nous pouvons donc appeler la méthode sur des scénarios fixes, identifiés au préalable.

def test_find_route (self) -> None:
    
    """
    This method tests the ``find_route(...)`` method.
    Here, we want to make sure that the output corresponds indeed to a route from the start to the end.

    We are going to check the following:
    - Outputs are of the expected types.
    - The route is a valid path from the start to the end.

    The method will be tested on some controlled examples, where we can easily check the validity of the output.
    """

    # Constants
    INPUTS = [{"routing_table": {0: None, 1: 0, 2: 1, 3: 2, 4: 3},
               "start": 0,
               "end": 4},
              {"routing_table": {0: 2, 1: None, 2: 1, 3: 0, 4: 0, 5: 4, 6: 1},
               "start": 1,
               "end": 6}]

    # Test on several controlled examples
    for i in range(len(INPUTS)):
        
        # Instantiate the player
        player = DFS()

        # Get the input data
        routing_table = INPUTS[i]["routing_table"]
        start = INPUTS[i]["start"]
        end = INPUTS[i]["end"]

        # Find the route
        route = player.find_route(routing_table, start, end)

        # Check the output type
        # It should be a list of integers
        self.assertTrue(isinstance(route, list))
        self.assertTrue(all(isinstance(v, int) for v in route))

        # Check that the route is a valid path from the start to the end
        self.assertEqual(route[0], start)
        self.assertEqual(route[-1], end)
        self.assertTrue(all(routing_table[route[j + 1]] == route[j] for j in range(len(route) - 1)))

Ici, nous définissons deux tables de routage fixes et les utilisons comme entrées pour tester la méthode find_route(...). Nous aurions pu en définir beaucoup d’autres, et également utiliser des tables de routage valides générées aléatoirement à partir de la fonction traversal(...) que nous avons précédemment développée et validée.

Dans ces tests, nous effectuons les vérifications suivantes :

• Le type de sortie est valide.

• Les parents dans la table de routage apparaissent bien comme prédécesseurs dans le chemin obtenu.

• Le chemin va bien du point de départ à la destination.

En relançant votre script de tests, vous devriez obtenir la sortie suivante :

This method tests the ``find_route(...)`` method. ... ok
test_traversal (__main__.DFS_Tests.test_traversal)
This method tests the ``traversal(...)`` method. ... ok

----------------------------------------------------------------------
Ran 2 tests in 1.649s

OK

1.4 — Assembler tout ça

1.4.1 — Implémentation

Maintenant, il ne reste plus qu’à assembler les morceaux !

• __init__(...) – Mettez à jour votre constructeur afin de déclarer un attribut self.actions = None. Vous pourriez directement l’initialiser avec une liste vide [], mais il est préférable de l’initialiser dans preprocessing(...) pour permettre de faire un reset(...) de la partie sans avoir des valeurs restantes de la partie précédente dans les attributs du joueur.

• preprocessing(...) – Pendant la phase de prétraitement, utilisez les méthodes introduites précédemment (traversal(...) et find_route(...)) pour calculer les actions à effectuer depuis votre position initiale (my_location = game_state.player_locations[self.get_name()]) jusqu’à la position du seul morceau de fromage (cheese_location = game_state.cheese[0]). Ensuite, stockez ces actions dans l’attribut self.actions.

  Information

  Pour obtenir des actions à partir d’un chemin, la classe Maze fournit une méthode locations_to_actions(...).

• turn(...) – À chaque tour, vous devez retourner une action provenant de self.actions. Il suffit d’extraire la prochaine action à effectuer depuis cet attribut et de la renvoyer.

1.4.2 — Tests

À présent, utilisez votre script visualize_DFS.py pour observer votre joueur.

Vous devriez obtenir un rat qui se comporte comme suit :

2 — Parcours en largeur (BFS)

Comme vous avez pu le voir dans la vidéo précédente, le DFS trouve un chemin qui n’est pas exactement le plus court. Nous allons maintenant utiliser un autre algorithme, appelé parcours en largeur (Breadth-First Search, BFS). Cet algorithme a la propriété de renvoyer le chemin le plus court dans un graphe non pondéré.

• Créez un fichier pour lancer une partie, nommé visualize_BFS.py, dans le sous-dossier games de votre workspace PyRat.

• Créez un fichier joueur nommé BFS.py dans le sous-dossier players. Pour ce dernier, vous pouvez partir d’une copie de votre fichier DFS.py, car il n’y aura pas beaucoup de différences !

• Adapter les fonctions pour que votre rat effectue un parcours en largeur pour déterminer le chemin le plus court. N’oubliez pas de modifier la documentation, pour qu’elle décrive bien votre nouveau joueur.

• N’oubliez pas non plus de tester vos fonctions ! Voici les tests que vous pouvez utiliser pour vous assurer que votre code fonctionne : tests/test_BFS.py.

  Information

  Remarquez à quel point les tests sont similaires à ceux du DFS.

  Notez également que nous avons ajouté une nouvelle fonction de test pour vérifier que nous trouvons effectivement les chemins les plus courts, sur quelques exemples contrôlés pour lesquels une seule table de routage est la solution du parcours.

Vous devriez obtenir un rat qui se comporte comme suit :

3 — Comparer aux programmes aléatoires

Maintenant que vous avez deux nouveaux joueurs, il serait intéressant de les comparer avec les joueurs aléatoires que vous avez développés lors de la séance précédente.

Pour aller plus loin

4 — Factoriser les codes

4.1 — Similarités et différences entre DFS et BFS

Comme vous l’avez peut-être remarqué, les codes de BFS et DFS sont extrêmement similaires. En fait, c’est la structure de données utilisée qui détermine l’ordre dans lequel les sommets sont explorés. En effet, avec une file (FIFO), la traversée effectue une recherche en largeur. Avec une pile (LIFO), la traversée effectue une recherche en profondeur.

Ainsi, de manière générale, une traversée peut être vue comme un algorithme global qui, à un moment donné, doit :

• Créer une structure de données.

• Ajouter un élément à la structure de données.

• Extraire un élément de la structure de données.

Le paradigme de la programmation orientée objet (POO) rend cela pratique grâce à un mécanisme appelé héritage. L’idée est de créer une classe de base qui factorise le code commun, et des sous-classes qui spécialisent les particularités.

Schématiquement, on pourrait organiser le code comme suit :

Avec cette organisation, on peut instancier bfs = BFSTraversal() et appeler la méthode bfs.traversal(...). Si traversal(...) appelle initialize_structure(...) dans son code, c’est l’implémentation de initialize_structure(...) dans BFSTraversal qui sera utilisée. À la fin, au lieu de renvoyer un résultat, traversal(...) pourra mettre à jour les attributs routing_table et distances, et on pourra accéder au résultat via bfs.routing_table et bfs.distances.

De même, on peut instancier dfs = DFSTraversal(...) et appeler dfs.traversal(...). Dans ce cas, traversal(...) utilisera l’implémentation de initialize_structure(...) dans DFSTraversal. Ainsi, le même code dans la fonction traversal(...) se comporte différemment selon la spécialisation des classes enfants.

4.2 — Implémentation

Mettons ça en pratique !

• Tout d’abord, téléchargez cette archive et extrayez son contenu dans un nouveau sous-dossier pyrat_workspace/utils. Cette archive contient un début de code pour les trois classes du diagramme ci-dessus.

• Téléchargez ensuite ce fichier de joueur, qui contient un joueur TraversalPlayer capable d’effectuer un parcours BFS ou DFS, spécifié à la création du joueur. Placez ce fichier dans le sous-dossier players de votre workspace PyRat.

• Enfin, téléchargez ce fichier de jeu avec BFS et ce fichier de jeu avec DFS. Placez ces fichiers dans le sous-dossier games de votre workspace PyRat.

Les fichiers BFSTraversal.py et DFSTraversal.py sont déjà fonctionnels. Regardez-les pour comprendre leurs différences.

Une fois terminé, lancez le script visualize_TraversalPlayer.py pour exécuter des parties avec le nouveau joueur.

5 — Arrêter l’algorithme de parcours plus tôt

Pour calculer les informations nécessaires pour se déplacer vers le morceau de fromage, il suffit uniquement de savoir où se trouve ce fromage. Cependant, le BFS et le DFS sont des algorithmes qui explorent le graphe jusqu’à ce que tous les sommets soient visités.

Dans notre cas, tous les calculs effectués après avoir trouvé ce morceau de fromage sont inutiles, car vous n’allez pas utiliser ces résultats. Une amélioration possible consiste donc à modifier l’algorithme de parcours pour qu’il s’arrête dès que toutes les informations nécessaires sont disponibles.

Pour aller encore plus loin

6 — Un parcours en profondeur récursif

Comme le parcours en profondeur utilise une pile, et que les fonctions récursivent exploitent la pile d’appels de fonctions pour calculer un résultat, il est assez facile de programmer un DFS récursivement.

7 — Programmation défensive

Dans les fichiers de tests que nous vous avons fournis, nous n’avons testé que le comportement attendu de la méthode testée. Lorsqu’on programme en pensant à un utilisateur, il est également recommandé d’anticiper les erreurs que l’utilisateur pourrait commettre et de lever une exception dans ce cas. Ceci s’appelle la programmation défensive.

Dans le cas de test_DFS.py, on pourrait par exemple imaginer les erreurs suivantes :

• Appeler la fonction traversal(...) à partir d’un sommet de départ qui n’existe pas.
• Appeler la fonction traversal(...) sur un labyrinthe qui n’est pas connexe (c’est à dire qu’il existe des cases telles qu’aucun chemin ne permet d’aller de l’une à l’autre).
• Appeler la fonction traversal(...) avec des arguments inattendus.
• Appeler la fonction find_route(...) avec un sommet de départ qui n’existe pas.
• Appeler la fonction find_route(...) avec un sommet d’arrivée qui n’existe pas.
• Appeler la fonction find_route(...) avec des arguments inattendus.
• Appeler la fonction find_route(...) avec une table de routage invalide.
• Appeler la fonction find_route(...) avec des sommets de départ et d’arrivée qui ne peuvent pas être reliés par un chemin.

Dans ces cas, il aurait été utile pour l’utilisateur d’obtenir une exception personnalisée, indiquant son erreur. Pour ce qui est des tests unitaires, vous pouvez vérifier que ces exceptions sont bien levées en utilisant self.assertRaises(...).

Pour un exemple, vous pouvez consulter le fichier Traversal.py fourni dans l’archive plus haut. Si l’on appelle find_route(...) avant d’avoir appelé traversal(...), une exception sera levée, car la table de routage n’a pas encore été initialisée.

8 — L’algorithme IDDFS

Une autre piste que vous pouvez explorer est de programmer un algorithme appelé IDDFS. Cet algorithme combine des aspects des algorithmes BFS et DFS, tout en nécessitant moins de mémoire que les deux.

9 — L’algorithme de Seidel

Alors que le BFS fournit le plus court chemin d’un sommet vers tous les autres, l’algorithme de Seidel permet d’obtenir les plus courts chemins entre tous les sommets dans un graphe non pondéré.