Challenge an opponent in a PyRat game

Presentation & objectives

In this session, we introduce an opponent in the maze. Your objective is to create a program that will win against it. To reach that goal, we present you a few notions of combinatorial game theory. This is just a possible direction to give you ideas, but you can choose any solution!

The notions above are covered by a few articles that you have to study before the class. In the practical activity, you will have to program a solution to the TSP based on an exhaustive search. This will allow you to grab all pieces of cheese in a minimum number of turns.

Contrary to previous sessions, there will be no evaluated quiz this time, to give you more time to work on your programs.

Before the class

Technical requirements

To be able to start working on the activity, you should meet the following requirements:

• Please bring your own computer.
• Make sure to have a functional network connection.

Submit your deliverable

Don’t forget, you have to submit your deliverable for session 5 before the start of this session!

Prior knowledge acquisition

To be able to start the practical activity efficiently, we introduced some needed concepts at the end of the previous session. Here are the slides used in class:

• Slides of the session.

These slides only cover the main elements of the course, and many more details are given in the associated articles. Thus, you should study the following articles at home after before the session:

• Combinatorial game theory.
• Computing winning positions in a game.

You can verify your understanding of these articles here:

• Self-assessment quiz.

During the class

Attribute roles

In the previous evaluation, you had to select one role, corresponding to your responsibility in the evaluated deliverable. This time, you have to take a different role. Use the following table to find which is yours:

Practical activity

The class is dedicated to a practical activity. Once you are done with all the things above, click on the link below to start:

• Practical activity.

After the class

Final presentation

This session is evaluated. The modality of evaluation is described on the project main page. During the final exam, you will have to make a short presentation to answer the following question:

How can you defeat an opponent in a PyRat game?

This presentation should respect the following (evaluated) points:

• It should last 10mn.
• You should prepare slides.
• Every student in the group should speak for an approximately equal duration.
• We will ask questions for 5mn after.

Regarding contents, we ask you that you present your strategy to defeat an opponent. You do not need to have a working code to reach that objective. We want to evaluate your inventivity, and your ability to design solutions for a given problem.

Here is a possible plan for your presentation. This is only an example, don’t hesitate to add other points. In particular, if you have a working strategy, please make a demo!

• Introduction – Who is responsible for which part? What is the plan of your presentation?
• Related work – Introduce the specific elements you need to present your strategy.
• A possible strategy – What is your strategy about? Why do you think it is interesting?
• Algorithmic and code elements – How would you design an algorithm to realize that strategy? Can you identify some standard algorithms to use? Which functions have you identified?
• How to evaluate the strategy – What tests should you perform to evaluate if your strategy is good against an opponent? What unit tests do you think are important to validate your code?
• Conclusions & perspectives – What are the strengths, limits, and possible improvements of your strategy?

Here are how responsabilities apply in this final presentation:

• Student in charge of the code quality – That student should address the part of the presentation on algorithmic and code elements.
• Student in charge of the unit tests – That student should address the part of the presentation on strategy evaluation.
• Student in charge of the documentation – That student should ensure the quality of the slides and clarity of the presentation.

The PyRat tournament

After the final exam, there is a dedicated time slot for a PyRat tournament. Please check the tournament page for details!