Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize "O3,omit-frame-pointer,inline"
- #include <chrono>
- #include <iostream>
- #include <cmath>
- #include <string>
- #include <cstring>
- // Constants
- #define WIDTH 16000
- #define HEIGHT 9000
- #define MAX_DP 100
- #define MAX_EN 100
- #define EN_VEL 500
- #define MY_VEL 1000
- #define MIN_DIST 2000 // Death distance
- #define MIN_DIST2 4000000 // Same, squared
- #define THRESHOLD 4000000
- #define INF 337000000 // W*W*H*H
- // State of a playout
- #define STATE_GAME_OVER 0
- #define STATE_ONGOING 1
- #define STATE_FINISHED 2
- // AI Mode (useless, was put there in case I wished to use another AI algorithm)
- #define AI_MODE_MC 0
- // Random moves around (0, 0)
- #define N_RANDOM 225
- const int rand_x[N_RANDOM] = {-10, -80, -151, -222, -292, -363, -434, -504, -575, -646, -717, -787, -858, -929, -1000, -9, -72, -136, -200, -263, -327, -391, -454, -518, -582, -646, -709, -773, -837, -900, -6, -50, -94, -138, -182, -226, -270, -314, -358, -403, -447, -491, -535, -579, -623, -2, -17, -33, -49, -65, -80, -96, -112, -128, -143, -159, -175, -191, -206, -222, 2, 17, 33, 49, 65, 80, 96, 112, 128, 143, 159, 175, 191, 206, 222, 6, 50, 94, 138, 182, 226, 270, 314, 358, 403, 447, 491, 535, 579, 623, 9, 72, 136, 200, 263, 327, 391, 454, 518, 582, 646, 709, 773, 837, 900, 10, 80, 151, 222, 292, 363, 434, 504, 575, 646, 717, 787, 858, 929, 1000, 9, 72, 136, 200, 263, 327, 391, 454, 518, 582, 646, 709, 773, 837, 900, 6, 50, 94, 138, 182, 226, 270, 314, 358, 403, 447, 491, 535, 579, 623, 2, 17, 33, 49, 65, 80, 96, 112, 128, 143, 159, 175, 191, 206, 222, -2, -17, -33, -49, -65, -80, -96, -112, -128, -143, -159, -175, -191, -206, -222, -6, -50, -94, -138, -182, -226, -270, -314, -358, -403, -447, -491, -535, -579, -623, -9, -72, -136, -200, -263, -327, -391, -454, -518, -582, -646, -709, -773, -837, -900, -10, -80, -151, -222, -292, -363, -434, -504, -575, -646, -717, -787, -858, -929, -1000};
- const int rand_y[N_RANDOM] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -4, -35, -65, -96, -127, -157, -188, -219, -249, -280, -311, -341, -372, -403, -433, -7, -63, -118, -173, -228, -284, -339, -394, -450, -505, -560, -615, -671, -726, -781, -9, -78, -147, -216, -285, -354, -423, -492, -561, -630, -699, -768, -837, -905, -974, -9, -78, -147, -216, -285, -354, -423, -492, -561, -630, -699, -768, -837, -905, -974, -7, -63, -118, -173, -228, -284, -339, -394, -450, -505, -560, -615, -671, -726, -781, -4, -35, -65, -96, -127, -157, -188, -219, -249, -280, -311, -341, -372, -403, -433, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 35, 65, 96, 127, 157, 188, 219, 249, 280, 311, 341, 372, 403, 433, 7, 63, 118, 173, 228, 284, 339, 394, 450, 505, 560, 615, 671, 726, 781, 9, 78, 147, 216, 285, 354, 423, 492, 561, 630, 699, 768, 837, 905, 974, 9, 78, 147, 216, 285, 354, 423, 492, 561, 630, 699, 768, 837, 905, 974, 7, 63, 118, 173, 228, 284, 339, 394, 450, 505, 560, 615, 671, 726, 781, 4, 35, 65, 96, 127, 157, 188, 219, 249, 280, 311, 341, 372, 403, 433, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
- #define DMG_THRESHOLD 12
- // Probabiity to one-shot an enemy
- #define PROB_OS 90
- // Cumulated probabilities for every strategy (sums to 150 ... sorry)
- #define PROB_GO_DP 25
- #define PROB_GO_EN 50
- #define PROB_GO_RD 75
- #define PROB_SHOOT 150
- // Macros
- //#define DEBUG
- #define min(a, b) (a < b ? a : b)
- #define max(a, b) (a > b ? a : b)
- #define RAND(x) ((int)(rand() / (float)RAND_MAX * x))
- // Timing
- using time_point = std::chrono::time_point<std::chrono::system_clock>;
- using duration = std::chrono::duration<float>;
- #define now std::chrono::system_clock::now
- #define TIME_LIMIT 0.096f
- #define LARGE_TIME_LIMIT 0.996f
- // Player actions
- #define ACTION_MOVE 0
- #define ACTION_SHOOT 1
- #define ACTION_NONE 2
- struct Action {
- int type; // if type == MOVE, p1 = x, p2 = y; if SHOOT; p1 = id, p2 = unused
- int p1, p2;
- };
- #define SOL_SIZE 200 // Maybe too much ?
- struct Solution {
- int nactions;
- int final_state;
- int dist_from_killer;
- Action actions[SOL_SIZE];
- int score;
- };
- // Distances
- inline int dist2(int x1, int y1, int x2, int y2) {
- int dx = x1-x2;
- int dy = y1-y2;
- return dx*dx+dy*dy;
- }
- // Moving an entity, /\ x and y are modified
- inline void move(int &x, int &y, int tx, int ty, int velocity) {
- int dx = tx - x;
- int dy = ty - y;
- if (dx != 0 || dy != 0) {
- float L = sqrt(dx*dx+dy*dy);
- if (L < velocity) {
- x = tx;
- y = ty;
- }
- else {
- float d = velocity / L;
- x += dx*d;
- if (x < 0)
- x = 0;
- else if (x >= WIDTH)
- x = WIDTH-1;
- y += dy * d;
- if (y < 0)
- y = 0;
- else if (y >= HEIGHT)
- y = HEIGHT-1;
- }
- }
- }
- // On squared distances
- inline int damage_dealt(int d2) {
- if (d2 <= 4082821)
- return 14;
- if (d2 <= 4641588)
- return 13;
- if (d2 <= 5333598)
- return 12;
- if (d2 <= 6206801)
- return 11;
- if (d2 <= 7333489)
- return 10;
- if (d2 <= 8827108)
- return 9;
- if (d2 <= 10874632)
- return 8;
- if (d2 <= 13803665)
- return 7;
- if (d2 <= 18235270)
- return 6;
- if (d2 <= 25477833)
- return 5;
- if (d2 <= 38732002)
- return 4;
- if (d2 <= 67860440)
- return 3;
- if (d2 <= 158988089)
- return 2;
- else
- return 1;
- }
- // Game constants
- int n_dp;
- int n_enemies;
- int total_life;
- int dp_x[MAX_DP];
- int dp_y[MAX_DP];
- int ai_mode;
- int turn;
- Solution current_solution;
- int turn_in_sol;
- time_point start;
- duration elapsed;
- // Game state
- struct State {
- int en_alive;
- int dp_alive;
- int shots;
- int x, y;
- int en_x[MAX_EN];
- int en_y[MAX_EN];
- int en_l[MAX_EN]; // Life
- int en_t[MAX_EN]; // Target DP
- int dp_a[MAX_DP];
- int dist2[MAX_EN];
- // Additional info in casae of death
- int killer; // Which enemy killed us
- int dist_from_killer; // At what distance were we
- State() {
- en_alive = 0;
- dp_alive = 0;
- shots = 0;
- x = 0;
- y = 0;
- killer = -1;
- }
- };
- // Gives us a random alive enemy on the map
- inline int random_enemy(State &s) {
- int eids[MAX_EN];
- int n_en = 0;
- for (int eid=0; eid < n_enemies; ++eid) {
- if (s.en_l[eid] > 0)
- eids[n_en++] = eid;
- }
- if (n_en == 0)
- return -1;
- return eids[RAND(n_en)];
- }
- // Reading the turn state on stdin
- void read_state_from_stdin(State &s, bool first) {
- std::cin >> s.x >> s.y;
- // Reset
- memset(s.en_x, 0, MAX_EN*sizeof(int));
- memset(s.en_y, 0, MAX_EN*sizeof(int));
- memset(s.en_l, 0, MAX_EN*sizeof(int));
- memset(s.dp_a, 0, MAX_EN*sizeof(int));
- // Data points
- int tmp;
- std::cin >> tmp;
- s.dp_alive = (int8_t)tmp;
- for (int i=0; i < s.dp_alive; ++i) {
- int id, x, y;
- std::cin >> id >> x >> y;
- #ifdef DEBUG
- std::cerr << "Data point #" << id << " at position : " << x << " " << y << std::endl;
- #endif
- s.dp_a[id] = 1;
- dp_x[id] = x;
- dp_y[id] = y;
- }
- if (first)
- n_dp = s.dp_alive;
- // Enemies
- int t = 0;
- std::cin >> tmp;
- s.en_alive = (int)tmp;
- for(int i=0; i < s.en_alive; ++i) {
- int id, x, y, life;
- std::cin >> id >> x >> y >> life;
- s.en_x[id] = x;
- s.en_y[id] = y;
- s.en_l[id] = life;
- // Distance to Wolff
- int d = dist2(s.en_x[id], s.en_y[id], s.x, s.y);
- s.dist2[id] = d;
- // Current target
- int best_dist = INF;
- for (int pid=0; pid < n_dp; ++pid) {
- if (s.dp_a[pid]) {
- int d = dist2(dp_x[pid], dp_y[pid], s.en_x[id], s.en_y[id]);
- if (d < best_dist) {
- best_dist = d;
- s.en_t[id] = pid;
- }
- }
- }
- #ifdef DEBUG
- std::cerr << "Enemy #" << id << " at position : " << x << " " << y << "; Life left : "
- << life << "; Target = " << s.en_t[id] << std::endl;
- #endif
- t += life;
- }
- // First turn info to store as globals
- if (first) {
- n_enemies = s.en_alive;
- total_life = t;
- #ifdef DEBUG
- std::cerr << "First turn init :" << std::endl;
- std::cerr << " - " << n_enemies << " enemies" << std::endl;
- std::cerr << " - Cumulating " << total_life << " life" << std::endl;
- std::cerr << " - Trying to capture " << n_dp << " data points " << std::endl;
- #endif
- }
- }
- // One step evolution of the game state
- // Here things have been reorganized to speed up the whole process :
- // In particular, Wolff's position is computed BEFORE the enemies.
- // This allows us to compute the distance to the enemy in the same loop as their new
- // position, and thus detecting Wolff's death much faster in only one loop.
- int evolve(State &s, const Action &a, bool check_for_death) {
- // 1- Moving Wolff
- if (a.type == ACTION_MOVE)
- move(s.x, s.y, a.p1, a.p2, MY_VEL);
- // 2- Moving enemies + checking for death
- for (int eid=0; eid < n_enemies; ++eid) {
- // Alive ?
- if (s.en_l[eid] > 0) {
- // No target or target collected ? We find a new one
- int tid;
- if (s.en_t[eid] == -1 || !s.dp_a[s.en_t[eid]]) {
- int best_dist = INF;
- tid = -1;
- // Looking for the closest DP
- for (int pid=0; pid < n_dp; ++pid) {
- if (s.dp_a[pid]) {
- int d = dist2(dp_x[pid], dp_y[pid], s.en_x[eid], s.en_y[eid]);
- if (d < best_dist) {
- best_dist = d;
- tid = pid;
- }
- }
- }
- s.en_t[eid] = tid;
- }
- else
- tid = s.en_t[eid];
- // Moving the enemy
- move(s.en_x[eid], s.en_y[eid], dp_x[tid], dp_y[tid], EN_VEL);
- // Storing the distance, and checking for death
- s.dist2[eid] = dist2(s.en_x[eid], s.en_y[eid], s.x, s.y);
- if (check_for_death && s.dist2[eid] <= MIN_DIST2) {
- s.killer = eid;
- s.dist_from_killer = s.dist2[eid];
- return STATE_GAME_OVER;
- }
- }
- }
- // 3- Shooting
- if (a.type == ACTION_SHOOT) {
- s.en_l[a.p1] -= damage_dealt(s.dist2[a.p1]);
- s.shots++;
- if (s.en_l[a.p1] <= 0 && --s.en_alive == 0)
- return STATE_FINISHED;
- }
- // 4- DP collection
- for (int eid=0; eid < n_enemies; ++eid) {
- if (s.en_l[eid] > 0) {
- int tid = s.en_t[eid];
- if (s.dp_a[tid] && s.en_x[eid] == dp_x[tid] && s.en_y[eid] == dp_y[tid]) {
- s.dp_a[tid] = false;
- if (--s.dp_alive == 0) {
- return (s.en_alive < n_enemies ? STATE_FINISHED : STATE_GAME_OVER);
- }
- }
- }
- }
- return STATE_ONGOING;
- }
- // Score at the end of the game
- int game_score(State &s) {
- return s.dp_alive * (100 + max(0, total_life - 3*s.shots) * 3) + 10*(n_enemies - s.en_alive);
- }
- // Util function to output the initial conditions of a case in a C++ fashion
- // Used to debug locally
- #define IC_OUT(k, v) (std::cerr << k << " = " << v << ";" << std::endl)
- void output_ICs(State &s) {
- IC_OUT("n_enemies", n_enemies);
- IC_OUT("n_dp", n_dp);
- IC_OUT("s.dp_alive", s.dp_alive);
- IC_OUT("s.en_alive", s.en_alive);
- IC_OUT("s.x", s.x);
- IC_OUT("s.y", s.y);
- for (int i=0; i < n_enemies; ++i) {
- IC_OUT("s.en_x["+std::to_string(i)+"]", s.en_x[i]);
- IC_OUT("s.en_y["+std::to_string(i)+"]", s.en_y[i]);
- IC_OUT("s.en_l["+std::to_string(i)+"]", s.en_l[i]);
- IC_OUT("s.en_t["+std::to_string(i)+"]", -1);
- }
- for (int i=0; i < n_dp; ++i) {
- IC_OUT("dp_x["+std::to_string(i)+"]", dp_x[i]);
- IC_OUT("dp_y["+std::to_string(i)+"]", dp_y[i]);
- IC_OUT("s.dp_a["+std::to_string(i)+"]", s.dp_a[i]);
- }
- }
- // Comparing two solutions
- bool operator>(Solution &s1, Solution &s2) {
- // If same final state
- if (s1.final_state == s2.final_state) {
- // If both finished
- if (s1.final_state == STATE_FINISHED) {
- // If same score, we keep the one that finished early
- if (s1.score == s2.score)
- return s1.nactions < s2.nactions;
- // Otherwise, best score
- else
- return s1.score > s2.score;
- }
- // If both losing solutions
- else {
- // If same number of turns played
- if (s1.nactions == s2.nactions) {
- // We keep the death that is the farthest from the killer
- return s1.dist_from_killer > s2.dist_from_killer;
- }
- // Otherwise we keep the solution that survives the longest
- else
- return s1.nactions > s2.nactions;
- }
- }
- // Different states, we keep the one that is not game over
- else
- return s1.final_state == STATE_FINISHED;
- }
- // Playing the turn, high level function
- void play_turn(State &s) {
- // First turn = 1s, rest of the time 100ms
- float time_limit = (turn == 1 ? LARGE_TIME_LIMIT : TIME_LIMIT);
- switch(ai_mode) {
- case AI_MODE_MC: play_mc(s, time_limit); break;
- }
- }
- // Playing a monte carlo move
- int play_mc(State &s, float time_limit) {
- start = now();
- bool done = false;
- int ite = 0;
- int nbok = 0;
- Solution sol;
- // Looping while we have time
- while (!done) {
- ite++;
- // Generating a new solution
- State ns(s);
- generate_random_solution(ns, sol, time_limit);
- // Comparing the solution with the best one up until now
- if (sol > current_solution) {
- current_solution = sol;
- turn_in_sol = 0;
- }
- // Counting how many solutions survive
- if (sol.final_state == STATE_FINISHED)
- nbok++;
- elapsed = now() - start;
- done = elapsed.count() > time_limit;
- }
- // Stats/Debug
- std::cerr << "Enemies alive : " << s.en_alive << std::endl;
- std::cerr << "DP alive : " << s.dp_alive << std::endl;
- std::cerr << "MC, score expected : " << current_solution.score << std::endl;
- std::cerr << "MC, state expected : ";
- switch(current_solution.final_state) {
- case STATE_ONGOING: std::cerr << "On going ...... ?!!" << std::endl; break;
- case STATE_GAME_OVER: std::cerr << "Lost !" << std::endl; break;
- case STATE_FINISHED: std::cerr << "Finished !" << std::endl; break;
- }
- std::cerr << ite << " solutions ; " << nbok << " solutions that survive" << std::endl;
- // Output
- Action best_action = current_solution.actions[turn_in_sol];
- if (best_action.type == ACTION_MOVE)
- std::cout << "MOVE " << best_action.p1 << " " << best_action.p2 << " " << ite << std::endl;
- else {
- std::cout << "SHOOT " << best_action.p1 << " " << ite << std::endl;
- s.shots++;
- }
- turn_in_sol++;
- // State after playing
- int res = (turn_in_sol < current_solution.nactions ? STATE_ONGOING : current_solution.final_state);
- return res;
- }
- // The main piece of code : Generating a random solution
- void generate_random_solution(State &s, Solution &sol, float time_limit) {
- int state = STATE_ONGOING;
- int t = 0;
- Action a;
- // Iterating until the end of the playout
- while (state == STATE_ONGOING) {
- // Looking for a viable enemy to one shot
- int best_id = -1;
- int best_dist = INF;
- int best_life = 0;
- int closest_id = -1;
- int closest_dist = INF;
- bool can_os = false;
- // We get the position of every enemy next turn
- State ns(s);
- a.type=ACTION_NONE;
- evolve(ns, a, false);
- // For every enemy
- for (int eid=0; eid < n_enemies; ++eid) {
- if (s.en_l[eid] > 0) {
- int d = ns.dist2[eid];
- int dmg = damage_dealt(d);
- // Can we one shot /
- if (dmg >= s.en_l[eid]) {
- can_os = true;
- // Closest enemy is preferrable to avoid death
- if (d < best_dist) {
- best_id = eid;
- best_dist = d;
- best_life = s.en_l[eid];
- }
- else if (d == best_dist && s.en_l[eid] > best_life) {
- best_id = eid;
- best_dist = d;
- best_life = s.en_l[eid];
- }
- }
- // We also use this loop to store the closest enemy
- if (d < closest_dist) {
- closest_dist = d;
- closest_id = eid;
- }
- }
- }
- // If we can one-shot we have a 90% probability to shoot
- if (can_os && RAND(100) < PROB_OS) {
- a = Action{ACTION_SHOOT, best_id, 0};
- sol.actions[t++] = a;
- state = evolve(s, a, true);
- continue;
- }
- // Si no one-shot, we find a random strategy between the following :
- // 1- Go towards a random DP (full speed)
- // 2- Go towards an enemy (full speed)
- // 3- Random move
- // 4- Kill an enemy (shoot until it's dead)
- int prob = 150; // Rescaling ... ugly but work
- int action = RAND(prob);
- int nreps = RAND(4) + 1; // How many repetitions ? (up to 5)
- int ite = 0;
- // 1- DP
- if (action <= PROB_GO_DP) {
- int pids[MAX_DP];
- int ndp=0;
- for (int i=0; i < n_dp; ++i)
- if (s.dp_a[i])
- pids[ndp++] = i;
- int tid = pids[RAND(ndp)];
- while (state == STATE_ONGOING && ite < nreps) {
- a = Action{ACTION_MOVE, dp_x[tid], dp_y[tid]};
- sol.actions[t++] = a;
- state = evolve(s, a, true);
- ite++;
- }
- }
- // 2- Enemy
- else if (action <= PROB_GO_EN) {
- int eid = random_enemy(s);
- while (state == STATE_ONGOING && ite < nreps) {
- int x = s.x;
- int y = s.y;
- move(x, y, s.en_x[eid], s.en_y[eid], MY_VEL);
- a = Action{ACTION_MOVE, x, y};
- sol.actions[t++] = a;
- state = evolve(s, a, true);
- ite++;
- }
- }
- // 3- Random move
- else if (action <= PROB_GO_RD) {
- int move = RAND(N_RANDOM);
- int rx = rand_x[move];
- int ry = rand_y[move];
- while (state == STATE_ONGOING && ite < nreps) {
- a = Action{ACTION_MOVE, s.x + rx, s.y + ry};
- sol.actions[t++] = a;
- state = evolve(s, a, true);
- ite++;
- }
- }
- // 4- Shooting the closest enemy
- else {
- a = Action{ACTION_SHOOT, closest_id, 0};
- while (state == STATE_ONGOING && s.en_l[closest_id] > 0) {
- sol.actions[t++] = a;
- state = evolve(s, a, true);
- }
- }
- }
- // Copying final state, and filling in the info
- sol.final_state = state;
- sol.score = game_score(s);
- if (state == STATE_GAME_OVER)
- sol.dist_from_killer = s.dist_from_killer;
- sol.nactions = t;
- }
- // Main, obvious
- int main() {
- srand(26111996);
- turn = 0;
- ai_mode = AI_MODE_MC;
- State s;
- turn_in_sol = 0;
- current_solution.score = -INF;
- while (true) {
- read_state_from_stdin(s, turn==0);
- turn++;
- play_turn(s);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement