Grid-Based Expansion for halite.io

hlt.py

"""
A Python-based Halite starter-bot framework.

This module contains a Pythonic implementation of a Halite starter-bot framework.
In addition to a class (GameMap) containing all information about the game world
and some helper methods, the module also imeplements the functions necessary for
communicating with the Halite game environment.
"""

import sys
from collections import namedtuple
from itertools import chain, zip_longest


def grouper(iterable, n, fillvalue=None):
    "Collect data into fixed-length chunks or blocks"
    # grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx"
    args = [iter(iterable)] * n
    return zip_longest(*args, fillvalue=fillvalue)

# Because Python uses zero-based indexing, the cardinal directions have a different mapping in this Python starterbot
# framework than that used by the Halite game environment.  This simplifies code in several places.  To accommodate
# this difference, the translation to the indexing system used by the game environment is done automatically by
# the send_frame function when communicating with the Halite game environment.

NORTH, EAST, SOUTH, WEST, STILL = range(5)

def opposite_cardinal(direction):
    "Returns the opposing cardinal direction."
    return (direction + 2) % 4 if direction != STILL else STILL


Site = namedtuple('Site', 'x y owner strength production')

class GameMap:
    def __init__(self, size_string, production_string, map_string=None):
        self.width, self.height = tuple(map(int, size_string.split()))
        self.production = tuple(tuple(map(int, substring)) for substring in grouper(production_string.split(), self.width))
        self.contents = None
        self.get_frame(map_string)
        self.starting_player_count = len(set(site.owner for site in self)) - 1

    def get_frame(self, map_string=None):
        "Updates the map information from the latest frame provided by the Halite game environment."
        if map_string is None:
            map_string = get_string()
        split_string = map_string.split()
        owners = list()
        while len(owners) < self.width * self.height:
            counter = int(split_string.pop(0))
            owner = int(split_string.pop(0))
            owners.extend([owner] * counter)
        assert len(owners) == self.width * self.height
        assert len(split_string) == self.width * self.height
        self.contents = [[Site(x, y, owner, strength, production)
                          for x, (owner, strength, production)
                          in enumerate(zip(owner_row, strength_row, production_row))]
                         for y, (owner_row, strength_row, production_row)
                         in enumerate(zip(grouper(owners, self.width),
                                          grouper(map(int, split_string), self.width),
                                          self.production))]

    def __iter__(self):
        "Allows direct iteration over all sites in the GameMap instance."
        return chain.from_iterable(self.contents)

    def neighbors(self, site, n=1, include_self=False):
        "Iterable over the n-distance neighbors of a given site.  For single-step neighbors, the enumeration index provides the direction associated with the neighbor."
        assert isinstance(include_self, bool)
        assert isinstance(n, int) and n > 0
        if n == 1:
            combos = ((0, -1), (1, 0), (0, 1), (-1, 0), (0, 0))   # NORTH, EAST, SOUTH, WEST, STILL ... matches indices provided by enumerate(game_map.neighbors(site))
        else:
            combos = ((dx, dy) for dy in range(-n, n+1) for dx in range(-n, n+1) if abs(dx) + abs(dy) <= n)
        return (self.contents[(site.y + dy) % self.height][(site.x + dx) % self.width] for dx, dy in combos if include_self or dx or dy)

    def get_target(self, site, direction):
        "Returns a single, one-step neighbor in a given direction."
        dx, dy = ((0, -1), (1, 0), (0, 1), (-1, 0), (0, 0))[direction]
        return self.contents[(site.y + dy) % self.height][(site.x + dx) % self.width]

    def get_distance(self, sq1, sq2):
        "Returns Manhattan distance between two sites."
        dx = min(abs(sq1.x - sq2.x), sq1.x + self.width - sq2.x, sq2.x + self.width - sq1.x)
        dy = min(abs(sq1.y - sq2.y), sq1.y + self.height - sq2.y, sq2.y + self.height - sq1.y)
        return dx + dy

#####################################################################################################################
# Functions for communicating with the Halite game environment (formerly contained in separate module networking.py #
#####################################################################################################################


def send_string(s):
    sys.stdout.write(s)
    sys.stdout.write('\n')
    sys.stdout.flush()


def get_string():
    return sys.stdin.readline().rstrip('\n')


