Description of the Lab
Overview 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 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.
Before engaging in the lab, please consult the documentation, in particular that of the data structure used to represent the labyrinth as a graph.
Set up the environment
Before we start, make a copy of the random AI as indicated in the video in Lab 1. For recall, you should go on the Google Colab random program, click on « File », then « Save copy in drive ». The copy should open in a new tab. Rename it as improved_random.ipynb, and make it accessible by link. We will refer to this link as <shared_link_to_improved_random.ipynb>.
In this Lab, we will use the following command:
python pyrat.py --rat "<shared_link_to_improved_random.ipynb>"
A tour of the random program
The program we will work from 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 its contents.
The following code defines four constants that correspond to what the turn function should return, i.e., a decision of a move to perform in the maze. These constants are the same as those defined in the template file and should not be changed.
MOVE_DOWN = 'D' MOVE_LEFT = 'L' MOVE_RIGHT = 'R' MOVE_UP = 'U'
Then, 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.
import random
def random_move () :
all_moves = [MOVE_DOWN, MOVE_LEFT, MOVE_RIGHT, MOVE_UP]
return random.choice(all_moves)
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.
def preprocessing (maze_map, maze_width, maze_height, player_location, opponent_location, pieces_of_cheese, time_allowed) :
pass
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.
def turn (maze_map, maze_width, maze_height, player_location, opponent_location, player_score, opponent_score, pieces_of_cheese, time_allowed) :
return random_move()
Improving the random algorithm
Avoiding walls
A first improvement we are going to make to the algorithm is to avoid rushing into walls. To do so, we are going to change the list of moves that we are allowed to draw a random element from at each turn.
Understanding the maze map structure
As we have seen before, the maze_map variable is coded as a dictionary. Python allows iterating over the keys of a dictionary 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")
Let us consider the following small maze:
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
Also, 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 "<shared_link_to_improved_random.ipynb>"
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
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 random neighbor location that has not been visited yet;
- If we can’t do it, we move at total random between all possible neighbors.
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 a local variable that disappears at the end of the function in which it is defined, global variables continue to exist, 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, because of how the PyRat software is designed. 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 errors.
In order to create a global variable, just write it at the most global level in your program, as follows:
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 "<shared_link_to_improved_random.ipynb>"
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 the improved random program you have written indeed improves the totally random one, 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 "<shared_link_to_improved_random.ipynb>" --python "https://colab.research.google.com/drive/1d1qiLXR2D_puecXGBx1o2sJiYeZIVrpF?usp=sharing" --tests 100 --nodrawing -x 10 -y 10 -p 6 -md 0.0 --synchronous
Let us detail the arguments used here:
--rat "<shared_link_to_improved_random.ipynb>"associates the improved random program with the rat;--python "https://colab.research.google.com/drive/1d1qiLXR2D_puecXGBx1o2sJiYeZIVrpF?usp=sharing"associates the totally random program with the python;--tests 100indicates we want to compute average statistics for 100 games;--nodrawingindicates not to show the maze (showing a whole game takes time);-x 10sets the width of the maze;-y 10sets the height of the maze;-p 6places 6 pieces of cheese inside the maze;-md 0.0sets to 0 the probability to have mud between two adjacent locations;--synchronousallows 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": 245.78
"miss_rat": 0.0
"moves_python": 239.88
"moves_rat": 485.66
"prep_time_python": 2.8824806213378906e-06
"prep_time_rat": 2.0313262939453124e-06
"score_python": 1.06
"score_rat": 3.85
"stucks_python": 0.0
"stucks_rat": 0.0
"turn_time_python": 4.336703252148335e-06
"turn_time_rat": 4.479652741784325e-05
"win_python": 0.01
"win_rat": 0.86
}
These statistics indicate that the improved random program never missed a move (miss_rat), and won 86% of the games (win_rat), while losing 1% (win_python), the rest being draws.