The PyRat project

Presentation & objectives

Welcome to the project page! The project will last all the semester, and will resolve around a software called PyRat.

In a few words, this software is a video game, in which you control a small rat in a maze. There are pieces of cheese at various places of the maze, that the rat wants to eat. In a first step, your goal is to help the rat eat all pieces of cheese. Later in the project, we will introduce one or more other players, that also want to get some cheese. The goal will then be to grab more pieces of cheese than the opponents.

In this project, you will learn about graph theory, that will help formalize some aspects of the game. You will study some classic algorithms, and will directly put them into practice to solve problems of increasing complexity.

The project will end with an informal tournament. All students will submit a program that they designed to challenge an opponent in a PyRat game. Detailed instructions will be provided in Session 6.

Schedule

• Session 1 – Discover the project and the PyRat software.

  First, we will discover what the project is about. Additionally, we will install the PyRat software, and follow its tutorial. At the end of the session, we should know how to write a PyRat program.

• Session 2 – Catch a single piece of cheese.

  In this session, there will be a single piece of cheese somewhere in the maze, that the rat will have to grab. To do so, we will study traversal algorithms, in particular the depth-first search (DFS) and the breadth-first search (BFS) algorithms.

• Session 3 – Catch a single piece of cheese… with mud.

  Now, we will introduce mud in the maze, that requires more than one move to cross. This change requires the introduction of a new traversal algorithm: Dijkstra’s algorithm.

• Session 4 – Catch multiple pieces of cheese.

  To make things more complex, the maze will then contain several pieces of cheese. The goal is to grab them all in a minimum number of moves. To do so, we will study the traveling salesperson problem (TSP) and will solve it naively.

• Session 5 – Catch multiple pieces of cheese… more efficiently.

  As seen in the previous session, the TSP is hard to solve. In this session, we will study approximate algorithms, that sacrifice optimality for less computation time. We will thus study greedy algorithms and other heuristics.

• Session 6 – Challenge an opponent in a PyRat game.

  The final objective of the project is to challenge an opponent in a PyRat game. You will have some time to work on a program of your own, based on your personal ideas. Maybe you will choose to adapt previous session programs, or develop solutions leveraging reinforcement learning, meta-heuristics, etc. The choice is yours!

How is a session organized?

Except for the first session, the project will be organized in flipped classes.

• Before the class – You will have to study a certain number of articles (most take the form of videos). You should carefully study them, so that you are ready to program during the classes. On each session page, you will find these articles, but also self-assessment quizzes (not evaluated), for you to verify that you understood everything correctly.

  Information

  These videos are also used in a MOOC, so don’t worry if they sometimes talk about the MOOC’s contents, a “previous lesson”, etc. Just ignore that.

• During the class – We will start with a short Wooclap test, to make sure that you understood all the key elements needed to start working on the project. If some elements need more explanations, we will take a little time to detail them more. The rest of the class will be dedicated to addressing the objective of the session. To do so, you will have to write some programs to guide the rat in the PyRat maze.

• After the class – As the project is organized in flipped classes, you will have to prepare the next session. Also, you will have to complete the current session before the start of the next one. This is especially important for the sessions that will be evaluated.

Evaluation

When?

You will be evaluated in multiple ways during the project:

• Quizzes at the beginning of sessions – Each session (except the first one) will start with a small quiz to verify that you understood well the concepts necessary to start programming efficiently.

• A deliverable of session 3 – Before the start of session 4, you should provide a deliverable of the codes asked in practical session 3. Instructions will be provided on the dedicated page.

• A deliverable of session 5 – Before the start of session 6, you should provide a deliverable of the codes asked in practical session 5. Instructions will be provided on the dedicated page.

• A final presentation – At the end of the course, you should present your strategy for winning a PyRat game during a 10mn talk. Instructions will be provided on the dedicated page.

How?

As the goal of the Wooclap quizzes is to make sure that you understood the notions, you will be evaluated individually for them. They will take place on Moodle (check the link at the bottom of the menu).

For the other three evaluations, you will not be evaluated on the same aspects each time. In fact, the whole project is made in teams of three students, so responsibilities will change from an evaluation to the other. In other words, for each evaluation, the grade will be distributed as follows:

• A common grade – 80% of the grade will be the same for all students of the project. This includes ensuring that the deliverable is functional, respects the asked requirements, and that the work is complete. In addition, provided codes should be documented and unit tests should be provided.

• An individual grade – The remaining 20% will be individual, and will focus on a particular part of the deliverable. We distinguish three such parts:

  • Code – The code should work as expected, and be clean. Variables and functions should have correct names, there should be useful comments to help understand the codes… These good programming practices will be covered during session 1 of the algorithms & programming course.

  • Documentation – The code should be well documented. Each function should indicate the expected inputs and outputs, and a small paragraph to describe its use.

  • Unit tests – Unit tests should be developed to test the functions developed in the practical sessions. These tests should be well-thought, and cover a sufficiently large number of cases to give confidence in your codes. Development of unit tests will be covered during session 4 of the algorithms & programming course.

For deliverable 1, student A will be responsible of the code, student B of the documentation, and student C of the tests. Then, for deliverable 2, student B will be responsible of the code, student C of the documentation, and student A of the tests. Finally, for the final presentation, student C will be responsible of the code, student A of the documentation, and student B of the tests.