Activité pratique

Durée2h30

Consignes globales

Dans cette activité, vous écrirez un programme PyRat qui affronte un adversaire dans un labyrinthe. Contrairement aux activités précédentes, nous ne vous imposons aucune consigne : les sections « Pour aller plus loin » et « Pour aller encore plus loin » proposent seulement des pistes.

Contenu de l’activité

Écrire votre propre programme PyRat

À faire

Le but de cette activité est d’écrire un programme capable d’affronter un adversaire dans une partie de PyRat.

Pour atteindre cet objectif, plusieurs pistes sont possibles :

  • Consultez les sections « Pour aller plus loin » et « Pour aller encore plus loin » des différents articles et séances précédents pour des idées.
  • Réutilisez ce que vous avez déjà fait et améliorez vos codes existants.
  • Cherchez sur Internet des solutions existantes pour des jeux similaires.
  • Soyez inventif(ve)s et imaginez votre propre solution !

Nous vous encourageons fortement à tester votre programme dans la configuration du tournoi présentée sur la page du tournoi.

Information

Bien que l’évaluation finale porte sur vos idées et votre inventivité et ne requière pas de code fonctionnel, nous vous demandons malgré tout de travailler sur un programme pendant cette activité. Cela sera utile pour deux raisons :

  • Vous ferez face à des problèmes pratiques, ce qui peut enrichir votre présentation.
  • Vous pourriez obtenir un excellent programme pour le tournoi final PyRat !

Pour aller plus loin

Anticiper l’adversaire

Les joueurs gloutons de la séance 5 réagissent à ce que fait l’adversaire, mais ne l’anticipent pas : ils peuvent viser un morceau de fromage que l’adversaire atteindra de toute façon avant eux, et perdre ainsi de nombreux tours.

Or, vous connaissez la position de l’adversaire (game_state.player_locations, et game_state.get_opponents(...) donne les noms des adversaires d’un joueur, c’est-à-dire les joueurs qui ne sont pas dans son équipe), et vous savez calculer des distances. Lancer l’algorithme de Dijkstra depuis sa position vous indique, pour chaque morceau de fromage, qui de vous deux peut l’atteindre en premier.

À faire

Essayez d’exploiter cette information. Par exemple :

  • Ne visez que les morceaux de fromage que vous atteignez strictement avant l’adversaire, et laissez-lui les autres.
  • Supposez que l’adversaire est un glouton qui va vers le morceau de fromage le plus proche de lui, prédisez sa cible, et évitez-la (ou au contraire, interceptez-la si vous êtes plus près).
  • Pensez au score final : pour gagner, il suffit d’attraper plus de la moitié des morceaux de fromage. Quels morceaux de fromage sont alors décisifs ?

Comparez ensuite votre joueur à GreedyEachTurn, en vous inspirant du script evaluate_greedy_matches.py de la séance 5.

Ces idées sont des premiers pas vers la théorie des jeux étudiée dans les articles de cette séance : vous ne cherchez plus seulement le meilleur chemin, mais la meilleure décision compte tenu de ce que fera l’adversaire.

Recherche arborescente Monte-Carlo

L’algorithme minimax, présenté dans les articles de cette séance, explore tout l’arbre des coups possibles, ce qui est impossible dans une partie de PyRat avec beaucoup de morceaux de fromage. La recherche arborescente Monte-Carlo (Monte Carlo Tree Search, ou MCTS) contourne ce problème : au lieu d’explorer tout l’arbre, elle simule de nombreuses fins de partie (par exemple, en faisant jouer deux gloutons à partir de l’état courant), et concentre ses simulations sur les coups qui semblent les plus prometteurs. C’est l’une des briques des programmes qui ont battu les meilleur(e)s joueur(se)s humain(e)s au jeu de go.

À faire

