NOTE: This challenge is currently dead, as I'm unable to install the languages needed to run a match. If someone else has the time and interest to do it, I'm not opposed.
See the bottom of the post for a leaderboard.
This is a semi-cooperative king-of-the-hill challenge, where the bots construct paths through a two-dimensional grid graph. The bot who controls the nodes with the most traffic is the winner. However, it takes more than one bot's resources to actually build a connecting path, so the bots will have to work together -- to some extent.
In the following, let
N > 0 be the number of bots in play.
The game is played on a two-dimensional integer grid of size
⌊4/3N2⌋ × ⌊4/3N2⌋, whose bottom left coordinate is at
(0,0). Each coordinate
0 ≤ y < ⌊4/3N2⌋-1 has outgoing edges to the three coordinates
(x+1,y+1) above it, where the
x-coordinates are taken modulo
⌊4/3N2⌋. This means that the grid wraps around at the east and west edges. Every bottom coordinate
(x,0) is a source, and every top coordinate
(x,⌊4/3N2⌋-1) is a sink.
The following picture shows an
8 × 8 grid.
Each vertex of the graph is either inactive, active, or broken. All vertices start inactive, and can be activated by bots, which will then be their owners. Also, bots can break vertices, and they cannot be repaired.
A turn consists of a destruction phase and an activation phase. In the destruction phase, each bot may break one inactive vertex. That vertex is broken from then on, and may not be activated by anyone. In the activation phase, each bot may activate one inactive vertex. From then on, they own that vertex, and it cannot be reactivated by anyone else. Several bots may own a single vertex, if they all activate it on the same turn. In each phase, the vertex selections are done simultaneously.
One round lasts for exactly
N2 turns. After this, the round is scored as follows. From each active source vertex, we perform
N times a randomized depth-first search along the active vertices (meaning that the children of each vertex are visited in a random order). If a path is found from the source to some sink, then for all vertices along that path, every owner of the vertex gets one point.
The entire game lasts for 100 rounds, and the bot with the most points overall is the winner. I may increase this number, if the variance of the scores is too high.
- No messing with the controller or other submissions.
- At most one submission per contestant.
- No external resources, except one private text file, wiped clean at the beginning of the game.
- Do not design your bot to beat or support specific opponents.
- Provide commands to compile and run your bot. Any compiler/interpreter that's freely available for Debian Linux is acceptable.
The controller is written in Python 3, and can be found in GitHub. See the README file for detailed instructions. Here's an API to get you started:
- Bots are started at the beginning of each round, and persist until the end of the round. The communicate with the controller via STDIN and STDOUT, using newline-terminated messages.
BEGIN [num-of-bots] [num-of-turns] [side-length]is input at the beginning.
DESTROY [turn]is input at the beginning of each destruction phase. Your bot shall respond with either
VERTEX x,yto choose a vertex, or
BROKEN [turn] [your-choice] [other-choices]is input at the end of each destruction phase. The order of the other bots is randomized at the beginning of each game, but stays fixed during it. The choices are presented as
OWNED [turn] [your-choice] [other-choices]are the equivalents of the above for the activation phase, and have the same semantics.
SCORE [your-score] [other-scores]is input at the end of the game.
- Your bot has 1 second to analyze the results of a phase and choose the next vertex, and 1 second to quit after given the score. I will test the submissions on my relatively old laptop, so it's better to leave some margin here.
Please remember to flush your output buffer. Not doing so may hang the controller in some environments.
Peacemaker is up and running, and Funnelweb received an update too. The scores jumped up by an order of magnitude. Connector exceeded the time limit in two games.
Funnelweb: 30911 Connector: 18431 Watermelon: 3488 Annoyance: 1552 Explorer: 735 Checkpoint: 720 Random Builder: 535 FaucetBot: 236 Peacemaker: 80
The full log with ASCII art graphics can be found in the controller's repository, in
- Connector can very easily be stopped by breaking a single vertex in front of it. I suspect Annoyance frequently does this. However, it currently makes little sense because only Connector can conceivably construct a path.
- Watermelon can get a decent score by simply happening to be on a connecting path (since the DFS is very likely to use its vertices).
- Explorer likes to grow vines from the watermelons.
- The updated Funnelweb gets really good scores, since Connector usually latches onto it in the lower half of the grid.
- The games are getting quite long, the average round taking about 25 seconds on my machine.