Contents of the page

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

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 our current location 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.

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

A reactive greedy-based strategy

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.

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 planify our route once and for all in the preprocessing function, and then apply the moves. Indeed, the route we are going to take 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.

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:

def turn (maze_map, maze_width, maze_height, player_location, opponent_location, player_score, opponent_score, pieces_of_cheese, time_allowed) :
    # Traversal + routing
    closest_cheese = # ...
    route_to_closest_cheese = # ...

    # Transformation into moves
    moves_to_perform = moves_from_locations(route_to_closest_cheese)
    return moves_to_perform[0]

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