def get_init():
    playerID = int(get_string())
    m = GameMap(get_string(), get_string())
    return playerID, m


def send_init(name):
    send_string(name)


def translate_cardinal(direction):
    "Translate direction constants used by this Python-based bot framework to that used by the official Halite game environment."
    # Cardinal indexing used by this bot framework is
    #~ NORTH = 0, EAST = 1, SOUTH = 2, WEST = 3, STILL = 4
    # Cardinal indexing used by official Halite game environment is
    #~ STILL = 0, NORTH = 1, EAST = 2, SOUTH = 3, WEST = 4
    #~ >>> list(map(lambda x: (x+1) % 5, range(5)))
    #~ [1, 2, 3, 4, 0]
    return (direction + 1) % 5


def send_frame(moves):
    send_string(' '.join(str(site.x) + ' ' + str(site.y) + ' ' + str(translate_cardinal(direction)) for site, direction in moves.items()))

PerimBot.py

# Note: Uses a modified version of @erdman's starter package, also contained in this gist.

import hlt
from hlt import *
import random

myID, game_map = hlt.get_init()

debug = open('debug.log', 'w')

# Locate my site
x_grid, y_grid = 3, 3
x_mod, y_mod = [(site.x % x_grid, site.y % y_grid) for site in game_map if site.owner == myID][0]
def on_grid(site):
    return site.x % x_grid == x_mod or site.y % y_grid == y_mod
threshold, piece_count = 0.99 * len([site for site in game_map if on_grid(site)]), 1
def can_use(site):
    return piece_count > threshold or on_grid(site)

# Get values of all sites on map.
values = {}
for u in game_map:
     values[(u.x, u.y)] = (pow(u.production, 2) + 1) / (u.strength + 1)

hlt.send_init("PerimBot")

while True:
    game_map.get_frame()

    piece_count = len([site for site in game_map if site.owner == myID])

    # Get all the sites we want to target, in order of value.
    perimeter = [site for site in game_map if site.owner != myID and can_use(site) and len([neighbor for neighbor in game_map.neighbors(site) if neighbor.owner == myID]) != 0]
    full_perim = { e: STILL for e in perimeter }
    perimeter.sort(key = lambda s: 1 / values[(s.x, s.y)])
    debug.write('Perimeter is of size ' + str(len(perimeter)) + '\n')

    # Clear moves.
    moves = {}
    
    # Try to route pieces to target sites.
    while len(perimeter) > 0:
        target = perimeter.pop()
        required = target.strength + 1
        route = [[(neighbor, opposite_cardinal(direction)) for direction, neighbor in enumerate(game_map.neighbors(target)) if neighbor.owner == myID]]
        required -= sum([element[0].strength for element in route[-1]])
        max_dist = 3
        while max_dist > 0 and required > 0 and len(route[-1]) > 0:
            new_sites = []
            for element in route[-1]:
                new_sites.extend([(neighbor, direction) for direction, neighbor in enumerate(game_map.neighbors(element[0]))])
            route.append([(neighbor, opposite_cardinal(direction)) for neighbor, direction in new_sites if neighbor.owner == myID and (len(route) < 2 or not neighbor in [element[0] for element in route[-2]])])
            required -= sum([element[0].strength for element in route[-1]])
            max_dist -= 1
        if required <= 0:
            for element in route.pop():
                moves[element[0]] = element[1]
            for stage in route:
                for element in stage:
                    moves[element[0]] = STILL
        else:
            for stage in route:
                for element in stage:
                    moves[element[0]] = STILL

    # Move pieces towards borders:
    route = [full_perim]
    while len(route[-1]) > 0:
        new_sites = []
        prev2 = {}
        if len(route) >= 2: prev2 = route[-2]
        for key in route[-1]:
            new_sites.extend([(neighbor, direction) for direction, neighbor in enumerate(game_map.neighbors(key)) if neighbor.owner == myID and not neighbor in prev2])
        debug.write(str(len(new_sites)) + '\n')
        route.append({ neighbor: opposite_cardinal(direction) for neighbor, direction in new_sites })
    route.pop(0) # Get rid of perimeter
    counter = 3
    for stage in route:
        for key in stage:
            if not key in moves:
                moves[key] = stage[key] if key.strength > 2 * counter or key.strength == 255 else STILL
        counter += 1
    

    hlt.send_frame(moves)