Le projet PyRat

Présentation & objectifs

Bienvenue sur la page du projet !

Le projet durera tout le semestre, et sera centré sur un logiciel appelé PyRat. En quelques mots, ce logiciel est un jeu vidéo, dans lequel vous contrôlez un petit rat dans un labyrinthe grâce à des codes Python. Il y a des morceaux de fromage à différents endroits du labyrinthe, que le rat veut manger.

Dans un premier temps, votre objectif sera d’aider le rat à manger tous les morceaux de fromage. Plus tard dans le projet, nous introduirons un ou plusieurs autres joueurs, qui voudront également ramasser des fromages. L’objectif sera alors de ramasser plus de morceaux de fromage que ceux-ci.

Dans ce projet, que vous réaliserez en trinômes, vous vous familiariserez à la théorie des graphes, qui aidera à formaliser certains aspects du jeu. Vous étudierez des algorithmes classiques, et vous les mettrez directement en pratique pour résoudre des problèmes de complexité croissante.

Le projet se terminera par un tournoi informel en amphi. Tous les étudiants soumettront un programme qu’ils auront conçu pour affronter un adversaire dans une partie de PyRat.

Calendrier

• Séance 1 – Découvrir le projet et le logiciel PyRat.

  La première séance a pour but de mettre en place le projet. Vous commencerez par installer PyRat, mettre en place un dépôt Git, et suivre un tutoriel. À la fin de la séance, vous devriez savoir comment écrire un premier programme PyRat.

• Séance 2 – Attraper un seul morceau de fromage.

  Dans cette séance, il y aura un seul morceau de fromage quelque part dans le labyrinthe, que le rat devra attraper. Pour ce faire, vous étudierez les algorithmes de parcours de graphe, en particulier le parcours en profondeur (DFS) et le parcours en largeur (BFS).

• Séance 3 – Attraper un seul morceau de fromage… avec de la boue.

  Nous introduirons ensuite de la boue dans le labyrinthe, qui prend plus d’un tour pour être traversée. Ce changement nécessite l’introduction d’un nouvel algorithme de parcours : l’algorithme de Dijkstra.

• Séance 4 – Attraper plusieurs morceaux de fromage.

  Pour rendre les choses plus complexes, le labyrinthe contiendra dès la séance 4 plusieurs morceaux de fromage. L’objectif sera alors de tous les ramasser en un nombre minimum de coups. Pour ce faire, vous étudierez le problème du voyageur de commerce (TSP) et le résoudrez de manière naïve.

• Séance 5 – Attraper plusieurs morceaux de fromage… plus efficacement.

  Comme vu lors de la séance 4, le TSP est difficile à résoudre optimalement. Dans cette séance, vous étudierez des algorithmes d’approximation, qui sacrifient l’optimalité pour un temps de calcul réduit. En particulier, vous verrez des algorithmes gloutons et d’autres heuristiques.

• Séance 6 – Affronter un adversaire dans une partie de PyRat.

  L’objectif final du projet est d’affronter un adversaire dans une partie de PyRat. Vous aurez du temps pour travailler sur un programme personnel, basé sur vos propres idées. Peut-être choisirez-vous d’adapter les programmes des séances précédentes, ou de développer des solutions à base d’IA, des méta-heuristiques, etc. ? Le choix vous appartient !

Comment est organisée une session ?

À l’exception de la première session, le projet sera organisé en classes inversées.

• Avant le cours – Vous devrez étudier un certain nombre d’articles (la plupart prennent la forme de vidéos). Vous devrez les étudier attentivement, afin d’être prêts à programmer pendant les cours. Sur chaque page de séance, vous trouverez ces articles, mais aussi des quiz d’auto-évaluation (non notés), pour vérifier que vous avez bien tout compris.

  Information

  Ces vidéos sont en anglais, car également utilisées dans un MOOC. Ne vous inquiétez pas si elles parlent parfois du contenu du MOOC, d’une “leçon précédente”, etc. Ignorez simplement ces références.

• Pendant le cours – Nous commencerons par un court test Wooclap, afin de vérifier que vous avez bien compris tous les éléments clés nécessaires pour commencer à travailler sur le projet. Si certains points nécessitent plus d’explications, nous prendrons un peu de temps pour les détailler. Le reste du cours sera consacré à l’objectif de la séance. Pour ce faire, vous devrez écrire des programmes pour guider le rat dans le labyrinthe de PyRat.

• Après le cours – Comme le projet est organisé en classes inversées, vous devrez préparer la séance suivante. De plus, vous devrez terminer le travail initié en classe avant le début de la suivante. Cela est particulièrement important pour les séances qui seront évaluées.

Évaluation

Quand ?

Vous serez évalués à plusieurs moments du projet, correspondant à des objectifs dans le jeu :

• Un livrable de la séance 3 – Avant le début de la séance 4, vous devrez fournir un livrable des codes demandés dans la séance 3. Cette évaluation portera sur vos solutions pour attraper un morceau de fromage dans le labyrinthe. Les instructions seront fournies sur la page dédiée.

• Un livrable de la séance 5 – Avant le début de la séance 6, vous devrez fournir un livrable des codes demandés dans la séance 5. Cette évaluation portera sur vos solutions pour attraper plusieurs morceaux de fromage. Les instructions seront fournies sur la page dédiée.

• Une présentation finale – À la fin du cours, vous devrez présenter votre stratégie pour gagner une partie de PyRat contre un adversaire lors d’un exposé de 10 minutes. Les instructions seront fournies sur la page dédiée.

Comment ?

Pour les trois évaluations, vous ne serez pas évalués sur les mêmes aspects à chaque fois. En effet, le projet est entièrement réalisé en équipes de trois étudiants, donc les responsabilités changeront d’une évaluation à l’autre. En d’autres termes, pour chaque évaluation, la note sera répartie comme suit :

• Une note commune – 70 % de la note sera identique pour tous les étudiants du projet. Cela inclut le fait que le livrable soit fonctionnel, respecte les exigences demandées, et que le travail soit complet. De plus, les codes fournis devront être documentés et des tests unitaires devront être fournis.

• Une note individuelle – Les 30 % restants seront individuels, et porteront sur une partie particulière du livrable. Nous distinguons trois parties :

  • Code – Le code doit fonctionner comme prévu, et être propre. Les variables et fonctions doivent avoir des noms corrects, il doit y avoir des commentaires utiles pour aider à comprendre les codes… Ces bonnes pratiques de programmation sont abordées lors de la pré-séance du cours de programmation.

  • Documentation – Le code doit être bien documenté. Chaque fonction doit indiquer les entrées et sorties attendues, et un petit paragraphe pour décrire son usage.

  • Tests unitaires – Des tests unitaires doivent être développés pour tester les fonctions réalisées dans les séances pratiques. Ces tests doivent être bien pensés, et couvrir un nombre suffisamment large de cas pour donner confiance dans vos codes. Le développement de tests unitaires sera abordé lors de la séance 3 du cours de programmation.

Pour le livrable 1, l’étudiant A sera responsable du code, l’étudiant B de la documentation, et l’étudiant C des tests. Ensuite, pour le livrable 2, l’étudiant B sera responsable du code, l’étudiant C de la documentation, et l’étudiant A des tests. Enfin, pour la présentation finale, l’étudiant C sera responsable du code, l’étudiant A de la documentation, et l’étudiant B des tests.