Deadline24, Interstellar, 86.40

interstellar.cpp

#include "game.h"
#include "geometry.h"
#include <queue>
#include <array>
#include <set>
#include <cstdlib>

constexpr size_t kNone = std::numeric_limits<size_t>::max();
constexpr double kEps = 1e-5;
constexpr size_t kProfitTurnsAfterReset = 10;
constexpr size_t kFinishTurns = 25;

struct MyGame : public Game {
  MyGame(
      int server_id,
      std::string ip,
      int port,
      std::string login,
      std::string pass) :
    Game(server_id, ip, port, login, pass),
    turns_to_end(0) {
  }

  double length_x, length_y;
  int64_t share_price, synergy_bonus, chain_bonus;
  double distance_bonus_linear, distance_bonus_exp;
  int64_t crouding_factor;
  int64_t delay_after_movement;
  double drop_efficiency_coeff, rise_efficiency_coeff;
  int64_t facility_cost, facility_cost_inc, facility_bonus_max, facility_bonus_drop;
  int64_t facility_limit_per_planet, facility_limit_global;
  size_t turn_duration;
  double scale_coeff;

  double cash, score;
  size_t vouchers;

  struct Trader {
    size_t id, planet_id, target_planet_id, turns_busy;
  };
  std::vector<Trader> traders;

  struct Planet {
    size_t id;
    double x, y;
    double local_income;
    size_t shares;
    double efficiency;
    size_t other_shares;
    size_t workers;
    size_t updated;
    size_t facilities;
    bool decreased;
    std::vector<std::pair<size_t, double>> history;
  }; 
  std::vector<Planet> planets;

  double optimal_efficiency_to_leave;
  double optimal_profit_per_move;

  size_t turns_to_update_planets;
  size_t turns_after_reset;
  size_t turns_to_end;
  size_t turns_after_invest;

  void update_world() {
    server << "DESCRIBE_WORLD" << flush;
    CHECK(server.get_response() == 0);
    server >> length_x >> length_y;
    server >> share_price >> synergy_bonus >> chain_bonus;
    server >> distance_bonus_linear >> distance_bonus_exp;
    server >> crouding_factor;
    server >> delay_after_movement;
    server >> drop_efficiency_coeff >> rise_efficiency_coeff;
    server >> facility_cost >> facility_cost_inc >> facility_bonus_max >> facility_bonus_drop;
    server >> facility_limit_per_planet >> facility_limit_global;
    size_t max_commands;
    server >> turn_duration >> max_commands >> scale_coeff;
    server.set_max_commands(max_commands);
  }

  void update_score() {
    server << "GET_SCORE" << flush;
    CHECK(server.get_response() == 0);
    server >> cash >> score >> vouchers;
  }

  void update_traders() {
    server << "GET_TRADERS MYSELF" << flush;
    CHECK(server.get_response() == 0);
    
    size_t cnt;
    server >> cnt;
    traders.clear();
    traders.reserve(cnt);

    auto get_id_with_none = [&]() {
      std::string s;
      server >> s;
      if (s == "None")
        return kNone;
      size_t number = 0;
      for (char c : s) {
        CHECK(isdigit(c));
        number = (10 * number) + (c - '0');
      }
      return number;
    };

    for (size_t i = 0; i < cnt; i++) {
      Trader trader;
      server >> trader.id;
      trader.planet_id = get_id_with_none();
      trader.target_planet_id = get_id_with_none();
      server >> trader.turns_busy;
      traders.push_back(trader);
    }
  
  }

  void update_planets() {
    if (turns_to_update_planets > 0) {
      return;
    }

    server << "GET_PLANETS_BASIC_INFO" << flush;
    CHECK(server.get_response() == 0);
  
    size_t cnt;
    server >> cnt;

    if (planets.empty()) {
      planets.reserve(cnt);
      for (size_t i = 0; i < cnt; i++) {
        Planet planet;
        server >> planet.id >> planet.x >> planet.y >> planet.local_income;
        planet.shares = 0;
        planet.efficiency = 100.0;
        planet.other_shares = 0;
        planet.workers = 0;
        planet.updated = 0;
        planet.decreased = false;
        planet.history.push_back({turns_after_reset, planet.local_income});
        planets.push_back(planet);
      }
    } else {
      for (size_t i = 0; i < cnt; i++) {
        Planet updated_planet;
        server >> updated_planet.id >> updated_planet.x >> updated_planet.y >> updated_planet.local_income;
        bool found = false;
        for (auto& planet : planets) {
          if (planet.id == updated_planet.id) {
            found = true;
            planet.x = updated_planet.x;
            planet.y = updated_planet.y;
            if (updated_planet.local_income < planet.local_income) {
              planet.decreased = true;
            }
            planet.local_income = updated_planet.local_income;
            planet.history.push_back({turns_after_reset, planet.local_income});
          }
        }
        CHECK(found);
      }
    }

    turns_to_update_planets = 10;
  }

