Activité pratique

Consignes globales

Lors de la séance précédente, vous avez vu qu’aucun algorithme exact ne permet d’attraper en un temps raisonnable les 21 morceaux de fromage d’une partie par défaut. Dans cette activité, vous allez donc développer un algorithme heuristique, qui trouve rapidement une bonne solution au TSP, sans garantie qu’elle soit optimale : un algorithme glouton. Nous allons travailler avec la configuration suivante :

• Un seul joueur, puis deux joueurs qui s’affrontent.
• Beaucoup de morceaux de fromage (20, par exemple).
• De la boue dans le labyrinthe (20% des arêtes, par exemple).

Vous rendrez ensuite votre glouton réactif, pour qu’il s’adapte à un adversaire. Dans les parties optionnelles, nous vous proposons d’améliorer les solutions trouvées (la partie sur 2-opt n’est pas très difficile, et elle est intéressante à tester), de factoriser vos codes, et d’essayer d’autres heuristiques.

Contenu de l’activité

L’algorithme glouton

Préparation

• players/greedy.py — Créez un nouveau joueur Greedy, héritant de la classe Player.

• games/visualize_greedy.py — Créez un script qui lancera une partie avec un joueur Greedy, dans un labyrinthe respectant les critères listés plus haut (arguments mud_percentage et nb_cheese). 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).

• tests/test_greedy.py — Créez un fichier qui contiendra les tests unitaires de votre joueur. Pour le moment, créez juste le fichier avec une classe de tests copiée-collée de test_exhaustive_player.py (ou de test_dijkstra.py), en changeant le nom de la classe et en enlevant les méthodes de test.

Découper le problème

Nous voulons utiliser l’heuristique suivante :

Le chemin le plus court qui passe par tous les morceaux de fromage peut être approximé en allant successivement vers le morceau de fromage le plus proche.

Plus tard dans cette activité pratique, nous vous demanderons de changer l’heuristique utilisée par votre algorithme glouton, et de le rendre réactif. Réfléchissez donc attentivement au découpage en méthodes : n’écrivez pas tout dans une seule méthode !

Implémentation

À quoi ça ressemble ?

À présent, utilisez votre script de visualisation pour observer votre joueur. La vidéo suivante montre un exemple de ce que vous devriez observer :

Comparer avec l’algorithme exhaustif

Comme vous l’avez vu dans les articles à étudier, un algorithme approché est un compromis entre précision, complexité, et parfois d’autres propriétés (mémoire requise, besoin de matériel spécifique…). Comparons votre joueur Greedy aux joueurs exacts de la séance précédente.

Évidemment, vous ne devriez pas aller très haut en nombre de morceaux de fromage pour les joueurs exacts. De plus, il est préférable de moyenner les résultats sur plusieurs parties, car il peut y avoir de la variabilité entre les parties. Comme lors des séances précédentes, faites jouer les joueurs sur les mêmes labyrinthes : cela permet de vérifier des propriétés qui doivent être vraies sur chaque labyrinthe.

Un glouton réactif

Jusqu’à présent, vous avez probablement suivi le même raisonnement que dans les séances précédentes : calculer le chemin dans preprocessing(...), et le dérouler à chaque appel de turn(...).

Maintenant, imaginons que vous ayez un adversaire dans le jeu. Si vous suivez un tel chemin prédéterminé sans considérer que votre adversaire peut manger certains morceaux de fromage entre-temps, vous allez sûrement perdre. En effet, vous allez essayer d’aller chercher des morceaux de fromage qui ont disparu, tandis que l’adversaire se concentrera sur ceux qui restent.

Une première amélioration

Revenons sur le fonctionnement de l’algorithme glouton :

• Considérez que vous êtes sur une case particulière du labyrinthe, et que vous exécutez votre algorithme glouton.
• La sortie devrait être une liste de morceaux de fromage à manger, triée dans l’ordre dans lequel les obtenir.
• Vous vous dirigez donc vers le premier morceau de fromage de cette liste.

