Halite.io Bot. Earlier version submitted to public tournament and this one used for internal Nerdery tournament.

MyBot.py

import operator
import time
from collections import namedtuple
from statistics import stdev, mean

import hlt
from hlt import EAST, NORTH, SOUTH, STILL, WEST, Move, Square

# uses:
# https://github.com/erdman/alt-python3-halite-starter/blob/master/hlt.py

me, game_map = hlt.get_init()
botname = 'scarpent'

LOGGING = False
DEBUG = False

turn = -1
origin_squares = {}
territory = {}
production = {}
strength = {}
my_squares = []
my_border_squares = []
production_values = []
initial_strength_values = []
initial_basic_values = []
num_opponents = 0
game_squares = 0
territory_avg = 0
territory_stdev = 0

targets = []  # TargetValue

opening_destination = None
opening_destination_point_attackers = []
distance_to_opening_destination = -1
opening_targets = []  # TargetValue

Point = namedtuple('Point', 'x, y')
TargetValue = namedtuple('TargetValue', 'square, value')
FartherNeighbor = namedtuple(
    'FartherNeighbor',
    'xdir, ydir, square, value, distance'
)

directions = {
    NORTH: 'North',
    EAST: 'East ',
    SOUTH: 'South',
    WEST: 'West ',
    STILL: 'Still',
}

MAX_STRENGTH = 255
NOBODY = 0


def log(message):
    if not LOGGING:
        return

    filename = 'bot.log'
    with open('/tmp/' + filename, 'a') as log_file:
        log_file.write('{turn:3}> {message}\n'.format(
            turn=turn,
            message=message
        ))


def init():
    init_start_time = int(round(time.time() * 1000))

    global origin_squares

    log('\nmap: {} x {} ({} squares)'.format(
        game_map.width,
        game_map.height,
        game_map.width * game_map.height
    ))

    origin_squares = {
        square.owner: square for square in game_map if square.owner != NOBODY
    }
    log('origin {id}: ({x}, {y})'.format(
        x=origin_squares[me].x,
        y=origin_squares[me].y,
        id=me
    ))

    global game_squares
    game_squares = game_map.width * game_map.height

    global production_values
    production_values = [square.production for square in game_map]
    global initial_strength_values
    initial_strength_values = [square.strength for square in game_map]
    global initial_basic_values
    initial_basic_values = [
        get_basic_square_value(square) for square in game_map
    ]
    log_stats('production', production_values)
    log_stats('strength', initial_strength_values)
    log_stats('value', initial_basic_values)

    nearest_opponent = 1000
    for player_id, square in origin_squares.items():
        if player_id != me:
            distance = game_map.get_distance(
                origin_squares[me],
                origin_squares[player_id]
            )
            if distance < nearest_opponent:
                nearest_opponent = distance
            log('me to {player} ({x}, {y}) distance: {distance}'.format(
                player=player_id,
                x=square.x,
                y=square.y,
                distance=distance
            ))

    global opening_targets
    opening_targets = []

    source_square = origin_squares[me]

    if len(origin_squares) > 4 and game_squares > 1200:
        n = 4  # play it conservative for nerdery finale
    elif len(origin_squares) > 4:
        n = 5
    else:
        n = 6

    opening_neighbors = get_spiral_neighborhood(origin_squares[me], n=n)

    opening_neighbors.sort(key=lambda x: x.distance)
    opening_neighbors.sort(key=lambda x: x.square.production, reverse=True)

    for opening_neighbor in opening_neighbors:
        opening_targets.append(TargetValue(
            opening_neighbor.square,
            opening_neighbor.value
        ))
        if len(opening_targets) > 50:
            break

    global opening_destination
    opening_destination = opening_targets[0]
    global distance_to_opening_destination
    distance_to_opening_destination = game_map.get_distance(
        origin_squares[me],
        opening_destination.square
    )
    log('opening destination (from origin): {dest}'.format(
        dest=get_farther_neighbor_info(source_square, opening_neighbors[0])
    ))

    log('init time: {}ms\n'.format(
        int(round(time.time() * 1000)) - init_start_time
    ))

    hlt.send_init(botname)


def get_basic_square_value(square):
    if square.strength:
        return square.production / square.strength
    else:
        return square.production


