Grid-Routing Battle

Question

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.

Additional Rules

• 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.

Leaderboard

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.

Answer 1

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()
        deadnodes = 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
                deadnodes.add(loc)
                freenodes.discard(loc)
                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:
                    mynodes.add(loc)
                freenodes.discard(loc)
                if loc in extra: extra.remove(loc)
        turn += 1

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

The spider is run with python funnelweb.py.

Answer 2

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.io.BufferedReader;
import java.io.InputStreamReader;
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() {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            try {
                String input = reader.readLine();
                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<>();
        endCells.add(thisCell);
        path.add(thisCell);
        for (int i = -1; i <= 1; i++) {
            int newX = (x + i + size) % size;
            if (grid[newX][newY] == ACTIVE || grid[newX][newY] == MINE) {
                endCells.add(findLastPathCell(newX, newY));
            }
        }
        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;
                        path.add(new Point(x,y));
                        previousCell = new Point(x,y);
                    } else {
                        grid[x][y] = ACTIVE;
                    }
                }
            }
        }
    }
}

Answer 3

Checkpoint, Java

This bot tries to create checkpoints so that any valid path passes through one of my vertices. Since there are N² turns and the board is 2N² 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;
import java.io.InputStreamReader;

public class Checkpoint {
    public static void main(String[] args) {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while(true)
            try {
                String input = reader.readLine();
                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.

Answer 4

FaucetBot (in R)

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

infile <- file("stdin")
open(infile)
repeat{
    input <- readLines(infile,1)
    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.

Answer 5

Watermelon, Java

Attempts to draw watermelons on the grid.

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    private static PrintStream out = System.out;

    public static void main(String[] args) throws IOException {
        while (true){
            String[] input = in.readLine().trim().split(" ");
            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.add(new Point(x, y));
            }
        }
        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.add(new Point(x, y));
            }
        }
        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");
    }
}

Answer 6

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.io.BufferedReader;
import java.io.InputStreamReader;
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() {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            try {
                String input = reader.readLine();
                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;
                    previousCellScore = adjacentCellsScore(i, 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;
                    }
                }
            }
        }
    }       
}

Answer 7

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.

Answer 8

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]

        #spread up
        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

        #spread down
        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)

    def add_act(s,al):
        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

    def add_ina(s,il):
        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(',')))]
        b.add_ina(pl)
    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(',')))]        
        b.add_act(pl)
    elif msg[0] == "SCORE":
        break       

    sys.stdout.flush()

Answer 9

Annoyance, Bash

#!/bin/bash

declare -A avail
broken=
owned=

while read c p
    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.

Answer 10

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
  attr_reader :x,:y

  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