Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

2017-12-16

[] 北大日立新概念マラソンでやった高速化色々 23:59 はてなブックマーク -  北大日立新概念マラソンでやった高速化色々 - TopCoderの学習のお時間


Competitive Programming Advent Calendar 2017 16日目の記事です。


北大日立新概念マラソン、1回目も2回目も、Simulated Annealingの良い近傍を適用できた人が上位になったという結果でした。

僕はこの手の良い近傍を見つけるという問題があまり得意でなく、かわりにナイーブな方法を頑張って高速化して対抗しようとしてしまう悪い癖があり、いろいろな高速化をやりました。その内容について、多少一般化した形にしながら書いていきます。

なお別に高速化のプロではないので、CPUパイプラインを埋める…とか先のキャッシュラインをプリフェッチ…とかの話はしません(できません)。アルゴリズムレイヤ中心です。


動的メモリ確保しない(影響度:☆☆☆☆☆)

とにかく動的なメモリ確保は取り除きます。

たとえば、小さな規模のBFSを何回もやるというシチュエーションはよく現れます(今回では、第2回で1ノードを取り除いたとき残った同じ番号のノードが連結かどうかを判定するのに使いました)。

void bfs(int pos) {
    vector<int> que = {pos}
    for (int i = 0; i < que.size(); i++) {
        // queにpush_backしたり
    }
}

毎回vectorを作るのが遅いので、十分なサイズのバッファをはじめに確保しておき、そこを使い回します。

int bfs_buf[2048];
void bfs(int pos) {
    int que_size = 1;
    bfs_buf[0] = pos;
    for (int i = 0; i < que_size; i++) {
        // bfs_buf[que_size++] = next_pos; とかでキューに追加
    }
}

「十分なサイズ」がとても大きくて全テストケースでその量のメモリを確保するのが嫌な場合は、グローバル(または関数スコープのstatic)なvectorにしておいて、毎回clearして使うのも可。


除算・剰余算を取り除く(影響度:☆☆☆☆☆)

除算・剰余算は遅いのでできる限り取り除きます。


その1:焼きなましの受理判定のときに発生する温度での除算は逆数の乗算にする

bool accept(int score_diff) {
    if (score_diff >= 0) return true;
    return rnd.next_double() <= exp(score_diff / temperature);
}

bool accept(int score_diff) {
    if (score_diff >= 0) return true;
    return rnd.next_double() <= exp(score_diff * temperature_inv);
}

その2:N点の中から動かす位置を決めるときは、乱数に対してNでmod取るののかわりに、順番に選んでいくようにする

void simulated_annealing() {
    for (int turn = 0; ;turn++) {
        int selected_pos = rnd.next_int() % N;
        // selected_pos を動かしたりする
    }
}

void simulated_annealing() {
    int selected_pos = 0;
    for (int turn = 0; ;turn++) {
        selected_pos++;
        if (selected_pos == N) selected_pos = 0;
        // selected_pos を動かしたりする
    }
}

または、候補になる位置をvectorに入れておき、要素を重複して入れることでそのvectorのサイズを2のべき乗にする。

選択される位置に偏りはできてしまうし、メモリアクセスの局所性は悪くなるものの、これで速くなって結果が良くなることもある

void simulated_annealing() {
    for (int turn = 0; ;turn++) {
        int selected_pos = cand_pos_list[rnd.next_int() & (cand_pos_list.size() - 1)];
        // selected_pos を動かしたりする
    }
}

スコア差分計算のために現在の値を保持(影響度:☆☆☆☆)

第1回では、ランダムな2点を交換するという近傍を採用しました。

このとき、スコア変化を調べるため「交換後に得られるスコア - 交換前のスコア」を計算する必要があります。

交換前のスコアは何度も同じ値にアクセスするため、事前に計算して保持しておいた方がよいです。

