agent_bee_v4_11_3.py

# -*- coding: utf-8 -*-
"""
v4_11_3 <- v4_11_2

* Test halite gradient map again.

590
{'agent_bee_v4_2_1.py': array([27.45762712, 20.50847458, 25.25423729, 26.77966102]),
 'agent_bee_v4_1_1.py': array([29.83050847, 45.08474576, 15.59322034,  9.49152542]),
 'agent_bee_v4_11_3.py': array([42.37288136, 22.71186441, 14.06779661, 20.84745763]),
 'agent_tom_v1_0_0.py': array([ 0.33898305, 11.69491525, 45.08474576, 42.88135593])}
"""

import random
import timeit
import logging
from collections import Counter, defaultdict
from enum import Enum, auto

import networkx as nx
import numpy as np
import scipy.optimize
from kaggle_environments.envs.halite.helpers import *

logging.basicConfig(level=logging.INFO)
logger = logging.getLogger(__name__)


# Mute print.
def print(*args, **kwargs):
  pass


MIN_WEIGHT = -99999

BEGINNING_PHRASE_END_STEP = 60
CLOSING_PHRASE_STEP = 300
NEAR_ENDING_PHRASE_STEP = 365

# If my halite is less than this, do not build ship or shipyard anymore.
MIN_HALITE_TO_BUILD_SHIPYARD = 1000
MIN_HALITE_TO_BUILD_SHIP = 1000

# Controls the number of ships.
MAX_SHIP_NUM = 60
MAX_SHIP_CARGO  = 500

# Threshold for attack enemy nearby my shipyard
TIGHT_ENEMY_SHIP_DEFEND_DIST = 5
LOOSE_ENEMY_SHIP_DEFEND_DIST = 7
AVOID_COLLIDE_RATIO = 0.95

SHIPYARD_TIGHT_COVER_DIST = 2
SHIPYARD_LOOSE_COVER_DIST = 6
MIN_BOMB_ENEMY_SHIPYARD_DIST = 4


# Threshod used to send bomb to enemy shipyard

POSSIBLE_MOVES = [
    Point(0, 0),
    Point(0, 1),
    Point(0, -1),
    Point(1, 0),
    Point(-1, 0)
]

# TURNS_OPTIMAL = np.array(
# [[0, 2, 3, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8],
# [0, 1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7],
# [0, 0, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7],
# [0, 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6],
# [0, 0, 0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6],
# [0, 0, 0, 0, 0, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5],
# [0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])

TURNS_OPTIMAL = np.array(
    [[0, 2, 3, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 8],
     [0, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7],
     [0, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7],
     [0, 1, 2, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7],
     [0, 1, 2, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7],
     [0, 1, 2, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7],
     [0, 1, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7],
     [0, 1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7],
     [0, 1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7],
     [0, 1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7],
     [0, 0, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7],
     [0, 0, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7],
     [0, 0, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7],
     [0, 0, 1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6],
     [0, 0, 1, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6],
     [0, 0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6],
     [0, 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6],
     [0, 0, 0, 1, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6],
     [0, 0, 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6],
     [0, 0, 0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6],
     [0, 0, 0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6],
     [0, 0, 0, 0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5],
     [0, 0, 0, 0, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5],
     [0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5],
     [0, 0, 0, 0, 0, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5],
     [0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5],
     [0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4],
     [0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4],
     [0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4],
     [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4],
     [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]])

# cached values
HALITE_RETENSION_BY_DIST = []
HALITE_GROWTH_BY_DIST = []
MANHATTAN_DISTS = None


def get_quadrant(p: Point):
  if p.x > 0 and p.y >= 0:
    return 1
  if p.x <= 0 and p.y > 0:
    return 2
  if p.x < 0 and p.y <= 0:
    return 3
  if p.x >= 0 and p.y < 0:
    return 4
  assert p == Point(0, 0), "not exist quadrant: %s %s" % (p.x, p.y)
  return 0


def optimal_mining_steps(C, H, rt_travel):
  # How many turns should we plan on mining?
  # C=carried halite, H=halite in square, rt_travel=steps to square and back to shipyard
  if C == 0:
    ch = 0
  elif H == 0:
    ch = TURNS_OPTIMAL.shape[0] - 1  # ?
  else:
    # ch = int(np.log(C / H) * 2.5 + 5.5)
    ch = int(np.log(C / H) * 10 + 24)
    ch = min(max(ch, 0), TURNS_OPTIMAL.shape[0] - 1)
  # rt_travel = int(np.clip(rt_travel, 0, TURNS_OPTIMAL.shape[1] - 1))
  rt_travel = int(min(max(rt_travel, 0), TURNS_OPTIMAL.shape[1] - 1))
  return TURNS_OPTIMAL[ch, rt_travel]


class Timer:

  def __init__(self, logging_text=None):
    self._logging_text = logging_text
    self._start = None
    self._end = None
    self._interval = None

  def __enter__(self):
    self._start = timeit.default_timer()
    return self

  def __exit__(self, *args):
    self._end = timeit.default_timer()
    self._interval = self._end - self._start
    if self._logging_text is not None:
      logger.info("Took %.3f seconds for %s", self._interval,
                  self._logging_text)

  @property
  def interval(self):
    return self._interval


def cargo(player):
  """Computes the cargo value for a player."""
  return sum([s.halite for s in player.ships], 0)


def axis_manhattan_dists(a: Point, b: Point, size):

  def dist(x, y):
    v = abs(x - y)
    return min(v, size - v)

  return dist(a.x, b.x), dist(a.y, b.y)


def manhattan_dist(a: Point, b: Point, size):
  if MANHATTAN_DISTS:
    return MANHATTAN_DISTS[a.x * size + a.y][b.x * size + b.y]

  dist_x, dist_y = axis_manhattan_dists(a, b, size)
  return dist_x + dist_y


def has_enemy_ship(cell, me):
  if not cell.ship_id:
    return False

  ship = cell.ship
  return ship.player_id != me.id


def direction_to_ship_action(position, next_position, board_size):
  if position == next_position:
    return None
  if (position + Point(0, 1)) % board_size == next_position:
    return ShipAction.NORTH
  if (position + Point(1, 0)) % board_size == next_position:
    return ShipAction.EAST
  if (position + Point(0, -1)) % board_size == next_position:
    return ShipAction.SOUTH
  if (position + Point(-1, 0)) % board_size == next_position:
    return ShipAction.WEST
  assert False, '%s, %s' % (position, next_position)


def make_move(position, move, board_size):
  return (position + move) % board_size


def get_neighbor_cells(cell, include_self=False):
  neighbor_cells = [cell] if include_self else []
  neighbor_cells.extend([cell.north, cell.south, cell.east, cell.west])
  return neighbor_cells


def init_globals(board):
  growth_factor = board.configuration.regen_rate + 1.0
  retension_rate_rate = 1.0 - board.configuration.collect_rate
  size = board.configuration.size

  global HALITE_GROWTH_BY_DIST
  if not HALITE_GROWTH_BY_DIST:
    HALITE_GROWTH_BY_DIST = [growth_factor**d for d in range(size**2 + 1)]

  global HALITE_RETENSION_BY_DIST
  if not HALITE_RETENSION_BY_DIST:
    HALITE_RETENSION_BY_DIST = [
        retension_rate_rate**d for d in range(size**2 + 1)
    ]

  global MANHATTAN_DISTS
  dists = np.zeros((size**2, size**2), dtype=int)
  with Timer("Init manhattan_dist"):
    for c1 in board.cells.values():
      for c2 in board.cells.values():
        a = c1.position
        b = c2.position
        d = manhattan_dist(a, b, size)
        dists[a.x * size + a.y][b.x * size + b.y] = d
  MANHATTAN_DISTS = dists.tolist()


