Description of the Lab

Overview of the Lab

In this Lab, we program a greedy algorithm that approximates « finding the shortest path that goes through all pieces of cheese » with « finding a series of shortest paths from a piece of cheese to another ».

There are multiple ways of doing so. In a first step of this Lab, we program a greedy algorithm as seen in the course. Then, we take a step back and see how we could improve it in the eventuality of a second player in the maze.null

Set up the environment

As always, you should start by duplicating the PyRat template file on Google Colab. For recall, you should go on the Google Colab template program, click on « File », then « Save copy in drive ». Rename it as greedy.ipynb, and make it accessible by link. We will refer to this link as <shared_link_to_greedy.ipynb>.

In this Lab, we will use the following command:

python --rat "<shared_link_to_exhaustive.ipynb>" -p 5 -x 15 -y 15 -d 0.5 --random_seed 1

This command line is the same as for the exhaustive search. This should easily allow you to compare obtained results.

The greedy algorithm

Finding the closest piece of cheese

As seen in the course, a greedy algorithm is a heuristic that will approximate a global minimum with a series of locally optimal minima. More formally, given a set of neighbors of a vertex in a graph, we want to go to the one which minimizes a certain value.

What we are going to do now is to write a function that associates with each possible (unvisited) neighbor a score, corresponding to the number of moves it takes to reach it.

Note: You can use the meta-graph computed before if you want. However this will restrict the set of vertices of interest to those used in the meta-graph. This will be sufficient to program the greedy algorithm, but you will not be able to change direction if you have an opponent and they grab your target cheese while you walk toward it. We will address this point later in the Lab.

def give_score (graph, current_vertex, neighbors) :
    # Associate a score (length of path) to each given neighbor

The greedy algorithm

Using this function, you should now be able to write a greedy algorithm, that iteratively selects the unvisited neighbor with the lowest score until all of them are visited.

def greedy (graph, initial_vertex, vertices_to_visit) :
    # Greedy algorithm that goes to the score minimizer until all vertices are visited

A strategy for PyRat based on the greedy approach

The greedy algorithm, formally defined, is what you programmed before.

Now, let us take a step back, and think about how we can adapt it to design a simple strategy that acts greedily, but is reactive to an opponent eating the piece of cheese we were going to eat.

It would be interesting to work on a different file now, and create a program called improved_greedy.ipynb. This would allow you to compare performance of the reactive strategy with a simple greedy algorithm.

What happens at each turn?

When roaming the path we computed with the greedy algorithm, we go toward the closest cheese at any point in time. Indeed, if you move one step toward the closest cheese, you have two possibilities:

  • We eat that piece of cheese: Then, we will now move toward the new closest piece of cheese;
  • We do not eat anything: Then, the closest piece of cheese remains the same, as we reduced the distance needed to go there by one step.

So, what it means is that we do not need to plan our route once and for all in the preprocessing function, and then apply the moves. Indeed, the route we are going to take by doing so is the same as the one we would take by just going one step toward the closest piece of cheese in the turn function and restarting the algorithm again.

This simplifies a lot of things compared to what you programmed before, as you just need to execute Dijkstra’s algorithm once each turn, and move in the direction of the closest piece of cheese.

A nice side-effect of this change is that, if the opponent eats a piece of cheese, we directly notice it since we perform a Dijkstra traversal each turn. We then move to the new closest one, and are more reactive to changes in the game.

Fastening Dijkstra’s algorithm

While this code should be fine for moderately large mazes, it may take some time for larger ones, as one call to Dijkstra’s algorithm per turn is still a bit time-consuming.

One possibility to improve this is to notice that we only need the route to the closest piece of cheese. With that in mind, adapt Dijkstra’s algorithm so that it stops when you have enough information.