Pour appliquer MCTS à PyRat, il vous faut un simulateur rapide d’une partie : une fonction qui, à partir de la position des joueurs et des morceaux de fromage restants, calcule le score final quand les deux joueurs suivent une stratégie donnée. Essayez d’en écrire un (sans la boue dans un premier temps), puis de l’utiliser pour choisir, à chaque morceau de fromage attrapé, la prochaine cible parmi les plus proches.

Pour aller encore plus loin

Jouer en équipe : le problème de tournées de véhicules

Jusqu’à présent, chaque équipe ne comptait qu’un seul joueur. Pourtant, PyRat permet de mettre plusieurs joueurs dans une même équipe : il suffit de leur donner le même nom d’équipe. Le score d’une équipe est la somme des scores de ses membres.

​
from pyrat import StartingLocation

# A team of three rats, starting at random locations
for i in range(3):
    game.add_player(MyPlayer(name="Rat %d" % i), team="Team Ratz", location=StartingLocation.RANDOM)

Supposons que votre équipe compte plusieurs rats, seuls dans le labyrinthe. Comment se répartir les morceaux de fromage pour tous les attraper le plus vite possible ? Si chaque rat applique un algorithme glouton de son côté, ils risquent de viser les mêmes morceaux de fromage, et de se gêner.

Ce problème est une généralisation du TSP, appelée problème de tournées de véhicules (Vehicle Routing Problem, ou VRP) : plusieurs véhicules (les rats) doivent se partager des clients à visiter (les morceaux de fromage), chacun suivant sa propre tournée. Comme le TSP en est un cas particulier (avec un seul véhicule), le VRP est lui aussi NP-difficile.

Le VRP se décline en de nombreuses variantes, selon les contraintes (capacité des véhicules, horaires de passage imposés, retour ou non au dépôt, etc.), mais aussi selon l’objectif choisi. Les plus courants sont les suivants :

  • Minimiser la distance totale — On minimise la somme des longueurs des tournées. C’est l’objectif du VRP « classique », où l’on cherche par exemple à économiser le carburant de toute la flotte.
  • Minimiser la tournée la plus longue — On minimise la longueur de la tournée la plus longue, c’est-à-dire l’heure à laquelle le dernier client est servi. On parle de VRP min-max, ou de minimisation du makespan. C’est l’objectif à choisir lorsque le travail n’est fini que quand tous les véhicules ont terminé.
  • Minimiser la somme des heures de passage — On cherche à servir chaque client le plus tôt possible, en moyenne. On parle de VRP cumulatif. C’est l’objectif des livraisons urgentes, par exemple pour acheminer de l’aide après une catastrophe.
  • Minimiser le nombre de véhicules — Lorsque les véhicules ont une capacité limitée, on cherche combien il en faut au minimum pour servir tous les clients.

Ces objectifs ne mènent pas aux mêmes solutions. Prenons par exemple un couloir de 11 cases numérotées de 0 à 10, sans boue, avec deux joueurs de la même équipe (un rat en case 0 et un python en case 5), et des morceaux de fromage en cases 4, 6 et 10 :

Couloir de 11 cases, avec un rat en case 0, un python en case 5, et des morceaux de fromage en cases 4, 6 et 10

Comparons deux répartitions :

Répartition Distance totale Tour du dernier ramassage Somme des tours de ramassage
Le python ramasse tout ($5 \rightarrow 4 \rightarrow 6 \rightarrow 10$), le rat ne bouge pas 7 7 $1 + 3 + 7 = 11$
Le rat va en case 4, le python fait $5 \rightarrow 6 \rightarrow 10$ 9 5 $4 + 1 + 5 = 10$

Minimiser la distance totale choisit la première répartition, qui laisse le rat inactif : l’équipe met alors 2 tours de plus à tout ramasser. Ici, minimiser la somme des tours de ramassage choisit aussi la seconde répartition (10 contre 11).