class ShipTask(Enum):

  UNKNOWN_TASK = auto()

  # Default task, to stay on current cell.
  STAY = auto()

  # Send a ship to a halite.
  GOTO_HALITE = auto()

  # Continuing collecting halite on current cell.
  COLLECT = auto()

  # Finish collecting halite and go back to shipyard.
  RETURN = auto()

  # Send a ship to attack enemy's shipyard.
  ATTACK_SHIPYARD = auto()

  # Attack enemy ship.
  ATTACK_SHIP = auto()

  # Send the first ship to a location to build the initial shipyard.
  INITIAL_SHIPYARD = auto()

  # Make one ship stay on the shipyard to protect it from enemy next to it.
  GUARD_SHIPYARD = auto()


class StrategyBase:
  """Class with board related method."""

  @property
  def me(self):
    return self.board.current_player

  @property
  def c(self):
    return self.board.configuration

  @property
  def step(self):
    return self.board.step

  @property
  def num_ships(self):
    return len(self.me.ship_ids)

  @property
  def sz(self):
    return self.c.size

  @property
  def num_shipyards(self):
    return len(self.me.shipyard_ids)

  @property
  def tight_defend_dist(self):
    # return 4 + max((self.num_ships - 15) // 5, 0)
    return TIGHT_ENEMY_SHIP_DEFEND_DIST

  @property
  def loose_defend_dist(self):
    return LOOSE_ENEMY_SHIP_DEFEND_DIST

  @property
  def home_grown_cell_dist(self):
    return self.tight_defend_dist

  @property
  def is_beginning_phrase(self):
    return self.step <= BEGINNING_PHRASE_END_STEP

  @property
  def is_closing_phrase(self):
    return self.step >= CLOSING_PHRASE_STEP

  @property
  def is_final_phrase(self):
    return self.step >= NEAR_ENDING_PHRASE_STEP

  @property
  def my_idle_ships(self):
    """All ships without task assignment."""
    for ship in self.ships:
      if ship.next_action or ship.has_assignment:
        continue
      yield ship

  @property
  def enemy_shipyards(self):
    for e in self.board.opponents:
      for y in e.shipyards:
        yield y

  @property
  def enemy_ships(self):
    for e in self.board.opponents:
      for s in e.ships:
        yield s

  @staticmethod
  def assign_task(ship, target_cell: Cell, task_type: ShipTask, enemy=None):
    """Add a task to a ship."""
    ship.has_assignment = True
    ship.target_cell = target_cell
    ship.task_type = task_type
    ship.target_cell.is_targetd = True
    ship.target_enemy = enemy

  def manhattan_dist(self, p, q):
    return manhattan_dist(p.position, q.position, self.c.size)

  def nearest_shipyards(self, cell: Cell, shipyards):
    dist_yards = [(self.manhattan_dist(y, cell), y) for y in shipyards]
    dist_yards = sorted(dist_yards, key=lambda x: x[0])
    return dist_yards

  def find_nearest_enemy(self, cell: Cell, enemy_ships):
    """Nearest enemy with least halite."""
    if not isinstance(enemy_ships, list):
      enemy_ships = list(enemy_ships)

    enemy_ships = sorted(enemy_ships,
                         key=lambda s: (self.manhattan_dist(cell, s), s.halite))
    for enemy in enemy_ships:
      return self.manhattan_dist(cell, enemy), enemy
    return 9999, None

  def get_nearest_home_yard(self, cell):
    if not hasattr(cell, 'home_yard_info'):
      cell.nearest_home_yards = self.nearest_shipyards(cell, self.shipyards)
      cell.home_yard_info = (9999, None)
      if cell.nearest_home_yards:
        cell.home_yard_info = cell.nearest_home_yards[0]
    return cell.home_yard_info

  def get_nearest_enemy_yard(self, cell):
    if not hasattr(cell, 'enemy_yard_info'):
      cell.nearest_enemy_yards = self.nearest_shipyards(cell,
                                                        self.enemy_shipyards)
      cell.enemy_yard_info = (9999, None)
      if cell.nearest_enemy_yards:
        cell.enemy_yard_info = cell.nearest_enemy_yards[0]
    return cell.enemy_yard_info

  def update(self, board):
    self.board = board

    # Cache it to eliminate repeated list constructor.
    self.shipyards = self.me.shipyards
    self.ships = self.me.ships

  def execute(self):
    pass

  def __call__(self):
    self.execute()


class FollowerDetector(StrategyBase):

  # >= 2 is considered as following.
  FOLLOW_COUNT = 2

  def __init__(self):
    self.board = None
    self.ship_index = {}  # Ship id => ship
    self.follower = {}  # ship_id => follower
    self.follow_count = Counter()

  def clear(self, ship_id):
    if ship_id not in self.follower:
      return
    del self.follower[ship_id]
    del self.follow_count[ship_id]

  def add(self, ship_id, follower: Ship):
    """Note: follower.halite < ship.halite"""
    prev_follower = self.follower.get(ship_id)
    if prev_follower is None or prev_follower.id != follower.id:
      # New follower.
      self.follow_count[ship_id] = 1
    else:
      # Existing follower.
      self.follow_count[ship_id] += 1

    self.follower[ship_id] = follower

  def update(self, board):
    """Updates follow info with the latest board state."""
    super().update(board)
    latest_ship_index = {s.id: s for s in self.ships}

    # Check last ship positions for follower.
    for ship_id, prev_ship in self.ship_index.items():
      ship = latest_ship_index.get(ship_id)
      if ship is None:
        # The ship has gone.
        self.clear(ship_id)
        continue

      follower = board[prev_ship.position].ship
      if follower is None or follower.halite >= ship.halite:
        # Not a follower.
        self.clear(ship_id)
        continue

      assert follower and follower.halite < ship.halite
      self.add(ship_id, follower)

    # Update with latest ship position.
    self.ship_index = latest_ship_index

  def is_followed(self, ship: Ship):
    """Returns true if the ship of mine is traced by enemy."""
    follower = self.follower.get(ship.id)
    assert not follower or follower.halite < ship.halite

    follow_count = self.follow_count.get(ship.id, 0)
    return follow_count >= self.FOLLOW_COUNT

  def get_follower(self, ship: Ship):
    return self.follower.get(ship.id)


class InitializeFirstShipyard(StrategyBase):

  def __init__(self):
    super().__init__()
    self.first_shipyard_set = False
    self.initial_yard_position = None
    self.initial_ship_position = None

  def estimate_cell_halite(self, candidate_cell):
    expected_halite = 0
    current_halite = 0
    num_halite_cells = 0
    for cell in self.halite_cells:
      # shipyard will destory the halite under it.
      if candidate_cell.position == cell.position:
        continue

      dist = self.manhattan_dist(cell, candidate_cell)
      # TODO(wangfei): try larger value?
      if dist <= self.home_grown_cell_dist and cell.halite > 0:
        expected_halite += self.halite_per_turn(None, cell, dist, dist)
        current_halite += cell.halite
        num_halite_cells += 1
    return expected_halite, current_halite, dist

  def select_initial_cell(self):

    def get_coord_range(v):
      DELTA = 0
      MARGIN = 5
      if v == 5:
        v_min, v_max = MARGIN, 5 + DELTA
      else:
        v_min, v_max = 15 - DELTA, 20 - MARGIN
      return v_min, v_max

    position = self.initial_ship_position
    x_min, x_max = get_coord_range(position.x)
    y_min, y_max = get_coord_range(position.y)
    for cell in self.board.cells.values():
      position = cell.position
      if (x_min <= position.x <= x_max and y_min <= position.y <= y_max):
        yield self.estimate_cell_halite(cell), cell

  def convert_first_shipyard(self):
    """Strategy for convert the first shipyard."""
    assert self.num_ships == 1, self.num_ships

    ship = self.ships[0]
    if not self.initial_ship_position:
      self.initial_ship_position = ship.position

      candidate_cells = list(self.select_initial_cell())
      if candidate_cells:
        candidate_cells.sort(key=lambda x: x[0], reverse=True)
        value, yard_cell = candidate_cells[0]
        self.initial_yard_position = yard_cell.position
        print(
            "Ship initial:", self.initial_ship_position, 'dist=',
            manhattan_dist(self.initial_ship_position,
                           self.initial_yard_position, self.c.size),
            'selected yard position:', self.initial_yard_position, 'value=',
            value)

    self.assign_task(ship, self.board[self.initial_yard_position],
                     ShipTask.INITIAL_SHIPYARD)
    if ship.position == self.initial_yard_position:
      ship.next_action = ShipAction.CONVERT
      self.first_shipyard_set = True