def get_overkill_square_value(square):
    if square.owner == NOBODY and square.strength > 0:
        return square.production / square.strength
    else:
        # return total potential damage caused by overkill
        # when attacking this square
        return sum(
            neighbor.strength for neighbor in game_map.neighbors(square)
            if neighbor.owner not in (me, NOBODY)
        )


def get_target_total_value(square, n=1):
    target_value = 0

    middle_game_aggression = False
    if num_opponents == 1:
        if game_squares < 1000 and turn > 110:
            middle_game_aggression = True
        elif turn > 150:
            middle_game_aggression = True

    for block in game_map.neighbors(square, n=n, include_self=True):
        if block.owner != me:
            target_value += get_basic_square_value(block)

            if block.owner == NOBODY:
                target_value += get_basic_square_value(block)
            else:
                if opening_destination:
                    enemy_factor = 1
                elif middle_game_aggression:
                    enemy_factor = 1.4
                else:  # be a bit more aggressive after opening
                    enemy_factor = 1.2

                target_value += (get_basic_square_value(block) * enemy_factor)

    return target_value


def get_spiral_neighborhood(center, n=6):
    neighbors = []
    square = center
    for n in range(1, (n * 2) + 1):
        if n % 2:
            square = add_to_spiral(neighbors, center, square, EAST)
            for i in range(n):
                square = add_to_spiral(neighbors, center, square, SOUTH)
            for i in range(n):
                square = add_to_spiral(neighbors, center, square, WEST)
        else:
            square = add_to_spiral(neighbors, center, square, WEST)
            for i in range(n):
                square = add_to_spiral(neighbors, center, square, NORTH)
            for i in range(n):
                square = add_to_spiral(neighbors, center, square, EAST)

    return neighbors


def add_to_spiral(neighbors, center_square, source_square, direction):
    target_square = game_map.get_target(source_square, direction)
    if target_square != me:
        xdir, ydir = get_direction(source_square, target_square)
        neighbors.append(FartherNeighbor(
            xdir=xdir,
            ydir=ydir,
            square=target_square,
            value=get_basic_square_value(target_square),
            distance=game_map.get_distance(center_square, target_square)
        ))
    return target_square


def refresh_opening_targets():
    global opening_destination

    if not opening_destination:
        return

    my_points = [Point(square.x, square.y) for square in my_squares]

    opening_destination_point = Point(
        opening_destination.square.x,
        opening_destination.square.y
    )

    if opening_destination_point in my_points:
        log('reached opening dest {} num my squares ({}) INIT'.format(
            get_point_string(opening_destination_point),
            len(my_squares)
        ))

        # related to init() values for opening spiral neighborhood "n"
        if len(origin_squares) > 4 and game_squares > 1200:
            my_squares_factor = 50
        elif len(origin_squares) > 4:
            my_squares_factor = 35
        else:
            my_squares_factor = 20

        if opening_targets and (len(my_squares) < my_squares_factor):
            for target in opening_targets:
                if Point(target.square.x, target.square.y) not in my_points:
                    log('new opening dest: {} (INIT)'.format(target.square))
                    opening_destination = target
                    global distance_to_opening_destination
                    distance_to_opening_destination = 7
                    return

        opening_destination = None


def get_farther_neighbor_info(source_square, target: FartherNeighbor):
    return(
        '{point_pair} prod {production} '
        'strength {strength} value {value:.2f} dist {distance}'.format(
            point_pair=get_point_pair_string(source_square, target.square),
            production=target.square.production,
            strength=target.square.strength,
            value=target.value,
            distance=target.distance
        )
    )


def get_point_pair_string(source_square, target_square):
    return '{source} -> {target}'.format(
        source=get_point_string(source_square),
        target=get_point_string(target_square)
    )


# can be square or Point
def get_point_string(coordinate):
    return '({x:2d}, {y:2d})'.format(x=coordinate.x, y=coordinate.y)


