Practical activity
Duration2h30Presentation & objectives
This practical activity aims at getting you prepared for the PyRat project. You are going to install the software and to write a toy program for it.
This tutorial may be quite long. If you do not have enough time to complete it in class, please finish at home. It contains all the necessary elements to understand well the project.
Activity contents
1 — Installing PyRat
1.1 — Download and install PyRat
In order to install PyRat, please first make sure that you meet all the technical requirements mentioned in the main page of the session.
Then, head to the PyRat software repository, and follow the installation instructions.
1.2 — The PyRat workspace
During step 4 of the installation, you were asked to create a workspace, by running a command that creates a default directory called pyrat_workspace
.
This directory contains three subdirectories:
-
pyrat_workspace/players
– This directory contains a few players. A player is a Python code that describes how a character moves in the maze. We are going to analyze this in details in this practical activity. -
pyrat_workspace/games
– This directory contains a few scripts that start PyRat games. In few words, a script basically just creates a game and players, then adds players to the game, and starts the game. Again, we are going to detail this in this activity. -
pyrat_workspace/doc
– This directory contains the documentation of the PyRat software, and of the files in the two subdirectories above. It was generated automatically in step 5 of the installation process. Don’t hesitate to run the same command again later if you want to integrate your new programs to the doc.
These directories are where you should put all the codes you will develop in the project.
Please keep them organized, i.e., you should put the players you will develop in pyrat_workspace/players
and your scripts in pyrat_workspace/games
.
1.3 — Installation verification
Now, open Visual Studio Code, and add the pyrat_workspace
in your Visual Studio Code workspace.
Head to the pyrat_workspace/games
subdirectory, and open the sample_game.ipynb
script.
Then, run this script by clicking on the “Run All” button.
You should see a maze, with two players – a rat and a python – that move to get pieces of cheese.
You can close the game window at any time using the cross on top of the window, or by pressing the “Esc” key.
However, closing the interface will not stop the game, as the actual game runs in the background (check here for details). If you want to stop the game entirely, you need to stop the PyRat process, either by clicking the “Stop” button in Visual Studio Code, or by hitting “Ctrl + C” in the terminal where the process is running.
If the installation did not succeed, please do in that order:
- Check the issues section of the PyRat repository.
- If you could not find a solution, ask your teacher, or on the course Discord using the button at the bottom left of the page.
- If the problem persists (or if multiple persons have the same problem), please raise an issue on the PyRat repository.
2 — Working in groups
In order to work efficiently with the other students of your group, we suggest you two possible solutions.
The first option is a lot easier than the second one. If you do not know Git already, we advise you to use Live Share. You can then come back to Git later during the semester if you wish to work differently.
2.1 — Live Share
Easy to use | Requires the host to be connected |
You see where others are working in real time | The project will be stored on the host’s computer only |
No versioning of the files |
This extension of Visual Studio Code allows you to share your coding session, and to all work simultaneously on the same project. You should already have installed it during environment session 2.
2.2 — Git
Keeps the history of modifications | Needs time to understand |
Others do not need to be connected to work | Beware of conflicts if multiple persons work on the same file |
Very used in industry/research | You do not see other users in real time |
A Git repository is a place online where your code is stored. Authorized people can download a local copy of that code, work on it and push their modifications online.
2.2.1 — Create the Git repository
To setup a Git repository, one of the students of your group should first head to the school’s GitLab. That student is going to prepare the repository.
Others will then join it later.
While the first student is preparing the repository, they should make sure they have a Gitlab account, and set up their account.
The first thing we are going to do is to create a group with other members of the team.
To do so, click on “Create a group”, and then on “Create group”.
Set the group name to “pyrat_group” (or the name you want, as long as it’s unused), and set its visibility to “Private”.
Finally, click on “Create group”.
Now that the group is created, click on its name on the left panel.
A new button will appear on the page to “Invite your colleagues” in a box named “Collaborate with your team”.
Click on it.
Then, search for all names of the members of your PyRat group, and select them.
Select the role “Developer”, and click on “Invite”.
Now that we have a group of students, let’s create the project.
Stay on the group page, and click on “Create new project” and then “Create blank project”.
Set the project name to “pyrat_git_workspace” (or the name you want, as long as it’s unused), and click on “Create project”.
If this is the first time you create a Git repository on Gitlab, you will be asked to create a SSH key. To do so, click on the button “Add SSH key” (or access the menu from your user settings). There, click on “Add new key”. In the field “Key”, paste your SSH key, that you can obtain as follows:
Here is a tutorial with multiple ways to create a SSH key for Windows. Follow it to create a SSH key, and copy it into the “Key” field. Also, remove the exiration date. Then, click on “Add key”.
Here is a tutorial to create a SSH key for Linux. Follow it to create a SSH key, and copy it into the “Key” field. Also, remove the exiration date. Then, click on “Add key”.
Here is a tutorial to create a SSH key for MacOS. Follow it to create a SSH key, and copy it into the “Key” field. Also, remove the exiration date. Then, click on “Add key”.
When done, go back to the project page.
2.2.2 — Clone the Git repository
OK!
Now, the group and project are created!
Let’s create a local copy to work on.
Click on the “Code” button, and copy the “Clone with SSH” field.
Then, open your favorite terminal, navigate (using cd
or dir
) to the directory where you want to create your local copy, and type the following command (replace <the_field_you_just_copied>
accordingly):
git clone <the_field_you_just_copied>
git clone <the_field_you_just_copied>
git clone <the_field_you_just_copied>
git clone <the_field_you_just_copied>
This should create a directory called pyrat_git_workspace
(or whatever name you gave it) on your computer, that only contains a README.md
file.
2.2.3 — Setup in Visual Studio Code
Let’s import this directory to Visual Studio code.
To do so, go to your VSCode workspace, and add the pyrat_git_workspace
folder to the workspace.
When done, your folder will appear in your workspace as follows:
If you click on “Source control” in VSCode, you will also see a new entry, as VSCode will detect that this is a Git repository:
2.2.4 — Add contents to the repository
Let’s initialize the repository with the basic PyRat elements.
Copy-paste the contents of your pyrat_workspace
directory that you created during installation inside your pyrat_git_workspace
folder.
You will see that files will appear in green, meaning that they are “Untracked”, i.e., not yet added to the repository.
Head to “Source Control”, and click on “Stage all changes” to indicate that you want to add all local changes to the repository.
You can also choose to do it file by file of you prefer.
Files will change from “Untracked” to “Added”.
Then, write a comment to describe what you have done, and click on “Commit”.
Finally, click on “Sync changes” to send your committed modifications to the server.
2.2.5 — Other team mates joint the project!
Now, everything is ready to start working! Other students of your the should clone the repository and add it to the VSCode workspace.
2.2.6 — Using Git to develop collaboratively
When you work with Git, you should do as follows:
- First, when you start working, retrieve the latest version from the Git server (“Pull”).
- Then, create, remove or update files, write codes, etc.
- Once you are satisfied, add the updated files to Git (“Stage changes”).
- Then, describe your changes with a message describing your changes (“Commit”).
- Finally, upload your changes to the Git server (“Sync changes”).
Note that if you work on the same files as your team mates, you may create conflicts. Indeed, if you push a version A of the code to the repository (where there was an earlier version B), it will work as expected. However, if your team mate was working on a version C of the code, derivated from B, then there might be incompatibilities with the currently online version A. In that case, they will be asked to resolve the conflict at hand, i.e., to merge their version C with A.
What we have presented you above is only the very basic usage of Git. You will find many resources online to explain you how Git works, especially regarding its more advanced features, like branches.
Above, we asked you to create your repository on the school’s Gitlab page. For storage reasons, this repository is cleaned every year. Therefore, at the end of the year, you will only have your local copy left.
You can also work on GitHub if you prefer, but it is not hosted at IMT Atlantique.
3 — How does PyRat work?
3.1 — Elements in the interface
When verifying the installation, you were asked to run a script called sample_game.ipynb
.
This script should have opened a graphical user interface (GUI) similar to the following:
Let’s have a look at the various elements in this image.
On the left part of the screen, you can see the scores area, that shows which players are engaged in the game, how they are grouped in teams, and their current scores.
In this example, we have a match between two teams, respectively named “Team Ratz” and “Team Pythonz”.
Here, each team contains a single player, respectively Random2
(with the skin of a rat), and Random3
(with the skin of a snake).
On the right part of the screen, you will find the maze, in which the game takes place.
The maze lies in a rectangle of dimensions maze_width
x maze_height
that may have some holes.
Cells are numbered from 0
to maze_width * maze_height - 1
.
You can also see some walls, and some cells separated with mud.
The former cannot be crossed, and the latter require the number of turns indicated to reach the cell on the other side.
Characters and pieces of cheese are rendered in the maze at their current location. Note however that the GUI is not synchronized with the actual game, to be able to visualize it nicely. Therefore, if you choose to print your current location in your code, you will not see the same cell as in the GUI. The color around players is there to indicate their teams. You may also notice some small flags in the middle of the maze, which indicate the starting locations.
3.2 — Winning a PyRat game
Depending on the number of teams in play, the rule for winning a PyRat game changes. More precisely, we distinguish the following two cases:
-
Single-team game – The game is over when all pieces of cheese have been caught.
-
Multi-team game – The game is over when rankings cannot change anymore, i.e., no team can catch enough cheese so that they will change the leaderboard.
When a game is over, you will have access to many information on what happened during the game. You will learn about this later in this activity.
3.3 — Phases of the game
PyRat is essentially a library of Python functions that allow one to create a maze game, in which players fight to grab pieces of cheese. A game of PyRat can be decomposed into three phases:
-
Turn – At each turn, players are given the current configuration of the game, and have to choose where to go next. More precisely, they have to choose an action among the four cardinal directions, or staying where they are. Turns are repetated until the game is over.
-
Preprocessing – In addition, players are given the opportunity to make some computations at the beginning of the game. This phase occurs before the first turn of the game, and is generally allocated a longer time that the turns. Typically, this is the moment to pre-compute some interesting trajectories, prepare a strategy, etc.
-
Postprocessing – Finally, when the game is over, a final phase occurs. In that phase, the players may use the information gathered during the game to improve a model, or may do some cleanup of temporary files, for instance.
The preprocessing and postprocessing phases are optional.
To create a PyRat program, only the function describing the turn behavior needs to be defined.
In nearly all cases, you will only need to describe the preprocessing
and turn
functions to reach your goals.
Depending on the parameterization of the game, the players may have a limited time to make their decisions, or not. By default, a PyRat game attributes 3s for preprocessing, and 0.1s per turn. Postprocessing is never limited in time.
3.4 — The various game modes
A standard PyRat game looks like the following diagram (click or download to zoom).
In this diagram, horizontal lines represent independent processes that run simultaneously on the computer.
Arrows represent communication between these processes.
The width of the various boxes represent the time it takes for the associated operation to complete, except for the preprocessing and turn boxes, that have a fixed duration (preprocessing_time
and turn_time
, respectively).
For these boxes, diamonds represent the moment when players end their computations.
Note that the GUI (game interface) also lives in its own process. If you close it, it will not interrupt the game, but will just stop rendering what happens. Check here for instructions on how to stop the game entirely.
Now, what happens when a player is too slow and does not end their preprocessing or turn computations within the attributed time?
This depends on the game_mode
option, that can be set when creating a PyRat game.
Here are the possible modes:
-
Match – In match mode (
game_mode=GameMode.MATCH
), if a player takes more time than attributed in a phase, it will skip turns until its computations are done. This can happen both in the preprocessing phase (the other players may then start walking before the late player), or at each turn. Even if late at some point, all players will always receive up to date information on the game.This is summarized with the following diagram. In this example, Player 1 was so slow during preprocessing that it has to skip two turns. Player 2 ended preprocessing in time and could thus perform its turn 1 normally. However it took too much time there and had to skip turn 2.
-
Synchronous – In synchronous mode (
game_mode=GameMode.SYNCHRONOUS
), the game will wait that all players have taken their decisions before applying them. Preprocessing and turn phases still have a fixed time, but players can go over it and turns will not be skipped.This translates in the following diagram. With the same timing issues as in the previous example, we can see that the behavior of the PyRat game is not the same.
-
Sequential – In sequential mode (
game_mode=GameMode.SEQUENTIAL
), multiprocessing is disabled. All operations are done one after the other, and timing misses are treated as in synchronous mode. The interest of this mode is that it accelerates computations, as isolating players in separate processes can cause a computation overhead.In the following diagram, we observe that players are running in the same process as the PyRat game. Note that the GUI is still running in its own process though. Arrows between PyRat and players are omitted for readability. Still, note that players receive the same information, and that they move simultaneously in the maze. Only the decision making process is sequential.
-
Simulation – Finally, the simulation mode should be used when you are running many PyRat games and want them to complete as fast as possible. setting
game_mode=GameMode.SIMULATION
is strictly equivalent to setting optionspreprocessing_time=0.0
,turn_time=0.0
,game_mode=GameMode.SEQUENTIAL
andrender_mode=RenderMode.NO_RENDERING
when creating the game.The resulting diagram is as follows. Rectangles indicate the start of the phase, and diamonds the end of computations. Contrary to the sequential mode, there is no GUI anymore, and turns will start as soon as all players are ready.
By default, PyRat uses the following options:
-
Single-team game – Sequential mode.
-
Multi-team game – Match mode.
3.5 — PyRat and OOP
PyRat is what we call an object-oriented program. For now, you do not really need to understand more about object-oriented programming (OOP) to be able to start working on the project. During the semester, you will follow a dedicated course on the topic.
Knowing a bit more on OOP can help you understand PyRat better. Normally, you should be able to write a PyRat program without this though, by accepting to use a few codes that you don’t fully understand. If some things are unclear during your reading, we encourage you to come back here to read the few elements below.
4 — Tutorial
4.1 — Discover PyRat
Now open Visual Studio Code.
In your PyRat workspace, in the pyrat_workspace/games
subdirectory, you should find a file named tutorial.ipynb
.
We invite you to read its content, and to run blocks of code along your read.
This tutorial will explain to you how to create a PyRat game, and how to write a PyRat player.
Once you are done reading the tutorial file, please continue reading this page.
4.2 — The PyRat template
When you create a PyRat workspace, you are given a few programs in the pyrat_workspace/players
subdirectory.
During the tutorial, you already met the TemplatePlayer.py
file, which can be used as a blank project for starting to create a PyRat player.
Let’s give more details on the various elements of this file:
-
Documentation – The program starts with a global documentation that explains what it contains. It is always good to add a small text like this, for you (or the other users of you code) to remember what you do. Also, this particular type of comments (
""" ... """
) is parsed when producing the documentation files, as you did during installation. You will find multiple places inTemplatePlayer.py
with documentation. In the following blocks of code, we will drop them for readability.""" This file contains useful elements to define a particular player. In order to use this player, you need to instanciate it and add it to a game. Please refer to example games to see how to do it properly. """
-
Imports – The next thing you will find in this file is a series of imports. The first three lines import some decorators, that allow one to indicate the types of the various function arguments in Python (e.g.,
x: Number
). This can be useful to indicate to people how to use your code properly. Also, some IDEs use these indications to detect possible bugs in the codes.# External imports from typing import * from typing_extensions import * from numbers import * # PyRat imports from pyrat import Player, Maze, GameState, Action
-
Class definition – A PyRat program should start with the following lines. When writing your own programs, you will have to change the class name
TemplatePlayer
for a name of your choice.Also, note that all PyRat players should inherit from class
Player
(defined in thepyrat
module). This is done by adding(Player)
after the class name below. By doing so, all players you will write will have access to the attributes (data) and methods (functions) defined in thePlayer
class. In particular, you can access thename
attribute, that will be useful to know where you are in the maze, as shown later on this page.class TemplatePlayer (Player):
InformationYou may want to have a look at the documentation of the
Player
class, that you generated during installation. It should be located in thepyrat_workspace/doc
subdirectory. -
Constructor – There is a particular method called
__init__
that is called when you create a player, i.e., when you run the codep = TemplatePlayer()
. This method should always start with the argumentself
, and finish with arguments*args, **kwargs
. You can add all the arguments you want in the middle. If you want more details, please refer to the PyRat and OOP section, and to this link.Also, this method’s body should always start with
super().__init__(*args, **kwargs)
. This line allows to pass the extra arguments inargs
andkwargs
to the parent constructor. In our case, these arguments arename
andteam
, defined in the constructor of classPlayer
.The
print
call is just there for the example. You can replace it with whatever you want (this is also true for subsequent methods).def __init__ ( self: Self, *args: Any, **kwargs: Any ) -> Self: # Inherit from parent class super().__init__(*args, **kwargs) # Print phase of the game print("Constructor")
-
Preprocessing – As mentioned above, a PyRat game starts with a preprocessing phase, i.e., some computations made before players start moving in the maze. The
preprocessing
method is where you should describe these computations. It is the PyRat game that will call this method when needed. For this reason, you cannot rename the method, or add/remove arguments, or the game will crash.@override def preprocessing ( self: Self, maze: Maze, game_state: GameState, ) -> None: # Print phase of the game print("Preprocessing")
InformationThe
@override
that appears abovepreprocessing
,turn
andpostprocessing
is a decorator that indicates that the method redefines an existing method in the parent classPlayer
. -
Turn – Here is where you should describe what happens during a turn of the game. As for
preprocessing
, the PyRat game will call it when needed, so do not touch is definition. Theturn
method should return a valid action, as described in theAction
enumeration (defined in thepyrat
module).@override def turn ( self: Self, maze: Maze, game_state: GameState, ) -> Action: # Print phase of the game print("Turn", game_state.turn) # Return an action return Action.NOTHING
-
Postprocessing – Finally, you have a
postprocessing
method to describe the postprocessing behavior of your player. As for previous methods, the PyRat game will call it when needed, so do not touch is definition.@override def postprocessing ( self: Self, maze: Maze, game_state: GameState, stats: Dict[str, Any], ) -> None: # Print phase of the game print("Postprocessing")
Note that you are not limited to these pre-defined methods.
If you want to add a method say_hello
to your player, all you have to do is add the following code:
def say_hello ( self: Self,
to_whom: str
) -> None:
print("Hello", to_whom)
You can then call that method from __init__
, preprocessing
, turn
, postprocessing
, or any method you have added to your class, depending on when you need it.
Now that you are familiar with the PlayerTemplate.py
file, let’s see how files Random1.py
, Random2.py
and Random3.py
were built.
We are now going to detail these three random programs.
This should help you get started in the practical activity below:
4.3 — Random 1
The first random program, defined in file Random1.py
is basically the most naive player you could imagine.
At each turn, the program will choose a decision at random, among the possible valid decision.
These possible decisions are defined in the Action
enumeration in the pyrat
module.
To create this program, we will make the following changes to the template.
First, we will use random numbers, so we need to import the random
library:
import random
Then, we rename the class to Random1
:
class Random1 (Player):
There is nothing to do at instantiation for that player, but we still need to keep the constructor to pass arguments name
and turn
to the constructor of class Player
if needed (with the line that starts with super
).
Similarly, we do not need to do anything during the preprocessing and postprocessing phases.
These methods can be removed, as they are optional.
We thus only have the turn
method left, that should return an action.
To do so, we choose to define a method called find_next_action
, that will do that:
@override
def turn ( self: Self,
maze: Maze,
game_state: GameState,
) -> Action:
# Return an action
action = self.find_next_action()
return action
Finally, let’s define that method find_next_action
, so that it returns a random action among the list of possible ones:
def find_next_action ( self: Self
) -> Action:
# Choose a random action to perform
action = random.choice(list(Action))
return action
Instead of creating a method find_next_action
, we could have directly written our turn
method as follows:
@override
def turn ( self: Self,
maze: Maze,
game_state: GameState,
) -> Action:
# Choose a random action to perform
action = random.choice(list(Action))
return action
However, finding the next action will become increasingly complex with the next random programs, so it is a good idea to create a function for it already.
In the pyrat_workspace/games
subdirectory, you can see a file called visualize_Random1.ipynb
.
This file creates a game with an instance of Random1
.
If you run its contents, you will see it move in the maze, as follows:
4.4 — Random 2
The second random player is a bit more intelligent.
Moving like Random1
has the drawback of sometimes running into walls, or maybe returning an action that does nothing (Action.NOTHING
).
Here, we are going to return an action at random, among those that lead somewhere.
To obtain this information, we will use the arguments provided by the PyRat game to the turn
method.
Concretely, let’s start from file Random1.py
to build file Random2.py
.
First, we change the class name to Random2
:
class Random2 (Player):
Now, let’s update the find_next_action
method to return a random valid action.
To do so, we will need to use the maze map and current game configuration, received by turn
as arguments maze
(an object of class Maze
, defined in the pyrat
module) and game_state
(an object of class GameState
, defined in the pyrat
module), respectively.
These arguments have multiple methods that can be called.
In particular, game_state
contains the current location of the player in the maze, that you can retrieve using game_state.player_locations[self.name]
(self.name
is defined in the parent class Player
).
Also, maze
contains a method get_neighbors
that can give you the cells around a given cell, and a method locations_to_action
, that return the action needed to go from a cell to an adjacent one.
If you check the documentation or the code of class Maze
, you will not find the method get_neighbors
we mention above.
In fact, as PyRat is object-oriented, Maze
inherits from class Graph
, as a maze is a particular graph.
This is indicated in Maze.py
by the following code:
class Maze (Graph):
In practice, it means that any variable of type Maze
will also have access to the attributes and methods of the parent class Graph
.
This is very practical for factorizing codes.
You will learn more about object-oriented programming (OOP) in programming session 4.
For now, just remember that you can check the available methods and attributes of a variable v
using the following Python command:
print(dir(v))
Let’s pass the necessary arguments to find_next_action
in turn
:
@override
def turn ( self: Self,
maze: Maze,
game_state: GameState,
) -> Action:
# Return an action
action = self.find_next_action(maze, game_state)
return action
And let’s update the find_next_action
method:
def find_next_action ( self: Self,
maze: Maze,
game_state: GameState,
) -> Action:
# Choose a random neighbor
neighbors = maze.get_neighbors(game_state.player_locations[self.name])
neighbor = random.choice(neighbors)
# Retrieve the corresponding action
action = maze.locations_to_action(game_state.player_locations[self.name], neighbor)
return action
You may want to have a look at the documentation of the Maze
and GameState
classes, that you generated during installation.
They should be located in the pyrat_workspace/doc
subdirectory.
Also, to know which method and attribute are usable, you can use the dir
keyword as follows: dir(maze)
or dir(game_state)
.
By convention, in Python, attributes and methods starting with an underscore should not be used by you.
In the pyrat_workspace/games
subdirectory, you can see a file called visualize_Random2.ipynb
.
This file creates a game with an instance of Random2
.
If you run its contents, you will see it move in the maze, as in the video below.
Note that since the program uses random values, you may observe a different trajectory.
4.5 — Random 3
The third random player works as follows: at each turn, it moves to a random unvisited adjacent cell.
If no such cell exists, it behaves like Random2
.
Let’s start with the contents of file Random2.py
to create file Random3.py
.
As before, we first rename the class to Random3
:
class Random3 (Player):
Now, contrary to what we did with the previous programs, we will need to remember information across turns. More precisely, we are going to maintain a set, that we will enrich turn after turn.
A set is a data structure that can contain elements.
Contrary to lists, there cannot be duplicates of an element in a set (for instance, adding 42
twice to a set is the same as adding it once).
Also, sets are unordered data structures.
To create this set, we need to declare and initialize it in the __init__
method as follows.
All variables defined in this particular method will be accessible to all methods of the class that start with the self
argument.
def __init__ ( self: Self,
*args: Any,
**kwargs: Any
) -> Self:
# Inherit from parent class
super().__init__(*args, **kwargs)
# We create an attribute to keep track of visited cells
self.visited_cells = set()
Then, let’s update the turn
method to fill that set:
@override
def turn ( self: Self,
maze: Maze,
game_state: GameState,
) -> Action:
# Mark current cell as visited
if game_state.player_locations[self.name] not in self.visited_cells:
self.visited_cells.add(game_state.player_locations[self.name])
# Return an action
action = self.find_next_action(maze, game_state)
return action
And let’s take that information into account in the find_next_action
method:
def find_next_action ( self: Self,
maze: Maze,
game_state: GameState,
) -> Action:
# Go to an unvisited neighbor in priority
neighbors = maze.get_neighbors(game_state.player_locations[self.name])
unvisited_neighbors = [neighbor for neighbor in neighbors if neighbor not in self.visited_cells]
if len(unvisited_neighbors) > 0:
neighbor = random.choice(unvisited_neighbors)
# If there is no unvisited neighbor, choose one randomly
else:
neighbor = random.choice(neighbors)
# Retrieve the corresponding action
action = maze.locations_to_action(game_state.player_locations[self.name], neighbor)
return action
In the pyrat_workspace/games
subdirectory, you can see a file called visualize_Random3.ipynb
.
This file creates a game with an instance of Random3
.
If you run its contents, you will see it move in the maze, as follows:
4.6 — Comparing the random programs
So, we now have three functional players, but do we know if our changes indeed improved the rat’s behavior?
A quick look at the videos above could suggest that maybe not, as the video duration for Random2
is longer than the one of Random1
.
In order to evaluate the quality of our programs, it is good practice to run multiple games and to observe results on average.
In the pyrat_workspace/games
subdirectory, we provide you a script called compare_all_randoms.ipynb
.
This script will perform 1,000 random games for each of the three players, and will remember how many turns it takes to complete each game.
All players will play the exact same 1,000 games (i.e., the mazes and locations of pieces of cheese will be the same) so that they are compared fairly.
If you check the script in details, you will see that it runs in simulation game mode, meaning that the GUI will not appear. This script may take some time to complete.
Once the script is over, it will produce a figure, that shows the cumulative distribution of these lists of needed turns. For each curve, the more on the left, the faster to complete all games:
From these curves, it feels pretty safe to conclude that Random3
is a better strategy than Random2
, which is a better strategy than Random1
.
However, this is still a visual interpretation.
Indeed, did we make enough games to have a result that makes sense?
Or would we observe something different with more runs?
We can make this conslusion more robust using a statistical hypothesis test. In few words, such a test will give you a quantitative information on the confidence you can have in your conclusion.
Here, we will use a Mann-Whitney U test to try to answer the question “Does Random2
catch the piece of cheese faster than Random1
?”.
The compare_all_randoms.ipynb
script performs this test for you (for all pairs of programs), and produces the following output:
Mann-Whitney U test between turns of program 'Random 1' and of program 'Random 2': MannwhitneyuResult(statistic=621982.0, pvalue=3.510523794197863e-21)
Mann-Whitney U test between turns of program 'Random 1' and of program 'Random 3': MannwhitneyuResult(statistic=787040.5, pvalue=1.821119832542608e-109)
Mann-Whitney U test between turns of program 'Random 2' and of program 'Random 3': MannwhitneyuResult(statistic=690090.5, pvalue=4.74979492768772e-49)
Without entering into details, you can consider that the “p-value” field is an indicator of the confidence of the answer. In many applications, a p-value lower than 0.05 is considered small enough for the test to be significant (i.e., we can trust its conclusions). You will learn more about these tests in your statistics classes.
We can now conclude safely that Random3
is a better strategy than Random2
, which is a better strategy than Random1
.
5 — Your first program
That was a pretty long (but necessary) introduction! Now, let’s dive into the code and write your first PyRat program.
5.1 — Random 4
We are going to write an improvement Random3
.
First, start by making a copy of that file and rename the copy Random4.py
.
Also, as we did in the first three random programs, you should rename the class to Random4
.
As you may have seen when running visualize_Random3.ipynb
, player Random3
has the drawback of moving randomly when stuck in an area where all cells were already visited.
A simple improvement would be to remember our trajectory, and to go back on our steps when we reach an area where all neighboring cells are visited.
To create this strategy, you will need to do the following:
-
__init__
– In the constructor, you should create a new attribute namedself.trajectory
. This should be a list, that will store all your past locations. -
preprocessing
– During the preprocessing phase, you should initialize the trajectory with your initial location. This location can be obtained withgame_state.player_locations[self.name]
. -
turn
– At the beginning of your turn phase, you should add your current location to the trajectory. This location can be obtained withgame_state.player_locations[self.name]
. -
find_next_action
– If there are no unvisited neighbors, instead of returning a random neighbor (else
clause of theif
test), you should:- Remove the last entry in your trajectory (use the
pop
function of lists). Indeed, since you are going back and you just added the current location to the trajectory, you don’t want to return there. Note that this location should still be invisited_cells
, preventing you to go there again later. - Extract the last entry in your trajectory (use the
pop
function of lists), as it is contains the neighbor where you want to go next.
- Remove the last entry in your trajectory (use the
Then, write a program visualize_Random4.ipynb
(in the pyrat_workspace/games
subdirectory) that starts a game with your program.
You should see your program act like player Random3
, except that it goes back more intelligently when stuck.
Here is a video of the behavior you should observe. Pay attention to when the rat enters a dead-end, or an area with visited neighbors only (marked with the brown trace):
5.2 — Compare the random programs
Once you are done, update the compare_all_randoms.ipynb
script, so that you compare all the random programs (1–4).
Then, run this extended script, and answer the following questions:
-
Is
Random4
faster thanRandom3
to grab a piece of cheese?Correction -
Is it significant?
Correction
To go further
6 — Random 5
Let’s write a final random program called Random5
.
Here, we are going to make a small improvement to Random4
.
Indeed, sometimes, the rat goes into dead-ends, which is useless.
There are multiple ways of avoiding to enter into a dead-end:
- You could compute a set of forbidden cells where you should never go (and use it in the
find_next_action
method). - Or you could update the maze object by removing the dead-ends (and use that update maze instead of the one received by the
turn
method).
We are going to take the second option here.
To do so, have a look at the documentation of the Maze
and Graph
classes in the pyrat
module.
You should find a function called remove_vertex
, that removes a cell from the maze.
This is going to be useful.
So, what is a dead-end? It is a cell that respects all the following points:
- It has a single neighbor.
- It is not your starting position.
- It does not contain a piece of cheese.
Note that if you remove a dead end cell, its neighboring cell may still be a dead-end. Therefore, you may have to go through your vertices multiple times.
Your work now is:
- Write a method
simplify_maze
that removes all dead-ends in the maze. - Call this method in
preprocessing
and store its output as an argumentself.updated_maze
of your class. - Update your
find_next_action
method to use that argument instead of the maze you receive at each turn through the arguments ofturn
.
Here is a video of the expected result. Notice how the rat avoids dead-ends:
7 — Compare the random programs
Once you are done, update again the compare_all_randoms.ipynb
script, so that you compare all the random programs (1–5).
Then, run this extended script, and answer the following questions:
-
Is
Random5
faster thanRandom4
to grab a piece of cheese?Correction -
Is it significant?
Correction
To go beyond
8 — Sort actions
Up to now, you have chosen the next action to visit randomly, with a uniform probability. A possible improvement would be to explore actions in an interesting order, depending on whether they bring you closer or farther to the piece of cheese.
Obviously, this notion of closer/farther is complex, as it would require to know how to reach the piece of cheese in the maze to evaluate. However, a good distance you can use is the Euclidean distance. In other words, here is what you can do:
- You have a list
L
of possible actions (i.e. once you have done all the filterings inRandom4
). - For each action
a
inL
, determine the cellc
where it would lead you. - Compute the Euclidean distance between
c
and the piece of cheese. - Choose the action with minimum value of
c
.