coreylowman / allyourturtles Goto Github PK

View Code? Open in Web Editor NEW

1.0 3.0 1.0 176 KB

Halite 3 Bot

Python 100.00%

allyourturtles's Introduction

AllYourTurtles bot for Halite III

Was able to make it into the top 10 with this.

Overview

Precompute a bunch of stuff
Compute halite/turn for every ship position pair
Spawn a ship if we are behind opponent in # of ships produced or it would give us positive return
Greedily assign ships to positions
1. once a ship is assigned, reduce the halite/turn of any other assignments to the same position accordingly
Plan dropoffs just based on halite around them, proximity to other dropoffs, and number of ships going there
Plan ships using WHCA* (windowed hierarchical cooperative A* - basically just A* with a time window where reservations matter)

The comments in the code have more details.

Code

Everything is in MyBot.py :X It's commented though, and (at least I think) fairly clean.

Entrypoint: main()

Classes:

Commander is the high level bot and uses all the rest of the classes
IncomeEstimation does value calculation of assignments and ROI calculation
ResourceAllocation assigns ships to goals
PathPlanning plans paths
OpponentModel naively computes a probability of an opponent being at a square

Notable functions:

allyourturtles's People

Contributors

Stargazers

Watchers

Forkers

scottgmcleod

allyourturtles's Issues

only consider top n assignments for each ship

that garuntees every ship will have something

don't assign to positions that are disconnected by enemy ships

build dropoff if turtles are within the radius

create a schedule of dropoffs based on knapsack problem

or even by doing space partitioning every possible way

dropoff discounted by enemies already around

should only make the same amount of ships as opponent

attack when we can get to resulting halite faster than opponent

            amount_gained = -ship.halite_amount

            opponent = gmap[destination].ship
            other_allies = list(me.get_ships())
            other_allies.remove(ship)
            other_opponents = list(opponent_ships)
            other_opponents.remove(opponent)
            if len(other_allies) > 0:
                closest_ally = min(other_allies, key=lambda s: gmap.dist(s.pos, destination))
                ally_dist = gmap.dist(closest_ally.pos, destination)
                if len(other_opponents) == 0:
                    closer_than_enemy = True
                else:
                    closest_enemy = min(other_opponents, key=lambda s: gmap.dist(s.pos, destination))
                    enemy_dist = gmap.dist(closest_enemy.pos, destination)
                    closer_than_enemy = ally_dist < enemy_dist
                if allies_nearby > opponents_nearby and closer_than_enemy:
                    amount_dropped = ship.halite_amount + opponent.halite_amount
                    amount_gained = min(constants.MAX_HALITE - closest_ally.halite_amount, amount_dropped)
                    amount_gained -= amount_dropped - amount_gained
                    turns_to_move += gmap.dist(closest_ally.pos, destination) + 1

protected positions

if a position might be occupied by a enemy ship, but is protected by one of our ships, allow ship to move to it

merge consecutive cells into clusters of 1k halite

time spent mining should also check dropoff hpt

just include halite / turns to drop in return if

don't assign turtle to somewhere blocked by enemy

including dropoffs.

only reserve position if ship can collect all halite

if there more than 1k halite, then should have multiple ships assigned

path planning connected components

connected_components = []
component_by_pos = {p: None for p in OBSTACLES}
unclaimed = positions - OBSTACLES
while len(unclaimed) > 0:
    open_set = {unclaimed.pop()}
    closed_set = set()
    component = len(connected_components)

    while len(open_set) > 0:
        current = open_set.pop()
        closed_set.add(current)
        component_by_pos[current] = component
        unclaimed.discard(current)

        for neighbor in cardinal_neighbors(current):
            if neighbor in OBSTACLES or neighbor in closed_set:
                continue
            open_set.add(neighbor)

    connected_components.append(closed_set)

consider enemy halite nearby

want to be close to enemies if they crash, especially in 4p

def od_a_star(gmap, width, height, starts, goals, halite, max_cost=math.inf, conflicts_by_t=None, illegals_by_t=None):
if not conflicts_by_t:
conflicts_by_t = defaultdict(set)
if not illegals_by_t:
illegals_by_t = defaultdict(set)

max_halite = max(gmap.values())

n = len(starts)
standard = (None,) * n

def actual_position(s, i):
    return s[i + n] if s[i + n] is not None else s[i]

def heuristic(s):
    return sum(2 * dist(actual_position(s, i), goals[i]) for i in range(n))

def neighbors(s, i):
    for position in position_neighbors(s[i], width, height):
        if position in s[n:]:
            continue
        neighbor = list(s)
        neighbor[i + n] = position
        if i == n - 1:
            yield tuple(neighbor[n:]) + standard, 1
        else:
            yield tuple(neighbor), 0

def _reconstruct_path(prev_by_node, current, n):
    total_path = [current[:n]]
    while current in prev_by_node:
        current = prev_by_node[current]
        if current[n:] == standard:
            total_path.append(current[:n])
    return list(reversed(total_path))

closed_set = set()
open_set = set()
g_score = defaultdict(lambda: math.inf)
h_score = defaultdict(lambda: math.inf)
f_score = defaultdict(lambda: math.inf)
c_score = defaultdict(int)
came_from = {}
halite_at = {}
extractions_at = {}
time_at = {}

start = tuple(starts) + standard

open_set.add(start)
g_score[start] = 0
h_score[start] = heuristic(start)
f_score[start] = g_score[start] + h_score[start]
c_score[start] = 0
halite_at[start] = list(halite)
extractions_at[start] = []
time_at[start] = 0

while len(open_set) > 0:
    # TODO break ties by heuristic and then conflicts
    current = min(open_set, key=f_score.get)

    open_set.remove(current)

    if current[n:] == standard:
        closed_set.add(current)
        if current[:n] == goals:
            return _reconstruct_path(came_from, current, n)

    actuals = tuple(actual_position(current, i) for i in range(n))
    t = time_at[current]
    halite_left = list(halite_at[current])
    halite_on_ground = list(gmap[actuals[i]] for i in range(n))
    for pos, _, amt in extractions_at[current]:
        for i in range(n):
            if pos == actuals[i]:
                halite_on_ground[i] -= amt

    agent_i = current.index(None) - n
    raw_move_cost = halite_on_ground[agent_i] / 4
    raw_extracted = halite_on_ground[agent_i] / 10
    move_cost = halite_on_ground[agent_i] / max_halite

    for neighbor, dt in neighbors(current, agent_i):
        if neighbor in closed_set:
            continue

        nt = t + dt
        pos = neighbor[agent_i + n]

        if pos in illegals_by_t[nt]:
            continue

        cost = 0 if current[agent_i] == neighbor[agent_i] else move_cost
        d = cost + 1
        g = g_score[current] + d

        if g > max_cost:
            continue

        if neighbor not in open_set:
            open_set.add(neighbor)
        elif g >= g_score[neighbor]:
            continue

        came_from[neighbor] = current
        g_score[neighbor] = g
        h_score[neighbor] = heuristic(neighbor)
        f_score[neighbor] = g_score[neighbor] + h_score[neighbor]
        time_at[neighbor] = nt
        c_score[neighbor] = c_score[current] + int(pos in conflicts_by_t[nt])

        if current[agent_i] == neighbor[agent_i]:
            extracted = raw_extracted
            halite_left[agent_i] += extracted
            halite_at[neighbor] = halite_left
            extractions_at[neighbor] = extractions_at[current] + [(current[agent_i], nt, extracted)]
        else:
            halite_left[agent_i] -= raw_move_cost
            halite_at[neighbor] = halite_left
            extractions_at[neighbor] = deepcopy(extractions_at[current])