int calc_score_diff(int pos1, int new_val) {
    int ret = 0;
    for (int i = 0; i < 8; ++i) {
        ret -= graph[node[pos1]][node[pos1 + DIFF_POS[i]]];
        ret += graph[new_val][node[pos1 + DIFF_POS[i]]];
    }
    return ret;
}

int calc_score_diff(int pos1, int new_val) {
    int ret = -pos_score[pos1];
    for (int i = 0; i < 8; ++i) {
        ret += graph[new_val][node[pos1 + DIFF_POS[i]]];
    }
    return ret;
}

ビット並列化(影響度:☆☆☆☆)

1bitの情報はできるだけbitset的データ構造で持って、64bit分(またはSIMD使って128bit, 256bit分)まとめて処理できるようにします。

たとえば第2回では、元のグラフGでノード間にエッジがあるかどうかと、現在のキンググラフに埋め込んだ盤面上でノード間にエッジがあるかどうかをどちらも(オレオレ)bitsetで保持して、スコア変化を V/64 回のループで計算できるようにしました。

https://beta.atcoder.jp/contests/hokudai-hitachi2017-2/submissions/1867989 の823行目あたり


メモリサイズを減らす(影響度:☆☆☆)

メモリアクセスは遅いです。

プログラミングにあまり慣れていなかった頃、「exp関数遅いし、細かく離散化してテーブルに入れておけばアクセス1回で値を引けて速くなるんじゃないの」と思ってやってみて、逆に遅くなったという経験をしたことがある人はそこそこいるんじゃないでしょうか(僕はあります)。

できるだけ使っているメモリがキャッシュに乗るよう、でかい配列はデータ型をコンパクトにします。

第1回では、元グラフでの辺の重みを保持する500*500の配列が大きかったので、はじめint32_tで持っていたのをuint8_tにしました。これだけで1割くらい速くなった記憶があります。

ただし何でも詰め込めば良いというわけでもなく、値が最大で15なのをいいことに1要素4bitで詰め込もうとしたら、今度は大幅に遅くなりました。さすがに自前でマスクしてシフトして、という処理があちこちに入るとそのオーバーヘッドの方が重かったようです。

状況によっては、頑張って詰めた方が良い場合もあるとは思います。



座標を1次元に潰す(影響度:☆☆☆)

普通はフィールドのデータは field[x][y] で持つと思いますが、座標を1次元に潰して field[(x << 6) | y] で扱うと速くなりました。

座標をxy別々に扱わずに済んで、いろいろ簡略化されるからだと思います。

おなじみの

