Contents of the page


Description of the Lab

In this Lab, we learn how to manipulate the PyRat maze and to write a simple program for it, that moves (kind of) randomly.

In short, we will first install the PyRat software, then go through a given program that moves at total random, and write a new program that draws inspiration from it. Finally, we will learn how to compute statistics to compare the improved random implementation with the provided one.

Installing the PyRat software

A first step before starting is to install the PyRat software. As this process is dependent on your operating system, we have dedicated a page to this step.

Please follow the instructions on this page. Once done, start a terminal, navigate to the PyRat directory, and run the following command:

python pyrat.py --rat AIs/random.py

If everything is fine, you should see a maze, in which a rat is moving randomly.

Before anything else, please type the following command in your terminal:

python pyrat.py -h

You will see a big text appear, which lists all possible options you can use with PyRat. Some of them allow you to customize the maze, others can be used to run multiple games, etc.

Now, we ask you to read this page, which describes how the PyRat software works.

A tour of the random program

The program we have used for the rat above is a simple random algorithm. At each turn, the program returns a move (up, down, left, right) at random, which may cause it to run into a wall, or come back to already visited locations.

Let us go quickly through the contents of the file AIs/random.py:

##############################################################
# The turn function should always return a move to indicate where to go
# The four possibilities are defined here
##############################################################

MOVE_DOWN = 'D'
MOVE_LEFT = 'L'
MOVE_RIGHT = 'R'
MOVE_UP = 'U'

The code above defines four constants that correspond to what the turn function should return, i.e., a decision of a move to perform in the maze.

##############################################################
# Please put your code here (imports, variables, functions...)
##############################################################

# Import of random module
import random



# Function that returns a random move
def random_move () :
    all_moves = [MOVE_DOWN, MOVE_LEFT, MOVE_RIGHT, MOVE_UP]
    return random.choice(all_moves)

In this code, we define a function random_move, that returns a possible move at random.

To do so, we choose to use the Python function random.choice, that returns an element from a list at random. Since this function is provided by the random module, we first need to import it.

##############################################################
# The preprocessing function is called at the start of a game
# It can be used to perform intensive computations that can be
# used later to move the player in the maze.
# ------------------------------------------------------------
# maze_map : dict(pair(int, int), dict(pair(int, int), int))
# maze_width : int
# maze_height : int
# player_location : pair(int, int)
# opponent_location : pair(int,int)
# pieces_of_cheese : list(pair(int, int))
# time_allowed : float
##############################################################

def preprocessing (maze_map, maze_width, maze_height, player_location, opponent_location, pieces_of_cheese, time_allowed) :
    
    # Nothing to do here
    pass

The preprocessing function is called exactly once before the PyRat game start. It gives you the possibility to make some time-consuming computations, and use their results in the turn function later.

Here, we choose not to do anything during this preprocessing step. Since this function must have a body, we use the keyword pass.

##############################################################
# The turn function is called each time the game is waiting
# for the player to make a decision (a move).
# ------------------------------------------------------------
# maze_map : dict(pair(int, int), dict(pair(int, int), int))
# maze_width : int
# maze_height : int
# player_location : pair(int, int)
# opponent_location : pair(int,int)
# player_score : float
# opponent_score : float
# pieces_of_cheese : list(pair(int, int))
# time_allowed : float
##############################################################

def turn (maze_map, maze_width, maze_height, player_location, opponent_location, player_score, opponent_score, pieces_of_cheese, time_allowed) :

    # Returns a random move each turn
    return random_move()

The final function of this program is turn, and is supposed to return a move among those we have defined at the beginning of the file.

What we do here is simply call random_move, and return its result. This will cause our character to make a random decision each turn.

Improving the random algorithm

We are going to improve the random algorithm presented before in multiple ways.

Before we start, make a copy of the AIs/random.py file, and rename it AIs/improved_random.py. We are going to work on this new file.

Avoiding walls

Undestanding the maze map structure

As we have discussed above, the random_move function returns a move at random from the list of all four possible directions. However, some of these moves may lead into a wall, causing the character not to move.

In order to avoid this, we will need to use some knowledge on the maze map. Notice in functions preprocessing and turnthe presence of an argument called maze_map. The commentary above these functions tell us this on its type:

# maze_map : dict(pair(int, int), dict(pair(int, int), int))

What it means is that maze_map is a variable containing a dictionary. If you don’t know about these data structures, here is the official documentation.

In Python, you can access the element of a list l at index i with the notation l[i]. For this code to work, i must be an integer between 0 and len(l)-1. In short, you can understand dictionaries as a generalization of lists, where the index is not necessarily an integer.

So let’s come back to maze_map. It is a dictionary in which keys are the possible locations in the maze (given as pairs (x, y)), and values (i.e., what we associate with the keys) are the adjacent locations which can be reached, along with the number of moves to reach it.

As an example, let us consider the following small maze:

maze_map = {(0, 0): {(1, 0): 1}, (0, 1): {(1, 1): 1}, (1, 0): {(1, 1): 6, (0, 0): 1}, (1, 1): {(1, 0): 6, (0, 1): 1}}

In this maze, location (0, 0) is at the bottom left. When writing maze_map[(0, 0)], we obtain {(1, 0): 1}, indicating that (0, 0) can access (1, 0) with a weight of maze_map[(0, 0)][(1, 0)] = 1.

Similarly, when writing maze_map[(1, 0)], we obtain {(1, 1): 6, (0, 0): 1}, indicating that (1, 0) can come back to (0, 0) with a weight of maze_map[(1, 0)][(0, 0)] = 1, and that (1, 0) can reach (1, 1) with a weight of maze_map[(1, 0)][(1, 1)] = 6 due to the presence of mud in the maze.