def set_targets():
    global targets
    targets = []

    temp_targets = [
        TargetValue(square, get_target_total_value(square, n=2))
        for square in game_map if square.owner != me
    ]

    temp_targets.sort(key=lambda x: x.value, reverse=True)

    if len(my_squares) < 20:
        num_targets = 10
    elif len(my_squares) < 30:
        num_targets = 20
    elif len(my_squares) < 40:
        num_targets = 40
    elif len(my_squares) < 50:
        num_targets = 50
    elif len(my_squares) < 60:
        num_targets = 60
    elif len(temp_targets) < 200:
        num_targets = len(temp_targets) // 2
    else:
        num_targets = 100

    horizon = 6

    for target in temp_targets:
        for owned in my_border_squares:
            if game_map.get_distance(target.square, owned) < horizon:
                targets.append(target)
                break

        if len(targets) > num_targets:
            break

    if DEBUG:
        for idx, target in enumerate(targets):
            log('DEBUG top targets {rank}: ({x},{y}) value {value:.2f}'.format(
                rank=idx,
                x=target.square.x,
                y=target.square.y,
                value=target.value
            ))

    if len(targets) < 1:
        targets.append(temp_targets[:100])

    log('total targets: {}, top targets: {}'.format(
        len(temp_targets),
        len(targets)
    ))


def log_stats(label, values):
    if not LOGGING:
        return

    log(
        '{label:12}: lo {lo:7.2f}   hi {hi:7.2f}   '
        'avg {avg:7.2f} stdev   {stdev:6.2f}'.format(
            label=label,
            lo=min(values),
            hi=max(values),
            avg=mean(values),
            stdev=stdev(values) if len(values) > 1 else 0
        )
    )


def get_direction(source, target):

    # there is also the case where width/height is an even number -
    # you might have a scenario where going north/south or east/west
    # will get you to the target in the same number of steps;
    # to be handled later...

    x = None
    y = None

    if target.x < source.x:
        if abs(target.x - source.x) < game_map.width / 2:
            x = WEST
        else:
            x = EAST
    elif target.x > source.x:
        if abs(target.x - source.x) < game_map.width / 2:
            x = EAST
        else:
            x = WEST

    if target.y < source.y:
        if abs(target.y - source.y) < game_map.height / 2:
            y = NORTH
        else:
            y = SOUTH
    elif target.y > source.y:
        if abs(target.y - source.y) < game_map.height / 2:
            y = SOUTH
        else:
            y = NORTH

    return x, y


def log_move_to_destination(square, destination, xdir, ydir, chosen):
    if not LOGGING or not DEBUG:
        return

    log(
        'DEBUG move to dest, ({source_owner}: {source_x},{source_y}) -> '
        '({target_owner}: {target_x},{target_y}) distance: {distance} '
        'direction: {y} {x} chosen: {chosen}'.format(
            source_owner=square.owner,
            source_x=square.x,
            source_y=square.y,
            target_owner=destination.owner,
            target_x=destination.x,
            target_y=destination.y,
            distance=game_map.get_distance(square, destination),
            y=directions[ydir] if ydir is not None else '',
            x=directions[xdir] if xdir is not None else '',
            chosen=directions[chosen]
        )
    )


def move_toward_destination(square: Square, destination: Square):

    xdir, ydir = get_direction(square, destination)

    production_factor = 5 * square.production

    x_target = None
    y_target = None

    x_combined_strength = -1
    y_combined_strength = -1

    if xdir is not None:
        x_target = game_map.get_target(square, xdir)
        if x_target.owner == me:
            if (square.strength == MAX_STRENGTH
                    or square.strength > production_factor):
                x_combined_strength = square.strength + x_target.strength

    if ydir is not None:
        y_target = game_map.get_target(square, ydir)
        if y_target.owner == me:
            if (square.strength == MAX_STRENGTH
                    or square.strength > production_factor):
                y_combined_strength = square.strength + y_target.strength

    if x_combined_strength > -1 and y_combined_strength > -1:
        if (x_combined_strength < y_combined_strength
                and opening_destination is None):
            log_move_to_destination(square, destination, xdir, ydir, xdir)
            return Move(square, xdir)
        else:
            log_move_to_destination(square, destination, xdir, ydir, ydir)
            return Move(square, ydir)
    elif x_combined_strength > -1:
        log_move_to_destination(square, destination, xdir, ydir, xdir)
        return Move(square, xdir)
    elif y_combined_strength > -1:
        log_move_to_destination(square, destination, xdir, ydir, ydir)
        return Move(square, ydir)

    # we'll prefer path over own territory
    if (
        (x_target is not None and x_target.owner == me)
            or (y_target is not None and y_target.owner == me)
    ):
        log_move_to_destination(square, destination, xdir, ydir, STILL)
        return Move(square, STILL)  # wait for more strength

    x_target_strength = -1
    y_target_strength = -1

    if x_target is not None:
        if square.strength > x_target.strength:
            x_target_strength = x_target.strength

    if y_target is not None:
        if square.strength > y_target.strength:
            y_target_strength = y_target.strength

    if x_target_strength > -1 and y_target_strength > -1:
        if x_target_strength < y_target_strength:
            log_move_to_destination(square, destination, xdir, ydir, xdir)
            return Move(square, xdir)
        else:
            log_move_to_destination(square, destination, xdir, ydir, ydir)
            return Move(square, ydir)
    elif x_target_strength > -1:
        log_move_to_destination(square, destination, xdir, ydir, xdir)
        return Move(square, xdir)
    elif y_target_strength > -1:
        log_move_to_destination(square, destination, xdir, ydir, ydir)
        return Move(square, ydir)

    log_move_to_destination(square, destination, xdir, ydir, STILL)
    return Move(square, STILL)