int DX[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int DY[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int DN[8] = {-65, -64, -63, -1, 1, 63, 64, 65};

になります。


番兵で条件判定を取り除く(影響度:☆☆)

盤面の端をはみ出たかの条件をif文で書く回数を減らせるよう、盤面を64*64分確保して、実際のデータはxyそれぞれ1ずらした位置に置き、外周1周分を番兵として使えるようにしました。


焼きなまし受理判定の枝刈り(影響度:☆☆)

exp関数は遅いので、スコア差分が圧倒的に悪くてほぼ受理されなそうなら、exp関数を呼ばずに棄却します。

bool accept(int score_diff) {
    if (score_diff >= 0) return true;
    double v = score_diff * temperature_inv;
    if (v < -6) return false; // 枝刈り
    return rnd.next_double() <= exp(v);
}

ループアンローリング(影響度:☆☆)

回数が固定されているループで、呼ばれる回数が多い箇所はループ展開します。

for (int i = 0; i < 8; i++) {
    int next_pos = pos + DN[i];
    // next_pos を使って何か
}

int next_pos = pos + DN[0];
// next_pos を使って何か
next_pos = pos + DN[1];
// next_pos を使って何か
(中略)
next_pos = pos + DN[7];
// next_pos を使って何か
}

また、必ず1回以上実行されることがわかっているループはwhileではなくdo-whileにする、とかもこれに含めて良いかと。

やり過ぎると命令メモリが増えることによりアクセス局所性が悪くなって遅くなっちゃいますが。


BFSで来た方向に戻る移動をしない(影響度:☆)

上でも書きましたが、第2回で同じ番号のノードの連結性の確認のためにBFSを使いました。

シンプルに書くと、次のようになります。

for (int i = 0; i < que.size(); i++) {
    int pos = que[i];
    for (int j = 0; j < 8; j++) {
        int next_pos = pos + DN[j];
        if (node[next_pos] == n && !visited[next_pos]) {
            que.push_back(next_pos);
            visited[next_pos] = true;
        }
    }
}

まず、各点で隣接するそれぞれのノードが自分と同じ番号かどうかを、1bitずつ計8bitの値で持っておきます。

すると、BFS内での同じ番号のノードかどうかのチェックが削除できて、隣接位置すべてを見るループも削減されて、次のようになります。

for (int i = 0; i < que.size(); i++) {
    int pos = que[i];
    int bits = surround[pos];
    while (bits) {
        int dir = __builtin_ctz(bits);
        int next_pos = pos + DN[dir];
        if (!visited[next_pos]) {
            que.push_back(next_pos);
            visited[next_pos] = true;
        }
        bits &= bits - 1; // 最下位bitをクリア	
    }
}

さらに、BFSでキューにpushしたときに、自分に戻ってくる側の移動は見なくて良いはずなので、それを教えてあげると、さらに少し速くなります。

for (int i = 0; i < que.size(); i++) {
    int pos = que[i]; // queに入っている値は、上位16bitが探索する方向の候補、下位16bitが位置を表す
    int bits = pos >> 16;
    pos &= 0xFF;
    while (bits) {
        int dir = __builtin_ctz(bits);
        int next_pos = pos + DN[dir];
        if (!visited[next_pos]) {
            int next_bits = surround[next_pos] - (1 << (7 - dir)); // 自分にすぐ戻る移動を抑制
            que.push_back((next_bits << 16) | next_pos);
            visited[next_pos] = true;
        }
        bits &= bits - 1; // 最下位bitをクリア	
    }
}

0〜N-1 の中から異なる2つをランダムに選ぶときのテク(影響度:☆)

ナイーブにやると次のようになります。

int v1 = rnd.next_int() % N;
int v2 = rnd.next_int() % N;
while (v2 == v1) {
    v2 = rnd.next_int() % N;
}

よく知られているテクとして、次のようにすれば乱数呼び出しが確実に2回で済みます。

(ただし分岐予測は効きにくくなるので速くなるかどうかは場合によるかも…)

int v1 = rnd.next_int() % N;
int v2 = rnd.next_int() % (N - 1);
if (v2 >= v1) v2++;

2017-12-02

[] マラソンマッチは役に立つ 18:29 はてなブックマーク -  マラソンマッチは役に立つ - TopCoderの学習のお時間


Competitive Programming Advent Calendar 2017 2日目の記事です。

近年のAdvent Calendar執筆ハードル上昇に対抗するため簡単な記事にします。

皆さんご存じのように競技プログラミングは役に立ちませんが、マラソンマッチやってるとたまに役に立つので役に立ったことを書きます。


人間を意識したコーディング

短時間コンテストでは自分でクラス作ったりすることはそんなに無いかもしれません。一方、マラソンコンテストで実装が重めのやつは1000行超える規模になって、ある程度は関心事の分離ができた構造になっていないと扱いづらく、なかなか死ねます。

また、整理されたコードを見るのは気分的にも良い。何度も同じコードを見ることになるのでこれは重要です。


計算量の感覚

短時間コンテストだと最悪計算量しか気にしませんが、実データで最悪ケースが来ることはそうそう無く「実際はどんなデータなのか?」を計測・分析して、実用上速いデータ構造・アルゴリズムを使うことになります。

プロコン以外のプログラミングでもこういうのが大事なところは多いかと。


ビジュアライザ

解答やテストデータの様子を確認するためにHTML+JavaScriptでツールを作ることはよくやります。場合によってはちょっとしたwebアプリ立てることも。


高速化

高速化やったところで最終的なスコアにほとんど意味ない場合も多いですが、わかっていてもついやりたくなっちゃうんだよね〜、ということを身をもって実感できます。

また、いざ高速化やるぞと取り組むときにはプロファイラ使ったりアセンブラ眺めたりして、これはこれで相当実用的な経験になります。


パラメタ最適化

マラソンマッチの終盤には、最適な答えを出すパラメタの探索をやります。これは機械学習のモデル作成でも課題となってくるところであり、ノウハウ知っておくのは良さそうです。

(僕はグリッドサーチしかやったことないですが…)

また、計算の実行にクラウド使うことも多いので「クラウド環境の活用経験あります!」と言えるようにもなりますね。


英語を利用する機会

英語に慣れなければという気持ちはあるものの、でも慣れていないので英語を実用で使う機会が得づらい、というスタートアップ問題がありますが、forumに書き込むのは自由なので貴重な機会になります。

他の書き込みを見ていると「文法無茶苦茶じゃねえか!」みたいな投稿がわりとあって勇気づけられることも。


まとめ

マラソンマッチをやろう!

2017-10-29

[][] TCO17 Onsite 20:44 はてなブックマーク -  TCO17 Onsite - TopCoderの学習のお時間


10月20日(金)


16時の飛行機で成田から出発。空港に着いたのは2時間弱前で、サンドイッチ食べるくらいの余裕はあった

こういう話があるので今後はもっと早く行った方が良さそう http://www.afpbb.com/articles/-/3148112?cx_position=34


12時間かけてワシントンまで行き、そこから乗り継いでバッファローまで。

乗り継ぎの間は1時間40分で、入国審査のカウンターが一つしか開いていなくて、列がなかなか進まず出発時間ぎりぎりだった。空港内をリアルマラソンしてなんとか(5年前と同じ…)


飛行機内では、機内誌を読んだりiPadで本を読んだり。仕事しようかとも思ってたけど、照明落とされるのでPCを開く気になれなかった。

機内誌にスタンディングデスクの広告が2つ載っていた。流行りか…。


現地時間の17時頃にバッファロー到着。Topcoderの手配でホテルまで送ってもらう。mugurelionutさんと一緒だった。

やっぱりホテルの部屋が一人には広すぎで落ち着かない。


ホテル近くのスポーツバーで夕食。サンドイッチやハンバーガーを頼んだところ、やっぱりアメリカンサイズのが出てきてワイルドだった。


10月21日(土)


朝食はホテルのバイキング。食べ物の種類は少ない。飲み物の種類が多く、持ち帰り用のカップがあるのは良い。


この日は夜にWelcome Receptionがあるだけなので1日オフ。chokudaiさんとりんごさんはナイアガラの滝に行っていたが、僕は体を休ませたいのと英語キーボード練習をしたいのとでホテルに残る。

持参したキーボードでAOJの軽い問題を解いたりしてた。

昼食はホテル近くのdomino's pizzaで。焼きたてのピザおいしすぎる…。


19時からWelcome Reception。会場はホテルとは別で、大学?研究所?のキャンパス。そこが今年のTCOのメインスポンサーでもある。ホテルから徒歩15分くらいで、シャトルバスも出ている。

バスがいつ来るかよくわからず、歩いて向かっているグループについて行った。


会場について参加賞をもらう。なんかノベルティ少なめだ。5年前に会った他のコンテスタントの人たちに挨拶する。

Marathon参加者の人たち、すでにデスクで各自準備を進めている。本来はコンテスト開始30分前からなんだけど、やっちゃっていいのかなあ…と思いつつ自分もやる。まあ、やることはそんなに無いのだけど。JDKが入ってなかったのでインストールしたくらい。英語版Windowsは普段使わないのでPATH通すのに手間取ったりしてた。


デスクの環境はこんな感じ。

f:id:tomerun:20171022082643j:image


MilaninさんがMM95の画像を表示していた。

f:id:tomerun:20171021201906j:image



10月22日(日)


朝は会場まで徒歩で行った。空気が気持ちいい(気温は東京と同じくらい)。

9時-19時でコンテスト。昼食として自席で食べられるサンドイッチを用意してもらえるのは大変ありがたい。

最初数分問題が開けなかったりしたけど、まあこういうのはよくあることなので慌てず待つ。

だいぶオーソドックスな問題だった。とりあえず問題を読んで、テスターのコードを読んでカスタマイズ(別プロセスではなく直接自分の解答を呼び出す・マルチスレッド化・出力に情報を追加)して、空解答を作って動かすまでが40分と、なかなか順調にいった。

10時間ではあまり難しいことできないので、基本的には近い所を取りに行くgreedy。それに評価関数の要素をいろいろ加えていく感じだった。ただ最後2時間くらいは、1位とはかなり差があったのに細かいパラメタ調整に終始することしかできず不毛だった。もうちょっと攻めるべきだった。

インタラクティブ形式でありつつ隠しパラメータがほとんど推測可能なので自分でシミュレーション可能という重要な特徴があるのだけど、それに最初気づいていなくてこの特徴を解答に取り入れることができず、残念。

やっぱり慣れないキーボードだとかなりタイピング速度が損なわれるので、次回は自分用のキーボードを持ち込もうと思った。


終了後は会場で夕食を取りつつAlgo Semifinal1を見る。

ホテルに戻ってからはTopcoderスタッフの方に連れられて2日前に行ったのと同じバーで軽く飲み。


10月23日(月)


さすがに前日は疲れたのでゆっくり目(8時半くらい)の起床。

一人で座って朝食を取っていたら、mugurelionutさんとmarek.cyganさんがやってきて、それからPaulJefferysさんも来て会話していた。途中からヨーロッパにおける政治事情の話になってまったくついていけず置物と化していた。

コンテストの問題についてとか、トピックが限定されていてなじみのあるものならまだなんとかコミュニケーション取れるのだけど…。


昼からナイアガラの滝を観に行った。会場からシャトルバスが出ており、25分ほど。

時間そんなにない&お金それなりにかかるということもあって、滝の下までは降りずに上を歩いて回っただけだけど、カナダ側は一帯が水しぶきで覆われていて、雨が降ってないのにずぶ濡れになる感じで満喫した。

f:id:tomerun:20171023145050j:image


帰りのバスの時間がわからず2時間待つ羽目になり、AlgoとMarathonの人は参加してね!と言われていたData Science Workshopには参加できなかった。


会場に戻り、UI PrototypeとDevelopmentのコンテスト風景を眺めた。みんなハッカソンガチ勢っぽい。使われているエディタが、Atom,VSCode,Sublimeなど様々に分かれていて、Developmentでは使われている言語も様々で面白かった。


10月24日(火)


翌日の飛行機が早いので、この日は早め(6時)に起床。

朝食後に会場へ。UI Design部門のコンテスト風景を眺めた。

このへんのコンテストの種類について書いておくと、こんな感じ。


あと、TCOブロガーであるgorbunovさんがたたずんでいたのでいろいろ話した。


午後からAlgo Final。りんごさんの応援をしつつ観戦する。

その後閉会式・結果発表。ニューヨーク州副知事が来ており、挨拶がいかにも政治家という話しぶりだった(ちなみに開会式にはバッファロー市長が来ていた)。


移動してバー的な店でclosing reception。

Nickolasさんにマラソン問題を作るときに考えていることについて聞いたり。

タコス食べたら相当おなかいっぱいになった。

f:id:tomerun:20171024195228j:image


10月25日(水)


飛行機が朝7時発なのでホテル出発が5時。眠い…

空港で軽い朝食を取って、まずはシカゴまで。

シカゴで4時間待ち。空港をうろついたりサンドイッチ食べたりだらだらしたりしていた。

その後成田まで13時間。本読もうとしたがなんかもう目が乾いてダメだった。半分寝ていた。


10月26日(木)


16時頃に到着。いったん会社に立ち寄って雑務やってから帰宅。

この日はまだ興奮してたのか6時間弱しか寝れなかったけど、次の日に13時間寝てしまってだいぶ疲れてたのだなあと。


また来年参加できるようがんばろう。もっとコミュニケーション取れるように英語も(生きていて英語使う機会がTCOしかないので、これを逃すと一生習得できない)。

2017-10-27

[] Marathon Match 95 CirclesMix 16:10 はてなブックマーク -  Marathon Match 95 CirclesMix - TopCoderの学習のお時間

https://community.topcoder.com/longcontest/?module=ViewStandings&rd=16959


1日目(木曜)


問題を読んだ


2日目(金曜)


テスターをカスタマイズ(いつもの)

  • マルチスレッドでのバッチテスト
  • 結果の出力を良い感じに
  • 問題パラメタを自分で指定できるようにする

3日目(土曜)


テスト画像をwikimediaからクロール

(イラストとか本のページとかの画像は弾くのだけど、基準に主観が入るので迷うのが多かった)

1000枚取ってきたけどそんなに要らなかったかな…


greedyに円を一つずつ置いていくのを実装

  • ランダムな位置・半径で円をたくさん作る
    • すでに生成したものと近すぎる円は生成されないようにする
    • 半径は徐々に小さくする
  • それぞれの円に対して、最適な色にしたときにペナルティがどれだけ減るかを評価
  • ペナルティ減少が一番大きい円を選ぶ
    • 選ばれたやつと重なるもの以外の円は保持しておいて再利用する

また、選んだ円に対して、位置と半径を動かす山登りを実装


4日目(日曜)


高速化色々、SSEも使う

円の最適な色を決めるために、円の内部のピクセルに対して中央値を取る処理が重いので、かわりに円の中心にある7*7の正方形範囲の中央値を使う、という大胆な近似を取り入れたり

最終的に、greedyフェーズでは各ターンで 10000/sqrt(N) 個の円を生成し、選ばれた円に 10000/sqrt(N) イテレーションの山登りを行った。所要時間は6,7秒くらい?


5日目(月曜)


まだまだ高速化


円を置いてしまった後に、時間いっぱい使って繰り返し山登りで改善するのを実装(高速化を頑張っていたのは、これをやる時間を作るため)

山登り対象になる円をランダムに選ぶと、評価のためにその円の上に重なっている円をすべて再描画しないといけなくなって受け入れられないほど遅そうで、そうならないよう1つめの円から順番にひとつずつ山登りした。

ピクセルごとに、未来側に円が何枚重なっているかと色の和を覚えておけば、再描画無しで評価できる。

  • まずN枚目〜2枚目までの情報を計算して、それを使って1枚目の円を山登りする
  • 未来側の情報から2枚目の円の寄与分を取り除いて、2枚目の円を山登りする
  • 以下同様

この問題は、とにかくいかに逐次改善可能な形に持って行くかが勝負だと思ったので、ここが一番の重要ポイントだった


6日目(火曜)


調整色々


前日実装したものが山登りになっていなかった(良い解になっても状態を更新しておらず、初期状態の近傍しか調べてなかった)という致命的なバグを修正


7日目(水曜)


パラメタ調整やる、が、ほとんど変わらず

AWSで36coreマシン借りて35スレッドでテストを実行したら、めちゃくちゃ遅くなってまともにテストできなかった。16スレッドに減らすと普通だったので、コア数もったいないがそれで。

原因は追ってないけど、テスターで画像を読んでるからだろうか?


やらなかったこ


  • はじめは画像を縮小して処理することで高速化
    • やったけど良くならなかった
  • 画像から円をパターン検出
    • seed=1を見るとそういうことを考えてしまいたくなるが、実装も実行もコスト高過ぎそうでやめた

結果


1位とだいぶ差があった。

最終日にしか提出しなかったのは、戦略のつもりではなくて、単に何度も提出するのがめんどいからです

2017-07-02

[][] TCO17 Marathon Round2 20:55 はてなブックマーク -  TCO17 Marathon Round2 - TopCoderの学習のお時間

https://community.topcoder.com/longcontest/?&sc=5&sd=desc&module=ViewStandings&rd=16928


準備フェーズ


とりあえず、感覚をつかむために次の2つの自明解を作った。

  • 毎ターン一番近い敵に攻撃
  • 990人まで貯まったら一番近い敵に攻撃

これだけでもそこそこ勝てている。前者が強い場合と後者が強い場合がだいぶはっきり分かれていて、勝ちやすいケースは前者が強くて、最終的に負けてしまうケースでは後者の方が強い。

これらをうまく組み合わせていく感じかなー、と考える。

スコアが順位ベースで決まるので、何もしない解に負けてしまうと大ダメージだからそれだけは無いようにしないといけない。


敵の方がPowerが高いことから、基本的には不利なんだけど、この不利を緩和したい。端数がたくさん切り捨てられるような攻撃をするといい、とかそういうのがありそう

…と考えていたら、6人以下で攻撃すると1:1でロスなし対消滅できて最もおトクであることに気づいた。速攻で連打するとそこそこ勝てるのは最初実装したやつで分かっているので、簡単に勝てるケースはこれをどこまで最適化できるかのゲームになるんだと理解する。

…で、そこではそんなに差がつかなさそうだからやっぱり難しいケースをどう賢くするかだなあ、という雰囲気になる。


モンテカルロシミュレーションやったりするのかなあと思いつつ、何やるにしても敵のパラメータ(power・attackT・locality)やTroopの行き先推定は必要なのでそいつらを実装していく。


実装フェーズ


そして実装していたら1週間経ってしまったので絶望する https://twitter.com/tomerun/status/864889052826288128

ついで、速攻ケースのシミュレーション+倒すbaseの順番での山登りを書き上げて、ある程度の高速化・パラメタ調整をやる。

この時点でまだ本丸(勝ちにくいケース)に手がついていないのに、もう2回目の週末が終わっていて絶望する https://twitter.com/tomerun/status/866298649680027648


とにかく、速攻で勝てないケースの戦略を作っていく。

とりあえず、全滅させられてしまう直前の逃避戦略を実装する。これはまあやるだけ

最序盤ですぐ倒せるところだけは速攻で倒しておくとして、基本は980まで貯めてから攻撃する。攻撃先をどこにするのかが考えるところ。

単純に一番近いところを攻撃するのは、すでに倒せるのが確定しているところに集まりすぎで損、というのはこれまでの結果から分かっている。

すでに倒せることが確定したbaseへは攻撃せず、他を狙うようにするとそれなりに良くなった。

あと、980貯まっていても、敵の攻撃が向かってきていて、攻撃で人数が半分になった状態では全滅させられてしまう場合は、攻撃せず待つようにしたり。

ここまででもう終了前日になってしまったので、全然細かい調整できてないんだけど観念して提出したら93万点とか出てびっくりした。

最後に、他の敵から攻撃されづらい位置にあるbaseを優先的に攻撃する、というのを入れようとしてみるが、良くならなくて終了


ビジュアライザ

f:id:tomerun:20170702204626p:image


カスタマイズした点は以下の通り。

  • 早送り・巻き戻し可能に
  • growRateに応じてbaseの形を変える
  • baseのindexも表示できるように(デバッグ用、普段はoff)
  • playerごとの合計人数を表示

そのほか


  • 今回は実装が難しそうで、そこまで高速化勝負にはならなさそうだったのでJavaを使った。結果的に、やっぱり実装がボトルネックだったのでこれは正解だった
  • 仲間同士で人数を1箇所に集中させて成長速度を増やすのはちょっとやってみようとしたが、あまり効果が感じられなくてやめた
  • 敵のlocalityも推定した(離散化してベイズ推定)けど結局使わなかった

結果