Amedeo
SYMBIOSYS OF
PURPOSE & STYLE
Follow us

Search

ekusiadadus
  -  Programming   -  Competitive Programming   -  天下一 Game Battle Contest 2021 Spring
天下一-game-battle-contest-2021-autumn

天下一 Game Battle Contest 2021 Spring

tenka1-2021-spring-0

天下一 Game Battle Contest 2021 Springに初参加しました。
結果は、22位でした。
途中までは、アルゴリズムでごり押して行けたけど
APIの実行時間までは、考えていなかったです。←過去問っておけばよかった
5機存在したので、(重さ/到達回数、-1×dis)の大きい順から4機動かす,1機は、重さ/到達回数の大きい順に動かすにしました。これも、5機全部動かしておけば、点数稼げてた。。。
AWSとか、GCPでちゃんとした環境を使わないとダメだった.
開始3時間くらいまでは10位以内だったので、途中で変な変更とか加えずにクラウドに切り替えてればよかった。

秋にもあるので、また参加しようと思います。

tenka1-2021-spring-1
tenka1-2021-spring-3
tenka1-2021-spring-3
import json
import os
import subprocess
import sys
from urllib.request import urlopen

GAME_SERVER = os.getenv('GAME_SERVER', 'https://contest.2021-spring.gbc.tenka1.klab.jp')
TOKEN = os.getenv('TOKEN', 'a982797cf9e9f06a64a6104383ee67f1')


p = subprocess.Popen(sys.argv[1:], stdin=subprocess.PIPE, stdout=subprocess.PIPE)


def call_api(x: str):
    with urlopen(f'{GAME_SERVER}{x}') as res:
        return json.loads(res.read())


def call_master_data():
    r = call_api('/api/master_data')
    assert len(r['checkpoints']) == 26
    p.stdin.write(f'{r["game_period"]} {r["max_len_task"]} {r["num_agent"]}\n'.encode())
    for c in r['checkpoints']:
        p.stdin.write(f'{c["x"]} {c["y"]}\n'.encode())
    p.stdin.write(f'{r["area_size"]}\n'.encode())
    p.stdin.flush()


def call_game():
    r = call_api(f'/api/game/{TOKEN}')
    assert r['status'] == 'ok'
    p.stdin.write(f'{r["now"]} {len(r["agent"])} {len(r["task"])}\n'.encode())
    for a in r['agent']:
        p.stdin.write(f'{len(a["move"])}\n'.encode())
        for m in a['move']:
            p.stdin.write(f'{m["x"]} {m["y"]} {m["t"]}\n'.encode())
        p.stdin.write(f'-{a["history"]}\n'.encode())
    for t in r['task']:
        p.stdin.write(f'{t["s"]} {t["t"]} {t["weight"]} {t["count"]} {t["total"]}\n'.encode())
    p.stdin.write(f'{r["next_task"]}\n'.encode())
    p.stdin.flush()


def call_move(type: str, param: str):
    r = call_api(f'/api/{type}/{TOKEN}/{param}')
    assert r['status'] == 'ok'
    assert len(r['move']) >= 2
    p.stdin.write(f'{r["now"]} {len(r["move"])}\n'.encode())
    for m in r['move']:
        p.stdin.write(f'{m["x"]} {m["y"]} {m["t"]}\n'.encode())
    p.stdin.flush()


def main():
    while True:
        line = p.stdout.readline()
        if not line:
            break
        a = line.decode().rstrip().split(' ')
        if a[0] == 'master_data':
            call_master_data()
        elif a[0] == 'game':
            call_game()
        elif a[0] in ('move', 'move_next'):
            call_move(a[0], a[1])
        else:
            assert False, f'invalid command {repr(a[0])}'


if __name__ == "__main__":
    main()
#include <stdlib.h>
#include <iostream>
#include <string>
#include <vector>
#include <thread>
#include <chrono>
#include <queue>
#include <random>
#include <bits/stdc++.h>
using namespace std;

const int GAME_INFO_SLEEP_TIME = 5000;

mt19937 mt;

struct MasterData {
    int game_period;
    int max_len_task;
    int num_agent;
    vector<pair<int, int>> checkpoints;
    int area_size;
};

struct AgentMove {
    double x;
    double y;
    int t;
};

struct Agent {
    vector<AgentMove> move;
    string history;
};

struct Task {
    string s;
    int t;
    int weight;
    int count;
    int total;
};

struct Game {
    int now;
    vector<Agent> agent;
    vector<Task> task;
    int next_task;
};

struct Move {
    int now;
    vector<AgentMove> move;
};

