''' @author: olivier.massot, 2019 ''' import heapq import sys import time # TODO: # * find a way to change direction without slowing down if possible # * Try to integer extra steps into the path algo, instead of adding independents paths # * Increase the shooting rate in the second part of the game (no barrels left) # * get_shooting_spots: try to intercept ennemy # * make a difference between moving cost, mines, cannonballs, out of grid and other ships # * Try to temporize when taking barrel, the more the ship can wait the better # * try to cut the road to ennemies when getting barrels # * if an ennemy has more rum that every owned ship: hunt! # Enhancements # * interception trajectories # * paths with extra-steps # * Part 1: Speed up # * Part 2: Increase shooting rate debug = True t0 = time.time() def log(*msg): if debug: print("{} - ".format(str(time.time() - t0)[1:5]), *msg, file=sys.stderr) current_turn = 0 class Queue(): def __init__(self): self.items = [] def __bool__(self): return bool(self.items) def __repr__(self): return str(self.items) def put(self, item, priority): heapq.heappush(self.items, (priority, item)) def fput(self, item, priority): while priority in [p for p, _ in self.items]: priority += 1 self.put(item, priority) def get(self): return heapq.heappop(self.items)[1] @classmethod def merge(cls, *args, reverse=False): q = cls() q.items = list(heapq.merge(*[a.items for a in args], key=lambda x: x[1], reverse=reverse)) return q class InterestQueue(Queue): def __add__(self, other): self.items += other.items return self def put(self, item): heapq.heappush(self.items, item) def get(self): return heapq.heappop(self.items) @classmethod def merge(cls, *args, reverse=False): q = cls() q.items = list(heapq.merge(*[a.items for a in args], reverse=reverse)) return q class ObjectivesQueue(InterestQueue): @classmethod def re_eval(cls, q, pos=None, d=None): new_q = cls() while q: o = q.get() o.eval(pos, d) new_q.put(o) return new_q class Base(): def __repr__(self): return f"<{self.__class__.__name__}: {self.__dict__}>" class BaseObjective(Base): def __init__(self, target): self.target = target self.interest = 0 def __lt__(self, other): return self.interest < other.interest def __repr__(self): return f"<{self.__class__.__name__}: target={self.target.id};int={self.interest})>" def _pre_eval(self, pos = None, d = None): self.distance = Grid.manhattan(pos, self.target.pos) if pos is not None else 0 self.alignment = abs(Grid.diff_directions(Grid.direction_to(*pos, *self.target.pos), d)) if d is not None else 0 def eval(self, pos = None, d = None): self._pre_eval(pos, d) self._compute_interest() def _compute_interest(self): self.interest = 7 * self.distance + 3 * self.alignment class GetBarrel(BaseObjective): def _pre_eval(self, pos = None, d = None): super()._pre_eval(pos, d) self.ennemy_near = any(Grid.manhattan(e.next_pos, self.target.pos) < self.distance for e in grid.ennemy_ships) def _compute_interest(self): self.interest = 6 * self.distance + 9 * self.alignment + 3 * self.target.dispersal + self.target.mine_threat * 2 + 12 * self.ennemy_near if self.distance <= 2 and self.alignment > 1: # dead angle self.interest += 36 class Attack(BaseObjective): def _compute_interest(self): self.interest = 7 * self.distance + 3 * self.alignment + self.target.stock // 4 - 20 * self.target.blocked_since class PathNode(tuple): def __new__(self, x, y, parent=None): n = tuple.__new__(self, (x, y)) n.parent = parent n.cost = 0 n.orientation = 0 return n def __repr__(self): return f"<{self[0]}, {self[1]}, c:{self.cost}, o:{self.orientation}>" class Grid(Base): w = 23 h = 21 _neighbors = {} _next_cell = {} def __init__(self): self.load_entities({}) @classmethod def preload(cls): cls._neighbors = {} for x in range(-1, cls.w + 1): for y in range(-1, cls.h + 1): cls.cache_neighbors(x, y) cls._next_cell = {} for x in range(0, cls.w): for y in range(0, cls.h): cls.cache_next_cell(x, y) for x in range(0, cls.w): for y in range(0, cls.h): Ship.cache_area(x, y) @classmethod def contains(cls, x, y): return 0 <= x < cls.w and 0 <= y < cls.h def __contains__(self, key): return self.contains(*key) def __iter__(self): for item in ((x, y) for x in range(self.w) for y in range(self.h)): yield item # data def load_entities(self, entities): # special: mines too far from ships are not recorded but still exist ghost_mines = [] if hasattr(self, "mines"): for m in self.mines: if not m.id in entities: if all((self.manhattan(m.pos, ship.pos) > 5) for ship in self.owned_ships): m.ghost = True ghost_mines.append(m) self.entities = entities self.index = {} self.ships = [] self.owned_ships = [] self.ennemy_ships = [] self.ships = [] self.barrels = [] self.mines = [] self.cannonballs = [] self.threat = {} for e in list(entities.values()) + ghost_mines: self.index[e.pos] = e type_ = type(e) if type_ is Ship: self.ships.append(e) if e.owned: self.owned_ships.append(e) else: self.ennemy_ships.append(e) elif type_ is Barrel: self.barrels.append(e) elif type_ is Mine: self.mines.append(e) elif type_ is Cannonball: self.cannonballs.append(e) if not e.pos in self.threat or e.countdown < self.threat[e.pos]: self.threat[e.pos] = e.countdown for s in self.owned_ships: s.allies = [other for other in self.owned_ships if other is not s] for s in self.ennemy_ships: s.allies = [other for other in self.ennemy_ships if other is not s] for s in self.ships: s.next_pos_proba(2) self.next_to_mine = {} for m in self.mines: for n in self.neighbors(*m.pos): self.next_to_mine[n] = m self.next_to_barrel = {} for b in self.barrels: for n in self.neighbors(*b.pos): self.next_to_barrel[n] = b self.update_moving_costs() grav_center = self.barrels_gravity_center() for b in self.barrels: b.dispersal = Grid.manhattan(grav_center, b.pos) if grav_center != None else 0 b.mine_threat = any(type(self.at(*c)) is Mine for c in self.neighbors(*b.pos)) for s in self.owned_ships: s._can_move = {c: (s.moving_cost(*c) < 1000) for c in [s.front, s.front_left, s.left, s.front_right, s.right, s.back_left, s.back_right]} s.objectives = ObjectivesQueue() s.ennemies = ObjectivesQueue() for b in self.barrels: obj = GetBarrel(b) obj.eval(s.prow, s.orientation) s.objectives.put(obj) for e in self.ennemy_ships: obj = Attack(e) obj.eval(s.pos, s.orientation) s.ennemies.put(obj) def at(self, x, y): try: return self.index[(x, y)] except KeyError: return None @classmethod def is_border(cls, x, y): return x == -1 or y == -1 or x == cls.w or y == cls.h def collision_at(self, x, y): e = self.at(x, y) return type(e) in [Mine, Ship, Cannonball] or not (x, y) in self.__iter__() def barrels_gravity_center(self): wx, wy, wtotal = 0,0,0 for b in self.barrels: wx += (b.x * b.amount) wy += (b.y * b.amount) wtotal += b.amount return (wx // wtotal, wy // wtotal) if wtotal else None def update_moving_costs(self): base_costs = {} self.collisions = [] for x in range(-1, self.w + 1): for y in range(-1, self.h + 1): base_costs[(x, y)] = 10 # base moving cost for x, y in base_costs: if x in (-1, self.w + 1) or y in (-1, self.h): base_costs[(x, y)] = 1000 # out of the map elif x in (0, self.w - 1) or y in (0, self.h - 1): base_costs[(x, y)] = 15 # borders are a little more expensive for c in self.next_to_mine: base_costs[c] += 30 for m in self.mines: base_costs[m.pos] += 1000 if m.pos in self.threat: if self.threat[m.pos] <= 2: # avoid the area of a mines going to explode for n in self.neighbors(*m.pos): base_costs[n] += 1000 for c in self.cannonballs: if 0 < c.countdown <= 2: base_costs[c.pos] += 1000 for ship in self.ships: ship._moving_costs = {} ship._moving_costs.update(base_costs) for other in self.ships: if other is ship: continue dist = self.manhattan(ship.pos, other.pos) if dist > 6: continue for c in self.zone(other.pos, 3): ship._moving_costs[c] += 25 next_positions = other.next_pos_proba() for c, proba in next_positions[1].items(): if proba >= 20: ship._moving_costs[c] = ship._moving_costs.get(c, 0) + 20 * proba if ship.owned and not other.owned and other.behind in ship._moving_costs: # the other ship could mine ship._moving_costs[other.behind] += 100 def shooting_spot(self, ship, target, current=None): shooting_spots = Queue() target_pos = target.next_pos if type(target) is Ship else target.pos for x, y in self.zone(target_pos, 8): if ship.moving_cost(x, y) > 100: continue if self.manhattan((x, y), target_pos) <= 2: continue interest = 0 # the lower the better if (x, y) == current: interest -= 20 interest += ship.moving_cost(x, y) # avoid cells too close from borders if not 3 < x < (self.w - 3): interest += 50 if not 3 <= y < (self.h - 3): interest += 50 # priorize cells in the current direction diff = abs(Grid.diff_directions(ship.orientation, Grid.direction_to(*ship.prow, x, y))) interest += 10 * abs(diff) # priorize spots at distance 6 from active ship interest += (10 * abs(6 - self.manhattan((x, y), ship.pos))) # priorize spots at distance 6 from targetted ship interest += (10 * abs(6 - self.manhattan((x, y), target.pos))) shooting_spots.put((x, y), interest) return shooting_spots.get() def runaway_spot(self, ship): runaway_spot = Queue() for x, y in iter(self): if ship.moving_cost(x, y) > 100: continue interest = 0 # the lower the better interest += ship.moving_cost(x, y) # avoid cells too close from borders if not 3 < x < (self.w - 3): interest += 70 if not 3 <= y < (self.h - 3): interest += 70 # priorize cells in the current direction diff = abs(Grid.diff_directions(ship.orientation, Grid.direction_to(*ship.prow, x, y))) interest += 20 * abs(diff) # priorize spots at distance 6 from active ship interest += (20 * abs(6 - self.manhattan((x, y), ship.pos))) # max distance from ennemies interest -= (10 * min([Grid.manhattan((x, y), e.next_pos) for e in self.ennemy_ships])) runaway_spot.put((x, y), interest) return runaway_spot.get() # geometrical algorithms @staticmethod def from_cubic(xu, yu, zu): return (zu, int(xu + (zu - (zu & 1)) / 2)) @staticmethod def to_cubic(x, y): zu = x xu = int(y - (x - (x & 1)) / 2) yu = int(-xu - zu) return (xu, yu, zu) @staticmethod def manhattan(from_, to_): xa, ya = from_ xb, yb = to_ return abs(xa - xb) + abs(ya - yb) @classmethod def zone(cls, center, radius): return [(x, y) for x in range(0, cls.w) for y in range(0, cls.h) if cls.manhattan(center, (x, y)) <= radius] @staticmethod def closest(from_, in_): return min(in_, key=lambda x: Grid.manhattan(from_, x.pos)) @staticmethod def directions(y): if y % 2 == 0: return [(1, 0), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1)] else: return [(1, 0), (1,-1), (0,-1), (-1, 0), (0, 1), (1, 1)] @staticmethod def direction_to(x0, y0, x, y): dx, dy = (x - x0), (y - y0) if dx > 0: if dy == 0: return 0 elif dy > 0: return 5 else: return 1 elif dx < 0: if dy == 0: return 3 elif dy > 0: return 4 else: return 2 else: if dy > 0: return 5 if y0 % 2 == 0 else 4 else: return 1 if y0 % 2 == 0 else 2 @staticmethod def add_directions(d1, d2): d = d2 + d1 if d < 0: d += 6 elif d > 5: d -= 6 return d @staticmethod def diff_directions(d1, d2): d = d2 - d1 if d <= -3: d += 6 elif d > 3: d -= 6 return d # @staticmethod # def next_cell(x, y, d, repeat=1): # for _ in range(repeat): # dx, dy = Grid.directions(y)[d] # x, y = x + dx, y + dy # return x, y @staticmethod def symetry(d): return d + 3 if d < 3 else d - 3 @staticmethod def abs_neighbors(x, y): return ((x + dx, y + dy) for dx, dy in Grid.directions(y)) @classmethod def cache_neighbors(cls, xc, yc): cls._neighbors[(xc, yc)] = [(x, y) for x, y in Grid.abs_neighbors(xc, yc) if 0 <= x < cls.w and 0 <= y < cls.h] @classmethod def neighbors(cls, x, y): try: return cls._neighbors[(x, y)] except KeyError: cls.cache_neighbors(x, y) return cls._neighbors[(x, y)] @classmethod def abs_next_cell(cls, x, y, d): dx, dy = Grid.directions(y)[d] return x + dx, y + dy @classmethod def cache_next_cell(cls, x, y): for d, dv in enumerate(Grid.directions(y)): dx, dy = dv cls._next_cell[(x, y, d)] = (x + dx, y + dy) @classmethod def next_cell(cls, x, y, d, repeat=1): for _ in range(repeat): try: x, y = cls._next_cell[(x, y, d)] except KeyError: x, y = cls.abs_next_cell(x, y, d) return x, y def rotate(self, center, coordinates, rotations): if coordinates == [center] or rotations % 6 == 0: return coordinates x0, y0 = center xu0, yu0, zu0 = self.to_cubic(x0, y0) result = [] for x, y in coordinates: xu, yu, zu = self.to_cubic(x, y) dxu, dyu, dzu = xu - xu0, yu - yu0, zu - zu0 for _ in range(rotations): dxu, dyu, dzu = -dzu, -dxu, -dyu xru, yru, zru = dxu + xu0, dyu + yu0, dzu + zu0 xr, yr = self.from_cubic(xru, yru, zru) result.append((xr, yr)) return result # pathfinding def path(self, start, start_d, target, moving_costs={}, inertia=None, incl_start=False, limit=10000): nodes = Queue() break_on, iteration = limit, 0 broken = False effective_start = start origin = PathNode(*effective_start) origin.orientation = start_d if inertia is not None: for _ in range(inertia): effective_start = self.next_cell(*effective_start, start_d) origin = PathNode(*effective_start, origin) origin.orientation = start_d nodes.put(origin, 0) neighbors = [] while nodes: current = nodes.get() if broken or current == target: path = [] previous = current while previous: if previous != start or incl_start: path.insert(0, previous) previous = previous.parent return path, iteration neighbors = self.neighbors(*current) for x, y in neighbors: if (x, y) == current.parent: continue iteration += 1 if break_on > 0 and iteration >= break_on: broken = True moving_cost = moving_costs.get((x, y), 1000) if moving_cost >= 1000: continue d = Grid.direction_to(*current, x, y) if inertia == 0: # special: if started with speed 0, first move will require a speed_up, # making impossible a direction change at first node if current.parent and current.parent == start and d != current.orientation: continue diff = abs(Grid.diff_directions(current.orientation, d)) if diff > 1: # change direction one degree at a time if current == (11,9) and (x, y) == (12,10): log("d") continue area = Ship.get_area(x, y, d)[::2] if diff: inertial_area = Ship.get_area(x, y, current.orientation) area += [inertial_area[0], inertial_area[2]] if any((moving_costs.get(c, 1000) >= 1000 and not Grid.is_border(*c)) for c in area): continue cost = current.cost + moving_cost + diff * 20 if (x, y) == start and inertia == 0 and d == start_d: # prefer to go right at start (if no speed) cost -= 10 priority = cost + 10 * Grid.manhattan((x, y), target) node = PathNode(x, y, current) node.cost = cost node.orientation = d nodes.put(node, priority) return None, iteration class Entity(Base): def __init__(self, ent_id): self.id = int(ent_id) self.x, self.y = 0, 0 self.args = [0,0,0,0] def update(self, x, y, *args): self.x, self.y = int(x), int(y) @property def pos(self): return (self.x, self.y) def __lt__(self, other): # default comparison, used to avoid errors when used with queues and priorities are equals return self.id < other.id class Position(Base): def __init__(self, pos, d, speed, weight=10): self.pos = pos self.d = d self.speed = speed self.weight = weight self.area = Ship.get_area(*self.pos, self.d) class Ship(Entity): MAX_SPEED = 2 SCOPE = 10 SLOW_DOWN = 1 SPEED_UP = 2 TURN_LEFT = 3 TURN_RIGHT = 4 MOVES = [None, SPEED_UP, TURN_LEFT, TURN_RIGHT, SLOW_DOWN] COMMANDS = {SLOW_DOWN: "SLOWER", SPEED_UP: "FASTER", TURN_LEFT: "PORT", TURN_RIGHT: "STARBOARD", None: "NONE"} areas = {} def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) self.x, self.y = 0, 0 self.orientation = 0 self.speed = 0 self.stock = 0 self.owned = 0 self.next_cell = None self.next_pos = None self.last_fire = None self.last_mining = None self.blocked_since = 0 self.same_traject_since = 0 self.last_action = "" self.allies = [] self._moving_costs = {} self.objectives = ObjectivesQueue() self.ennemies = ObjectivesQueue() self.objective = None self.objectives_next = [] self.target_ennemy = None self.path = [] self.distance = 0 self.alignment = 0 def __repr__(self): return f"" @classmethod def abs_area(cls, x, y, d): return [Grid.next_cell(x, y, d), (x, y), Grid.next_cell(x, y, Grid.add_directions(d, 3))] @classmethod def cache_area(cls, x, y): for d in range(3): area = [Grid.next_cell(x, y, d), (x, y), Grid.next_cell(x, y, d + 3)] Ship.areas[(x, y, d)] = area Ship.areas[(x, y, d + 3)] = list(reversed(area)) @classmethod def get_area(cls, x, y, d): try: return list(Ship.areas[(x, y, d)]) except KeyError: return cls.abs_area(x, y, d) def update(self, x, y, *args): previous_state = self.state() previous_traject = self.traject() super().update(x, y) self.orientation, self.speed, self.stock, self.owned = map(int, args) self.objectives = ObjectivesQueue() self.ennemies = ObjectivesQueue() self.objective = None self.objectives_next = [] self.target_ennemy = None self.goto = None self.path = [] self.area = Ship.get_area(self.x, self.y, self.orientation) self.prow, _, self.stern = self.area self.next_cell = self.get_next_cell() self.next_pos = self.get_next_pos() self.next_move = None self.next_area = Ship.get_area(*self.next_pos, self.orientation) self.front = Grid.next_cell(*self.prow, self.orientation) self.front_left = Grid.next_cell(*self.prow, Grid.add_directions(self.orientation, 1)) self.left = Grid.next_cell(*self.prow, Grid.add_directions(self.orientation, 2)) self.front_right = Grid.next_cell(*self.prow, Grid.add_directions(self.orientation, -1)) self.right = Grid.next_cell(*self.prow, Grid.add_directions(self.orientation, -2)) self.back_left = Grid.next_cell(*self.stern, Grid.add_directions(self.orientation, 1)) self.back_right = Grid.next_cell(*self.stern, Grid.add_directions(self.orientation, -1)) self.behind = Grid.next_cell(*self.stern, Grid.add_directions(self.orientation, 3)) self._can_move = {} if self.traject() != previous_traject: self.same_traject_since += 1 else: self.same_traject_since = 0 if self.state() == previous_state: self.blocked_since += 1 else: self.blocked_since = 0 def traject(self): return (self.orientation, self.speed) def state(self): return (self.x, self.y, self.orientation, self.speed) @classmethod def get_pos_in(cls, current, speed, orientation, in_=1): return Grid.next_cell(*current, orientation, repeat=speed * in_) def get_next_pos(self, in_=1): return self.get_pos_in(self.pos, self.speed, self.orientation, in_) def next_pos_proba(self, in_=1): # guess next positions positions = {0: [Position(self.pos, self.orientation, self.speed)]} for i in range(in_): positions[i + 1] = [] for p in positions[i]: pos, d, speed = p.pos, p.d, p.speed # next pos with inertia inertia = Grid.next_cell(*pos, d, repeat=speed) # wait, fire or mine p = Position(inertia, d, speed, 30) if self.moving_cost(*p.pos) >= 1000: p.weight = 10 # turn left p = Position(inertia, Grid.add_directions(d, 1), speed) if not self.moving_cost(*p.pos) >= 1000: positions[i + 1].append(p) # turn right p = Position(inertia, Grid.add_directions(d, -1), speed) if not self.moving_cost(*p.pos) >= 1000: positions[i + 1].append(p) # speed up if speed < self.MAX_SPEED: p = Position(Grid.next_cell(*pos, d, repeat=speed + 1), d, speed + 1) if not self.moving_cost(*p.pos) >= 1000: positions[i + 1].append(p) # slow down if speed > 1: p = Position(Grid.next_cell(*pos, d, repeat=speed - 1), d, speed - 1) if not self.moving_cost(*p.pos) >= 1000: positions[i + 1].append(p) # we voluntary ignore the case where a ship at speed 1 would slow down, # as it is not expected to be a standard behaviour for a ship # agregate proba = {} for i, plst in positions.items(): proba[i] = {} weights = {} total_weight = sum([p.weight for p in plst]) for p in plst: for c in p.area: weights[c] = weights.get(c, 0) + p.weight for c in weights: proba[i][c] = 100 * weights[c] // total_weight return proba def guess_next_positions(self, in_=1): proba = self.next_pos_proba(in_) best = {} for i in proba: best[i] = max(proba[i].items(), key=lambda x: x[1])[0] return best def get_next_cell(self, in_=1): return Grid.next_cell(self.x, self.y, self.orientation, repeat=in_) def in_current_direction(self, x, y): return self.orientation == Grid.direction_to(*self.pos, x, y) def moving_cost(self, x, y): return self._moving_costs.get((x, y), 1000) def can_turn_left(self): return (self._can_move[self.left] or grid.is_border(*self.left)) \ and (self._can_move[self.right] or grid.is_border(*self.right)) \ and (self._can_move[self.back_right] or grid.is_border(*self.back_right)) def can_turn_right(self): return (self._can_move[self.right] or grid.is_border(*self.right)) \ and (self._can_move[self.left] or grid.is_border(*self.left)) \ and (self._can_move[self.back_left] or grid.is_border(*self.back_left)) def can_move_fwd(self): return self._can_move[self.front] and not Grid.is_border(*self.prow) def can_move(self): return self.can_move_fwd() or self.can_turn_left() or self.can_turn_left() def area_after_moving(self, move): new_speed = self.speed new_orientation = self.orientation if move == Ship.SPEED_UP: new_speed += 1 elif move == Ship.SLOW_DOWN: new_speed -= 1 elif move == Ship.TURN_LEFT: new_orientation = Grid.add_directions(self.orientation, 1) elif move == Ship.TURN_RIGHT: new_orientation = Grid.add_directions(self.orientation, -1) new_pos = self.get_next_cell(new_speed) return self.get_area(*new_pos, new_orientation) def plan_next_move(self): blocked = False if self.speed: if any(self.front in (s.area if not s.speed else [s.area[1], s.area[0], s.prow]) for s in grid.ships if s is not self): log("Blocked: speed 0") blocked = True self.speed = 0 if self.path: planned = self._follow_path(self.path) if self.path is None: if self.can_move(): available = {} if self.can_move_fwd(): if self.speed: available[None] = 0 else: available[Ship.SPEED_UP] = 0 if self.can_turn_left(): available[Ship.TURN_LEFT] = 0 if self.can_turn_right(): available[Ship.TURN_RIGHT] = 0 for m in available: new_area = self.area_after_moving(m) available[m] = abs(Grid.diff_directions(self.orientation, Grid.direction_to(*new_area[1], *self.goto))) + \ (2 if self.moving_cost(*new_area[1]) > 10 else 0) planned = min(available.items(), key=lambda x: x[1])[0] log(f"(!) broken: automove ({Ship.COMMANDS[planned]})") else: log(f"(!) broken: can not move") planned = None elif not self.path: return False next_move = None available_moves = [planned] + [m for m in Ship.MOVES if m != planned] risk = Queue() for move in available_moves: new_area = self.area_after_moving(move) # takes inertia in account if move == Ship.SPEED_UP or self.speed and move == None: for c in self.get_area(*Grid.next_cell(*new_area[1], self.orientation, self.speed + int(move == Ship.SPEED_UP)), self.orientation): if not c in new_area: new_area.append(c) r = 0 for i, c in enumerate(new_area): mc = self.moving_cost(*c) if mc >= 1000 and (c in grid or i == 1): # special: extra-grid cells are not consider as collisions since a part of the ship can go there countdown = grid.threat.get(c, 0) if countdown > 1 and mc < 2000: # cannonball will hit there after next turn r += 100 else: if blocked and move in (Ship.SLOW_DOWN, None, Ship.SPEED_UP): r = 1000 if i == 1: # the center of the ship is threaten r += 500 else: r += 250 if not r: if move == planned: r = -1 elif self.speed <= 1 and move == Ship.SLOW_DOWN: r = 50 # we don't want to slow down except there is a danger else: # distance from the prow to the current objective r = abs(Grid.diff_directions(self.orientation, Grid.direction_to(*new_area[1], *self.goto))) r += (2 if self.moving_cost(*new_area[1]) > 10 else 0) risk.fput(move, r) if r >= 100: log(f"/!\ Danger: planned move <{Ship.COMMANDS[move]}> could lead to collision (risk={r}, area={new_area})") elif r < 0: next_move = move log(f"Safe move: {Ship.COMMANDS[move]}") break else: log(f"Available move <{Ship.COMMANDS[move]}> (risk={r}, area={new_area})") else: try: next_move = risk.get() log(f"* Go to the less risky: {Ship.COMMANDS[next_move]}") except IndexError: next_move = planned log(f"* No collision-free move was found, go to the initial one: {Ship.COMMANDS[next_move]}") self.next_move = next_move self.next_area = new_area return True def _follow_path(self, path): # flags represent direction changes or end of the path last_flag = len(path) - 1 next_flag = next((i for i, n in enumerate(path) if n.orientation != self.orientation), last_flag) afternext_flag = next((i for i, n in enumerate(path[next_flag:]) if n.orientation != path[next_flag].orientation), last_flag) if not self.speed: diff = Grid.diff_directions(self.orientation, path[0].orientation) if diff > 0 and self.last_action == "STARBOARD" or diff < 0 and self.last_action == "PORT": # special: avoid the starting hesitation return Ship.SPEED_UP if diff and next_flag == 0: # start, with a direction change if diff > 0: return Ship.TURN_LEFT elif diff < 0: return Ship.TURN_RIGHT # start straight else: return Ship.SPEED_UP elif self.speed == self.MAX_SPEED: if next_flag <= self.speed: if afternext_flag >= (next_flag + 2): # there is at least one straight cell after this drift # drift diff = Grid.diff_directions(self.orientation, path[next_flag].orientation) if diff > 0: return Ship.TURN_LEFT elif diff < 0: return Ship.TURN_RIGHT else: return Ship.SLOW_DOWN if next_flag <= self.speed + 1: # next direction change or target will be passed at current speed return Ship.SLOW_DOWN elif self.speed == 1: if next_flag <= 1: diff = Grid.diff_directions(self.orientation, path[next_flag].orientation) if diff > 0: return Ship.TURN_LEFT elif diff < 0: return Ship.TURN_RIGHT elif next_flag >= 4: return Ship.SPEED_UP return None def move(self): if self.next_move == Ship.SPEED_UP: self.speed_up() elif self.next_move == Ship.SLOW_DOWN: self.slow_down() elif self.next_move == Ship.TURN_LEFT: self.turn_left() elif self.next_move == Ship.TURN_RIGHT: self.turn_right() else: return False return True def fire_at_will(self, *args, **kwargs): return self._fire_at_will(*args, **kwargs) def _fire_at_will(self): if not self.can_fire(): return False avoid = [] for ship in grid.owned_ships: avoid += ship.next_area barrels = [b.pos for b in grid.barrels] for bpos in barrels: if any(Grid.manhattan(ship.pos, bpos) <= Grid.manhattan(e.pos, bpos) for ship in grid.owned_ships for e in grid.ennemy_ships): avoid.append(bpos) for m in grid.mines: if any((Grid.manhattan(s.next_pos, m.pos) <= 2 or \ abs(Grid.diff_directions(self.orientation, Grid.direction_to(*s.next_pos, *m.pos))) <= 1)\ for s in grid.owned_ships): avoid.append(m.pos) all_shots = {} for target in grid.ennemy_ships: next_positions = target.next_pos_proba(4) # include avoid, mines, barrels, and other ennemies for t in next_positions: probas = next_positions[t] mines_next = {} for c, proba in probas.items(): if c in grid.next_to_mine: mpos = grid.next_to_mine[c].pos mines_next[mpos] = mines_next.get(mpos, 1) + proba probas.update(mines_next) for c in probas: if c in barrels: probas[c] *= 2 for t, probas in next_positions.items(): shots = sorted(probas.items(), key=lambda x: x[1], reverse=True) for c, proba in shots: if c in avoid: continue if proba < 20: continue dist = Grid.manhattan(self.prow, c) if dist > self.SCOPE: continue # time for the cannonball to reach this pos (including fire turn) delay = 1 + round(dist / 3) if delay != t: continue if not c in all_shots: all_shots[c] = (proba - t) else: all_shots[c] += (proba - t) if all_shots: best_shot = max(all_shots.items(), key=lambda x: x[1])[0] log(f"[x] precise shoot: pos={best_shot}") ship.fire(*best_shot) return True return False def can_mine(self): return self.last_mining is None or (current_turn - self.last_mining) >= 4 def can_fire(self): return self.last_fire is None or (current_turn - self.last_fire) >= 1 def mine_maybe(self): if self.can_mine(): if not any(Grid.manhattan(self.prow, ally.next_pos) <= 5 for ally in self.allies): self.mine() return True return False # --- Basic commands def _act(self, cmd, *args): self.last_action = cmd output = " ".join([cmd] + [str(a) for a in args]) log(f"ship {self.id}: {output}") print(output) def auto_move(self, x, y): self._act("MOVE", x, y) def speed_up(self): self._act("FASTER") def slow_down(self): self._act("SLOWER") def turn_right(self): self._act("STARBOARD") def turn_left(self): self._act("PORT") def wait(self): self._act("WAIT") def mine(self): self.last_mining = current_turn self._act("MINE") def fire(self, x, y): self.last_fire = current_turn self._act("FIRE", x, y) class Barrel(Entity): def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) self.amount = 0 self.dispersal = 0 self.mine_threat = False self.ennemy_near = False def __repr__(self): return f"" def update(self, x, y, *args): super().update(x, y) self.amount = int(args[0]) class Mine(Entity): def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) self.ghost = False def __repr__(self): return f"" class Cannonball(Entity): def update(self, x, y, *args): super().update(x, y) self.sender, self.countdown = int(args[0]), int(args[1]) entities = {} map_entity = {"SHIP": Ship, "BARREL": Barrel, "MINE": Mine, "CANNONBALL": Cannonball} Grid.preload() grid = Grid() ### *** Main Loop *** while True: seen = [] current_turn += 1 # <--- get input my_ship_count, entity_count = int(input()), int(input()) ent_input = [input().split() for _ in range(entity_count)] # ---> log(f"### TURN {current_turn}") log(">> Load input") # <--- load input previous_ent, entities = grid.entities, {} for e in ent_input: ent_id, ent_type, *data = e ent_id = int(ent_id) entities[ent_id] = grid.entities.get(ent_id, map_entity[ent_type](ent_id)) entities[ent_id].update(*data) grid.load_entities(entities) # ---> # log(f"Owned Ships: {grid.owned_ships}") log(f"Ennemy Ships: {grid.ennemy_ships}") log(f"Barrels: {grid.barrels}") # log(f"Mines: {grid.mines}") log(f"Cannonballs: {grid.cannonballs}") max_it = 9000 // len(grid.owned_ships) ### Acquire log("# Acquiring") # main objective while not all(s.objective for s in grid.owned_ships): try: acquired = sorted([(s, s.objectives.get()) for s in grid.owned_ships if not s.objective], key= lambda x: x[1].interest) for s, o in acquired: if not s.objective and not any(al.objective.target is o.target for al in s.allies if al.objective): s.objective = o except IndexError: break # targetted ennemy for s in grid.owned_ships: s.target_ennemy = s.ennemies.get() ### Plan log("# Planning") for ship in grid.owned_ships: log(f"---- ship {ship.id} ---") log(f"ship: {ship}") it_consumed = 0 if ship.objective: ship.goto = ship.objective.target.pos elif ship.target_ennemy: if all(s.stock < ship.stock for s in grid.ships if not s is ship): log("Best stock: runaway!") ship.goto = grid.runaway_spot(ship) else: ship.goto = grid.shooting_spot(ship, ship.target_ennemy.target, current=ship.goto) else: log("ERROR: No target") continue log(f"goto: {ship.goto}") ship.path, its = grid.path(ship.pos, ship.orientation, ship.goto, moving_costs=ship._moving_costs, inertia=ship.speed, limit=(max_it - it_consumed)) it_consumed += its if ship.objective and ship.path and ship.path[-1] == ship.goto: while ship.objectives and len(ship.path) < 15: pos, d = ship.path[-1], ship.path[-1].orientation ship.objectives = ObjectivesQueue.re_eval(ship.objectives, pos, d) current_obj = ship.objectives.get() ship.objectives_next.append(current_obj) new_path, its = grid.path(pos, d, current_obj.target.pos, moving_costs=ship._moving_costs, limit=(max_it - it_consumed)) it_consumed += its if new_path and new_path[-1] == current_obj.target.pos: ship.path += new_path else: break ship.plan_next_move() log(f"obj: {ship.objective}; next: {ship.objectives_next}") log(f"target: {ship.target_ennemy}") log(f"path: {ship.path}") log(f"next_move: {Ship.COMMANDS[ship.next_move]}") ### Process log("# Processing") for ship in grid.owned_ships: log(f"---- ship {ship.id} ---") if not ship.objective and not ship.target_ennemy: log("No target: wait") ship.wait() if ship.move(): continue # no movement was required, can fire if ship.fire_at_will(): continue # or mine if ship.mine_maybe(): continue log("ERROR: Did not act, wait") ship.wait() # Changelog: # 2019-04-17 # * if no available move, takes the less risky # * add the ennemy_near evaluation to the pre_eval method of GetBarrel and update it # * ignore probas < 20 in the moving cost calc (about ennemy next positions) # * get_shooting_spots: discurage direction changes # * increase shooting_spots distance from 5 to 7 # * fire on mines, do not shoot mines that are in front of the ship # * increase the weight of a dead angle in GetBarrel.eval() from 18 to 36 <=> the weight of a distance of 6 needed to turn # * mines: increase moving_cost of neighbors if a cannon ball is going to hit the mine # * Improve the _follow_path algo # * anticipate the speed at 0 when blocked # * coeff 20 instead of 10 for the presence probability, making it impassable from 50% instead of 100% # *(disactivated) moving cost takes now in account the order of play of the ships # * increase the max length of the path from 10 to 15 when seeking for next objectives # * minor improvement to automove # * Avoid shooting barrels unless ennemy is nearest # * include distance to ennemy in the eval of the shooting spot # * (disactivated because of below) avoid consecutives direction changes # * path: direction change moving cost changed from 10 to 20 because of the slowing effect # 2019-04-18 # * take in account the inertial_area in path computing when direction change # * improve the esquive algo by priorizing moves in direction of the target # * remove cache on 'next_pos_proba' # * improve the fire_at_will algo # * takes all ennemies in account to find the best shot # 2019-04-19 # * path(): fix the special speed-up-inertia when start whith speed 0 # * fix the grid.threat update # * add a moving cost at the prow of enemy ships to avoid a possible mine