Dans PyRat, une équipe seule dans le labyrinthe veut avoir ramassé tous les morceaux de fromage le plus tôt possible : on cherche donc la répartition qui minimise le tour auquel le dernier morceau de fromage est ramassé. Ce tour est la longueur de la tournée la plus longue, mesurée en nombre de tours (boue comprise) : c’est le VRP min-max. Deux autres particularités :

  • Chaque rat part de sa propre position (on parle de VRP multi-dépôts).
  • Les rats n’ont pas besoin de revenir à leur position de départ (on parle de VRP ouvert).
À faire
  • Écrivez un joueur destiné à jouer en équipe, qui calcule une répartition optimale des morceaux de fromage entre les membres de l’équipe (c’est-à-dire qui minimise le tour auquel le dernier morceau de fromage est ramassé), à l’aide d’un solveur.
  • Comme le TSP, le VRP devient vite trop long à résoudre exactement lorsque le nombre de morceaux de fromage augmente. Écrivez aussi un joueur qui approxime une solution avec une heuristique, et comparez sa solution à la solution optimale.
  • Comparez enfin le nombre de tours nécessaires à une équipe de chacun de ces joueurs et à une équipe de joueurs GreedyEachTurn, pour différentes tailles d’équipe.
Information

Quelques indications :

  • L’attribut game_state.teams donne, pour chaque équipe, la liste de ses membres. Chaque joueur peut donc connaître ses coéquipier(ère)s et leurs positions.
  • Les joueurs ne peuvent pas communiquer entre eux : en mode GameMode.MATCH, chacun s’exécute même dans son propre processus. Une solution est que chaque membre calcule le plan de toute l’équipe avec le même algorithme, et suive sa propre tournée. Mais attention : cet algorithme doit alors être déterministe, pour que tous les membres trouvent le même plan !
  • Pour la solution exacte, la bibliothèque OR-Tools, utilisée lors de la séance 4, fournit un solveur appelé CP-SAT (si vous ne l’avez pas encore installée, lancez uv add ortools depuis le dossier pyrat_workspace). Sa contrainte AddMultipleCircuit permet de modéliser des tournées qui partent toutes d’un même sommet (un « dépôt »), ce qui peut être un sommet virtuel relié aux positions de départ des rats.
  • Pour l’heuristique, une approche simple consiste à construire les tournées en insérant les morceaux de fromage un par un, à l’endroit qui allonge le moins la tournée la plus longue, puis à améliorer chaque tournée avec 2-opt (voir la séance 5).

Voici un exemple de trois joueurs travaillant en équipe, pour minimiser le tour auquel le dernier morceau de fromage est ramassé :

Coordination d’agents

Le VRP n’est qu’un des problèmes qui apparaissent lorsque plusieurs agents doivent coopérer. Dans PyRat comme dans un entrepôt rempli de robots, d’autres questions se posent :

  • Problème dynamique — Que faire si de nouveaux morceaux de fromage apparaissent pendant la partie ? Il faut alors replanifier en cours de route, sans tout recalculer.
  • Recherche de chemins multi-agents — Comment planifier les chemins de plusieurs agents qui ne doivent pas se trouver au même endroit au même moment, comme des robots dans un entrepôt ? (Ce n’est pas une contrainte dans PyRat, mais c’en serait une intéressante.)
  • Équipes adverses — Lorsque deux équipes de plusieurs rats s’affrontent, faut-il envoyer un rat disputer ses cibles à l’adversaire, ou tous les rats ramasser du fromage ? (Dans PyRat, les joueurs peuvent occuper la même case : on ne peut pas bloquer physiquement un adversaire.)

Apprentissage par renforcement

Une autre approche consiste à apprendre une stratégie, plutôt qu’à la programmer : un programme joue de très nombreuses parties, et ajuste peu à peu sa manière de jouer en fonction des récompenses obtenues (les morceaux de fromage attrapés). C’est l’apprentissage par renforcement, qui a permis à AlphaZero d’apprendre seul à jouer aux échecs et au go. Le mode GameMode.SIMULATION de PyRat, qui joue des parties sans affichage et très rapidement, est un bon point de départ pour générer les parties nécessaires.