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?
Red, Yellow, and Green Hats
17 hours ago
Also, this is pretty cool:
ReplyDeletehttp://www.snibbe.com/scott/bf/