MasterData call_master_data() {
    cout << "master_data" << endl;
    MasterData res;
    cin >> res.game_period >> res.max_len_task >> res.num_agent;
    res.checkpoints = vector<pair<int, int>>(26);
    for (auto& c : res.checkpoints) {
        cin >> c.first >> c.second;
    }
    cin >> res.area_size;
    return res;
}

Game call_game() {
    cout << "game" << endl;
    Game res;
    int num_agent, num_task;
    cin >> res.now >> num_agent >> num_task;
    res.agent.resize(num_agent);
    for (auto& a : res.agent) {
        int num_move;
        cin >> num_move;
        a.move.resize(num_move);
        for (auto& m : a.move) {
            cin >> m.x >> m.y >> m.t;
        }
        string h;
        cin >> h;
        a.history = h.substr(1);
    }
    res.task.resize(num_task);
    for (auto& t : res.task) {
        cin >> t.s >> t.t >> t.weight >> t.count >> t.total;
    }
    cin >> res.next_task;
    return res;
}

Move read_move() {
    Move res;
    int num_move;
    cin >> res.now >> num_move;
    res.move.resize(num_move);
    for (auto& m : res.move) {
        cin >> m.x >> m.y >> m.t;
    }
    return res;
}

Move call_move(int index, int x, int y) {
    cout << "move " << index << "-" << x << "-" << y << endl;
    return read_move();
}

Move call_move_next(int index, int x, int y) {
    cout << "move_next " << index << "-" << x << "-" << y << endl;
    return read_move();
}