  void update_efficiencies() {
    CHECK(!planets.empty());
    server << "GET_EFFICIENCIES MYSELF" << flush;
    CHECK(server.get_response() == 0);
    for (auto& planet : planets) {
      planet.efficiency = 100.0;
    }
    size_t cnt;
    server >> cnt;
    for (size_t i = 0; i < cnt; i++) {
      size_t id;
      double efficiency;
      bool found = false;
      server >> id >> efficiency;
      for (auto& planet : planets) {
        if (planet.id == id) {
          planet.efficiency = efficiency;
          found = true;
        }
      }
      CHECK(found);
    }
  }

  void update_shares() {
    server << "GET_SHARES MYSELF" << flush;
    CHECK(server.get_response() == 0);
    size_t cnt;
    server >> cnt;
    for (size_t i = 0; i < cnt; i++) {
      size_t id;
      size_t shares;
      bool found = false;
      server >> id >> shares;
      for (auto& planet : planets) {
        if (planet.id == id) {
          planet.shares = shares;
          found = true;
        }
      }
      CHECK(found);
    }
  }

  void update_facilities() {
    for (auto& planet : planets) {
      planet.facilities = 0;
    }
    server << "GET_FACILITIES" << flush;
    CHECK(server.get_response() == 0);
    size_t cnt;
    server >> cnt;
    INFO() << "Facilities: " << cnt;
    for (size_t i = 0; i < cnt; i++) {
      size_t planet_id;
      bool found = false;
      server >> planet_id;
      for (auto& planet : planets) {
        if (planet.id == planet_id) {
          ++planet.facilities;
          found = true;
        }
      }
      CHECK(found);
    }
  }

  Planet update_single_planet(size_t id) {
    Planet planet;
    server << "GET_PLANET_DETAILS " << id << flush;
    CHECK(server.get_response() == 0);
    server >> planet.shares >> planet.other_shares >> planet.efficiency >> planet.workers;
    for (size_t i = 0; i < planet.workers; i++) {
      std::string id, dest_id;
      server >> id >> dest_id;
    }
    return planet;
  }

  void reset() override {
    traders.clear();
    planets.clear();
    turns_after_reset = 0;
    turns_after_invest = 0;
    turns_to_update_planets = 0;
    update_world();
    update_score();
    update_traders();
    update_planets();
    update_shares();
    update_facilities();
    recalc_optimals();
    spent_initial_vouchers();
  }

  void recalc_optimals() {
    optimal_profit_per_move = 0.0;

    CHECK(drop_efficiency_coeff > 0.0);
    CHECK(rise_efficiency_coeff > 0.0);
    size_t max_moves_to_stay = 100.0 / drop_efficiency_coeff + 1;
    for (size_t moves_to_stay = delay_after_movement; moves_to_stay <= max_moves_to_stay; moves_to_stay++) {
      double profit = 0.0;
      double scale = 100.0;
      for (size_t move = 0; move < moves_to_stay; move++) {
        profit += scale;
        scale -= drop_efficiency_coeff;
      }
      size_t moves_to_rest = (100 - scale) / rise_efficiency_coeff + 1;

      size_t total_moves = moves_to_stay + moves_to_rest + 1;
      double profit_per_move = profit / total_moves;

      if (profit_per_move > optimal_profit_per_move) {
        optimal_profit_per_move = profit_per_move;
        optimal_efficiency_to_leave = scale + kEps;
      }
    }

    INFO() << "Best efficiency to leave: " << optimal_efficiency_to_leave;
    INFO() << "Best profit per move: " << optimal_profit_per_move;
  }

  void init_round() override {
    bool reseted = false;

    size_t new_turns_to_end = 0;
    server << "TIME_TO_END" << flush;
    CHECK(server.get_response() == 0);
    server >> new_turns_to_end;
    if (new_turns_to_end > turns_to_end) {
      INFO() << "New game, reset";
      reset();
      reseted = true;
    }
    turns_to_end = new_turns_to_end;
    ++turns_after_reset;
    ++turns_after_invest;

    update_planets();
    if (turns_to_update_planets > 0) {
      --turns_to_update_planets;
    }

    update_score();
    update_traders();
    update_efficiencies();
    if (!reseted)
      update_shares();
    update_facilities();
  }

  size_t count_invested_planets() {
    size_t already = 0;
    for (const auto& planet : planets) {
      if (planet.shares > 0) {
        ++already;
      }
    }
    return already;
  }

  void spent_initial_vouchers() {
    CHECK(traders.size() <= planets.size());
    while (vouchers > 0 &&
        server.commands_sent() < server.max_commands() &&
        count_invested_planets() < traders.size()) {
      std::random_shuffle(planets.begin(), planets.end());
      Planet* target_planet = &planets.front();
      for (auto& planet : planets) {
        if (planet.shares == 0) {
          target_planet = &planet;
        }
      }
      if (target_planet->shares == 0) {
        server << "BUY_SHARES " << target_planet->id << " " << 1 << flush;
        CHECK(server.get_response() == 0);
        target_planet->shares++;
        vouchers--;
      }
    }
  }

  double get_planet_score_per_move(Planet planet, size_t add_shares = 0, size_t add_workers = 0, bool with_history = false) {
    double planet_scale = kEps;

    if (planet.updated) {
      size_t total_shares = (add_shares + planet.shares + planet.other_shares);
      if (total_shares > 0) {
        double share_scale = double(planet.shares + add_shares) / total_shares;
        double worker_scale = std::max(0.0, (100.0 + planet.facilities * facility_bonus_max - (planet.workers + add_workers) * crouding_factor)) / 100.0;
        double income = planet.local_income;

        if (with_history && planet.history.size() >= 2) {
          double moves_passed = planet.history.back().first - planet.history.front().first;
          double income_changed = planet.history.back().second - planet.history.front().second;
          CHECK(moves_passed > 0);
          double avg_per_move = income_changed / moves_passed;
          income += turns_to_end * avg_per_move * 0.5;
        }

        planet_scale = share_scale * income * worker_scale;
      }
    }

    return planet_scale * (optimal_profit_per_move / 100.0);
  }

  void move_traders() {
    std::vector<Trader> free_traders;
    std::set<size_t> busy_planets;
    for (const auto& trader : traders) {
      if (trader.turns_busy == 0) {
        free_traders.push_back(trader);
      }
      busy_planets.insert(trader.planet_id);
    }

    for (const auto& trader : free_traders) {
      if (server.commands_sent() < server.max_commands()) {
        const Planet* trader_planet = nullptr;
        for (const auto& planet : planets) {
          if (planet.id == trader.planet_id) {
            trader_planet = &planet;
          }
        }
        CHECK(trader.planet_id == kNone || trader_planet != nullptr);

        bool must_move = (trader_planet &&
          trader_planet->shares > 0 &&
          trader_planet->efficiency < optimal_efficiency_to_leave &&
          turns_to_end > kFinishTurns);

        std::vector<std::pair<size_t, double>> good_planets;
        std::vector<size_t> stock_planets;
        for (const auto& planet : planets) {
          if (busy_planets.count(planet.id) == 0) {
            if (planet.shares > 0 && planet.efficiency == 100.0) {
              double score = get_planet_score_per_move(planet, 0, 1);
              good_planets.push_back({planet.id, score});
            } else if (planet.shares == 0) {
              stock_planets.push_back(planet.id);
            }
          }
        }
        std::sort(good_planets.begin(), good_planets.end(), [](auto l, auto r){
          return l.second > r.second;
        });
        std::random_shuffle(stock_planets.begin(), stock_planets.end());

        size_t move_to = kNone;

        if (must_move) {
          if (!good_planets.empty()) {
            INFO() << "Move, must, good";
            move_to = good_planets.front().first;
          } else if (!stock_planets.empty()) {
            INFO() << "Move, must, bad";
            move_to = stock_planets.front();
          }
        } else {
          if (!good_planets.empty()) {
            double current_score = (trader_planet ? get_planet_score_per_move(*trader_planet) : 0.0);
            if (trader_planet) {
              current_score *= (trader_planet->efficiency / 100.0);
            }
            double new_score = good_planets.front().second;
            if (new_score > current_score) {
              move_to = good_planets.front().first;
              INFO() << "Move, can, better," <<
                " from: " << trader.planet_id << " " << current_score <<
                " to: " << move_to << " " << new_score;
            }
          }
        }

        if (move_to != kNone) {
          server << "PUT_TRADER " << trader.id << " " << move_to << flush;
          CHECK(server.get_response() == 0);
          busy_planets.insert(move_to);
        }
      }
    }
  }

  size_t optimal_planets() {
    return 2 * traders.size() + traders.size() * (drop_efficiency_coeff / rise_efficiency_coeff);
  }