Toutefois, au lieu de calculer cette liste une seule fois au début du jeu, vous pouvez la recalculer chaque fois que vous atteignez un morceau de fromage. Cela permet de s’adapter aux changements dans le labyrinthe, tels que les morceaux de fromage qui ont été mangés par l’adversaire.

Encore mieux

Le joueur GreedyEachCheese a encore un inconvénient. En effet, si l’adversaire récupère le morceau de fromage vers lequel nous nous dirigeons, nous terminerons quand même notre trajectoire.

Afin de le rendre encore plus réactif, repensons notre GreedyEachCheese :

• Considérez que vous êtes sur une case particulière du labyrinthe, et que vous exécutez votre algorithme glouton.
• La sortie devrait être le prochain morceau de fromage à récupérer (appelons-le c).
• Une fois que vous avez déterminé c, vous effectuez une action dans sa direction.

Si nous faisons un pas dans la direction de c, nous pouvons distinguer les deux scénarios suivants :

• c est toujours là — Alors, c est toujours le morceau de fromage le plus proche, car nous avons réduit le nombre de tours nécessaires pour y aller de 1 (ou plus s’il y avait de la boue). Nous devrions continuer dans sa direction.
• c a été attrapé par un adversaire — Alors, nous devrions nous concentrer sur un autre morceau de fromage.

Notez que nous pouvons traiter les deux scénarios en exécutant notre algorithme glouton à chaque tour pour déterminer la prochaine action (et non le prochain morceau de fromage comme GreedyEachCheese). En faisant cela, nous trouverions le même chemin à suivre si le fromage est toujours là, et nous nous déplacerions ailleurs si nécessaire.

Comparer les programmes

Vous avez maintenant trois algorithmes gloutons. Essayons de les comparer pour voir si les améliorations apportées ont un impact sur les résultats.

Vous devriez faire démarrer les joueurs à des emplacements aléatoires en utilisant un code similaire à celui-ci :

from pyrat import StartingLocation

game.add_player(player_1, team="Team Ratz", location=StartingLocation.RANDOM)
game.add_player(player_2, team="Team Pythonz", location=StartingLocation.RANDOM)

Sinon, les deux joueurs commenceront au milieu du labyrinthe, et suivront les mêmes trajectoires.

Pour une comparaison équitable, jouez chaque labyrinthe deux fois, en échangeant les positions de départ des deux joueurs.

Pour ce faire, vous pouvez utiliser un test de Student pour un échantillon, qui vérifie si la liste des différences de scores a (ou non) une moyenne de 0.

Pour aller plus loin

2-opt

Il existe de nombreux autres algorithmes approchés que vous pouvez utiliser pour approximer la solution au TSP. Nous pouvons distinguer deux catégories :

• Solution unique — Une seule solution au problème TSP est trouvée, puis éventuellement améliorée pour obtenir une meilleure solution. L’algorithme glouton entre dans cette catégorie.
• Solutions multiples — De nombreuses solutions sont trouvées et mélangées pour produire de meilleures solutions. Les algorithmes génétiques entrent dans cette catégorie.

L’algorithme glouton construit une solution unique et l’utilise ensuite. Il n’effectue aucune amélioration de cette solution, bien que certaines améliorations simples soient possibles.

Une heuristique simple pour s’appuyer sur le résultat glouton est 2-opt. L’algorithme part d’une solution particulière au TSP (soit aléatoire, soit construite avec un algorithme glouton), et l’améliore progressivement en supprimant les croisements du chemin.

Factoriser les codes

Avant d’essayer d’autres heuristiques (voir la section suivante), il est intéressant de factoriser votre code : ajouter une heuristique sera ensuite beaucoup plus simple. Comme lors des séances précédentes, l’idée est de séparer le joueur de l’algorithme qu’il utilise : ici, l’heuristique qui choisit le prochain morceau de fromage.

Voici un diagramme UML qui représente une factorisation possible. Consultez la séance 2 pour un guide sur la lecture de celui-ci.

Dans cette organisation :

