King of the Hill: Robot Battle

Question

Your task here is to write an AI for a simple robot battle. The class to be implemented is provided at the bottom of this post, and source of the controller can be found here.

Requirements

1. Write a class which implements the abstract Bot class, provided at the bottom of this post
2. You must provide a 0-argument constructor, this must change the value of the Name field, but may not change any other inherited fields
3. Outside of the constructor, you may not change any of the inherited fields in any way
4. Your action method should, when called (it will be called once per turn cycle, with a copy of the 64 by 64 map as its argument), return one of the Action enum fields:

UP  to move up (towards y=0)
DOWN to move down
LEFT to move left (towards x=0)
RIGHT to move right
MINE to plant a mine and then move a random direction
PASS to pass

5. Within the passed map, 0 represents an empty cell, -1 represents a mined cell, and anything else denotes a cell occupied by a bot (each bot will be represented by its unique bot_id, you can get your bot's id by calling this.id())
6. A bot is eliminated in any of the following situations:

• It moves out of the map
• It moves into a cell occupied by a mine
• Another bot moves into the cell it currently occupies
• Its action method takes more than 50ms to respond
• Its action method throws any exception that is not caught within its own bounds

To win

Have your bot be the last bot standing!

Additional Rules

The round is not allowed to last more than 1,000 turn cycles. If, after the 1,000th turn cycle, more than one bot is still standing, all of the surviving bots are considered to have tied that round.

Each time a new bot is submitted, it will, as soon as possible, be pitted in two two-bot, three three-bot, and three-four bot rounds; each time against randomly selected opponents.

Scoring

total score=1000*(wins+(1/3) ties - (1/12) losses)/roundsPlayed

The exceptions to this are that any bot that has played at least one round that it didn't lose is guaranteed at least one point, and no bot may have a negative score.

The class to be implemented:

import java.util.*;

public abstract class Bot {
    public static enum Action{
        UP,DOWN,LEFT,RIGHT,MINE,PASS;
    }
    public static final class Position{
        public int x;
        public int y;
        public String toString(){
            return "("+x+","+y+")";
        }
        public double distance(Position p){
            int dx=p.x-this.x;
            int dy=p.y-this.y;
            return Math.sqrt(dx*dx+dy*dy);
        }
        public Position(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    public String toString(){return name;}
    public Position p;
    public String name="";
    public abstract Action action(int[][] map);
    private int bot_id;
    public final int id(){return bot_id;}
    public final void register(List<Bot> a){
        a.add(this);
        bot_id=a.size();
    }
}

Leaderboard

The full match log may be read here

ProtectiveBot (6 wins, 6 ties, 1 loss)- 609 points
Albert (2 wins, 8 ties, 0 losses)- 467 points
Frozen (1 win, 8 ties, 0 losses)- 407 points
Cocoon (1 win, 3 ties, 3 losses)-250 points
Wanderlust (0 wins, 3 ties, 5 losses)- 73 points
MineThenBoom (0 wins, 2 ties, 11 losses)- 1 point
PatientBot (0 wins, 0 ties, 13 losses)- 0 points

Sample Bots

Simple Pathfinder: http://pastebin.com/raw.php?i=aNBf00VU

RandomBot: http://pastebin.com/raw.php?i=VD8iGaHC

Minelayer: http://pastebin.com/raw.php?i=sMN1zSa0

Answer 1

ProtectiveBot

A bunch of ideas rolled together to form something. There are a number of states that it can enter. Firstly, if there is no-one around them, it will build itself a cocoon which is just about indestructible, and sit in it for a while, killing anyone it can.

If there is someone close during startup, there is less then 200 turns left, or there is only one enemy bot remaining, the bot will enter a aggressive mode, which is essentially an enhanced pathfinder, attempting to trick its opponents. This mode uses a flood style pathfinding system at close range, and the same technique in the provided pathfinding example at long range.

If there are multiple instances of this bot in game, the bots will refrain from killing each other until the end.

Its big as well, weighing in at 527 741 lines. Compiling against Java 8. Also, have a graphic renderer of the battle system: https://github.com/j-selby/RobotBattleController

I've reached the limit for how big these posts can be, see bot src at https://github.com/j-selby/RobotBattleController/blob/master/src/main/java/ProtectiveBot.java. Sorry...

Rev 3:

• Threaded pathfinding. No more timeouts!
• Detection of stalemates. TODO: Do something about them.
• Full A* pathfinding. No more dumb stuff.
• Checks OTHER bots positions for unfair play (trapping themselves in completely).

Rev 2:

• Stopped bot being killed at corners
• Smarter building logic
• Will never do any move that could endanger us, excluding against other instances of ProtectiveBot.

Answer 2

Frozen

After analyzing how the controller worked, I determined the only way to lose is to move. Therefore, this robot stays in place unless absolutely necessary.

public class Frozen extends Bot{
        public Frozen(){
            this.name="Frozen";
        }
        public Action action(int[][] map) {
            if (p.x > 0 && map[p.x-1][p.y] > 0) return Action.LEFT;
            if (p.x < map.length-1 && map[p.x+1][p.y] > 0) return Action.RIGHT;
            if (p.y > 0 && map[p.x][p.y-1] > 0) return Action.UP;
            if (p.y < map.length-1 && map[p.x][p.y+1] > 0) return Action.DOWN;
            return Action.PASS;
        }
}

Answer 3

Wanderlust

I join the competetion with a bot called Wanderlust! Its algorithm is actually pretty straightforward. While it's trying to avoid mines and not running off the map, it's randomly spraying mines around. If an enemy bot would come closer, though, it scurries off in the opposite direction.

Wanderlust's a decent bot, but just doesn't cut it when there are A* algorithm bots on the field. You can see it running away while the enemy bot is figuring out how to get closer, but eventually it dies. (Unless those bots get trapped of course, which then simply results in a tie.)

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

public class Wanderlust extends Bot {

private static final double NEAR_ENEMY_RUN_DISTANCE = 12;
private static final double NEAR_ENEMY_PASS_DISTANCE = 2.5;
private static final int SAFE_NUMBER_OF_MINES = 0;
private Random random;

public Wanderlust() {
    this.name = "Wanderlust";
    this.random = new Random(System.currentTimeMillis());
}

@Override
public Action action(int[][] map) {

    List<Action> actions = new ArrayList<Action>();
    List<Position> enemyPositions = mapEnemyPositions(map);
    Position nearestBotPosition = getNearestBotPosition(enemyPositions);
    Action action = Action.PASS;

    if (nearestBotPosition != null && nearestBotPosition.distance(this.p) < NEAR_ENEMY_RUN_DISTANCE) {
        // Run! Can't risk to drop a mine because of the random movement afterwards.
        // So check where the enemy is and run the opposite way!
        // This is all good unless the enemy is reaaaally close. In that case, we're just struck with fear and stand still.

        if (nearestBotPosition.distance(this.p) < NEAR_ENEMY_PASS_DISTANCE) {
            return Action.PASS;
        }

        int dx = this.p.x - nearestBotPosition.x;
        int dy = this.p.y - nearestBotPosition.y;

        Action horizontalAction = dx < 0 ? Action.LEFT : Action.RIGHT;
        Action verticalAction = dy < 0 ? Action.UP : Action.DOWN;

        // Is the enemy closer to me on the x-axis, or the y-axis?
        if (Math.abs(dx) < Math.abs(dy)) {
            // OK, which way do we run away from the enemy? Left or right?
            // And if we can't run left or right, we should think about a back-up plan: moving vertically.
            Action primaryAction = dx < 0 ? Action.LEFT : Action.RIGHT;
            actions.add(primaryAction);
            actions.add(verticalAction);
            action = getValidMove(actions, true, map);
        } else {
            // OK, which way do we run away from the enemy? Up or down?
            // And if we can't run up or down, we should think about a back-up plan: moving horizontally.
            Action primaryAction = dy < 0 ? Action.UP : Action.DOWN;
            actions.add(primaryAction);
            actions.add(horizontalAction);
            action = getValidMove(actions, true, map);
        }
    } else {
        // Just casual strolling. Hey, perhaps dropping a mine? #casualThings
        actions.add(Action.LEFT);
        actions.add(Action.RIGHT);
        actions.add(Action.UP);
        actions.add(Action.DOWN);
        actions.add(Action.MINE);

        if (this.p.x == 0 || this.p.x == 63 || this.p.y == 0 || this.p.y == 63 || getNumberOfMinesAroundPosition(this.p, map) > SAFE_NUMBER_OF_MINES) {
            actions.remove(Action.MINE);
        }

        action = getValidMove(actions, false, map);
    }

    return action;
}

private Action getValidMove(List<Action> actions, boolean preserveOrder, int[][] map) {

    List<Action> validMoves = new ArrayList<Action>();

    for (Action action : actions) {
        if (action == Action.LEFT && this.p.x > 0 && map[this.p.x-1][this.p.y] >= 0) {
            validMoves.add(Action.LEFT);
        }

        if (action == Action.RIGHT && this.p.x < 63 && map[this.p.x+1][this.p.y] >= 0) {
            validMoves.add(Action.RIGHT);
        }

        if (action == Action.UP && this.p.y > 0 && map[this.p.x][this.p.y-1] >= 0) {
            validMoves.add(Action.UP);
        }

        if (action == Action.DOWN && this.p.y < 63 && map[this.p.x][this.p.y+1] >= 0) {
            validMoves.add(Action.DOWN);
        }

        if (action == Action.MINE) {
            validMoves.add(Action.MINE);
        }
    }

    if (validMoves.isEmpty()) {
        return Action.PASS;
    }

    return preserveOrder ? validMoves.get(0) : validMoves.get(random.nextInt(validMoves.size()));
}

private int getNumberOfMinesAroundPosition(Position position, int[][] map) {
    int count = 0;

    if (position.x > 0 && map[position.x-1][position.y] == -1) {
        count++;
    }

    if (position.x < 63 && map[position.x+1][position.y] == -1) {
        count++;
    }

    if (position.y > 0 && map[position.x][position.y-1] == -1) {
        count++;
    }

    if (position.y < 63 && map[position.x][position.y+1] == -1) {
        count++;
    }

    return count;
}

private Position getNearestBotPosition(List<Position> enemyPositions) {
    Position botPosition = null;
    double distance = Double.MAX_VALUE;

    for (Position position : enemyPositions) {
        double botDistance = position.distance(this.p);
        if (botDistance <= distance) {
            distance = botDistance;
            botPosition = position;
        }
    }

    return botPosition;
}

private List<Position> mapEnemyPositions(int[][] map) {

    List<Position> enemyPositions = new ArrayList<Position>();

    for (int yy = 0; yy < 63; yy++) {
        for (int xx = 0; xx < 63; xx++) {
            if (map[xx][yy] > 0 && map[xx][yy] != id()) {
                enemyPositions.add(new Position(xx, yy));
            }
        }           
    }

    return enemyPositions;
}
}

Answer 4

MineThenBoom

A modified version of the pathfinder.
His priorities are crush, mine, leave, sit. Yeah, the guy's a little crazy.
Updates to this bot may be given as I find new strategies. Please notify me if something goes wrong.

import java.util.*;


public class MineThenBoom extends Bot{
    public MineThenBoom() {
        this.name="MineThenBoom";
    }
    public Action action(int[][] map) {
        List<Position> enemies=new ArrayList<Position>();
        for(int x=1;x<map.length;x++){
            for(int y=1;y<map[x].length;y++){
                if(map[x][y]!=0&&map[x][y]!=this.id()&&map[x][y]!=-1){
                    enemies.add(new Position(x,y));
                }
            }
        }
        double d=200;
        Position x=null;
        for(Position pos:enemies){
            if(p.distance(pos)<d){
                x=pos;
                d=p.distance(pos);
            }
        }
    // initialize checking for walls
    boolean can_move_left = p.x != 0;
    boolean can_move_right = p.x != 63;
    boolean can_move_up = p.y != 0;
    boolean can_move_down = p.y != 63;
    // Check if there's anyone nearby to crush, if it won't put us in danger.
        if(x.x<p.x&&map[p.x-1][p.y]!=-1&&x.x<p.x&&map[p.x-1][p.y]!=0) {
       boolean no_one_around = map[p.x-1][p.y-1] < 1 && map[p.x-1][p.y+1] < 1;
       if(no_one_around)return Action.LEFT;
    }
        if(x.x>p.x&&map[p.x+1][p.y]!=-1&&x.x<p.x&&map[p.x-1][p.y]!=0) {
       boolean no_one_around = map[p.x+1][p.y-1] < 1 && map[p.x+1][p.y+1] < 1;
       if(no_one_around)return Action.RIGHT;
    }
        if(x.y>p.y&&map[p.x][p.y+1]!=-1&&x.x<p.x&&map[p.x-1][p.y]!=0) {
       boolean no_one_around = map[p.x-1][p.y+1] < 1 && map[p.x+1][p.y+1] < 1;
       if(no_one_around)return Action.DOWN;
    }
        if(x.y<p.y&&map[p.x][p.y-1]!=-1&&x.x<p.x&&map[p.x-1][p.y]!=0) {
       boolean no_one_around = map[p.x-1][p.y-1] < 1 && map[p.x+1][p.y-1] < 1;
       if(no_one_around)return Action.UP;
    }
    // If we've come this far, it means no one is crushable. Lay a mine, but only if we're ABSOLUTELY safe.
    boolean no_one_around = map[p.x+1][p.y-1] < 1 && map[p.x+1][p.y+1] < 1 && map[p.x-1][p.y-1] < 1 && map[p.x-1][p.y+1] < 1;
    boolean not_walking_into_mine = map[p.x+1][p.y] == 0 && map[p.x-1][p.y] == 0 && map[p.x][p.y-1] == 0 && map[p.x][p.y+1] == 0;
    boolean not_walking_near_danger = map[p.x+2][p.y] < 1 && map[p.x-2][p.y] < 1 && map[p.x][p.y+2] < 1 && map[p.x][p.y-2] < 1;
    if(no_one_around && not_walking_into_mine && not_walking_near_danger)return Action.MINE;
    // OK, let's take a little walk.
        if(x.x<p.x&&map[p.x-1][p.y]!=-1) {
       boolean no_one_around = map[p.x-1][p.y-1] < 1 && map[p.x-1][p.y+1] < 1;
       if(no_one_around)return Action.LEFT;
    }
        if(x.x>p.x&&map[p.x+1][p.y]!=-1) {
       boolean no_one_around = map[p.x+1][p.y-1] < 1 && map[p.x+1][p.y+1] < 1;
       if(no_one_around)return Action.RIGHT;
    }
        if(x.y>p.y&&map[p.x][p.y+1]!=-1) {
       boolean no_one_around = map[p.x-1][p.y+1] < 1 && map[p.x+1][p.y+1] < 1;
       if(no_one_around)return Action.DOWN;
    }
        if(x.y<p.y&&map[p.x][p.y-1]!=-1) {
       boolean no_one_around = map[p.x-1][p.y-1] < 1 && map[p.x+1][p.y-1] < 1;
       if(no_one_around)return Action.UP;
    }
    // We clearly are pinned down by some number of players on one or more edges. Let's make our way out of here!
    no_one_around = map[p.x-1][p.y-1] < 1 && map[p.x-1][p.y+1] < 1 && map[p.x-2][p.y] < 1 && map[p.x-1][p.y] == 0 && x.x<p.x;
    if(no_one_around)return Action.LEFT;
    no_one_around = map[p.x+1][p.y-1] < 1 && map[p.x+1][p.y+1] < 1 && map[p.x+2][p.y] < 1 && map[p.x+1][p.y] == 0 && x.x>p.x;
    if(no_one_around)return Action.RIGHT;
    no_one_around = map[p.x-1][p.y-1] < 1 && map[p.x+1][p.y-1] < 1 && map[p.x][p.y-2] < 1 && map[p.x][p.y-1] == 0 && x.y<p.y;
    if(no_one_around)return Action.DOWN;
    no_one_around = map[p.x-1][p.y+1] < 1 && map[p.x+1][p.y+1] < 1 && map[p.x][p.y+2] < 1 && map[p.x][p.y+1] == 0 && x.y>p.y;
    if(no_one_around)return Action.UP;
    // Well then. We can't crush, lay a mine, or escape.
    // We are most likely near a player who, if they move, will either no longer be a threat or we can crush.
    // If we are somehow surrounded by mines, we're safe anyways.
    return Action.PASS; 

    }
}

CHANGES

• Fixed bot so it wouldn't always lay mines, and won't be crushed too easily.
• Fixed severe logic flaws in bot, as well as minor tune-ups.
• Once again, rewrote all the logic.
• v1.0: Added code to try to move around a little, see if we can force other bots like us to move.

Thanks to SuperJedi224 for helping me with my code.

Answer 5

PatientBot

Super simple bot that puts down a defensive wall and then just waits. (I will probably write a more serious solution later, but this will do for now.)

public class PatientBot extends Bot{
    public PatientBot(){
        name="PatientBot";
    }
    int turn = 0;
    public Action action(int[][] map){
        switch(turn++){
        case 0: return Action.UP;
        case 1: return Action.MINE;
        case 2: return Action.LEFT;
        case 3: return Action.DOWN;
        case 4: return Action.MINE;
        case 5: return Action.DOWN;
        case 6: return Action.RIGHT;
        case 7: return Action.MINE;
        case 8: return Action.RIGHT;
        case 9: return Action.UP;
        case 10: return Action.MINE;
        default: return Action.PASS;
        }
    }
}

Answer 6

Well, here's another Simple Pathfinder variant I wrote, and I decided... why not enter it this time?

Albert

import java.util.*;

public class Albert extends Bot{
    private Random r=new Random();
    public Albert(){
        this.name="Albert";
    }
    private int countMines(int[][] map,Position p){
        int mines=0;
        if(p.y==63||map[p.x][p.y+1]==-1)mines++;
        if(p.y==0||map[p.x][p.y-1]==-1)mines++;
        if(p.x==0||map[p.x-1][p.y]==-1)mines++;
        if(p.x==63||map[p.x+1][p.y]==-1)mines++;
        return mines;
    }
    @Override
    public Action action(int[][] map) {
        List<Position> enemies=new ArrayList<Position>();
        for(int x=1;x<map.length;x++){
            for(int y=1;y<map[x].length;y++){
                if(map[x][y]!=0&&map[x][y]!=this.id()&&map[x][y]!=-1){
                    enemies.add(new Position(x,y));
                }
            }
        }
        double d=200;
        Position x=null;
        for(Position pos:enemies){
            if(p.distance(pos)<d){
                x=pos;
                d=p.distance(pos);
            }
        }
        if(countMines(map,p)==0&&r.nextDouble()<0.5&&d>2.01)return Action.MINE;
        if(d>1.03&&d<3)return Action.PASS;
        if(x==null)return Action.PASS;
        if(x.x<p.x&&map[p.x-1][p.y]!=-1&&countMines(map,new Position(p.x-1,p.y))<2&&r.nextDouble()<0.8)return Action.LEFT;
        if(x.x>p.x&&map[p.x+1][p.y]!=-1&&countMines(map,new Position(p.x+1,p.y))<2&&r.nextDouble()<0.8)return Action.RIGHT;
        if(x.y>p.y&&map[p.x][p.y+1]!=-1&&countMines(map,new Position(p.x,p.y+1))<2&&r.nextDouble()<0.8)return Action.DOWN;
        if(x.y<p.y&&map[p.x][p.y-1]!=-1&&countMines(map,new Position(p.x,p.y-1))<2&&r.nextDouble()<0.8)return Action.UP;
        List<Action> v=new ArrayList<Action>();
        if(p.y>0&&map[p.x][p.y-1]!=-1&&countMines(map,new Position(p.x,p.y-1))<3)v.add(Action.UP);
        if(p.y<63&&map[p.x][p.y+1]!=-1&&countMines(map,new Position(p.x,p.y+1))<3)v.add(Action.DOWN);
        if(p.x>0&&map[p.x-1][p.y]!=-1&&countMines(map,new Position(p.x-1,p.y))<3)v.add(Action.LEFT);
        if(p.x<63&&map[p.x+1][p.y]!=-1&&countMines(map,new Position(p.x+1,p.y))<3)v.add(Action.RIGHT);
        v.add(Action.PASS);
        return v.get((new Random()).nextInt(v.size()));
    }
}

Answer 7

Cocoon

I borrowed a bit of utility code from some other bots. The basic strategy here is to get into a safe spot. To accomplish that, I try to lay mines in spots likely to bump me into safe spots. Nearby goals are preferred over distant goals. Absolutely nothing is done about other bots. This bot can usually build a safe spot in a few dozen turns after laying down a checkerboard of failures, so it will at least tie with other bots that can't seek it out and kill it that fast. A bit of code to avoid or kill other bots would improve that scenario.

import java.awt.*;
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

public class CocoonBot extends Bot{
    private static final int Y = 64, X = 64;
    public CocoonBot() {
        this.name="Cocoon";
    }

    private int neighborMines(int[][] map, Point p){
        int mines=0;
        if (p.y>=Y-1||map[p.x][p.y+1]==-1) mines++;
        if (p.y<=  0||map[p.x][p.y-1]==-1) mines++;
        if (p.x>=X-1||map[p.x+1][p.y]==-1) mines++;
        if (p.x<=  0||map[p.x-1][p.y]==-1) mines++;
        return mines;
    }

    @Override
    public Action action(int[][] map) {

        Point firstPoint = new Point(p.x, p.y);
        if ( neighborMines(map,firstPoint) == 4 ) {
            return Action.PASS; // we've built a cocoon and are safe
        }

        // calculate how many mines surround each point of the map, 0-4
        Map<Point, Integer> safety = new HashMap<>();
        for(int x=0; x<X; x++) {
            for(int y=0; y<Y; y++) {
                //TODO: teach the bot that it won't ever lay mines on the edge or adjacent to other mines
                //      so effective safety is 0 if getting to 3 requires one of those actions
                Point p = new Point(x,y);
                int s = neighborMines(map,p);
                safety.put(p,s);
            }
        }

        // flood fill the map to find travel paths and distances from the current square to each other non-mine square
        LinkedBlockingQueue<Point> frontier = new LinkedBlockingQueue<>();
        Map<Point, Point> came_from = new HashMap<>();
        Map<Point, Integer> distance = new HashMap<>();
        frontier.add(firstPoint);
        came_from.put(firstPoint, new Point(-1, -1));
        distance.put(firstPoint,0);
        Point current;
        while((current = frontier.poll()) != null) {
            // TODO: bail here for squares too far away to be worth considering
            for(int d=0; d<4; d++) {
                int dx = d<2?(d*2-1):0; //-1 +1  0  0
                int dy = d<2?0:(d*2-5); // 0  0 -1 +1
                if (current.y+dy<Y && current.y+dy>=0 && current.x+dx<X && current.x+dx>=0) {
                    if (map[current.x+dx][current.y+dy] != -1) {
                        Point next = new Point(current.x+dx, current.y+dy);
                        if(!distance.containsKey(next)) {
                            frontier.add(next);
                            came_from.put(next, current);
                            distance.put(next,distance.get(current)+1);
                        }
                    }
                }
            }
        }

        // calculate the safety of where we might end up after dropping a mine
        // weighted towards safer spaces, we really want to end up in space that's already safety=3
        Map<Point, Integer> safety2 = new HashMap<>();
        for(int x=0; x<X; x++) {
            for(int y=0; y<Y; y++) {
                int s = 0;
                for(int d=0; d<4; d++) {
                    int dx = d<2?(d*2-1):0; //-1 +1  0  0
                    int dy = d<2?0:(d*2-5); // 0  0 -1 +1
                    Point p = new Point(x+dx,y+dy);
                    if ( x+dx<0||x+dx>=X||y+dy<0||y+dy>=Y || map[x+dx][y+dy]==-1 ) {
                        // never risk moving into a mine or off the map!
                        s = -999;
                        break;
                    } else if ( safety.containsKey(p) ) {
                        // safety 3 is great
                        // safety 2 is ok
                        // safety 1 is better than nothing
                        s += safety.get(p)>2?12:safety.get(p)>1?3:safety.get(p); // magic numbers!
                    }
                }
                Point p = new Point(x,y);
                safety2.put(p,s);
            }
        }

        // find the safest/closest point
        Point bestpoint = firstPoint;
        double bestscore = safety2.get(firstPoint)+0.1;
        distance.remove(firstPoint);
        for (Map.Entry<Point,Integer> pd : distance.entrySet()) {
            Point p = pd.getKey();
            double score = safety2.get(p)/Math.pow(pd.getValue(),0.8); // magic number!
            if(score > bestscore) {
                bestscore = score;
                bestpoint = p;
            } else if (score == bestscore) {
                if ( (bestpoint.x-X/2)*(bestpoint.x-X/2)+(bestpoint.y-Y/2)*(bestpoint.y-Y/2) > 
                     (p.x-X/2)*(p.x-X/2)+(p.y-Y/2)*(p.y-Y/2) ) {
                    // aim for the middle, less wasted time at edges
                    bestscore = score;
                    bestpoint = p;
                }
            }
        }

        // we're in the right spot, place a mine and hope for a good random bump
        if(bestpoint == firstPoint) {
            return Action.MINE;
        }

        // walk back up came_from to figure out which way to step to get to bestpoint
        while(came_from.get(bestpoint) != firstPoint) {
            bestpoint = came_from.get(bestpoint);
        }
        if ( bestpoint.x > firstPoint.x ) {
            return Action.RIGHT;
        }
        if ( bestpoint.x < firstPoint.x ) {
            return Action.LEFT;
        }
        if ( bestpoint.y > firstPoint.y ) {
            return Action.DOWN;
        }
        if ( bestpoint.y < firstPoint.y ) {
            return Action.UP;
        }

        // should never happen
        return Action.MINE;
    }

}