  void make_investments() {
    if (server.commands_sent() + 2 > server.max_commands()) {
      return;
    } else if (cash <= share_price && vouchers == 0) {
      return;
    } else if (turns_after_reset <= kProfitTurnsAfterReset) {
      return;
    }

    std::vector<double> lowest_scores;

    for (auto& planet : planets) {
      if (planet.shares > 0) {
        double score_now = get_planet_score_per_move(planet, 0, 0, true) * turns_to_end;
        lowest_scores.push_back(score_now);
      }
    }
    std::sort(lowest_scores.rbegin(), lowest_scores.rend());

    double lowest_score = (optimal_planets() >= lowest_scores.size() ? 0.0 : lowest_scores[optimal_planets()]);

    double best_profit = 0.0;
    Planet* best_planet = nullptr;

    for (auto& planet : planets) {
      if (planet.decreased || !planet.updated)
        continue;
      double score_now = get_planet_score_per_move(planet, 0, planet.shares == 0, true) * turns_to_end;
      double score_new = get_planet_score_per_move(planet, 1, 1, true) * turns_to_end;
      double profit = score_new - score_now;
      if (planet.shares == 0)
        profit -= lowest_score;
      if (profit > best_profit) {
        best_profit = profit;
        best_planet = &planet;
      }
    }

    if (!best_planet) {
      return;
    }

    INFO() << "Best planet" <<
      " lowest_score: " << lowest_score <<
      " candidate: " << best_planet->id <<
      " expected profit: " << best_profit;

    Planet updated_planet = update_single_planet(best_planet->id);

    if (updated_planet.other_shares != best_planet->other_shares) {
      INFO() << "Best planet changed, skip";
      best_planet->other_shares = updated_planet.other_shares;
      best_planet->updated = turns_after_reset;
      return;
    }

    double target_price = vouchers ? 0 : share_price

    if (best_profit > target_price) {
      CHECK(best_planet != nullptr);
      server << "BUY_SHARES " << best_planet->id << " " << 1 << flush;
      best_planet->shares += 1;
      CHECK(server.get_response() == 0);
      turns_after_invest = 0;
      INFO() << "Invest into: " << best_planet->id << " expected profit: " << best_profit;
    }
  }

  void make_move() override {
    make_investments();
    move_traders();
  }

  void after_round() override {
    random_shuffle(planets.begin(), planets.end());
    std::sort(planets.begin(), planets.end(), [](auto l, auto r) {
      return l.updated < r.updated;
    });
    for (auto& planet : planets) {
      if (server.commands_sent() < server.max_commands()) {
        Planet updated_planet = update_single_planet(planet.id);
        planet.shares = updated_planet.shares;
        planet.other_shares = updated_planet.other_shares;
        planet.efficiency = updated_planet.efficiency;
        planet.workers = updated_planet.workers;
        planet.updated = turns_after_reset;
      }
    }
  }

  void print_stat() override {
    for (const auto& planet : planets) {
      if (planet.updated) {
        INFO() << "Planet info," <<
          " id: " << planet.id <<
          " local_income: " << planet.local_income <<
          " our shares: " << planet.shares <<
          " other shares: " << planet.other_shares << 
          " workers: " << planet.workers << 
          " score per move: " << get_planet_score_per_move(planet) <<
          " efficiency: " << planet.efficiency <<
          " decreased: " << planet.decreased << 
          " facilities: " << planet.facilities;
      }
    }

    INFO() << "Turns to end: " << turns_to_end;
    INFO() << "Turns after reset: " << turns_after_reset;
    INFO() << "Turns after investment: " << turns_after_invest;
    INFO() << "Cash: " << cash;
    INFO() << "Score: " << score;
    INFO() << "Vouchers: " << vouchers;
    INFO() << "Share price: " << share_price;
    INFO() << "Traders: " << traders.size();
    INFO() << "Already invested planets: " << count_invested_planets();
    INFO() << "Optimal planets: " << optimal_planets();
    INFO() << "Rise scale: " << drop_efficiency_coeff / rise_efficiency_coeff;
  }
};

int main(int argc, char** argv) {
  if (argc != 2) {
    std::cerr << "choose the server (0|1)";
    exit(1);
  }
  // Fill
  std::string ip = "10.24.24.1";
  int ports[2] = { 20005, 20006 };
  std::string login = "team25";
  std::string pass = "jrxinmswpg";

  int server_id = atoi(argv[1]);
  SCREEN() << "Starting game server: " << server_id;
  MyGame game(server_id, ip, ports[server_id], login, pass);
  game.run();
  ERROR() << "Game finished: " << server_id;
}