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. The only thing a solution needs to do is create a class that extends the abstract class VoronoiGraphPlayerAlgorithm: check out the VoronoiRandomPlayerAlgorithm and VoronoiGraphGreedyPlayerAlgorithm classes for inspiration. To test them out, replace lines 45 of VoronoiGame.java with your class name. Put whatever class you'd like for line 46. To test it out, compile and run the VoronoiGame.java 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 press enter on the terminal in order to advance the visual game. If you'd like to skip the visualization, comment out lines 51-91. 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! Check out Algo-Arena for explicit details. On the final two labs of the semester, 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 have you submission uploaded to the website prior to the start of your lab.

Extensions

  1. Any additional algorithm you analyze in the same as in the exploration after the first would count as an extension.
  2. You may notice that the graphs that I generate for this game, they're basically randomly tweaked grids. Analyzing your algorithms on different types of graphs (say, random graphs) is definitely a reasonable extension.

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!