Friday, December 11, 2009

Game: The Voronoi Game

As someone mentioned on the computational complexity blog yesterday, the Voronoi Game is a game of perfect information without randomness. The two-player version is a good partisan combinatorial game.

The game is based on Voronoi diagrams, which describes which areas of a plane are closest to each of a collection of points. Given a set of points, S, in a space, a Voronoi diagram is a partition of that space such that each partition contains exactly those points closest to one of the elements of S. Border-case points (those equivalently far from multiple points in S) are in a separate set belonging to other points that are also equivalently far from the same subset of S.

In the Voronoi Game, players take turns choosing points on a filled square until each has chosen some fixed number, m. At that point, a Voronoi diagram of the square is created and each player scores points equal to the total area of diagrams containing the points they chose.

As far as I can tell, the game was created by Indrit Selimi, as he is mentioned on the original Voronoi Game page. The blog mentions a newer version which can be played with many people.

Is there anything known about strategies for this game?

1 comment:

  1. Also, this is pretty cool: