# Grid-Routing Battle

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.

# Gameplay

In the following, let N > 0 be the number of bots in play.

## The Grid

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 (x,y) with 0 ≤ y < ⌊4/3N2⌋-1 has outgoing edges to the three coordinates (x-1,y+1), (x,y+1), and (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.

## Turn Order

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.

## Scoring

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

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,y to choose a vertex, or NONE.
• 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 x,y or N.
• ACTIVATE [turn] and 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.

Updated 3/13/2015

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 graphical_log.txt.

Some observations:

• 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.
• @Alex I tried to design the challenge so that suicidal bots won't mess everything up. Three well designed bots should always be able to construct a valid path, if they work together. – Zgarb Feb 19 '15 at 21:42
• @Zgarb Suicide shouldn't mess it up, but a couple troll-bots working together could probably also block all paths, ruining the game. – Geobits Feb 20 '15 at 4:51
• @CarpetPython Active nodes cannot be destroyed. – Zgarb Feb 20 '15 at 8:55
• It seems we are unlikely to see any interesting games with the current players and rules. I suggest you change the rules slightly to create opportunities for interesting games. Changing the grid size to 1.5*N^2 instead of 2*N^2 should be good and not confuse existing robots too much. – Logic Knight Feb 28 '15 at 6:29
• @justhalf That's true. The games in the log were actually played with the further reduced grid size of 4/3*N^2, and even there, the bots had problems forming valid paths. However, Connector was temporarily disqualified due to an error, and now that it has been fixed, I expect the games to be more interesting. I'll run another batch tonight. – Zgarb Mar 5 '15 at 9:52

## Connector (Java)

Tries to create a path at a random position. Because it can't create a path on its own, it searches for active cells and uses them. Credit goes to Geobits, from whom I stole some code. Also, this submission isn't finished yet, as it simply stops doing anything as soon as the path is built.

Edit: If a path is built, Connector tries to create multiple paths along the existing one.

import java.awt.Point;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Connector {
private static final int INACTIVE = 0;
private static final int ACTIVE   = 1;
private static final int BROKEN   = 2;
private static final int MINE     = 3;

private int size = 0;
private int[][] grid = new int[size][size];
private Point previousCell = null;
private final List<Point> path = new ArrayList<>();

public static void main(String[] args) {
new Connector().start();
}

private void start() {
while(true) {
try {
act(input);
} catch (Exception e) {
e.printStackTrace();
System.exit(0);
}
}
}

private void act(String input) throws Exception {
String[] msg = input.split(" ");
String output = "";
int turn;
switch(msg[0]){
case "BEGIN":
size = Integer.parseInt(msg[3]);
grid = new int[size][size];
break;
case "DESTROY":
output = "NONE";
break;
case "BROKEN":
update(msg, true);
break;
case "ACTIVATE":
turn = Integer.parseInt(msg[1]);
output = activate(turn);
break;
case "OWNED":
update(msg, false);
break;
case "SCORE":
System.exit(0);
break;
}
if (output.length() > 0) {
System.out.println(output);
}
}

private String activate(int turn) {
if (turn == 0) {
Random r = new Random();
previousCell = new Point(r.nextInt(size), 0);
return "VERTEX " + previousCell.x + "," + 0;
}
Point lastCell = findLastPathCell(previousCell.x, previousCell.y);
if (lastCell.y == size-1) {
//path is done
Point extendingPathPoint = findExtendingPathPoint();
if (extendingPathPoint == null) {
return "NONE";
}
return "VERTEX " + extendingPathPoint.x + "," + extendingPathPoint.y;
} else {
int x = findBestX(lastCell.x, lastCell.y);
return "VERTEX " + x + "," + (lastCell.y + 1);
}
}

private int findBestX(int x, int y) {
int bestScore = Integer.MIN_VALUE;
int bestX = 0;
for (int i = -1; i <= 1; i++) {
int newY = y + 1;
int newX = (x + i + size) % size;
int score = calcCellScore(newX, newY, 10);
if (score > bestScore) {
bestScore = score;
bestX = newX;
} else if (score == bestScore && Math.random() < 0.3) {
bestX = newX;
}
}
return bestX;
}

private int calcCellScore(int x, int y, int depth) {
int newY = y + 1;
if (depth < 0) {
return 1;
}
if (newY >= size)
return 100;
int cellScore = 0;
for (int i = -1; i <= 1; i++) {
int newX = (x + i + size) % size;
if (grid[newX][newY] == ACTIVE || grid[newX][newY] == MINE) {
cellScore += 5;
} else if (grid[newX][newY] == INACTIVE) {
cellScore += 1;
} else {
cellScore -= 2;
}
cellScore += calcCellScore(newX, newY, depth -1);
}
return cellScore;
}

private Point findLastPathCell(int x, int y) {
Point thisCell = new Point(x,y);
int newY = y + 1;
if (newY >= size) {
return thisCell;
}
List<Point> endCells = new ArrayList<>();
for (int i = -1; i <= 1; i++) {
int newX = (x + i + size) % size;
if (grid[newX][newY] == ACTIVE || grid[newX][newY] == MINE) {
}
}
int bestY = -1;
Point bestPoint = null;
for (Point p : endCells) {
if (p.y > bestY) {
bestY = p.y;
bestPoint = p;
}
}
return bestPoint;
}

private Point findExtendingPathPoint() {
if (path.size() == 0)
return null;
Random rand = new Random();
for (int i = 0; i < size; i++) {
Point cell = path.get(rand.nextInt(path.size()));
for (int j = -1; j <= 1; j += 2) {
Point newCellX = new Point((cell.x + j + size) % size, cell.y);
if (grid[newCellX.x][newCellX.y] == INACTIVE)
return newCellX;

Point newCellY = new Point(cell.x, cell.y + j);
if (cell.y < 0 || cell.y >= size)
continue;
if (grid[newCellY.x][newCellY.y] == INACTIVE)
return newCellY;
}
}
return null;
}

private void update(String[] args, boolean destroyPhase) {
for(int i = 2; i < args.length; i++) {
String[] tokens = args[i].split(",");
if(tokens.length > 1){
int x = Integer.parseInt(tokens[0]);
int y = Integer.parseInt(tokens[1]);
if (grid[x][y] == INACTIVE) {
if (destroyPhase) {
grid[x][y] = BROKEN;
} else if (i == 2) {
grid[x][y] = MINE;
previousCell = new Point(x,y);
} else {
grid[x][y] = ACTIVE;
}
}
}
}
}
}

• @Zgarb Sorry, I created a bug while fixing the other one. It works now – CommonGuy Mar 5 '15 at 8:07
• @Manu, it is good you are back in the game. There are too many exploiters and not enough builders. With Connector running, the games may become more interesting (more that 1 game in 100 with a score). – Logic Knight Mar 5 '15 at 8:44
• Connector took 28 seconds to respond in one of the latest games (see the log). Seems like it ran into Watermelon and had a hard time deciding where to go next. – Zgarb Mar 13 '15 at 17:51
• I ran some games again with the improved Peacemaker, and Connector threw an error: java.lang.ArrayIndexOutOfBoundsException: -1 at Connector.findExtendingPathPoint(Connector.java:166). – Zgarb Mar 19 '15 at 18:37

# Funnelweb, Python 2

version 1.2 - Better joining code, added new animation

Named after one of Australia's less friendly spiders. This bot first builds a funnel-shaped nest in the top rows, then lures other bots into building paths for traffic to the nest.

Here is a new animation of a 6 bot game on a 4/3N^2 board showing the funnelweb and some simpler bots:

The funnelweb's Python code:

from random import *
import sys
ME = 0
def pt(x,y): return '%u,%u' % (x % side_len, y)

while True:
msg = raw_input().split()

if msg[0] == 'BEGIN':
turn = 0
numbots, turns, side_len = map(int, msg[1:])
R = range(side_len)
top = side_len - 1
grid = dict((pt(x, y), []) for x in R for y in R)
mynodes = set()
freenodes = set(grid.keys())
mycol = choice(R)
extra = sample([pt(x,top) for x in R], side_len)
path = [(mycol, y) for y in range(top, top - side_len/6, -1)]
moves = []
fence = []
for x,y in path:
moves.append( [pt(x,y), pt(x+1,y), pt(x-1,y)] )
fence.extend( [pt(x+1,y), pt(x-1,y)] )
for dx in range(2, side_len):
fence.extend( [pt(x+dx,y), pt(x-dx,y)] )
for x,y in [(mycol, y) for y in
range(top - side_len/6, top - 3*side_len/4, -1)]:
moves.append( [pt(x,y), pt(x+1,y), pt(x-1,y)] )

elif msg[0] == 'DESTROY':
target = 'NONE'
while fence:
loc = fence.pop(0)
if loc in freenodes:
target = 'VERTEX ' + loc
break
print target
sys.stdout.flush()

elif msg[0] == 'BROKEN':
for rid, loc in enumerate(msg[2:]):
if loc != 'N':
grid[loc] = None
if loc in extra: extra.remove(loc)

elif msg[0] == 'ACTIVATE':
target = 'NONE'
while moves:
loclist = moves.pop(0)
goodlocs = [loc for loc in loclist if loc in freenodes]
if goodlocs:
target = 'VERTEX ' + goodlocs[0]
break
if target == 'NONE':
if extra:
target = 'VERTEX ' + extra.pop(0)
else:
target = 'VERTEX ' + pt(choice(R), choice(R))
print target
sys.stdout.flush()

elif msg[0] == 'OWNED':
for rid, loc in enumerate(msg[2:]):
if loc != 'N':
grid[loc].append(rid)
if rid == ME:
if loc in extra: extra.remove(loc)
turn += 1

elif msg[0] == 'SCORE':
break


The spider is run with python funnelweb.py.

• Changed algorithm and tested it. It should run now. – Logic Knight Feb 21 '15 at 19:27
• Works great now! – Zgarb Feb 23 '15 at 8:39

# Checkpoint, Java

This bot tries to create checkpoints so that any valid path passes through one of my vertices. Since there are N2 turns and the board is 2N2 across, I can activate/break every node on a single horizontal line (assuming I'm there first). Do this in an alternating pattern (x is broken, o is mine):

xoxoxoxoxoxox...


If you want to make a path, you need to go through my checkpoints :)

Now, there are several issues this might face. First, it's not going to do very well at all unless there are many paths. Since he doesn't make any productive paths himself, he really is totally reliant on there being some competitors. Even a couple competitors combining to make a single path won't help much, since he only scores one spot for each path found. What he needs to shine is probably quite a few bots making quite a few different paths. Even then, it might not score very highly, but it was an idea I had in chat, so...

If one of the spaces on the line is blocked/claimed already, I just search for a nearby spot I can use (preferably on the same x line, just shifted vertically).

import java.io.BufferedReader;

public class Checkpoint {
public static void main(String[] args) {
while(true)
try {
act(input);
} catch (Exception e) {
e.printStackTrace();
System.exit(0);
}
}

static void act(String input) throws Exception{
String[] msg = input.split(" ");
String output = "";
int turn;
boolean found = false;
switch(msg[0]){
case "BEGIN":
size = Integer.parseInt(msg[3]);
grid = new int[size][size];
target = size/2;
break;
case "DESTROY":
turn = Integer.parseInt(msg[1]);
for(int x=0;x<size;x+=2)
for(int y=0;y<size&&!found;y++)
if(grid[(x+turn*2)%size][(y+target)%size]==INACTIVE){
output = "VERTEX " + ((x+turn*2)%size) + "," + ((y+target)%size);
found = true;
}
if(output.length() < 1)
output = "NONE";
break;
case "BROKEN":
for(int i=2;i<msg.length;i++){
String[] tokens = msg[i].split(",");
if(tokens.length>1){
int x = Integer.parseInt(tokens[0]);
int y = Integer.parseInt(tokens[1]);
if(grid[x][y]==INACTIVE)
grid[x][y] = BROKEN;
}
}
break;
case "ACTIVATE":
turn = Integer.parseInt(msg[1]);
for(int x=1;x<size;x+=2)
for(int y=0;y<size&&!found;y++)
if(grid[(x+turn*2)%size][(y+target)%size]==INACTIVE){
output = "VERTEX " + ((x+turn*2)%size) + "," + ((y+target)%size);
found = true;
}
if(output.length() < 1)
output = "NONE";
break;
case "OWNED":
for(int i=2;i<msg.length;i++){
String[] tokens = msg[i].split(",");
if(tokens.length>1){
int x = Integer.parseInt(tokens[0]);
int y = Integer.parseInt(tokens[1]);
if(i==2){
if(grid[x][y]==INACTIVE)
grid[x][y] = MINE;
}else{
if(grid[x][y]==INACTIVE)
grid[x][y]=ACTIVE;
}
}
}
break;
case "SCORE":
System.exit(0);
break;
}
if(output.length()>0)
System.out.println(output);
}

static int size = 2;
static int target = size/2;
static int[][] grid = new int[size][size];

static final int INACTIVE = 0;
static final int ACTIVE   = 1;
static final int BROKEN   = 2;
static final int MINE     = 3;
}


To compile, it's javac Checkpoint.java. To run, java Checkpoint. You'll want to add/change the path to reflect wherever it is.

# Watermelon, Java

Attempts to draw watermelons on the grid.

import java.awt.*;
import java.io.IOException;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Watermelon {

private static int numberOfBots;
private static int numberOfTurns;
private static int sideLength;

private static int turn = 0;

private static int[][] theGrid;

private static final int INACTIVE = -2;
private static final int BROKEN   = -1;
private static final int MINE     =  0;
private static final int ACTIVE   =  1;

private static PrintStream out = System.out;

public static void main(String[] args) throws IOException {
while (true){
String instruction = input[0];
switch (instruction){
case "BEGIN":
begin(input);
break;
case "DESTROY":
destroy(input);
break;
case "BROKEN":
broken(input);
break;
case "ACTIVATE":
activate(input);
break;
case "OWNED":
owned(input);
break;
default:
return;
}
out.flush();
}
}

private static void begin(String[] input) {
numberOfBots = Integer.parseInt(input[1]);
numberOfTurns = Integer.parseInt(input[2]);
sideLength = Integer.parseInt(input[3]);
theGrid = new int[sideLength][sideLength];
for (int x = 0; x < sideLength; x++){
for (int y = 0; y < sideLength; y++){
theGrid[x][y] = INACTIVE;
}
}
}

private static void owned(String[] input) {
turn = Integer.parseInt(input[1]);
for (int i = input.length - 1; i >= 2; i--){
if (input[i].equals("N")){
continue;
}
String[] coordinates = input[i].split(",");
int x = Integer.parseInt(coordinates[0]);
int y = Integer.parseInt(coordinates[1]);
int player = i - 2;
if (player == 0){
theGrid[x][y] = MINE;
} else {
theGrid[x][y] = ACTIVE;
}
}
}

private static void activate(String[] input) {
turn = Integer.parseInt(input[1]);
double[][] values = new double[sideLength][sideLength];
List<Point> pointList = new ArrayList<>();
for (int x = 0; x < sideLength; x++){
for (int y = 0; y < sideLength; y++){
if (theGrid[x][y] == MINE || theGrid[x][y] == ACTIVE){
for (int x1 = 0; x1 < sideLength; x1++){
for (int y1 = 0; y1 < sideLength; y1++){
double distance = Math.pow(x - x1, 2) + Math.pow(y - y1, 2);
values[x1][y1] += 1 / (distance + 1);
}
}
}
}
}
pointList.sort(Comparator.comparingDouble((Point a) -> values[a.x][a.y]).reversed());
for (Point point : pointList){
if (theGrid[point.x][point.y] == INACTIVE){
out.println("VERTEX " + point.x + "," + point.y);
return;
}
}
out.println("NONE");
}

private static void broken(String[] input) {
turn = Integer.parseInt(input[1]);
for (int i = 2; i < input.length; i++){
if (input[i].equals("N")){
continue;
}
String[] coordinates = input[i].split(",");
int x = Integer.parseInt(coordinates[0]);
int y = Integer.parseInt(coordinates[1]);
theGrid[x][y] = BROKEN;
}
}

private static void destroy(String[] input) {
turn = Integer.parseInt(input[1]);
double[][] values = new double[sideLength][sideLength];
List<Point> pointList = new ArrayList<>();
for (int x = 0; x < sideLength; x++){
for (int y = 0; y < sideLength; y++){
if (theGrid[x][y] == MINE){
for (int x1 = 0; x1 < sideLength; x1++){
for (int y1 = 0; y1 < sideLength; y1++){
double distance = Math.pow(x - x1, 2) + Math.pow(y - y1, 2);
values[x1][y1] -= 1 / (distance + 1);
}
}
}
if (theGrid[x][y] == ACTIVE){
for (int x1 = 0; x1 < sideLength; x1++){
for (int y1 = 0; y1 < sideLength; y1++){
double distance = Math.pow(x - x1, 2) + Math.pow(y - y1, 2);
values[x1][y1] += 1 / (distance + 1) / (numberOfBots - 1);
}
}
}
}
}
pointList.sort(Comparator.comparingDouble((Point a) -> values[a.x][a.y]).reversed());
for (Point point : pointList){
if (theGrid[point.x][point.y] == INACTIVE){
out.println("VERTEX " + point.x + "," + point.y);
return;
}
}
out.println("NONE");
}
}


# FaucetBot (in R)

Creates a bottleneck on the second line, and activate nodes on the path behind it.

infile <- file("stdin")
open(infile)
repeat{
args <- strsplit(input," ")[[1]]
if(args[1]=="BEGIN"){
L <- as.integer(args[4])
M <- N <- matrix(0,nrow=L,ncol=L)
x0 <- sample(2:(L-1),1)
}
if(args[1]=="DESTROY"){
if(args[2]==0){
X <- x0
Y <- 2
}else{
free <- which(M[,2] == 0)
mine <- which(N[,2] == 1)
X <- free[which.min(abs(free-mine))]
Y <- 2
}
if(length(X)){cat(sprintf("VERTEX %s,%s\n",X-1,Y-1))}else{cat("NONE\n")}
flush(stdout())
}
if(args[1]=="BROKEN"){
b <- strsplit(args[args!="N"][-(1:2)],",")
o <- strsplit(args[3],",")[[1]]
b <- lapply(b,as.integer)
if(o[1]!="N") N[as.integer(o[1])+1,as.integer(o[2])+1] <- -1
for(i in seq_along(b)){M[b[[i]][1]+1,b[[i]][2]+1] <- -1}
}
if(args[1]=="ACTIVATE"){
if(args[2]==0){
broken <- which(M[,2] == -1)
free <- which(M[,2] == 0)
X <- free[which.min(abs(broken-free))]
Y <- 2
}else{
y <- 3
X <- NULL
while(length(X)<1){
lastrow <- which(N[,y-1]==1)
newrow <- unlist(sapply(lastrow,function(x)which(M[,y]==0 & abs((1:L)-x)<2)))
if(length(newrow)){
X <- sample(newrow,1)
Y <- y
}
y <- y+1
if(y>L){X <- x0; Y <- 1}
}
}
cat(sprintf("VERTEX %s,%s\n",X-1,Y-1))
flush(stdout())
}
if(args[1]=="OWNED"){
b <- strsplit(args[args!="N"][-(1:2)],",")
o <- strsplit(args[3],",")[[1]]
b <- lapply(b,as.integer)
if(o[1]!="N") N[as.integer(o[1])+1,as.integer(o[2])+1] <- 1
for(i in seq_along(b)){M[b[[i]][1]+1,b[[i]][2]+1] <- 1}
}
if(args[1]=="SCORE") q(save="no")
}


If I didn't screw up, the final configuration should be something like:

........    .a..aa..
..aaa...    ..aaa...
.xxaxx..    xxxaxxx.    etc.
........    ........


Command is Rscript FaucetBot.R.

# Peacemaker, Java

Based on Manu's code.

Peacemaker search conflict zones (i.e. most BROKEN or ACTIVE vertex concentration) and activates a random vertex nearby.

import java.awt.Point;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.stream.IntStream;

public class Peacemaker {
private static final int INACTIVE = 0;
private static final int ACTIVE   = 1;
private static final int BROKEN   = 2;
private static final int MINE     = 3;

private int size = 0;
private int[][] grid = new int[size][size];
private int startingPoint = 0;

public static void main(String[] args) {
new Peacemaker().start();
}

private void start() {
while(true) {
try {
act(input);
} catch (Exception e) {
e.printStackTrace();
System.exit(0);
}
}
}

private void act(String input) throws Exception {
String[] msg = input.split(" ");
String output = "";
int turn;
switch(msg[0]){
case "BEGIN":
size = Integer.parseInt(msg[3]);
grid = new int[size][size];
break;
case "DESTROY":
output = "NONE";
break;
case "BROKEN":
update(msg, true);
break;
case "ACTIVATE":
turn = Integer.parseInt(msg[1]);
output = activate(turn);
break;
case "OWNED":
update(msg, false);
break;
case "SCORE":
System.exit(0);
break;
}
if (output.length() > 0) {
System.out.println(output);
}
}

private String activate(int turn) {
Random r = new Random();
if (turn == 0) {
startingPoint = r.nextInt(size);
return "VERTEX " + startingPoint + "," + 0;
} else {

Point point = searchConflicts();

int posX = point.x;
int posY = point.y;

while (grid[posX][posY] != INACTIVE) {
int previousX = (posX - 1 < 0 ? size - 1 : posX - 1);
int nextX = (posX + 1 > size - 1 ? 0 : posX + 1);
int previousY = (posY - 1 < 0 ? size - 1 : posY - 1);
int nextY = (posY + 1 > size - 1 ? 0 : posY + 1);

int choice = r.nextInt(4);
switch (choice) {
case 0: posX = previousX; break;
case 1: posX = nextX; break;
case 2: posY = previousY; break;
case 3: posY = nextY; break;
}
}

return "VERTEX " + posX + "," + posY;
}
}

private Point searchConflicts() {

int previousCellScore = 0;
int cellX = 0;
int cellY = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j ++) {
if (previousCellScore < adjacentCellsScore(i, j)) {
cellX = i; cellY = j;
}
}
}
return new Point(cellX, cellY);
}

/*  Format of adjacent cells :
*
*   0 1 2
*   3 . 4
*   5 6 7
*/
private int adjacentCellsScore(int x, int y) {

int[] scores = new int[8];

int previousX = (x - 1 < 0 ? size - 1 : x - 1);
int nextX = (x + 1 > size - 1 ? 0 : x + 1);
int previousY = (y - 1 < 0 ? size - 1 : y - 1);
int nextY = (y + 1 > size - 1 ? 0 : y + 1);

scores[0] = calcScore(previousX, nextY);
scores[1] = calcScore(x, nextY);
scores[2] = calcScore(nextX, nextY);
scores[3] = calcScore(previousX, y);
scores[4] = calcScore(nextX, y);
scores[5] = calcScore(previousX, previousY);
scores[6] = calcScore(x, previousY);
scores[7] = calcScore(nextX, previousY);

return IntStream.of(scores).reduce(0, (a, b) -> a + b);
}

private int calcScore(int x, int y) {
int activeScore = 2;
int mineScore = 1;
int inactiveScore = 0;
int brokenScore = 3;

if (grid[x][y] == ACTIVE)
return activeScore;
else if (grid[x][y] == MINE)
return mineScore;
else if (grid[x][y] == INACTIVE)
return inactiveScore;
else if (grid[x][y] == BROKEN)
return brokenScore;
else
return 0;
}

private void update(String[] args, boolean destroyPhase) {
for(int i = 2; i < args.length; i++) {
String[] tokens = args[i].split(",");
if(tokens.length > 1){
int x = Integer.parseInt(tokens[0]);
int y = Integer.parseInt(tokens[1]);
if (grid[x][y] == INACTIVE) {
if (destroyPhase) {
grid[x][y] = BROKEN;
} else if (i == 2) {
grid[x][y] = MINE;
} else {
grid[x][y] = ACTIVE;
}
}
}
}
}
}

• @Zgarb Thanks, I should have resolved this issue now. – Thrax Mar 11 '15 at 13:07
• Peacemaker works now, and is included in the leaderboard. However, it doesn't seem to do much, so there are probably still some bugs left. – Zgarb Mar 13 '15 at 17:49
• Actually, looking at your code, I think the problem is in the while loop of the activate method. You stop the search once you find a vertex that is not yours and not broken -- but it could be owned by someone else, so you cannot activate it. – Zgarb Mar 13 '15 at 17:58
• @Zgarb I misread the specs and thought multiple players could activate the same vertex anytime. I guess I just have to change my search and look for inactive vertex only. – Thrax Mar 16 '15 at 7:39

# Random Builder, Python 3

This is a stupid example bot that never destroys anything, and tries to activate a random vertex every turn. Note that it doesn't need to check whether the vertex is inactive; the controller takes care of that.

import random as r

while True:
msg = input().split()
if msg[0] == "BEGIN":
side_len = int(msg[3])
elif msg[0] == "DESTROY":
print("NONE")
elif msg[0] == "ACTIVATE":
print("VERTEX %d,%d"%(r.randrange(side_len), r.randrange(side_len)), flush=True)
elif msg[0] == "SCORE":
break


Run with the command

python3 random_builder.py


You may need to replace python3 by python depending on your Python installation. To do this, just edit the bots.txt file. I updated the controller, and there's no need to mess with file paths anymore.

• Since your using python 3, instead of sys.stdout.flush() you can just do flush=True as an argument to print. – matsjoyce Feb 23 '15 at 21:34
• @matsjoyce Thanks, I didn't know that. I'll edit the repository version later. – Zgarb Feb 24 '15 at 13:38

# Explorer, Python 3

Activation strategy:

Creates a heatmap based on the state of every node (active/inactive/broken) and chooses the node which would have the biggest expected heatmap-value per person if it would choose that one.

Destruction strategy:

Never destroys anything as that doesn't help the bot much.

import sys

class bd:

def __init__(s, l):

s.l=l
s.b=[]
s.v=[]
s.m=[]
s.bm=[]
s.utd=False #up_to_date
s.bmc=1

for i in range(s.l):
s.b+=[[]]
s.v+=[[]]
s.m+=[[]]
s.bm+=[[]]
for k in range(s.l):
s.b[i]+=[0]
s.v[i]+=[0]
s.m[i]+=[0]
s.bm[i]+=[s.bmc]

def update(s):
s.utd=True

vu=[]
vd=[]
for i in range(s.l):
vu+=[[]]
vd+=[[]]
for k in range(s.l):
vu[i]+=[1]
vd[i]+=[1]

for i in range(s.l):
vu[i][0]*=s.bm[i][0]

for k in range(1,s.l):
for i in range(s.l):
sumv=vu[(i-1)%s.l][k-1]+vu[(i)%s.l][k-1]+vu[(i+1)%s.l][k-1]
vu[i][k]*=sumv*s.bm[i][k]/3

t=s.l-1
for i in range(s.l):
vd[i][t]*=s.bm[i][t]

for k in range(s.l-2,-1,-1):
for i in range(s.l):
sumv=vd[(i-1)%s.l][k+1]+vd[(i)%s.l][k+1]+vd[(i+1)%s.l][k+1]
vd[i][k]*=sumv*s.bm[i][k]/3

#mult
for i in range(s.l):
for k in range(s.l):
if s.b[i][k]==-1 or s.m[i][k]==1:
s.v[i][k]=float(-1)
else:
s.v[i][k]=vu[i][k]*vd[i][k]/(s.b[i][k]+1)

s.utd=False

for ind, ap in enumerate(al):
i,k=ap
s.b[i][k]+=1
s.bm[i][k]=2*s.bmc
#doesn't work alone WHY???
if ind==0: s.m[i][k]=1

s.utd=False

for ind, ip in enumerate(il):
i,k=ip
s.b[i][k]=-1
s.bm[i][k]=0

def get_newact(s):
s.update()
vm=-28
pm=None
for i in range(s.l):
for k in range(s.l):
if s.v[i][k]>vm:
vm=s.v[i][k]
pm=(i,k)
#doesn't work alone WHY???
s.m[pm[0]][pm[1]]=1
return pm

b=None

while True:
inp=input()
msg = inp.split()
if msg[0] == "BEGIN":
b = bd(int(msg[3]))
elif msg[0] == "DESTROY":
print("NONE")
elif msg[0] == "BROKEN":
pl=[]
for m in msg[2:]:
if m!='N':
pl+=[tuple(map(int,m.split(',')))]
elif msg[0] == "ACTIVATE":
at=b.get_newact()
print("VERTEX %d,%d"%(at[0], at[1]))
elif msg[0] == "OWNED":
pl=[]
for m in msg[2:]:
if m!='N':
pl+=[tuple(map(int,m.split(',')))]
elif msg[0] == "SCORE":
break

sys.stdout.flush()


# Annoyance, Bash

#!/bin/bash

declare -A avail
broken=
owned=

case "$c" in ACTIVATE|BROKEN) v=broken;; *) v=owned esac case "$c" in
BEGIN)
read b t n <<<"$p" list=$(
eval "echo {0..$((n-1))},{0..$((n-1))}\$'\\n'" | shuf ) for i in$list; do
avail[$i]=1 done;; DESTROY|ACTIVATE) for t in$(
for i in ${!v}; do [ "$i" != N ] &&
if [ "$c" = ACTIVATE ]; then echo$(((${i%,*}+2)%n)),${i#*,}
echo $(((${i%,*}-2+n)%n)),${i#*,} else echo${i%,*},$(((${i#*,}+1)%n))
echo ${i%,*},$(((${i#*,}-1+n)%n)) fi done | shuf )$list; do
[ "${avail[$t]}" ] && echo VERTEX $t && break done || echo NONE;; BROKEN|OWNED) read x m$v <<<"$p"; for i in$m ${!v}; do unset avail[$i]
done;;
SCORE)! :
esac
do :;done


Tried to make the result looks more interesting.

Run with bash annoyance.sh.

• Your bot prints all its inputs to STDERR. It's not forbidden or anything, just an annoyance (pun intended). – Zgarb Feb 24 '15 at 17:38
• @Zgarb Sorry, I pasted the wrong version. Fixed. – jimmy23013 Feb 24 '15 at 18:19

# Middle Man

I saw that some bots built from the top, and some from the bottom. This is the first (I think) to start in the middle and work up and down.

(it is not tested with the controller, so if it dose not work, let me know.)

class Node

def self.set_size s
@@grid = Array.new(s,Array.new(s,0))
end

def initialize x,y
@x=x
@y=y
end

def offset dx,dy
return Node.new @x+dx,@y+dy
end

def state
return -1 if @x<0 || @y<0 || @x>=@@grid.length || @y>=@@grid.length
@@grid[@x][@y]
end

def state= n
return -1 if @x<0 || @y<0 || @x>=@@grid.length || @y>=@@grid.length
@@grid[@x][@y]=n
end

def active?
state > 0
end

def open?
state == 0
end

def to_s
"VERTEX #{@x},#{@y}"
end

def scan_down
ans = nil
[0,-1,1].each do|offset|
n = Node.new @x+offset,@y-1
ans = (ans||n) if n.open?
ans = (n.scan_down||ans) if n.active?
end
return ans
end

def scan_up
ans = nil
[0,-1,1].each do|offset|
n = Node.new @x+offset,@y+1
ans = (ans||n) if n.open?
ans = (n.scan_up||ans) if n.active?
end
return ans
end

end

input = gets.split
input.shift

BotCount = input.shift.to_i
Turns = input.shift.to_i
GridSize = input.shift.to_i

Node.set_size GridSize

midRow = GridSize/2

toDestroy = (0...GridSize).map{|i|Node.new i,midRow}
toDestroy.reject!{|n| n.x==midRow}

chain = []
Turns.times do
gets;
toDestroy.each{|x|
if x.active?
toDestroy.push x.offset 0,1
toDestroy.push x.offset 1,1
toDestroy.push x.offset -1,1
end
}
toDestroy.reject!{|x|!x.open?}
puts toDestroy.sample
input = gets.split
input.shift;input.shift
input.each{|str|
a,b = str.split ','
(Node.new a.to_i,b.to_i).state=1
}
gets;

if chain.length == 0
n = Node.new midRow,midRow
until n.open?
n = Node.new n.x+1,midRow
end
puts chain[0]=n
elsif rand>0.5
n=nil
loop do
h=chain[0]
n = h.scan_down
break if !n
chain.shift
end
h.unshift n
puts n
else
loop do
h=chain[-1]
n = h.scan_up
h.pop if !n
brake if n
end
chain.push n
puts n
end

input = gets.split
input.shift;input.shift
input.each{|str|
a,b = str.split ','
(Node.new a,b).state=-1
}

end
gets
exit

• Thank you for the submission! Unfortunately, this challenge has been dormant for almost half a year, and I'm currently unable to run most of the bots, since I don't have access to a computer where I could install the languages. – Zgarb Aug 26 '15 at 19:14
• @Zgarb I understand. maybe someday I will answer a challenge in a reasonable time frame... – MegaTom Aug 26 '15 at 19:16