Voronoi diagram area game

Red area:

Blue area:

Game mode

Turns per player

Sandbox mode

Random sites

In sandbox mode, moving the mouse (or touching and dragging along the screen) previews the Voronoi diagram that would result from placing a site there.

Options

Hide sites h

Limit sites to a grid of Pixels between points g

Limit sites to one dimension d Rectangular canvas r Play against computer a Quarantine mode (minimum distance between points) q

Playing against the computer only works in sandbox mode currently and can be started on either player's turn (red or blue). The computer player uses a simple greedy algorithm to pick its next point, looping through a grid of possible locations (with a spacing of 10 pixels between points to keep it reasonably fast) and choosing the one that maximizes its area after that turn.

Info

Take turns placing points in the plane to maximize the area of your cells in the resulting Voronoi diagram. The player with a greater area after a set number of turns wins.

For more in-depth analysis of strategy in the 2D Voronoi game, see Bouzy, Metivier, & Pellier, MCTS Experiments on the Voronoi Game, Advances in Computer Games, 7168 (2011) , which suggests a balanced cell approach. The Voronoi game in 1D was solved by H. Ahn et al., Competitive facility location: the Voronoi game, Theoretical Computer Science, 310.1 (2004) and can be played here by checking the "Limit sites to one dimension" box.