def get_opening_target(square):
    if opening_destination and opening_destination_point_attackers:
        if Point(square.x, square.y) in opening_destination_point_attackers:
            return opening_destination.square


def get_move(square):

    target = None
    if opening_destination:
        target = get_opening_target(square)

    if opening_destination is None or target is None:
        target, direction = max(
            (
                (neighbor, direction) for direction, neighbor in enumerate(
                    game_map.neighbors(square)
                )
                if neighbor.owner != me
            ),
            default=(None, None),
            key=lambda t: get_overkill_square_value(t[0])
        )
        if target is not None and target.strength < square.strength:
            return Move(square, direction)
        elif square.strength < 5 * square.production or square.strength == 0:
            return Move(square, STILL)

        # find nearest best target value
        target = None
        target_distance = 1000
        for idx, possible in enumerate(targets):
            distance = game_map.get_distance(square, possible.square)
            if distance < target_distance:
                target = possible.square
                target_distance = distance

        if DEBUG:
            log(
                'DEBUG selected top target is ({x:2d}, {y:2d}) '
                'for ({xx:2d}, {yy:2d}) dist: {distance}'.format(
                    x=target.x,
                    y=target.y,
                    xx=square.x,
                    yy=square.y,
                    distance=target_distance
                )
            )

    return move_toward_destination(square, target)


def log_time(label, the_time, times_list):

    if not LOGGING:
        return

    if the_time is None:
        the_time = -1

    if len(times_list) < 2:
        log('{label:>14}: {time:4d}ms'.format(
            label=label,
            time=the_time
        ))
    else:
        log(
            '{label:>14}: {time:4d}ms (max: {max:4d} avg: {avg:3d} '
            'stddev: {std:3d})'.format(
                label=label,
                time=the_time,
                max=max(times_list),
                avg=int(mean(times_list)),
                std=int(stdev(times_list))
            )
        )


def get_opening_attacker_factor():
    if distance_to_opening_destination < 4:
        low_attacker_factor = 3
        high_attacker_factor = 2
        high_square_count = 16
    else:
        low_attacker_factor = 4
        high_attacker_factor = 3
        if distance_to_opening_destination < 6:
            high_square_count = 20
        elif distance_to_opening_destination < 8:
            high_square_count = 28
        elif distance_to_opening_destination < 10:
            high_square_count = 34
        else:
            high_square_count = 42

    if len(my_squares) < high_square_count:
        return low_attacker_factor
    else:
        return high_attacker_factor


init()
turn_times = []
prelim_times = []
opening_destination_times = []
set_targets_times = []
moves_times = []

