gistfile1.txt

// This software is released under the DBAD (Dont be a duche) license.
// If you improve this code in any way, you must release your modifications publicly.

#include "Map.h"
#include <string>
#include <vector>
#include <iostream>

#define DEPTH 1

const char *moves[] = {
        "SOUTH",
        "NORTH",
        "EAST",
        "WEST"
};

bool is_blocked(int x, int y, const Map &map,
        std::vector<std::vector<bool> > &blocked_grid)
{
        return map.IsWall(x, y) || blocked_grid[x][y];
}


int flood_fill_grid(const Map &map,
        std::vector<std::vector<bool> > &blocked_grid,
        std::vector<std::vector<bool> > &grid,
        int x, int y)
{
        int count = 1;
        if (is_blocked(x, y, map, blocked_grid) || grid[x][y])
                return 0;
        grid[x][y] = true;
        count += flood_fill_grid(map, blocked_grid, grid, x, y+1);
        count += flood_fill_grid(map, blocked_grid, grid, x, y-1);
        count += flood_fill_grid(map, blocked_grid, grid, x+1, y);
        count += flood_fill_grid(map, blocked_grid, grid, x-1, y);
        return count;
}

std::vector<std::vector<bool> > *create_map_grid(const Map &map)
{
        return new std::vector<std::vector<bool> >(map.Width(),
                std::vector<bool>(map.Height(), false));
}

bool can_move_from(int x, int y, const Map &map, std::vector<std::vector<bool> > &blocked_grid)
{
        if(!is_blocked(x, y+1, map, blocked_grid))
                return true;
        if(!is_blocked(x, y-1, map ,blocked_grid))
                return true;
        if(!is_blocked(x+1, y, map, blocked_grid))
                return true;
        if(!is_blocked(x-1, y, map, blocked_grid))
                return true;
        return false;
}

bool is_same_location(int x1, int y1, int x2, int y2)
{
        return x1 == x2 && y1 == y2;
}

int max(std::vector<int> &vals)
{
        unsigned int i;
        int highest;
        highest = vals[0];
        for(i=1;i<vals.size();i++)
        {
                if(vals[i] > highest)
                        highest = vals[i];
        }
        return highest;
}

int score_my_move(const Map &map,
        std::vector<std::vector<bool> > &blocked_grid,
        int my_x, int my_y,
        int their_x, int their_y,
        int max_depth);

int move_count(const Map &map,
        std::vector<std::vector<bool> > &blocked_grid,
        int x, int y)
{
        int count = 0;
        if(!is_blocked(x, y+1, map, blocked_grid))
                count++;
        if(!is_blocked(x, y-1, map, blocked_grid))
                count++;
        if(!is_blocked(x+1, y, map, blocked_grid))
                count++;
        if(!is_blocked(x-1, y, map, blocked_grid))
                count++;
        return count;
}


int abs(int val)
{
        if(val >= 0)
                return val;
        return -val;
}

int score_their_move(const Map &map,
        std::vector<std::vector<bool> > &blocked_grid,
        int my_x, int my_y,
        int their_x, int their_y,
        int max_depth)
{
        int my_area, their_area;
        bool they_have_moves, we_have_moves;
        std::vector<int> scores(4, -100);

        if(is_same_location(my_x, my_y, their_x, their_y))
                return 50;

        they_have_moves = can_move_from(their_x, their_y, map, blocked_grid);
        we_have_moves = can_move_from(my_x, my_y, map, blocked_grid);
        if(!they_have_moves)
        {
                if(!we_have_moves)
                        return 50;
                return -100;
        }
        if(!we_have_moves)
                return 100;

        if(max_depth > 0)
        {
                max_depth--;
                blocked_grid[my_x][my_y] = true;
                blocked_grid[their_x][their_y] = true;

                if(!is_blocked(my_x, my_y+1, map, blocked_grid))
                        scores[0] = -score_my_move(map, blocked_grid, my_x, my_y+1, their_x, their_y, max_depth);
                if(!is_blocked(my_x, my_y-1, map, blocked_grid))
                        scores[1] = -score_my_move(map, blocked_grid, my_x, my_y-1, their_x, their_y, max_depth);
                if(!is_blocked(my_x+1, my_y, map, blocked_grid))
                        scores[2] = -score_my_move(map, blocked_grid, my_x+1, my_y, their_x, their_y, max_depth);
                if(!is_blocked(my_x-1, my_y, map, blocked_grid))
                        scores[3] = -score_my_move(map, blocked_grid, my_x-1, my_y, their_x, their_y, max_depth);

                blocked_grid[my_x][my_y] = false;
                blocked_grid[their_x][their_y] = false;
                return max(scores);
        }

        std::vector<std::vector<bool> > *fg = create_map_grid(map);
        my_area = flood_fill_grid(map, blocked_grid, *fg, my_x, my_y);
        if(!(*fg)[their_x][their_y])
        {
                their_area = flood_fill_grid(map, blocked_grid, *fg, their_x, their_y);
                delete fg;
                fg = 0;
                if(their_area > my_area)
                        return 75;
                if(their_area < my_area)
                        return -75;
        }
        if(fg)
                delete fg;

        float area = my_area;
        return -20 + (area / (map.Width() * map.Height())) * 40.0f;
}


int score_my_move(const Map &map,
        std::vector<std::vector<bool> > &blocked_grid,
        int my_x, int my_y,
        int their_x, int their_y,
        int max_depth)
{
        if(is_blocked(my_x, my_y, map, blocked_grid))
                return -100;
        std::vector<int> scores(4, -100);

        if(!is_blocked(their_x, their_y+1, map, blocked_grid))
                scores[0] = -score_their_move(map, blocked_grid, my_x, my_y, their_x, their_y+1, max_depth);
        if(!is_blocked(their_x, their_y-1, map, blocked_grid))
                scores[1] = -score_their_move(map, blocked_grid, my_x, my_y, their_x, their_y-1, max_depth);
        if(!is_blocked(their_x+1, their_y, map, blocked_grid))
                scores[2] = -score_their_move(map, blocked_grid, my_x, my_y, their_x+1, their_y, max_depth);
        if(!is_blocked(their_x-1, their_y, map, blocked_grid))
                scores[3] = -score_their_move(map, blocked_grid, my_x, my_y, their_x-1, their_y, max_depth);

        return max(scores);
}

std::string MakeMove(const Map& map) {
        int x = map.MyX();
        int y = map.MyY();
        int their_x = map.OpponentX();
        int their_y = map.OpponentY();
        int best_score = -101;
        int best_move = 0;
        int score;

        std::vector<std::vector<bool> > *grid = create_map_grid(map);

#define try_move(my_x, my_y, n)\
        if (!map.IsWall(my_x, my_y)) {\
                score = score_my_move(map, *grid, my_x, my_y, their_x, their_y, DEPTH);\
                if(score > best_score)\
                {\
                        best_score = score;\
                        best_move = n;\
                }\
        }\

        try_move(x, y+1, 0);
        try_move(x, y-1, 1);
        try_move(x+1, y, 2);
        try_move(x-1, y, 3);

#undef try_move

        return moves[best_move];
}

// Ignore this function. It is just handling boring stuff for you, like
// communicating with the Tron tournament engine.
int main() {
  while (true) {
    Map map;
    Map::MakeMove(MakeMove(map));
  }
  return 0;
}