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.

The greedy algorithm

Set up the environment

As always, you should start by copying template.py into a file greedy_1.py.

Now, let’s setup the maze configuration. Here, we will use the same settings as in previous Episode, with a bit more cheese:

#################################################################################################################
###################################################### GO ! #####################################################
#################################################################################################################

if __name__ == "__main__":

    # Map the functions to the character
    players = [{"name": "greedy 1", "preprocessing_function": preprocessing, "turn_function": turn}]

    # Customize the game elements
    config = {"maze_width": 15,
              "maze_height": 11,
              "mud_percentage": 40.0,
              "nb_cheese": 21,
              "trace_length": 1000}

    # Start the game
    game = PyRat(players, **config)
    stats = game.start()

    # Show statistics
    print(stats)

#################################################################################################################
#################################################################################################################

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:

def give_score ( graph:          Union[numpy.ndarray, Dict[int, Dict[int, int]]],
                 current_vertex: int,
                 targets:        List[int]
               ) ->              Tuple[List[float], Dict[int, Union[None, int]]]:

    """
        Function that associates a score to each target.
        In:
            * graph:          Graph containing the vertices.
            * current_vertex: Current location of the player in the maze.
            
        Out:
            * scores:        Scores given to the targets.
            * routing_table: Routing table obtained from the current vertex.
    """
    
    # TODO: Fill here

Note: Do not forget what functions you have coded in previous Labs, some may help you here.

As usual, don’t forget to test your function!

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:          Union[numpy.ndarray, Dict[int, Dict[int, int]]],
             initial_vertex: int,
             vertices:       List[int]
           ) ->              List[int]:

    """
        Greedy algorithm that goes to the score maximizer in a loop.
        In:
            * graph:          Graph containing the vertices.
            * initial_vertex: Initial location of the player in the maze.
            * vertices:       Vertices to visit with the greedy heuristic.
        Out:
            * route: Route to follow to perform the path through all vertices.
    """
    
    # TODO: Fill here

Now, use the greedy function and functions you have written in earlier Labs (import them, do not copy!) in the preprocessing function to compute the path to take at the start of the game, and unroll the decisions in the turn function. Don’t forget about the tests too.

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 greedy_2.py. 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 greedy_1.py, 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. This is your work for this part of the Lab!

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

More improvements!

Here are a few things you can do to write a greedy_3.py program, if you feel so.

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

Optional: improved score function

The score function above associates to each cheese the number of moves to reach it. This is a choice, which can be improved. Try changing that score function, with one of the following suggestions:

  • You could compute a density of cheese around each cheese, and associate that as a score to the cheese. Note that you would want to go the the cheese maximizing that density, when before you wanted to go to the cheese that minimized the score, so you would have to change a min into a max;
  • Easier option: adapt the TSP algorithm to stop at depth D (fixed constant), and de fine the score of a cheese as the length of the shortest path of length D that starts with it.