Practical activity

Presentation & 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.

2 — Working in groups

In order to work efficiently with the other students of your group, we suggest you two possible solutions.

2.1 — Live Share

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

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”.

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.

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.

• Multiple-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.

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:

• Standard – By default (game_mode=GameMode.STANDARD), 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.SIMULATION), 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 options preprocessing_time=0.0, turn_time=0.0, game_mode=GameMode.SEQUENTIAL and render_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.

  

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.

# Here, we create a class "Animal"
class Animal ():

  # Classes have a special method "__init__" called a constructor
  # This is the code that will be executed when you instantiate an animal later
  # All methods of a class should start with the keyword "self"
  # This keyword references the object itself when the class is instantiated
  def __init__ (self, name):
    self.nickname = name # Create an attribute to store the name
    self.nb_meals = 0 # Create an attribute to count how many meals the animal had

  # Now, let's define another method that does custom stuff
  def eat_stuff (self, stuff_name):
    print("Yum, tasty", stuff_name)
    self.nb_meals += 1

# Instantiate two objects of class Animal
a = Animal("Snoopy")
b = Animal("Garfield")

# Show their attributes
print(a.nickname, a.nb_meals)
print(b.nickname, b.nb_meals)

# Call a method on the first object
a.eat_stuff("cookie")

# Show their attributes again
print(a.nickname, a.nb_meals)
print(b.nickname, b.nb_meals)

Snoopy 0
Garfield 0
Yum, tasty cookie
Snoopy 1
Garfield 0

# Here, we create a class "Dog"
# Note that class "Dog" inherits from "Animal"
class Dog (Animal):

  # When class Dog is instantiated, it is its constructor that is called
  # It is good practice to also call the parent's constructor
  # Then you can complement with additional codes
  # It is also good practice not to repeat arguments of the parent class
  # Arguments *args and **kwargs are here for this purpose
  def __init__ (self, size, *args, **kwargs):
    super().__init__(*args, **kwargs) # Call parent's constructor
    self.size = size # Create an attribute to store the size

  # Now, let's define a new method
  def bark (self):
    print("Woof")

# Instantiate an object of class Dog
a = Dog(42, "Snoopy")

# Show its attributes
print(a.nickname, a.size, a.nb_meals)

# Call its methods
a.eat_stuff("cookie")
a.bark()

# Show its attributes again
print(a.nickname, a.size, a.nb_meals)

Snoopy 42 0
Yum, tasty cookie
Woof
Snoopy 42 1

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 in TemplatePlayer.py with documentation. In the following blocks of code, we will drop them for readability.

  ​

  Python

  """
      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.

  ​

  Python

  # 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 the pyrat 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 the Player class. In particular, you can access the name attribute, that will be useful to know where you are in the maze, as shown later on this page.

  ​

  Python

  class TemplatePlayer (Player):

  Information

  You may want to have a look at the documentation of the Player class, that you generated during installation. It should be located in the pyrat_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 code p = TemplatePlayer(). This method should always start with the argument self, 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 in args and kwargs to the parent constructor. In our case, these arguments are name and team, defined in the constructor of class Player.

  The print call is just there for the example. You can replace it with whatever you want (this is also true for subsequent methods).

  ​

  Python

  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.

  ​

  Python

  @override
  def preprocessing ( self:       Self,
                      maze:       Maze,
                      game_state: GameState,
                    ) ->          None:
      
      # Print phase of the game
      print("Preprocessing")

  Information

  The @override that appears above preprocessing, turn and postprocessing is a decorator that indicates that the method redefines an existing method in the parent class Player.

• 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. The turn method should return a valid action, as described in the Action enumeration (defined in the pyrat module).

  ​

  Python

  @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.

  ​

  Python

  @override
  def postprocessing ( self:       Self,
                       maze:       Maze,
                       game_state: GameState,
                       stats:      Dict[str, Any],
                     ) ->          None:
  
      # Print phase of the game
      print("Postprocessing")

def say_hello ( self:    Self,
                to_whom: str
              ) ->       None:
    
    print("Hello", to_whom)

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

@override
def turn ( self:       Self,
           maze:       Maze,
           game_state: GameState,
         ) ->          Action:

    # Choose a random action to perform
    action = random.choice(list(Action))
    return action

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.

class Maze (Graph):

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

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.

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.

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 named self.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 with game_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 with game_state.player_locations[self.name].

• find_next_action – If there are no unvisited neighbors, instead of returning a random neighbor (else clause of the if 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 in visited_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.

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 than Random3 to grab a piece of cheese?

  Correction

  Click here to reveal the answer.

  Yes. Visually, we observe that the cumulative curve associated to Random4 is at the left of the one for Random3.

• Is it significant?

  Correction

  Click here to reveal the answer.

  Yes. The Mann-Whitney U test gives us the following output:

  Output

  Python

  Mann-Whitney U test between turns of program 'Random 3' and of program 'Random 4': MannwhitneyuResult(statistic=621805.0, pvalue=3.9989134611571045e-21)

  The p-value is sufficiently low to conclude of test significance.

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 argument self.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 of turn.

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 than Random4 to grab a piece of cheese?

  Correction

  Click here to reveal the answer.

  Yes. Visually, we observe that the cumulative curve associated to Random5 is at the left of the one for Random4.

• Is it significant?

  Correction

  Click here to reveal the answer.

  Yes. The Mann-Whitney U test gives us the following output:

  Output

  Python

  Mann-Whitney U test between turns of program 'Random 4' and of program 'Random 5': MannwhitneyuResult(statistic=609971.0, pvalue=1.6479782581220633e-17) 

  The p-value is sufficiently low to conclude of test significance.

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 in Random4).
• For each action a in L, determine the cell c where it would lead you.
• Compute the Euclidean distance between c and the piece of cheese.
• Choose the action with minimum value of c.