The Voronoi Game

First, some loose motivation: suppose some competing companies are deciding where to build their stores. For some market research, they've mapped out various districts and calculated the revenue that could be gained from servicing each district. They've observed that consumers only care about whatever the closest store is; each district also has a rule that only one store can be built in it. Each company wants to come up with a strategy that maximizes their revenue subject to the choices of the other companies.

We'll model this game as a 2 player game on graphs. Consider the following graph:

The edges in this graph are drawn to indicate distance between neighboring districts. Each vertex has a value associated with it (corresponding to the revenue to be obtained from that district). The players (who we'll denote red and blue) will take turns picking two vertices to build a store on; neither player can pick a vertex that has already been chosen. After they have picked their two vertices, we'll color every vertex in the graph the same color as their closest store.

In the above graph, the red player chose the vertices of value 89 and 98, while the blue player chose the vertices of value 23 and 70.

As a result, the combined value of the red vertices is 75+89+59+57+98=378, while the combined value of the blue vertices is 48+40+23+72+77+70+31+25+45+77+16=524. So even though the red player chose the 2 highest value vertices, the blue player got much more combined value!

In general, we'll say the Voronoi Game on Graphs has the following format:

Input: A graph G where each edge has an associated distance and each vertex has an associated value.

Mechanism: Each player alternately takes turns k times choosing a vertex such that neither player can choose a vertex that has previously been chosen. After each player has chosen k vertices, every vertex v in the graph is assigned to the player who chose the nearest vertex to v.

Result: Which ever player has the highest summed value of vertices assigned to them is declared the winner.

In particular, for our class we will use the following additional rules:

  1. All graphs will have 100 vertices. Each vertex has an integer value chosen uniformly at random from 0 to 100, each edge will have a distance chosen uniformly at random between 1 and 2, and every pair of vertices will be connected with an edge with probability 10% (resolved independently).
  2. Each player will take k = 10 turns (alternately). Each turn is only allowed .5 seconds. If the player takes longer than that (or their algorithm crashes), they lose their turn.
  3. Neither player is allowed to change the ‘nature’ of the graph, such as adding/changing vertices/edges, or remove tokens already placed, or anything else that is clearly not in the spirit of the game.

Here's the framework I'll use for testing.. Download this, unzip it, and add your Graph, Edge and Vertex classes. You can run a game by running VoronoiGame.java. When prompted, input the names of the 2 player classes. You have been given a VoronoiRandomPlayer and a VoronoiGreedyPlayer. The greedy player should typically do better. See the example below for how to run the game. Advance the game by clicking the visualization. After the game is done, you will get the results of 20 simulations. The better player will win more games.

The only thing a solution needs to do is create a class that extends the abstract class VoronoiPlayerAlgorithm: check out the VoronoiRandomPlayer and VoronoiGraphGreedyPlayer classes for inspiration. To test it out, compile and run the VoronoiGame file; the first part of the main method is just a visual display on a 'simple' graph of 16 vertices just for visualization. The game requires you to click the window in order to advance the visual game. If you'd like to skip the visualization, comment out lines 55-144. After the visual game is played, 20 games are played (10 where Player1 goes first, 10 where Player1 goes second). The results of these games are then printed out.

Exploration

Your main requirement for this project is to devise at least one strategy that is consistently better than the random algorithm, and usually better than the greedy algorithm. In your report, you should

Extra Credit

For extra credit, participate in our contest-finale! On the final day of class, we'll hold a contest and see who came up with the best algorithm for this game! Participation will automatically get you a reasonable amount of extra credit: winning will get a heftier amount. To participate, you must come to class on Friday, 05/09!

Extensions

  1. Implement an additional player algorithm and evaluate it as you did for your exploration. (Up to 4 points)
  2. You may notice that the graphs that I generate for this game are basically randomly tweaked grids. Analyzing your algorithms on different types of graphs (say, random graphs) is definitely a reasonable extension. (Up to 4 points)

Congrats, you're done with everything except for your project report where you will communicate your findings from all that code! Make sure to write up your report in the project report file in the Google Classrooms assignment. The project report is an important part of the work in this project, so don't forget to do it!