The PyRat project

Présentation & objectifs

Bienvenue sur la page du projet !

Le projet durera tout le semestre, et tournera autour d’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.
Il y a des morceaux de fromage à différents endroits du labyrinthe, que le rat veut manger.
Dans un premier temps, votre objectif est d’aider le rat à manger tous les morceaux de fromage.
Plus tard dans le projet, nous introduirons un ou plusieurs autres joueurs, qui veulent aussi obtenir du fromage.
Le but sera alors de récupérer plus de morceaux de fromage que les adversaires.

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

Le projet se terminera par un tournoi informel.
Tous les étudiants soumettront un programme qu’ils auront conçu pour défier un adversaire dans une partie de PyRat.
Des instructions détaillées seront fournies dans la Session 6.

Planning

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

  D’abord, nous découvrirons de quoi il s’agit dans ce projet.
  De plus, nous installerons le logiciel PyRat, et suivrons son tutoriel.
  À la fin de la session, nous devrions savoir comment écrire un programme PyRat.

• Session 2 – Attraper un seul morceau de fromage.

  Dans cette session, il y aura un seul morceau de fromage quelque part dans le labyrinthe, que le rat devra attraper.
  Pour cela, nous étudierons des algorithmes de parcours, en particulier les algorithmes depth-first search (DFS) et breadth-first search (BFS).

• Session 3 – Attraper un seul morceau de fromage… avec de la boue.

  Maintenant, nous introduirons de la boue dans le labyrinthe, qui nécessite plus d’un déplacement pour être traversée.
  Ce changement nécessite l’introduction d’un nouvel algorithme de parcours : Dijkstra’s algorithm.

• Session 4 – Attraper plusieurs morceaux de fromage.

  Pour complexifier les choses, le labyrinthe contiendra alors plusieurs morceaux de fromage.
  Le but est de tous les attraper en un nombre minimal de déplacements.
  Pour cela, nous étudierons le traveling salesperson problem (TSP) et le résoudrons naïvement.

• Session 5 – Attraper plusieurs morceaux de fromage… plus efficacement.

  Comme vu dans la session précédente, le TSP est difficile à résoudre.
  Dans cette session, nous étudierons des algorithmes approximatifs, qui sacrifient l’optimalité pour un temps de calcul réduit.
  Nous étudierons donc les greedy algorithms et d’autres heuristics.

• Session 6 – Défier un adversaire dans une partie de PyRat.

  L’objectif final du projet est de défier un adversaire dans une partie de PyRat.
  Vous aurez du temps pour travailler sur un programme personnel, basé sur vos idées.
  Peut-être choisirez-vous d’adapter les programmes des sessions précédentes, ou de développer des solutions utilisant le reinforcement learning, les meta-heuristics, 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 sous forme de vidéos).
  Vous devez les étudier attentivement, afin d’être prêt à programmer pendant les cours.
  Sur chaque page de session, vous trouverez ces articles, mais aussi des quiz d’auto-évaluation (non notés), pour vérifier que vous avez bien compris.

  Information

  Ces vidéos sont aussi utilisées dans un MOOC, donc ne vous inquiétez pas si elles parlent parfois du contenu du MOOC, d’une “leçon précédente”, etc.
  Ignorez simplement cela.

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

• Après le cours – Comme le projet est organisé en classes inversées, vous devrez préparer la session suivante.
  De plus, vous devrez compléter la session en cours avant le début de la suivante.
  Ceci est particulièrement important pour les sessions qui seront évaluées.

Évaluation

Quand ?

Vous serez évalué de plusieurs manières durant le projet :

• Quiz au début des sessions – Chaque session (sauf la première) commencera par un petit quiz pour vérifier que vous avez bien compris les concepts nécessaires pour commencer à programmer efficacement.

• Un livrable de la session 3 – Avant le début de la session 4, vous devrez fournir un livrable des codes demandés lors de la session pratique 3.
  Les instructions seront fournies sur la page dédiée.

• Un livrable de la session 5 – Avant le début de la session 6, vous devrez fournir un livrable des codes demandés lors de la session pratique 5.
  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 lors d’un exposé de 10 minutes.
  Les instructions seront fournies sur la page dédiée.

Comment ?

Comme le but des quiz Wooclap est de s’assurer que vous avez compris les notions, vous serez évalué individuellement pour ceux-ci.
Ils auront lieu sur Moodle (vérifiez le lien en bas du menu).

Pour les trois autres évaluations, vous ne serez pas évalué sur les mêmes aspects à chaque fois.
En effet, tout le projet est 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 – 80 % de la note sera la même pour tous les étudiants du projet.
  Cela inclut la garantie que le livrable est fonctionnel, respecte les exigences demandées, et que le travail est complet.
  De plus, les codes fournis doivent être documentés et des tests unitaires doivent être fournis.

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

  • Code – Le code doit fonctionner comme attendu, et être propre.
    Les variables et fonctions doivent avoir des noms corrects, il doit y avoir des commentaires utiles pour aider à comprendre le code…
    Ces bonnes pratiques de programmation seront abordées lors de la session 1 du cours d’algorithmes & programmation.

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

  • Tests unitaires – Des tests unitaires doivent être développés pour tester les fonctions développées lors des sessions pratiques.
    Ces tests doivent être bien réfléchis, et couvrir un nombre suffisamment large de cas pour donner confiance dans vos codes.
    Le développement des tests unitaires sera abordé lors de la session 4 du cours d’algorithmes & programmation.

Pour le livrable 1, l’étudiant A sera responsable du code, l’étudiant B de la documentation, et l’étudiant C des tests.
Puis, 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.