class GradientMap(StrategyBase):

  def __init__(self):
    self.board = None
    self.enemy_gradient = None

  def get_nearby_cells(self, center: Cell, max_dist):
    visited = set()
    nearby_cells = []

    def dfs(c: Cell):
      if c.position in visited:
        return
      visited.add(c.position)

      if self.manhattan_dist(c, center) > max_dist:
        return
      nearby_cells.append(c)
      for next_cell in get_neighbor_cells(c):
        dfs(next_cell)

    dfs(center)
    return nearby_cells

  def compute_gradient(self, center_cells, max_dist, value_func):
    gradient = np.zeros((self.sz, self.sz))
    for center in center_cells:
      for nb_cell in self.get_nearby_cells(center, max_dist):
        p = nb_cell.position
        gradient[p.x, p.y] += value_func(center, nb_cell)
    return gradient

  def get_enemy_gradient(self,
                         center_cell,
                         max_dist=2,
                         broadcast_dist=1,
                         halite=999999):
    """The amount enemy can hurt me."""

    def nearby_enemy_cells():
      for cell in self.get_nearby_cells(center_cell, max_dist):
        if has_enemy_ship(cell, self.me):
          yield cell

    def enemy_cost(dist):
      if dist > broadcast_dist:
        return 0
      return self.c.spawn_cost / (dist or 1)

    def enemy_value(enemy_cell, nb_cell):
      enemy = enemy_cell.ship
      dist = self.manhattan_dist(nb_cell, enemy_cell)
      if enemy.halite < halite:
        return enemy_cost(dist)
      return 0

    return self.compute_gradient(nearby_enemy_cells(), max_dist, enemy_value)

  def get_full_map_enemy_gradient(self, max_dist=4, min_halite=10):

    def all_enemy_cells():
      for enemy in self.enemy_ships:
        yield enemy.cell

    def enemy_value(enemy_cell, nb_cell):
      enemy = enemy_cell.ship
      dist = self.manhattan_dist(nb_cell, enemy_cell)

      h = enemy.halite
      if h <= min_halite:
        h = 0
      h = min(50, h)
      hurt_factor = 1 - (h / 50)
      return hurt_factor * self.c.spawn_cost / (dist + 1)

    return self.compute_gradient(all_enemy_cells(), max_dist, enemy_value)

  def get_halite_gradient_map(self, max_dist=3, min_halite=0,
                              include_center=True, normalize=True):
    def all_halite_cells():
      for cell in self.board.cells.values():
        if cell.halite > min_halite:
          yield cell

    def halite_value(cell, nb_cell):
      dist = self.manhattan_dist(nb_cell, cell)
      # Do not account for the halite of the cell itself.
      if dist == 0 and not include_center:
        return 0
      return cell.halite / (dist + 1)

    g = self.compute_gradient(all_halite_cells(), max_dist, halite_value)
    if normalize:
      g = g / np.max(g)
    return g