while True:
    turn_start_time = int(round(time.time() * 1000))
    prelim_start_time = turn_start_time
    turn += 1
    game_map.get_frame()

    my_squares = []
    my_border_squares = []
    for square in game_map:
        if square.owner == me:
            my_squares.append(square)
            border = any(
                neighbor.owner != me for neighbor in game_map.neighbors(square)
            )
            if border:
                my_border_squares.append(square)

    log('border squares: {}'.format(len(my_border_squares)))

    territory = {}
    production = {}
    strength = {}
    for square in game_map:
        territory[square.owner] = territory.get(square.owner, 0) + 1
        production[square.owner] = (production.get(square.owner, 0)
                                    + square.production)
        strength[square.owner] = (strength.get(square.owner, 0)
                                  + square.strength)

    sorted_owned = sorted(
        territory.items(),
        key=operator.itemgetter(1),
        reverse=True
    )

    num_opponents = len(territory) - 1  # - me
    if NOBODY in territory:
        num_opponents -= 1  # - nobody
        log(
            '     OPEN: squares {squares:4d}, prod {production:5d}, '
            'strength {strength:6d}'.format(
                squares=territory[NOBODY],
                production=production.get(NOBODY, 0),
                strength=strength.get(NOBODY, 0)
            ))

    territory_values = []
    strength_values = []
    place_counter = 0
    my_place = -1
    for key, value in sorted_owned:
        if key != NOBODY:
            place_counter += 1
            territory_values.append(value)
            strength_values.append(strength[key])
            if key == me:
                my_place = place_counter

            log(
                'player {owner:>2}: squares {squares:4d}, prod {prod:5d}, '
                'strength {strength:6d}'.format(
                    owner=key if key != me else 'me',
                    squares=value,
                    prod=production.get(key, 0),
                    strength=strength.get(key, 0)
                )
            )

    prelim_time = int(round(time.time() * 1000)) - prelim_start_time

    opening_destination_time = None
    if opening_destination:
        opening_destination_start_time = int(round(time.time() * 1000))
        # make sure to do this after my_squares and other things are updated
        refresh_opening_targets()
        opening_destination_point_attackers = []

        if opening_destination is not None and len(my_squares) > 7:
            # find our squares closest to opening destination
            my_farther_squares = []
            for square in my_squares:
                my_farther_squares.append(FartherNeighbor(
                    xdir=None,
                    ydir=None,
                    square=square,
                    value=None,
                    distance=game_map.get_distance(
                        square,
                        opening_destination.square
                    )
                ))

            my_farther_squares.sort(key=lambda x: x.distance)

            index = len(my_farther_squares) // get_opening_attacker_factor()
            for my_farther_square in my_farther_squares[:index]:
                opening_destination_point_attackers.append(
                    Point(
                        my_farther_square.square.x,
                        my_farther_square.square.y
                    )
                )

        opening_destination_time = (
            int(round(time.time() * 1000)) - opening_destination_start_time
        )

    set_targets_start_time = int(round(time.time() * 1000))
    set_targets()
    set_targets_time = (
        int(round(time.time() * 1000)) - set_targets_start_time
    )

    moves_start_time = int(round(time.time() * 1000))
    moves = [get_move(square) for square in game_map if square.owner == me]

    if turn > 100 and my_place >= 3:
        territory_avg = mean(territory_values)
        territory_stdev = stdev(territory_values)
        territory_max = max(territory_values)
        if (territory[me] < territory_avg
                and territory[me] + territory_stdev < territory_max):
            log('defensive mode... (INIT)')
            strength_stdev = stdev(strength_values)
            strength_max = max(strength_values)
            if strength[me] > strength_max - (strength_stdev / 2):
                log('defensive mode COUNTERATTACK! (INIT)')
                moves = [
                    get_move(square) for square in game_map
                    if square.owner == me
                ]
            else:
                moves = [
                    get_move(square) for square in game_map
                    if square.owner == me and square.strength > 100
                ]

    moves_time = int(round(time.time() * 1000)) - moves_start_time
    turn_time = int(round(time.time() * 1000)) - turn_start_time

    if LOGGING:
        if turn > 0:
            turn_times.append(turn_time)
            prelim_times.append(prelim_time)
            if opening_destination_time is not None:
                opening_destination_times.append(opening_destination_time)
            if set_targets_time is not None:
                set_targets_times.append(set_targets_time)
            moves_times.append(moves_time)

        log_time('turn', turn_time, turn_times)
        log_time('prelim', prelim_time, prelim_times)
        log_time(
            'opening dest',
            opening_destination_time,
            opening_destination_times
        )
        log_time('set targets', set_targets_time, set_targets_times)
        log_time('moves', moves_time, moves_times)

    hlt.send_frame(moves)