Jerry! Jerry!
I
just spent a few hours programming a Java applet in which the game
board consists of squares that have been grouped to electoral
districts. Each square is coloured between red and blue to show how
much support the red party has in that area. The player can use the
mouse to click on a square to move it into a neighbouring district. The
idea is to maximize (or minimize, if you lean that way ideologically)
the number of winning districts for the red party with gerrymandering
techniques. There is no other restriction for the shape of the district
than that it must be continuous. In addition, each square is considered
to have the same population and all districts must be of equal size, a
district can be considered winning for red only if it contains a proper
number of squares, since otherwise the game would be trivial.
I put the simple applet "Jerry" available online, although I don't think that it is very playable yet. Perhaps nicer graphics would help, now that the logic of the game itself works. The applet needs Java 5 to run (I like the new features of this language, and this way I can perhaps use the code for educational purposes), so it won't run in an unmodified Internet Explorer.
I won't post the source code until I have cleaned it up a bit, though. There is still much to add to this game, since right now the initial square colours are simply assigned randomly. It would be interesting to try various standard techniques for creating a terrain that is random but not totally random but has some kind of statistical regularity. (For example, in a Civilization-type game the random world can't be created just by selecting the contents of each cell randomly, since this would result in a very silly-looking patchwork world.)
It would also seem to be an interesting algorithmic problem to carve optimal districts for a given board of squares. This problem (or strictly speaking, the decision problem induced by the satisficing version of this optimization problem) very much feels like it would be NP-complete.
I put the simple applet "Jerry" available online, although I don't think that it is very playable yet. Perhaps nicer graphics would help, now that the logic of the game itself works. The applet needs Java 5 to run (I like the new features of this language, and this way I can perhaps use the code for educational purposes), so it won't run in an unmodified Internet Explorer.
I won't post the source code until I have cleaned it up a bit, though. There is still much to add to this game, since right now the initial square colours are simply assigned randomly. It would be interesting to try various standard techniques for creating a terrain that is random but not totally random but has some kind of statistical regularity. (For example, in a Civilization-type game the random world can't be created just by selecting the contents of each cell randomly, since this would result in a very silly-looking patchwork world.)
It would also seem to be an interesting algorithmic problem to carve optimal districts for a given board of squares. This problem (or strictly speaking, the decision problem induced by the satisficing version of this optimization problem) very much feels like it would be NP-complete.
Hex
There's a game for you. Try to beat the computer crossing the board.
Posted by Anonymous | 6:51 AM