Python allows iterating over the keys of a dictionary d as follows:

for location in maze_map :
    for neighbor in maze_map[location] :
        print("Location", location, "can access", neighbor, "in", maze_map[location][neighbor], "moves")

On the example above, this would print the following lines:

Location (0, 0) can access (1, 0) in 1 moves
Location (0, 1) can access (1, 1) in 1 moves
Location (1, 0) can access (1, 1) in 6 moves
Location (1, 0) can access (0, 0) in 1 moves
Location (1, 1) can access (1, 0) in 6 moves
Location (1, 1) can access (0, 1) in 1 moves

Finally, you can check if a location l1 can access another location l2 using maze_map with the following code:

if l2 in maze_map[l1] :
    # Here, maze_map[l1][l2] exists
else :
    # Here, it doesn't

Converting two locations into a move

maze_map allows you to easily access the neighbors of a given location. However, it says nothing about the move you have to perform to go from one to the other.

We will write a function that takes as an argument two locations, and returns the move it takes to go from the first to the second. If the move is not feasible, this function should raise an exception to indicate an error:

def move_from_locations (source_location, target_location) : 
    difference = (target_location[0] - source_location[0], target_location[1] - source_location[1])
    if difference == (0, -1) :
        return MOVE_DOWN
    elif difference == (0, 1) :
        return MOVE_UP
    elif difference == (1, 0) :
        return MOVE_RIGHT
    elif difference == (-1, 0) :
        return MOVE_LEFT
    else :
        raise Exception("Impossible move")

Avoiding walls

With all that said, you should now be able to modify the function random_move to make it choose at random between moves that lead to a location which is a neighbor of the current location.

Note that the location of your character is given both in preprocessing and turn through the argument player_location.

Verification

Now, let’s check if your program performs as expected. Run the following command inside your terminal:

python pyrat.py --rat AIs/improved_random.py

If everything is fine, you should see your rat moving at random, but the Miss count (which indicates how many invalid or late moves were performed) should stay at 0.

Exploring unseen areas

Algorithm

Another problem of the random algorithm is that it can go back to already visited cells. We are now going to reduce the probability for this to happen, by programming the following algorithm:

  • At each turn, we move to a neighboring location that has not been visited yet;
  • If we can’t do it, we move at random.

The second step could be improved, for example by returning to the last known position with neighbors not yet visited.

Global variables

In order to remember which locations have been visited already, we are going to use a global variable. Contrary to local variables that disappear at the end of each function, global variables continue to exists, and keep their value between multiple function calls.

Important! In PyRat, global variables are the only way to save information between the preprocessing step and the various turns. However, in general, using global variables is a bad idea when you can do otherwise. Indeed, because they retain their value between two function calls, a function may work properly once, and then behave in a weird way due to side-effects of global variables being initialized differently, leading to hard to debug bugs.

In order to create a global variable, just write it at the most global level in your program, as follows:

##############################################################
# Please put your code here (imports, variables, functions...)
##############################################################


# Global variable to remember locations that have been visited
visited_locations = []

Then, in order to access the global variable from a function, we need to declare it as global using the Python keyword global.

For instance, doing so in the turn function gives the following code:

def turn (maze_map, maze_width, maze_height, player_location, opponent_location, player_score, opponent_score, pieces_of_cheese, time_allowed) :

    # Declare visited_locations as an existing global variable
    global visited_locations

    # Add the current location inside it if not already there
    if player_location not in visited_locations :
        visited_locations.append(player_location)

    # ...

Exploring unseen areas

You should now be able to write a program that implements the algorithm above.

Verification

To check if your program performs as expected. Run the following command inside your terminal:

python pyrat.py --rat AIs/improved_random.py

If everything is fine, you should see your rat rushing to new directions, and then start moving at random when it reaches a dead end. If you use the improved version of random_move we discussed previously, the Miss count should stay at 0.

Comparing algorithms

In order to check if AIs/improved_random.py indeed mproves AIs/random.py, we are going to compare them.

Note: Here, we only make some very small comparisons. However, a more complete page on the blog explains how to make statistics to evaluate a program.

Let us run the following command:

python pyrat.py --rat ./AIs/random.py --python AIs/improved_random.py --tests 100 --nodrawing -x 10 -y 10 -p 6 -md 0.0 --synchronous

Let us detail the arguments used here:

  • --rat AIs/random.py associates the random program with the rat;
  • --rat AIs/improved_random.py associates the improved random program with the python;
  • --tests 100 indicates we want to compute average statistics for 100 games;
  • --nodrawing indicates not to show the maze (showing a whole game takes time);
  • -x 10 sets the width of the maze;
  • -y 10 sets the height of the maze;
  • -p 6 places 6 pieces of cheese inside the maze;
  • -md 0.0 sets to 0 the probability to have mud between two adjacent locations;
  • --synchronous allows the game to proceed as soon as both players have returned a decision (rather than waiting for a fixed time).

After all 100 games have proceeded, we obtain the following result:

{
	"miss_python": 0.0
	"miss_rat": 245.78
	"moves_python": 485.66
	"moves_rat": 239.88
	"prep_time_python": 2.0313262939453124e-06
	"prep_time_rat": 2.8824806213378906e-06
	"score_python": 3.85
	"score_rat": 1.06
	"stucks_python": 0.0
	"stucks_rat": 0.0
	"turn_time_python": 4.479652741784325e-05
	"turn_time_rat": 4.336703252148335e-06
	"win_python": 0.86
	"win_rat": 0.01
}

These statistics indicate that AIs/improved_random.py never missed a move (miss_python), and won 86% of the games (win_python), while losing 1% (win_rat), the rest being draws.