class ShipStrategy(InitializeFirstShipyard, StrategyBase):
  """Sends every ships to the nearest cell with halite.

  cell:
    |is_targetd|: prevent more than 1 alley ships choose the same halite.

  ship:
    |next_cell|: next cell location of the ship.
    |has_assignment|: has already has task assignment for this ship.
    |target_cell|: send ship to this cell, may be the same of current cell.
    |task_type|: used to rank ship for moves.
  """

  def __init__(self, simulation=False):
    super().__init__()
    self.board = None
    self.simulation = simulation
    self.follower_detector = FollowerDetector()
    self.gradient_map = GradientMap()
    self.keep_halite_value = 0.0

  def update(self, board):
    """Updates board state at each step."""
    if self.board is None:
      init_globals(board)

    super().update(board)

    self.board = board
    self.cost_halite = 0
    self.halite_ratio = -1
    self.num_home_halite_cells = 0
    self.mean_home_halite = 100

    self.init_halite_cells()

    # Default ship to stay on the same cell without assignment.
    for ship in self.ships:
      ship.has_assignment = False
      ship.target_cell = ship.cell
      ship.next_cell = ship.cell
      ship.task_type = ShipTask.STAY

    self.follower_detector.update(board)
    self.gradient_map.update(board)
    self.halite_gradient = self.gradient_map.get_halite_gradient_map(max_dist=3)

  def init_halite_cells(self):
    HOME_GROWN_CELL_MIN_HALITE = 80
    MAX_STEP_FACTOR = 2

    def home_extend_dist():
      return max(self.num_ships // 10, 2)

    def is_home_grown_cell(cell):
      num_covered = len(cell.convering_shipyards)
      return (num_covered >= 2 or num_covered > 0 and
              cell.convering_shipyards[0][0] <= home_extend_dist())

    def keep_halite_value(cell):

      # Collect larger ones first
      discount_factor = (0.9 if self.is_beginning_phrase else 0.5)
      threshold = self.mean_halite_value * discount_factor

      if self.is_final_phrase:
        return min(30, threshold)

      if is_home_grown_cell(cell):
        ship_factor = self.num_ships / 40

        step_factor = max(self.step - BEGINNING_PHRASE_END_STEP, 0) / 180 * MAX_STEP_FACTOR
        step_factor = min(MAX_STEP_FACTOR, step_factor)

        cover_factor = 0
        if self.num_ships >= 30:
          num_covered = len(cell.convering_shipyards)
          cover_factor += num_covered / 3

        keep_factor = ship_factor + cover_factor + step_factor + 1
        keep_halite = HOME_GROWN_CELL_MIN_HALITE * keep_factor
        self.keep_halite_value = keep_halite
        threshold = max(keep_halite, threshold)

        # Force increase home halite cells with max value
        if NEAR_ENDING_PHRASE_STEP <= self.step <= CLOSING_PHRASE_STEP:
          threshold = 480

        if 250 <= self.step <= 275:
          threshold = 60

        if self.step < 80:
          threshold = 60

      # Do not go into enemy shipyard for halite.
      # enemy_yard_dist, enemy_yard = self.get_nearest_enemy_yard(cell)
      # if (enemy_yard and enemy_yard_dist <= 5):
      # ally_yard_dist, alley_yard = self.get_nearest_home_yard(cell)
      # if (alley_yard and enemy_yard_dist < ally_yard_dist):
      # # if the cell is nearer to the enemy yard.
      # return 1000


      return min(threshold, 499)

    # Init halite cells
    self.halite_cells = []
    for cell in self.board.cells.values():
      cell.is_targetd = False
      cell.is_home_grown_cell = False

      if cell.halite > 0:
        self.halite_cells.append(cell)

    # Initialize covered cells by shipyards.
    for cell in self.halite_cells:
      # Populate cache
      self.get_nearest_home_yard(cell)
      home_yards = [
          x for x in cell.nearest_home_yards
          if x[0] <= self.home_grown_cell_dist
      ]
      cell.convering_shipyards = home_yards

    self.mean_halite_value = 0
    if self.halite_cells:
      halite_values = [c.halite for c in self.halite_cells]
      self.mean_halite_value = np.mean(halite_values)
      self.std_halite_value = np.std(halite_values)

    for cell in self.halite_cells:
      cell.keep_halite_value = keep_halite_value(cell)

  @property
  def me_halite(self):
    return self.me.halite - self.cost_halite

  def collect_game_info(self):

    # Computes neighbour cells mean halite values.
    # TODO: reuse
    def cell_to_yard_dist(cell):
      min_dist, _ = self.get_nearest_home_yard(cell)
      return min_dist

    self.mean_home_halite = 100

    home_cell_halite = []
    for cell in self.halite_cells:
      if cell_to_yard_dist(cell) <= self.home_grown_cell_dist:
        home_cell_halite.append(cell.halite)
        cell.is_home_grown_cell = True

    if home_cell_halite:
      self.mean_home_halite = np.mean(home_cell_halite)

    # Player info
    self.me.total_halite = self.me.halite + cargo(self.me)

    self.max_enemy_halite = -1
    self.max_enemy = None
    self.total_enemy_ship_num = 0
    for p in self.board.opponents:
      p.total_halite = p.halite + cargo(p)
      if p.total_halite >= self.max_enemy_halite:
        self.max_enemy_halite = p.halite
        self.max_enemy = p

      self.total_enemy_ship_num += len(p.ship_ids)

  def bomb_enemy_shipyard(self):
    """Having enough farmers, let's send ghost to enemy shipyard."""

    def estimate_halite(player):
      h = player.halite
      s = len(player.ship_ids) * self.c.spawn_cost
      return h + s

    def max_bomb_dist(enemy_yard):
      # Don't use bomb if ship group is small.
      if self.num_ships <= 16:
        return 0

      # Elimination program.
      if (self.num_ships >= 50 and
          self.num_ships >= self.total_enemy_ship_num + 10):
        return self.sz * 2

      if self.num_ships >= 30:
        return (self.num_ships - 20) // 5 + MIN_BOMB_ENEMY_SHIPYARD_DIST

      # Only attack nearby enemy yard when the player is weak.
      if enemy_yard.player.halite <= self.c.spawn_cost:
        return MIN_BOMB_ENEMY_SHIPYARD_DIST
      return 0

    def is_near_my_shipyard(enemy_yard):
      for yard in self.shipyards:
        dist = self.manhattan_dist(yard, enemy_yard)
        if dist <= max_bomb_dist(enemy_yard):
          return True
      return False

    def non_targeted_enemy_shipyards():
      for y in self.enemy_shipyards:
        if y.cell.is_targetd:
          continue
        if not is_near_my_shipyard(y):
          continue
        yield y

    def select_bomb_ship(enemy_yard):
      min_dist = 99999
      bomb_ship = None
      for ship in self.my_idle_ships:
        # Don't send halite to enemy.
        if ship.halite > 0:
          continue
        dist = self.manhattan_dist(enemy_yard, ship)
        if dist < min_dist:
          min_dist = dist
          bomb_ship = ship
      return min_dist, bomb_ship, enemy_yard

    # Do not send bomb at beginning stage.
    if self.is_beginning_phrase:
      return

    enemy_shipyards = (
        select_bomb_ship(y) for y in non_targeted_enemy_shipyards())
    enemy_shipyards = [x for x in enemy_shipyards if x[1]]
    enemy_shipyards.sort(key=lambda x: x[0])
    for _, bomb_ship, enemy_yard in enemy_shipyards:
      self.assign_task(bomb_ship, enemy_yard.cell, ShipTask.ATTACK_SHIPYARD)

      # One bomb at a time
      break

  def convert_shipyard(self):
    """Builds shipyard to maximize the total number of halite covered within
    |home_grown_cell_dist|."""
    MAX_SHIPYARD_NUM = 20

    MANHATTAN_DIST_RANGE1 = range(7, 8 + 1)
    AXIS_DIST_RANGE1 = range(3, 5 + 1)
    MANHATTAN_DIST_RANGE2 = range(6, 7 + 1)
    AXIS_DIST_RANGE2 = range(1, 6 + 1)
    MAX_SHIP_TO_SHIPYARD_DIST = 8

    HALITE_CELL_PER_SHIP = 2.5
    if self.is_beginning_phrase:
      HALITE_CELL_PER_SHIP = 2.8
    elif self.step >= 230 and self.num_ships >= 23:
      HALITE_CELL_PER_SHIP = 3.2

    MIN_CONVERT_SHIP_NUM = 9

    self.halite_ratio = -1
    # No ship left.
    if not self.num_ships:
      return

    def shipyard_num_by_ship_num():
      # Force build shipyard with 10 ships
      if self.num_ships >= MIN_CONVERT_SHIP_NUM:
        return min(2 + max((self.num_ships - MIN_CONVERT_SHIP_NUM) // 6, 0),
                   MAX_SHIPYARD_NUM)
      return 1

    def shipyard_num_by_halite_ratio():
      num_halite_cells = 0
      for cell in self.halite_cells:
        min_dist, _ = self.get_nearest_home_yard(cell)
        if min_dist <= self.home_grown_cell_dist:
          num_halite_cells += 1

      num_yards = self.num_shipyards
      halite_ratio = num_halite_cells / (self.num_ships or 1)
      self.num_home_halite_cells = num_halite_cells
      self.halite_ratio = halite_ratio
      if (halite_ratio < HALITE_CELL_PER_SHIP
          and self.num_ships >= MIN_CONVERT_SHIP_NUM):
        num_yards += 1
        print('more shipyard: halite cell / ship =', halite_ratio)
      return num_yards

    def max_shipyard_num():
      return max(shipyard_num_by_ship_num(), shipyard_num_by_halite_ratio())

    # Reach max shipyard num.
    if self.num_shipyards >= max_shipyard_num():
      return


    def convert_threshold():
      threshold = MIN_HALITE_TO_BUILD_SHIPYARD

      # Use as much as I can.
      if (self.num_shipyards == 0 or
          self.board.step <= BEGINNING_PHRASE_END_STEP or
          self.num_ships <= MAX_SHIP_NUM):
        threshold = self.c.convert_cost
      return max(self.c.convert_cost, threshold)

    def has_enough_halite(ship):
      return ship.halite + self.me.halite >= convert_threshold()
      # return self.me_halite >= convert_threshold()

    def has_enemy_shipyard_nearby(cell):
      if self.num_ships >= 30:
        return False
      min_dist, min_yard = self.get_nearest_enemy_yard(cell)
      if min_yard and min_dist <= 3:
        return True
      return False

    def has_enemy_nearby(cell):
      return any(
          has_enemy_ship(c, self.me)
          for c in get_neighbor_cells(cell, include_self=True))

    def within_predefined_range(cell):
      if not self.me.shipyard_ids:
        return True

      dist_range = (MANHATTAN_DIST_RANGE1
                    if self.num_shipyards == 1 else MANHATTAN_DIST_RANGE2)

      self.get_nearest_home_yard(cell)  # populate cache
      for dist, yard in cell.nearest_home_yards[:2]:
        if dist not in dist_range:
          return False

        dist_x, dist_y = axis_manhattan_dists(cell.position, yard.position,
                                              self.c.size)
        axis_dist_range = (AXIS_DIST_RANGE1
                           if self.num_shipyards == 1 else AXIS_DIST_RANGE2)
        # That satisfy some axis distance constraints to make me feel safe.
        if dist_x not in axis_dist_range or dist_y not in axis_dist_range:
          return False
      return True

    def compute_convert_score(candidate_cell):
      MAX_COVER_HALITE = 2

      # Maximize the total value of halite when converting ship.
      score = 0
      shipyards = self.shipyards + [candidate_cell
                                   ]  # Fake the cell as shipyard.
      for cell in self.halite_cells:
        if cell.position == candidate_cell.position:
          continue

        covered = 0
        dist_yards = [(self.manhattan_dist(y, cell), y) for y in shipyards]
        dist_yards = sorted(dist_yards, key=lambda x: x[0])
        dist_yards = [(d, y) for (d, y) in dist_yards
                      if d <= SHIPYARD_LOOSE_COVER_DIST]

        if dist_yards:
          score += 0.1

        # Strongly covered cell
        if dist_yards and (len(dist_yards) >= MAX_COVER_HALITE
                           or dist_yards[0][0] <= SHIPYARD_TIGHT_COVER_DIST):
          score += 1
      return score

    def nominate_shipyard_positions():
      for cell in self.board.cells.values():
        # Exclude existing shipyard position (including enemy ones).
        if cell.shipyard_id:
          continue

        # Not convert too near enemy shipyard.
        if has_enemy_shipyard_nearby(cell):
          # print(f"c[{cell.position.x}, {cell.position.y}]: too near enemy")
          continue

        if not within_predefined_range(cell):
          # print(f"c[{cell.position.x}, {cell.position.y}]: not in defined range")
          continue

        # Have a nearby ship.
        dist_to_yard, _ = self.find_nearest_enemy(cell, self.ships)
        if dist_to_yard > MAX_SHIP_TO_SHIPYARD_DIST:
          # print(f"c[{cell.position.x}, {cell.position.y}]: no near by ships")
          continue

        cell.convert_score = compute_convert_score(cell)
        yield cell

    def convert_ship(ship):
      self.cost_halite += (self.c.convert_cost - ship.halite)
      ship.next_action = ShipAction.CONVERT
      ship.has_assignment = True
      ship.cell.is_targetd = True

    def call_for_ship(cell):
      ships = sorted(self.ships, key=lambda s: self.manhattan_dist(s, cell))
      for ship in ships:
        if not has_enough_halite(ship):
          continue

        dist_to_yard = self.manhattan_dist(ship, cell)
        # Annoy nearby enemy.
        min_enemy_to_yard_dist, min_enemy = self.find_nearest_enemy(
            cell, self.enemy_ships)
        if (min_enemy and min_enemy_to_yard_dist <= dist_to_yard and
            min_enemy.halite < ship.halite):
          continue

        if ship.position == cell.position and not has_enemy_nearby(ship.cell):
          convert_ship(ship)
          return True

        if ship.position != cell.position:
          print("Send ship(%s %s) to shipyard position (%s), dist=%s" %
                (ship.id, ship.position, cell.position, dist_to_yard))
          # Let's use GOTO_HALITE for now.
          self.assign_task(ship, cell, ShipTask.INITIAL_SHIPYARD)
          return True

      return False

    # Pre cash money for shipyard conversion when moving towards.
    self.save_for_converting = self.c.convert_cost

    candidate_cells = list(nominate_shipyard_positions())
    print("Convert shipyard: nominate cells count =", len(candidate_cells))
    if not candidate_cells:
      return

    candidate_cells.sort(key=lambda c: c.convert_score, reverse=True)
    for cell in candidate_cells:
      if call_for_ship(cell):
        # One shipyard at a time.
        return

  def compute_ship_moves(self):
    """Computes ship moves to its target.

    Maximize total expected value.
    * prefer the move to the target (distance is shorter)
    * not prefer move into enemy with lower halite (or equal)
    """
    spawn_cost = self.board.configuration.spawn_cost
    convert_cost = self.board.configuration.convert_cost
    collect_rate = self.board.configuration.collect_rate

    def compute_weight(ship, next_position):
      ignore_neighbour_cell_enemy = False
      target_cell = ship.target_cell
      next_cell = self.board[next_position]

      # If a non-followed ship's next move is to alley SPAWNING shipyard, skip
      yard = next_cell.shipyard
      if (yard and yard.player_id == self.me.id and
          yard.next_action == ShipyardAction.SPAWN and
          not hasattr(ship, "follower")):
        return MIN_WEIGHT

      dist = manhattan_dist(next_position, target_cell.position, self.c.size)
      ship_dist = self.manhattan_dist(ship, target_cell)
      wt = ship_dist - dist

      # When attacking, do not stay on halite cell
      if (ship.task_type in (ShipTask.ATTACK_SHIP, ShipTask.ATTACK_SHIPYARD) and
          ship.position == next_position and ship.cell.halite > 0):
        wt -= 2000

      # Do not stay when followed
      if ship.task_type in (ShipTask.RETURN, ) and hasattr(ship, "follower"):
        wt -= 2000

      # Try not move onto home halite cells when possible
      if next_cell.halite > 0 and next_position != target_cell.position:
        halite_gradient = self.halite_gradient[next_position.x, next_position.y]
        wt -= halite_gradient * 0.5

      # If collecting halite
      if ((ship.task_type == ShipTask.GOTO_HALITE or
           ship.task_type == ShipTask.COLLECT) and target_cell.halite > 0):
        ship_to_poi = dist
        poi_to_yard, min_yard = self.get_nearest_home_yard(next_cell)
        if min_yard is None:
          poi_to_yard = 1
        expect_return = self.halite_per_turn(ship, target_cell, ship_to_poi,
                                             poi_to_yard)
        if expect_return < 0:
          return MIN_WEIGHT
        wt += expect_return

      # If go back home
      if ship.task_type == ShipTask.RETURN:
        wt += ship.halite / (dist + 1)
        if hasattr(ship, 'follower'):
          wt += self.c.spawn_cost

      # If goto enemy yard.
      if ship.task_type == ShipTask.ATTACK_SHIPYARD:
        # TODO: use what value as weight for destory enemy yard?
        wt += convert_cost / (dist + 1)

      # Do not step on shipyard
      if (ship.task_type != ShipTask.ATTACK_SHIPYARD and
          next_cell.shipyard_id and next_cell.shipyard.player_id != self.me.id):
        wt -= convert_cost / (dist + 1)

      if ship.task_type == ShipTask.ATTACK_SHIP:
        wt += convert_cost / (dist + 1)
        enemy = ship.target_enemy
        enemy_dist = manhattan_dist(next_position, enemy.position, self.c.size)
        wt += enemy.halite / (enemy_dist + 1)

      if ship.task_type == ShipTask.GUARD_SHIPYARD:
        wt += 1 / (dist + 1)
        # Only ignore enemy when the ship is on the yard.
        if next_position == target_cell.position:
          ignore_neighbour_cell_enemy = True

      def move_away_from_enemy(enemy, ship, side_by_side=True):
        """Collides with enemy if my ship has less halite."""
        if ship.halite < enemy.halite:
          return False
        elif ship.halite > enemy.halite:
          return True

        # enemy.halite == ship.halite
        assert enemy.halite == ship.halite
        if ship.halite > 0:
          return True

        if getattr(enemy, 'within_home_boundary', False):
          avoid_rate = AVOID_COLLIDE_RATIO
        else:
          avoid_rate = 0.99

        return random.random() < avoid_rate

      # If there is an enemy in next_position with lower halite
      if has_enemy_ship(next_cell, self.me):
        # If there is an enemy sitting on its shipyard, collide with him.
        if (ship.task_type == ShipTask.ATTACK_SHIPYARD and
            next_cell.position == target_cell.position):
          pass
        elif move_away_from_enemy(next_cell.ship, ship, side_by_side=True):
          wt -= (spawn_cost + ship.halite)

      # If there is an enemy in neighbor next_position with lower halite
      if not ignore_neighbour_cell_enemy:
        for nb_cell in get_neighbor_cells(next_cell):
          if has_enemy_ship(nb_cell, self.me):
            if move_away_from_enemy(nb_cell.ship, ship, side_by_side=False):
              wt -= (spawn_cost + ship.halite)
      return wt

    # Skip only convert ships.
    ships = [s for s in self.ships if not s.next_action]
    next_positions = {
        make_move(s.position, move, self.c.size)
        for s in ships
        for move in POSSIBLE_MOVES
    }

    # Duplicate position at final stage for more halite.
    if self.step + 7 >= self.c.episode_steps:
      def duplicate_positions(positions):
        for p in positions:
          cell = self.board[p]
          if cell.shipyard_id and cell.shipyard.player_id == self.me.id:
            # Each positions can only accept 4 incoming moves at maximum.
            for _ in range(4):
              yield p
          else:
            yield p

      next_positions = list(duplicate_positions(next_positions))

    def get_position_to_index():
      d = defaultdict(list)
      for i, pos in enumerate(next_positions):
        d[pos].append(i)
      return d

    position_to_index = get_position_to_index()
    C = np.ones((len(ships), len(next_positions))) * MIN_WEIGHT
    for ship_idx, ship in enumerate(ships):
      for move in POSSIBLE_MOVES:
        next_position = make_move(ship.position, move, self.c.size)
        for poi_idx in position_to_index[next_position]:
          poi_idx = position_to_index[next_position]
          C[ship_idx, poi_idx] = compute_weight(ship, next_position)

    rows, cols = scipy.optimize.linear_sum_assignment(C, maximize=True)

    index_to_position = list(next_positions)
    for ship_idx, poi_idx in zip(rows, cols):
      ship = ships[ship_idx]
      next_position = index_to_position[poi_idx]

      ship.next_cell = self.board[next_position]
      ship.next_action = direction_to_ship_action(ship.position, next_position,
                                                  self.c.size)
      # print(ship.id, 'at', ship.position, 'goto', next_position)

    if len(rows) != len(ships):
      matched_ship_ids = set()
      for ship_idx in rows:
        matched_ship_ids.add(ships[ship_idx].id)

      for ship in ships:
        print('ship %s (matchd=%s), at %s, has_assignment=%s, task=%s' %
              (ship.id, ship.id in matched_ship_ids, ship.position,
               ship.has_assignment, ship.task_type))
        for move in POSSIBLE_MOVES:
          next_position = make_move(ship.position, move, self.c.size)
          wt = compute_weight(ship, next_position)
          print('   to %s, wt=%.2f' % (next_position, wt))
    # assert len(rows) == len(ships), "match=%s, ships=%s" % (len(rows),
                                                            # len(ships))

  def spawn_ships(self):
    """Spawns farmer ships if we have enough money and no collision with my own
    ships."""
    SHIP_NUM_HARD_LIMIT = 100

    # When leading, convert as much as possible.
    def max_ship_num():
      by_cash = max(0, (self.me_halite - 3000) // 1000) + MAX_SHIP_NUM

      by_enemy_halite = 0
      if self.me.total_halite > self.max_enemy_halite + 6 * self.c.spawn_cost:
        by_enemy_halite = SHIP_NUM_HARD_LIMIT

      return min(SHIP_NUM_HARD_LIMIT, max(by_cash, by_enemy_halite))

    def spawn(yard):
      self.cost_halite += self.c.spawn_cost
      yard.next_action = ShipyardAction.SPAWN

    def spawn_threshold():
      threshold = self.save_for_converting
      if self.num_ships <= MAX_SHIP_NUM:
        threshold += self.c.spawn_cost
      else:
        threshold += MIN_HALITE_TO_BUILD_SHIP
      return threshold

    # Too many ships.
    mx = max_ship_num()
    if self.num_ships >= max_ship_num():
      return

    # No more ships after ending.
    if self.num_ships >= 3 and self.is_closing_phrase:
      return

    random.shuffle(self.shipyards)
    for shipyard in self.shipyards:
      # Only skip for the case where I have any ship.
      if self.num_ships and self.me_halite < spawn_threshold():
        continue

      spawn(shipyard)

  def final_stage_back_to_shipyard(self):
    MARGIN_STEPS = 7
    MIN_HALITE_TO_YARD = 10

    def ship_and_dist_to_yard():
      for ship in self.my_idle_ships:
        if ship.halite <= MIN_HALITE_TO_YARD:
          continue
        _, yard = self.get_nearest_home_yard(ship.cell)
        if yard:
          dist = self.manhattan_dist(ship, yard)
          yield dist, ship, yard

    if not self.me.shipyard_ids:
      return

    ship_dists = list(ship_and_dist_to_yard())
    if not ship_dists:
      return

    for min_dist, ship, min_dist_yard in ship_dists:
      if self.step + min_dist + MARGIN_STEPS > self.c.episode_steps:
        self.assign_task(ship, min_dist_yard.cell, ShipTask.RETURN)

  def spawn_if_shipyard_in_danger(self):
    """Spawn ship if enemy nearby my shipyard and no ship's next_cell on this
    shipyard."""
    if self.is_final_phrase:
      return

    ship_next_positions = {
        ship.next_cell.position
        for ship in self.ships
        if ship.next_action != ShipAction.CONVERT
    }

    def is_shipyard_in_danger(yard):
      # If there is one of my ship will be the on yard in the next round.
      if yard.position in ship_next_positions:
        return False
      return yard.is_in_danger

    def spawn(yard):
      self.cost_halite += self.c.spawn_cost
      yard.next_action = ShipyardAction.SPAWN

    for yard in self.shipyards:
      # Skip shipyard already has action.
      if yard.next_action:
        continue
      if is_shipyard_in_danger(yard) and self.me_halite >= self.c.spawn_cost:
        print('spawn for danger: y=', yard.position, 'in_danger=',
              is_shipyard_in_danger(yard))
        spawn(yard)

  def print_info(self):

    def mean_cargo(player):
      num_ships = len(player.ship_ids)
      if num_ships == 0:
        return 0
      return int(cargo(player) / num_ships)

    def print_player(player, end='\n'):
      num_ships = len(player.ship_ids)
      num_shipyards = len(player.shipyard_ids)
      print('  p[%s](s=%s, y=%s, h=%s, c=%s, mc=%s)' %
            (player.id, num_ships, num_shipyards, player.halite, cargo(player),
             mean_cargo(player)),
            end=end)

    def print_ship_task_type():
      task = Counter()
      for ship in self.ships:
        task[ship.task_type] += 1
      items = sorted(task.items(), key=lambda x: x[0].name)
      print(", ".join("%s=%s(%.0f%%)" % (k.name, v, v / self.num_ships * 100)
                      for k, v in items))

    print(
        '#%s' % self.step, 'halite(n=%s, mean=%s, std=%s)' %
        (len(self.halite_cells), int(
            self.mean_halite_value), int(self.std_halite_value)),
        'home_halite=(d=%s, cover=%.0f%%, n=%s, m=%s, n/s=%.1f KF=%.1f)' %
        (self.home_grown_cell_dist, self.num_home_halite_cells /
         len(self.halite_cells) * 100, self.num_home_halite_cells,
         int(self.mean_home_halite), self.halite_ratio, self.keep_halite_value))
    print_player(self.me, end=' ')

    enemy = sorted(self.board.opponents, key=lambda x: -(len(x.ship_ids)))[0]
    print_player(enemy, end='\n')
    print_ship_task_type()
    print()

  def halite_per_turn(self,
                      ship,
                      poi: Cell,
                      ship_to_poi,
                      poi_to_yard,
                      min_mine=1):
    """Computes the expected return for mining with optimial steps.

    to mimic the we don't want back home.
    """
    enemy_carry = 0
    halite_left = poi.halite
    if ship and has_enemy_ship(poi, self.me):
      # Dist to move to neighour cell of POI.
      dist = max(0, ship_to_poi - 1)

      # Halite will decrease if there is ship sitting on it.
      halite_left = poi.halite * HALITE_RETENSION_BY_DIST[dist]

      # Give up if my ship has more halite then enemy.
      enemy = poi.ship
      enemy_halite = poi.ship.halite + int(poi.halite - halite_left)
      if ship and ship.halite >= enemy_halite:
        return MIN_WEIGHT

      enemy_carry = enemy.halite

    CARRY_DISCOUNT = 0
    carry = ship and ship.halite or 0

    travel = ship_to_poi + poi_to_yard
    opt_steps = optimal_mining_steps(carry * CARRY_DISCOUNT, poi.halite, travel)
    if opt_steps < min_mine:
      opt_steps = min_mine

    total_halite = (carry
                    + (1 - HALITE_RETENSION_BY_DIST[opt_steps]) * halite_left)
    # Only add enemy_carry if halite_left is large enough
    if halite_left >= 100:
      total_halite += enemy_carry
    return total_halite / (ship_to_poi + opt_steps + poi_to_yard / 7)

  def get_trapped_enemy_ships(self, max_attack_num):
    """A enemy is trapped if there're at least one ship in each quadrant."""
    # Do not attack enemy during ending.
    if self.is_final_phrase:
      return

    adjust = 0
    if self.num_ships >= 25:
      adjust = 1
    MAX_ATTACK_DIST = 4 + adjust

    MIN_ATTACK_QUADRANT_NUM = 3
    # if self.step >= 100:
      # MIN_ATTACK_QUADRANT_NUM -= 1
    if self.num_ships >= 35:
      MIN_ATTACK_QUADRANT_NUM -= 1

    def is_enemy_within_home_boundary(enemy):
      """1. Within distance of 2 of any shipyard
         2. double covered by multiple shipyards.
      """
      covered = 0
      self.get_nearest_home_yard(enemy.cell)  # populate cache.
      for dist, yard in enemy.cell.nearest_home_yards:
        if dist <= SHIPYARD_TIGHT_COVER_DIST + 1:
          return True
        if dist <= SHIPYARD_LOOSE_COVER_DIST:
          covered += 1
      return covered >= 2

    def get_attack_ships(enemy):
      # Extra attack distance for enemy within home boundary.
      max_attack_dist = MAX_ATTACK_DIST
      if enemy.within_home_boundary:
        max_attack_dist = max(5, max_attack_dist + 1)

      for ship in self.my_idle_ships:
        dist = self.manhattan_dist(ship, enemy)
        if dist <= max_attack_dist and ship.halite < enemy.halite:
          yield dist, ship

    def annotate_by_quadrant(dist_ships, enemy):
      """Sort to make sure at least one ship is selected in each quadrant."""
      quadrants = set()
      for dist, ship in dist_ships:
        q = get_quadrant(ship.position - enemy.position)
        q_exist = int(q in quadrants)
        quadrants.add(q)
        yield (q_exist, dist), ship

    for enemy in self.enemy_ships:
      enemy.within_home_boundary = is_enemy_within_home_boundary(enemy)
      dist_ships = get_attack_ships(enemy)
      dist_ships = list(annotate_by_quadrant(dist_ships, enemy))
      dist_ships.sort(key=lambda x: x[0])
      quadrant_num = len({
          get_quadrant(ship.position - enemy.position) for _, ship in dist_ships
      })

      # Reduce quadrant_num for home boundary enemy.
      min_attack_quadrant_num = MIN_ATTACK_QUADRANT_NUM
      # if enemy.within_home_boundary:
      # min_attack_quadrant_num -= 1

      if quadrant_num >= min_attack_quadrant_num:
        enemy.quadrant_num = quadrant_num
        enemy.attack_ships = [ship for _, ship in dist_ships][:max_attack_num]
        yield enemy

  def get_ship_halite_pairs(self, ships, halites):
    CHECK_TRAP_DIST = 5
    TRAP_COST_VALUE = 350
    enemy_gradient = self.gradient_map.get_full_map_enemy_gradient(
        min_halite=10)
    for poi_idx, cell in enumerate(halites):
      for ship_idx, ship in enumerate(ships):
        # Do not go to halite with too many enemy around.
        dist = self.manhattan_dist(ship, cell)
        if dist <= CHECK_TRAP_DIST:
          if enemy_gradient[cell.position.x, cell.position.y] >= TRAP_COST_VALUE:
            continue

        yield ship_idx, poi_idx

  def optimal_assignment(self):
    ATTACK_PER_ENEMY = 6
    SHIPYARD_DUPLICATE_NUM = 5

    def shipyard_duplicate_num():
      if self.is_final_phrase:
        return 1
      return SHIPYARD_DUPLICATE_NUM

    ships = list(self.my_idle_ships)
    halites = [c for c in self.halite_cells if c.halite >= c.keep_halite_value]
    ship_halite_pairs = set(self.get_ship_halite_pairs(ships, halites))

    # Shipyards is duplicated to allow multiple ships having a same target.
    shipyards = [y.cell for y in self.shipyards] * shipyard_duplicate_num()

    # Attack enemy.
    trapped_enemy_ships = list(self.get_trapped_enemy_ships(ATTACK_PER_ENEMY))
    enemy_cells = [e.cell for e in trapped_enemy_ships] * ATTACK_PER_ENEMY
    attack_pairs = {
        (s.id, e.id) for e in trapped_enemy_ships for s in e.attack_ships
    }

    # Guard shipyard.
    offended_shipyards = list(self.get_offended_shipyard())
    offended_cells = [y.cell for y, _ in offended_shipyards]
    guard_paris = {
        (s.id, y.id) for y, ships in offended_shipyards for s in ships
    }

    pois = halites + shipyards + enemy_cells + offended_cells

    def is_halite_column(x):
      return x < len(halites)

    def is_shipyard_column(x):
      return len(halites) <= x < len(halites) + len(shipyards)

    def is_enemy_column(x):
      return (len(halites) + len(shipyards) <= x and
              x < len(halites) + len(shipyards) + len(enemy_cells))

    # Value matrix for ship target assginment
    # * row: ships
    # * column: halite cells + shipyards with duplicates.
    # TODO(wangfei): can we add enemy to this matrix?
    C = np.zeros((len(ships), len(pois)))
    for i, ship in enumerate(ships):
      for j, poi in enumerate(pois):
        # Init distances: from ship to POI and POI to the nearest yard.
        ship_to_poi = manhattan_dist(ship.position, poi.position, self.c.size)
        poi_to_yard, min_yard = self.get_nearest_home_yard(poi)
        if min_yard is None:
          poi_to_yard = 1

        if is_halite_column(j):
          if (i, j) not in ship_halite_pairs:
            v = MIN_WEIGHT
          else:
            # If the target is a halite cell, with enemy considered.
            v = self.halite_per_turn(ship, poi, ship_to_poi, poi_to_yard)
        elif is_shipyard_column(j):
          # If the target is a shipyard.
          if ship_to_poi > 0:
            # v = ship.halite / min(ship_to_poi, 7)
            v = ship.halite / ship_to_poi
          else:
            # The ship is on a shipyard.
            v = 0

          # If have follower, let the followed ship back.
          if hasattr(ship, 'follower'):
            v += self.c.spawn_cost

          # Force send ship home.
          if ship.halite >= MAX_SHIP_CARGO and not self.is_closing_phrase:
            v += 5000
        elif is_enemy_column(j):
          # If attack enemy
          enemy = poi.ship
          v = MIN_WEIGHT  # not exists edge.
          if (ship.id, enemy.id) in attack_pairs:
            v = (self.c.spawn_cost + enemy.halite + enemy.cell.halite) / ship_to_poi
            if getattr(enemy, 'within_home_boundary', False):
              v += 100
        else:
          # If shipyard is offended.
          yard = poi.shipyard
          v = MIN_WEIGHT
          if (ship.id, yard.id) in guard_paris:
            v = (self.c.spawn_cost + self.c.convert_cost +
                 ship.halite) / (ship_to_poi or 1)

            # If selected as guard ship, the followed ship has priority.
            if hasattr(ship, 'follower'):
              v += self.c.spawn_cost

        C[i, j] = v

    rows, cols = scipy.optimize.linear_sum_assignment(C, maximize=True)
    # assert len(rows) == len(ships), "ships=%s, halites=%s" % (len(ships),
    # len(halites))
    for ship_idx, poi_idx in zip(rows, cols):
      ship = ships[ship_idx]
      poi_cell = pois[poi_idx]
      # print('send ship(id=%s, p=%s, h=%s)' % (ship.id, ship.position,
      # ship.halite),
      # 'to poi_cell(p=%s, h=%s)' % (poi_cell.position,
      # poi_cell.halite))
      enemy = None
      if is_halite_column(poi_idx):
        if ship.position == poi_cell.position:
          task_type = ShipTask.COLLECT
        else:
          task_type = ShipTask.GOTO_HALITE
      elif is_shipyard_column(poi_idx):
        task_type = ShipTask.RETURN
      elif is_enemy_column(poi_idx):
        task_type = ShipTask.ATTACK_SHIP
        enemy = poi_cell.ship
      else:
        task_type = ShipTask.GUARD_SHIPYARD
        shipyard = poi_cell.shipyard
        shipyard.is_in_danger = False
        enemy = shipyard.offend_enemy
        # print('guide task: ', ship.position, poi_cell.position,
        # shipyard.offend_enemy.position)

      self.assign_task(ship, poi_cell, task_type, enemy=enemy)

  def get_offended_shipyard(self):
    """Guard shipyard."""

    def shipyard_defend_dist():
      if len(self.me.shipyard_ids) > 1 or self.me_halite >= self.c.spawn_cost:
        return 3
      return 4

    def offend_enemy_ships(yard):
      not_enough_halite_to_spawn = self.me_halite < self.c.spawn_cost
      for enemy in self.enemy_ships:
        if self.manhattan_dist(enemy, yard) > shipyard_defend_dist():
          continue

        # If the enemy has money, then I'll just let it send it for me.
        if not_enough_halite_to_spawn or enemy.halite == 0:
          yield enemy

    def get_defend_ships(yard, enemy, enemy_to_yard_dist):
      for ship in self.my_idle_ships:
        dist_to_yard = self.manhattan_dist(ship, yard)
        if (dist_to_yard < enemy_to_yard_dist or
            (dist_to_yard == enemy_to_yard_dist and
             (enemy.halite > 0 and ship.halite < enemy.halite or
              enemy.halite == 0 and ship.halite == 0))):
          # print('defend enemy(%s) by ship(%s, %s)' % (enemy.position, ship.id, ship.position))
          yield ship

    for yard in self.shipyards:
      yard.is_in_danger = False
      min_enemy_dist, enemy = self.find_nearest_enemy(yard.cell,
                                                      offend_enemy_ships(yard))
      if enemy is None:
        continue
      # No need guard shipyard if enemy has halite (by turn order, spawn comes
      # before collision)
      if yard.next_action == ShipyardAction.SPAWN and enemy.halite > 0:
        continue

      defend_ships = list(get_defend_ships(yard, enemy, min_enemy_dist))
      for ship in defend_ships:
        dist_to_yard = self.manhattan_dist(ship, yard)
        # If my move away is still more near than enemy, not in danger.
        if dist_to_yard + 1 <= min_enemy_dist - 1:
          continue

      yard.is_in_danger = True
      if defend_ships:
        yard.offend_enemy = enemy
        yield yard, defend_ships

  def update_ship_follower(self):
    """If a ship is followed by enemy, send it back home."""
    for ship in self.my_idle_ships:
      if not self.follower_detector.is_followed(ship):
        continue

      _, yard = self.get_nearest_home_yard(ship.cell)
      if not yard:
        continue

      ship.follower = self.follower_detector.get_follower(ship)
      # self.assign_task(ship, yard.cell, ShipTask.RETURN)
      # print('ship(%s) at %s is followed by enemy(%s) at %s by %s times' %
      # (ship.id, ship.position, ship.follower.id, ship.follower.position,
      # self.follower_detector.follow_count[ship.id]))

  def clear_spawn_ship(self):
    """Clear ship spawn for ship to return homeyard with follower."""

    def is_my_shipyard_spawning(cell):
      return (cell.shipyard_id and cell.shipyard.player_id == self.me.id and
              cell.shipyard.next_action == ShipyardAction.SPAWN)

    for ship in self.ships:
      cell = ship.next_cell
      if cell and is_my_shipyard_spawning(cell):
        cell.shipyard.next_action = None

  def convert_trapped_ship_to_shipyard(self):

    def is_ship_trapped(ship):
      enemy_nearby_count = 0
      danger_cell_count = 0
      enemy_gradient = self.gradient_map.get_enemy_gradient(ship.cell,
                                                            halite=ship.halite,
                                                            broadcast_dist=1,
                                                            max_dist=2)
      for cell in get_neighbor_cells(ship.cell):
        if has_enemy_ship(cell, self.me):
          enemy = cell.ship
          if enemy.halite < ship.halite:
            enemy_nearby_count += 1
            continue

        if enemy_gradient[cell.position.x,
                          cell.position.y] >= self.c.spawn_cost:
          danger_cell_count += 1

      return (enemy_nearby_count == 4 or
              (enemy_nearby_count == 3 and danger_cell_count == 1))

    def has_enough_halite(ship):
      return ship.halite + self.me_halite >= self.c.convert_cost

    for ship in self.ships:
      if (ship.halite >= 100 and ship.next_action != ShipAction.CONVERT and
          is_ship_trapped(ship) and has_enough_halite(ship)):
        ship.next_action = ShipAction.CONVERT
        self.cost_halite += (self.c.convert_cost - ship.halite)
        print("Convert ship in danger %s at %s h=%s for trapped." %
              (ship.id, ship.position, ship.halite))

  def execute(self):
    self.save_for_converting = 0
    self.collect_game_info()

    if self.first_shipyard_set:
      self.convert_shipyard()
      self.update_ship_follower()
      self.spawn_ships()

      self.bomb_enemy_shipyard()

      self.final_stage_back_to_shipyard()
      self.optimal_assignment()
    else:
      self.convert_first_shipyard()

    self.compute_ship_moves()
    self.spawn_if_shipyard_in_danger()

    self.clear_spawn_ship()
    self.convert_trapped_ship_to_shipyard()
    if not self.simulation:
      self.print_info()


STRATEGY = ShipStrategy()


@board_agent
def agent(board):
  STRATEGY.update(board)
  STRATEGY.execute()