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

Before arriving in class, you should study the following articles:

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

You can verify your understanding of these articles here:

• Follow this link for a 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:

• Follow this link for the 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. This is an optional event, only made for you to have fun and challenge your friends. Therefore, there is no evaluation associated.

Here are a few videos that were taken since the PyRat course was created! Some are more “commercial” than others, but that’s a cool overview of the atmosphere during the tournament, as well as a glimpse on the various versions of the game!

• 2015.
• 2016.
• 2019.

Tournament organization

Unfortunately, we won’t have time to get everyone to compete in the final tournament. Consequently, we will proceed in the form of pools in which all players will compete against each other, in two winning rounds. In each pool, we will keep the best program, i.e., the one with the highest number of points in the pool matches (1 point for a win, 0.5 for a tie). In the event of a tie after all matches, we will consider as best program the program with lower total execution time.

Once the winners of the pools have been determined (16 AIs), the tournament itself will take place in an amphitheater. The matches will be randomly determined.

The winner of the tournament will win a trophy, and their AI will serve as the final boss for next year’s students!

PyRat parameters

The following options will be used to create the PyRat games:

• maze_width: 31.
• maze_height: 29.
• cell_percentage: 80.0.
• wall_percentage: 60.0.
• mud_percentage: 20.0.
• mud_range: [4, 9].
• nb_cheese: 41.
• preprocessing_time: 3.0.
• turn_time: 0.1.

Here is the game script we will use to run the tournament.

How to participate?

In order to participate, you have to submit your program on Moodle, at least 3 days before the date of the tournament.

Your program should be placed in an achive named team_name.zip, where team_name is the name of your team. This archive should be structured as follows:

team_name.zip
|
|_ games
|  |  # Put a simple game script here that starts a game with your program
|  |  # This will allow us to check that it works
|  |  # Also, it will show us if your player needs extra arguments when instantiated
|  |_ # Take inspiration from the visualize_XXX.ipynb game scripts with the tournament settings
|
|_ players
|  |  # Put your player here
|  |  # This directory should only contain your player file that will participate in the tournament
|  |_ # If you need functions defined in other players, please put them in utils
|
|_ utils
|  |_ # Put your additional codes here (if any)
|
|_ data
|  |_ # Put your other files here (if any)
|
|_ README_TOURNAMENT.md

You can find the file README_TOURNAMENT.md at this link. Please replace everything in <...>.