struct Bot {
    MasterData master_data;
    Game game_info;
    chrono::system_clock::time_point start_time;
    int start_game_time_ms;
    int next_call_game_info_time_ms;
    vector<int> agent_move_finish_ms;
    vector<queue<pair<int, int>>> agent_move_point_queue;
    vector<pair<int, int>> agent_last_point;
    Bot() {
        master_data = call_master_data();
        game_info = call_game();
        start_game_time_ms = game_info.now;
        cerr << "Start:" << start_game_time_ms << endl;
        start_time = chrono::system_clock::now();
        next_call_game_info_time_ms = get_now_game_time_ms() + GAME_INFO_SLEEP_TIME;
        agent_move_finish_ms.resize(master_data.num_agent);
        agent_move_point_queue.resize(master_data.num_agent);
        agent_last_point.resize(master_data.num_agent);
        for (int i = 0; i < master_data.num_agent; ++ i) {
            agent_last_point[i] = {(int)game_info.agent[i].move.back().x, (int)game_info.agent[i].move.back().y};
            set_move_point(i);
        }
    }
    cont T
    const Task& choice_task(int agnum) {
        //int r = uniform_int_distribution<>(0, game_info.task.size()-1)(mt);
        int rec = 0;
        double ans = 0;
        vector<pair<pair<double,double>,int> > agnums(game_info.task.size());
        if(agnum != 4){
            for(int i = 0; i < game_info.task.size()-1; ++i){
                if(game_info.task[i].t > game_info.now) continue;
                int cnt = max(game_info.task[i].total,game_info.task[i].count);
                pair<int,int> bfp  = agent_last_point[agnum];
                string str = game_info.task[i].s;
                vector<pair<int,int>> st(str.length());

                st[0] = get_checkpoint(str[0]);
                double dis = sqrt(pow((double)bfp.first-(double)st[0].first,2)+pow((double)bfp.second-(double)st[0].second,2)); 
                for(int i = 1; i < str.size(); ++i){
                    st[i] = get_checkpoint(str[i]);
                    dis += sqrt(pow((double)st[i-1].first - (double)st[i].first,2)+pow((double)st[i-1].second-(double)st[i].second,2));
                }
                dis *= -1;
                if(cnt == 0) cnt = 1;
                agnums.push_back(make_pair(make_pair((double)game_info.task[i].weight/(double)cnt,dis),i));
            }
            sort(agnums.rbegin(),agnums.rend());
            pair<int,int> nxt = get_checkpoint(game_info.task[agnums[(agnum)%3].second]);

            return game_info.task[agnums[(agnum)%3].second];
        }
        // if(agnum == 3){
        //  vector<pair<double,int>> asp;
        //  for(int i = 0; i < game_info.task.size()-1; ++i){
        //      if(game_info.task[i].t > game_info.now) continue;
        //      pair<int,int> bfp  = agent_last_point[agnum];
        //      string str = game_info.task[i].s;
        //      vector<pair<int,int>> st(str.length());

        //      st[0] = get_checkpoint(str[0]);
        //      double dis = sqrt(pow((double)bfp.first-(double)st[0].first,2)+pow((double)bfp.second-(double)st[0].second,2)); 
        //      vector<pair<pair<double,double>,int>> asp;
        //      for(int i = 1; i < str.size(); ++i){
        //          st[i] = get_checkpoint(str[i]);
        //          dis += sqrt(pow((double)st[i-1].first - (double)st[i].first,2)+pow((double)st[i-1].second-(double)st[i].second,2));
        //      }
        //      double cnt = max(game_info.task[i].total,game_info.task[i].count);
        //      asp.push_back(make_pair(make_pair((double)game_info.task[i].weight/(double)cnt,-1*dis),i));
        //  }
        //  sort(asp.rbegin(),asp.rend());
        //  return game_info.task[asp[0].second];
        // }
        if(agnum == 4){
            vector<pair<double,int>> asp;
            for(int i = 0; i < game_info.task.size()-1; ++i){
                if(game_info.task[i].t > game_info.now) continue;
                double cnt = max(game_info.task[i].total,game_info.task[i].count);
                asp.push_back(make_pair((double)game_info.task[i].weight/(double)cnt,i));
            }
            sort(asp.rbegin(),asp.rend());
            return game_info.task[asp[0].second];
        }
        // if(agnum == 4){
        //  vector<pair<pair<int,int>,int>> asp;
        //  for(int i = 0; i < game_info.task.size()-1; ++i){
        //      if(game_info.task[i].t > game_info.now) continue;
        //      double cnt = max(game_info.task[i].total,game_info.task[i].count);
        //      if(cnt == 0) cnt = 1e9;
        //      asp.push_back(make_pair(make_pair(-1*cnt,game_info.task[i].weight),i));
        //  }
        //  sort(asp.rbegin(),asp.rend());
        //  return game_info.task[asp[0].second];
        // }
    }
    pair<int, int> get_checkpoint(char c) {
        return master_data.checkpoints[c - 'A'];
    }
    // 移動予定を設定
    void set_move_point(int index) {
        const auto& next_task = choice_task(index);
        cerr << "Agent#" << index+1 << " next task:" << next_task.s << endl;
        int cnt = 0;
        for (char c : next_task.s) {
            auto before_point = agent_last_point[index];
            auto move_point = get_checkpoint(c);

            // 移動先が同じ場所の場合判定が入らないため別の箇所に移動してからにする
            if (before_point == move_point && cnt != 0) {
                //int tmp_x = master_data.area_size / 2;
                int tmp_x = master_data.area_size / 2;
                if(before_point.first+1 < master_data.area_size) tmp_x = before_point.first+1;
                else if(before_point.first-1 >= 0) tmp_x = before_point.first-1;
                int tmp_y = before_point.second;
                agent_move_point_queue[index].push({tmp_x, tmp_y});
            }

            agent_move_point_queue[index].push(move_point);
            agent_last_point[index] = move_point;
            cnt++;
        }
    }
    int get_now_game_time_ms() {
        auto t = chrono::duration_cast<std::chrono::milliseconds>(chrono::system_clock::now() - start_time).count();
        return start_game_time_ms + t;
    }
    Move move_next(int index) {
        auto [x, y] = agent_move_point_queue[index].front();
        agent_move_point_queue[index].pop();
        auto move_next_res = call_move_next(index+1, x, y);
        cerr << "Agent#" << index+1 << " move_next to (" << x << ", " << y << ")" << endl;

        //agent_move_finish_ms[index] = move_next_res.move[1].t + 100;
        agent_move_finish_ms[index] = move_next_res.move[1].t;

        // タスクを全てやりきったら次のタスクを取得
        if (agent_move_point_queue[index].empty()) {
            set_move_point(index);
        }

        return move_next_res;
    }
    double get_now_score() {
        double score = 0.0;
        for (const auto& task : game_info.task) {
            if (task.total == 0) continue;
            score += (double)(task.weight * task.count) / task.total;
        }

        return score;
    }
    void solve() {
        for (;;) {
            int now_game_time_ms = get_now_game_time_ms();
            //追加
            int cnt = 0;
            //
            // エージェントを移動させる
            for (int i = 0; i < master_data.num_agent; ++ i) {
                if (agent_move_finish_ms[i] < now_game_time_ms) {
                    auto move_next_res = move_next(i);
                    // 次の移動予定がない場合もう一度実行する
                    if (move_next_res.move.size() == 2) {
                        cnt++;
                        move_next(i);
                    }
                }
            }

            // ゲーム情報更新
            if (next_call_game_info_time_ms < now_game_time_ms) {
                cerr << "Update GameInfo" << endl;
                game_info = call_game();
                next_call_game_info_time_ms = get_now_game_time_ms() + GAME_INFO_SLEEP_TIME;
                cerr << "Score: " << get_now_score() << endl;
            }

            this_thread::sleep_for(chrono::milliseconds(500));
        }
    }
};

int main() {
    random_device seed_gen;
    mt = mt19937(seed_gen());

    Bot bot;
    bot.solve();
}
Leave a Comment