Pursuit Evasion on Graphs

In this project you will be implementing a turn-based version of a pursuit evasion game on graphs. In the 2-player model of this game, our 2 players are an evader and a pursuer, where the evaders goal is to indefinitely evade capture by the pursuer, while the pursuer's goal is to catch the evader. In the context of graphs, we will imagine each player as maintaining a token on the graph which they takes turns moving across edges. If the two tokens ever occupy the same vertex, the game is over and the pursuer has won.

Testing

As always, as you are coding up this project write tests for each class you create exercising the public methods implemented in this class.

Tasks

We'll begin by nailing down the idea of a PlayerAlgorithm:

  1. Setup

    Make a new folder for this week's project.

  2. Create an AbstractPlayerAlgorithm class

    In this class, we'll need to define the methods that any player needs to have:

    • public AbstractPlayerAlgorithm(Graph graph): Constructs the necessary fields of the class.
    • public Graph getGraph(): returns the underyling Graph.
    • public Vertex getCurrentVertex(): returns the current Vertex of the player.
    • public void setCurrentVertex(Vertex vertex): updates the current Vertex of the player to be the given Vertex vertex.
    • public abstract Vertex chooseStart(): returns a Vertex for the player to start at and updates the current Vertex to that location.
    • public abstract Vertex chooseStart(Vertex other): returns a Vertex for the player to start at based on where the other player chose to start. Updates the current Vertex to the chosen location.
    • public abstract Vertex chooseNext(Vertex otherPlayer): returns a Vertex for the player to move to based on where the other player currently is. Updates the current Vertex to the given next location.

  3. Create a RandomPlayer class

    This class will not be very smart, but will be useful for testing purposes. This RandomPlayer will extend the AbstractPlayerAlgorithm class, so it only needs to implement the abstract methods (and the constructor). For choosing the starting vertex, this player always chooses a random vertex. For choosing next, this player always chooses a random vertex in the neighborhood of the current vertex (so it chooses uniformly at random out of the options of sitting still and moving to an adjacent vertex).

    Once you've reached this point, we recommend jumping to the Visualizing the Game section that walks you through setting up the visualization and gives you a template Driver class to run the game. You should be able to run the game after that with both players making random moves, but the 2 players won't behave particularly smartly until you go back and write the classes for the MoveTowardsPlayerAlgorith (the pursuer) and the MoveAwayPlayerAlgorithm (the evader).

  4. Create a MoveTowardsPlayerAlgorithm class

    This class will also extend the AbstractPlayerAlgorithm class, but this time it will always try to move toward the other player. When choosing its start without knowing the other player's location, you can just pick a random Vertex (though you are welcome to implement a smarter choice if you'd like, something like picking the Vertex whose maximal distance to any other Vertex is minimized). When choosing the start position after the other player, move it directly to the other player's position. Note that we'll never use this in the game since it would immediately end the game in 1 move.

    When playing the game, the pursuer will move second and follow this strategy.

  5. Create a MoveAwayPlayerAlgorithm class

    This class will also extend the AbstractPlayerAlgorithm class, but this time it will always try to move away from the other player. When choosing its start without knowing the other player's location, you can just pick a random Vertex.

    When playing the game, the evader will move first and follow this strategy.

Visualizing the Game

The last required task is to add visualization and add a Driver to control the flow of the game. For visualization, we've given you this GraphDisplay class. (Note: taking arbitrary graphs and displaying them in a 'clean' way is a difficult problem. If you'd like to do better, a super valid extension is to put in the time and research to make a better version of this class. In particular, this GraphDisplay class makes awful looking graphs if the graph isn't one single connected component - however, optimal play on a disconnected graph is very boring anyway.)

To make a Driver, I've gotten you started by building this Driver class, to show you the basic structure of running this game. You may want to start by making both of your players RandomPlayers until you have finished implementing the move-towards and move-away versions.

Exploration

It turns out both of the 'smarter' algorithms you've implemented are not optimal for this problem.

  1. What percentage of the time does the pursuer catch the evader on random graphs? Hw many steps does it take on average? Compute these for 6 or more different settings of the number of nodes and the probability of an edge being drawn. Be sure to average your results across several different runs. Required element 1: include these results in the results section of your report as a table and describe your findings.
  2. Find a graph on which the evader could have evaded the pursuer indefinitely using an optimal strategy, but instead gets captured while using the MoveAwayPlayerAlgorithm strategy. Run your code to show this by using the filename-based graph constructor and writing your own file to represent the graph. Required element 2: submit a video of this. In the results section of your report, explain why it worked.
  4. Find a graph on which the pursuer could have caught the evader, but instead indefinitely stays at least one vertex away while using the MoveTowardsPlayerAlgorithm strategy. Run your code to show this by using the filename-based graph constructor and writing your wn file to represent the graph. Required element 3: submit a video of this. In the results section of your report, explain why it worked.

Extensions

Report

Your intended audience for your report are your peers not in the class, but who have taken a CS course. Your report should explain the core CS concept used, present the results of your program, and discuss the meaning of the results: what did you discover and does it make sense?

Your project report should contain the following elements. Please include a header for each section.