• Chaque heuristique donne un score à chaque morceau de fromage restant (méthode abstraite score(...)), et select_next_cheese(...) choisit celui de plus petit score.
• Les heuristiques ont besoin de résultats de l’algorithme de Dijkstra, éventuellement depuis d’autres cases que la position du joueur. La méthode get_traversal(...) les fournit, en les mémorisant (voir la section « Réutiliser les parcours »).
• Au début de chaque partie, le joueur appelle la méthode preprocessing(...) de l’heuristique, qui vide la mémoire des parcours. Les heuristiques qui ont besoin de calculs préalables (par exemple, les parcours depuis tous les morceaux de fromage) la redéfinissent.
• GreedyPlayer crée l’heuristique choisie à sa création, et l’utilise à chaque tour.

Une autre heuristique

Jusqu’à présent, votre heuristique était de favoriser le morceau de fromage le plus proche. Voici deux autres heuristiques possibles que vous pouvez implémenter.

Pour ce faire, vous pouvez résoudre un TSP jusqu’à la profondeur $k$.

Pour ce faire, vous devez calculer une mesure de densité pour chaque morceau de fromage.

Réutiliser les parcours

Vous avez peut-être déjà remarqué que vous exécutez plusieurs fois l’algorithme de Dijkstra au cours du jeu. Parfois, vous utilisez même l’algorithme plusieurs fois à partir du même endroit. Cela peut arriver par exemple lorsque vous exécutez l’algorithme à partir d’une position que vous avez déjà visitée plus tôt dans le jeu, ou lors du calcul d’une heuristique à partir d’un morceau de fromage.

Puisque c’est une opération coûteuse, il peut être judicieux de stocker les résultats dans un attribut pour éviter de recalculer les tables de routage si vous l’avez déjà fait. C’est une approche que vous avez vue en cours, appelée mémoïsation.

Une solution rapide est de créer un attribut, et de vérifier d’abord son contenu avant d’exécuter le code coûteux :

def __init__ (...):
    self.dijkstras = {}

def my_method (...):
    if source not in self.dijkstras:
        self.dijkstras[source] = ...
    make_some_computations(self.dijkstras[source])

Pour aller encore plus loin

Recherche locale

La recherche locale est une méta-heuristique qui explore l’espace des solutions comme un parcours dans un graphe. L’idée est que nous allons créer un graphe de solutions dynamiquement, et l’explorer jusqu’à ce que nous soyons bloqués dans un optimum local. Plus précisément, pour implémenter une recherche locale, vous pouvez :

1. Partir d’une solution donnée $s$.

2. Identifier toutes les solutions voisines de $s$. Pour ce faire, vous devez définir une opération qui, lorsqu’elle est appliquée à $s$, générera de nouvelles solutions. Par exemple, vous pourriez permuter deux sommets dans la solution. Cela générera une solution voisine pour chaque paire de sommets.

3. Évaluer les voisins, et votre nouveau $s$ devient la meilleure solution parmi les voisins.

4. Boucler jusqu’à ce qu’aucun voisin ne soit meilleur que $s$.

Recuit simulé

Le recuit simulé est une méthode efficace pour approcher la solution du TSP. Comme pour la recherche locale, vous avez besoin d’une méthode pour générer des voisins. Vous pouvez ensuite appliquer le recuit simulé comme suit :

1. Partir d’une solution initiale $s$.

2. Initialiser le recuit simulé :

   • Définir la température initiale $T$.
   • Choisir une stratégie de décroissance de température, par exemple, décroissance exponentielle $T \leftarrow \alpha \cdot T$, où $\alpha$ est légèrement inférieur à 1 (par exemple, 0,99).
   • Définir un critère d’arrêt, tel qu’un nombre maximum d’itérations ou une température minimale.

3. Pour chaque itération :

   • Générer une nouvelle solution $s'$ en modifiant légèrement $s$.
   • Calculer l’augmentation de longueur $\delta = L(s') - L(s)$.
   • Si $s'$ est meilleure, l’accepter.
   • Si $s'$ est moins bonne, l’accepter avec une probabilité dépendant de la température actuelle et de la différence de coût. Cette probabilité est calculée comme $P = \exp\left(-\frac{\delta}{T}\right)$.
   • Réduire la température selon la stratégie de décroissance.

4. Arrêter lorsque la température est suffisamment basse ou après un nombre prédéfini d’itérations.