## 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

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