TCO2017 Marathon Round2 "AbstractWars"

参加しながら考えたことの源泉かけ流し。

1日目

所感

いや 2 月にあった CodinGame の Ghost in the Cell まんまやないか~い。

f:id:iwashi31:20170512002939p:plain

真面目にやったつもりだったがあまり良い順位が取れなかったコンテストなので、ちょっとブルーな感じ。

それにしても、Round1 に続いて Round2 でも似たような実装やったことある問題が出るとは…。

Ghost in the Cell との相違点

  • ボムや生産性向上とかのスキルがない。
  • 基地にいるユニット数が多いほど生産性が向上する。
  • 一つの基地のユニット数に上限がある。
  • 敵の troop についても行き先が(ある程度)分かる。
  • 最終的な勝ち負けだけでなく、スコアの概念がある。

しばらくはビジュアライザ内蔵 AI に勝つことを目標に進めることになるけど、最終的にはスコアの最適化もしないとだろうなぁ。

実装したこと

とりあえず「半分投げて倒せそうなら投げる」「ユニット数が 800 を超えたら近くの敵の基地に投げる」を実装してみたものの、下手したらサンプルより弱そう。
どの基地もだいたい同じペースで数増えてくし、speed=1 とかだと距離が遠すぎて倒せる判定が立たないのかな。

あと、同じ基地に大量のユニットを同時に投げて、上限を突破してロスしがちに見える。
ユニット数上限あるのなにげにつらそう。

f:id:iwashi31:20170512004738p:plain

ひとまず、

  • 自分がどこに何ユニット投げて、いつ到着するのかを覚えておく。
  • 敵のユニットが目指す先を予測する / 敵のユニットが届くことを考慮する。
  • 複数の基地で連携して攻撃。

あたりはやらないとだ。重い…。

2日目

所感

提出後スコアの計算方法の誤読に気付く。
competitor ってそのゲームで戦った AI のことかと思ってたよ。

…, you get 1 point for each competitor you beat on this test case …

あと、昨日は自分の基地ベース(自分の基地 i がどこに投げるか)で考えてたけど、敵の基地ベース(敵の基地 i にどこから投げるか)を考えたほうが復数基地で連携して攻撃しやすそうかもしれないとふと思った。

なんかいつもの MM はコアなアイデアを一つ考えてそれに肉付けしていくって感じだけど、今回はいきなりやることが多くてつらいなぁという感じ。

実装したこと

あまりに気が乗らないので、ひとまず集計用のなにかをシェルスクリプトで書く。

scores=()

for ((i=$1; i <= $2; i++)); do
    score=`java -jar tester.jar -exec ./a -seed $i -novis | sed -e "s/Score = //g"`
    scores+=($score)
    echo "Case #$i: $score"
done

: > score.txt
for score in ${scores[@]}; do
    echo $score >> score.txt
done

clip < score.txt

これを ./run.sh 1 5 みたいな感じで実行すれば、seed 1~5 のケースが実行された後、それらのスコアがクリップボードにコピーされる。

後はそれを Excel にペタッと貼って適当に管理。

f:id:iwashi31:20170512210611p:plain

3日目

実装したこと

  • 自分がどこに何ユニット投げて、いつ到着するのか覚えておく。
  • 各(敵の)基地について、近くの自基地から攻撃して潰せるなら攻撃する。

というのを実装した。
手元で 20 ケース試してみたところ初日に書いたやつよりは強そう。
てことで提出。

f:id:iwashi31:20170513203535p:plain

サンプルより弱いらしい。マジか。

f:id:iwashi31:20170513204236p:plain

マジだった。
パッと見た感じ 1000 溜まった基地をそのままにしてるのが良くなさそうだ。

1000 溜まる前にひとまず投げる先としては…どうなんだろう?
一番近くの自基地とかだと 1000 溜まる基地同士で投げ合いそうな気がする。

いや、自分の Troop については何ターン後に届くのか管理するようにしたんだから、「投げても任意ターン後に 1000 を超えないような近くの自基地」とかでおkかな。
敵基地に投げたほうが良い場合についてはまた今度考えることにする。

あ、あと倒した際にユニット数がちょうど 0 になって数が増えない基地がポツポツあるみたいなので、倒す際に若干マージン用意したほうが良さそうだな。

f:id:iwashi31:20170513211808p:plain

→マージン用意したらスコア下がった。なぜ…。
→敵の power に倍率がかかるのを忘れてた。とりあえず敵の power は *1.2 するようにしたらちょっとスコアアップ。

この後、ひとまず 950 超えたらランダムに投げるようにしたらサンプルには勝てるようになり、30 位 / 43 位(スコア:296666.67)。う~ん。

もういっちょ、(Troop を受け取ったりして)次のターンに 980 を超えそうなら放出するようにしたら 30 位 / 46 位(スコア:354222.22) に。山登りはできてるけどう~ん。

4日目

所感

敵の power の倍率、公開されてないからとりあえず *1.2 にしてたけど、ユニット同士がバトったときの増減から倍率推測できることに気が付いた。めんどいなぁ。
ちなみに、各基地の growthRate の推測については昨日時点で実装済みである。頼むから素直に情報を渡してくれ。

growthRate 高い基地を重視するとかした方が良いのかな?
ユニット数増えると growthRate の恩恵下がっていくし後回しで良いかもしれない。分からん。

スコア計算方法を読み直し、移動中の Troop もスコアの対象になることに気付く。
絶滅しそうになったら一番遠くの基地に全放出することでちょびっとスコア伸ばせるな。

一番割合高い敵を優先度高めで叩くとかした方が良いかも。

実装したこと

気まぐれで攻撃時連携をしないように&倒したときのユニット数が 300 以上になるようにしてみたところ、最高スコアがいっぱい出た( ↓ 画像一番右)。
f:id:iwashi31:20170514043305p:plain

殲滅可能なときは早々に攻めたほうが良さそうなので、初期状態により殲滅できそうフラグみたいなのを立ててパラメータの変更をする。
→ 27位 / 47 人(スコア:474565.22)。

殲滅可能なケースは少ない気がするので、殲滅不可能そうなケースでできるだけ生き残ることを考えよう。
一旦敵への攻撃は一切やめて、初期の自基地間で投げあいまくるようにしてみる。
→ 415625.00 から 475208.33 へ。

first submit で 500k 点↑出してる人たくさんいるし、何か見落としてるんだろうなぁ。

980 超える分を自基地に投げる → 自基地に最も近い敵基地に投げる に変更で新たに殲滅可能となったケースが 40 ケース中 6 ケースも増えた。やったね!
→ 444509.80 から 519215.69 へ。
今のところ殲滅できるケースが 3 割くらい。この割合を増やすべきか。

この後敵の powerRate を推定する処理を書いて、20k 点ほどアップ。刻むなぁ。

ここまでのスコア推移

一応一定のペースで伸びてはいる。
f:id:iwashi31:20170515012340p:plain

5日目

所感

敵の Troop の行き先予測について

行き先予測 → 守りの手段 というイメージだったので後でいいやと思ってたけど、敵が他の敵を倒した直後は占領しやすいはずなので、攻めの手段としても強力だなぁということに気が付いた。
Troop の座標格子点に近似されるからつらいよな~と思ったけど、テスタの実装は配られてるわけだし、一直線上とかじゃない限り行き先は特定はできるのよね。(まぁ Troop が密集してると厳しそうだけど)
そのうち実装しよう。

MM、つらい

みんなつらそう。

marek.cygan 氏潜伏の影響

現時点で 930625.00 と圧倒的だった marek 氏が 0.0 を出したことで、僕のスコアが 10k 点ほど上がった。
現時点での参加人数が 65 人程なので…ということを考慮しつつこねこねすると、僕が何ケース marek 氏に勝ってたのか導出できそう。

marek 氏全勝ちだったなら 15k 点程上昇、僕が全勝ちだったなら 15k 点程減少するはずので、marek 氏の勝率は 83% くらいか。
スコア的に marek 氏の平均勝率は 93% なので、目を離していた間に他の人が提出したことによる誤差を考慮しても、僕がやや無理して高得点狙ってる傾向にある気がする。

ん!これ、こういう考え方ができるなら、自分が潜伏すれば各参加者に対する勝率特定できちゃうのか。

実装したこと

残業で体力が残ってないので、パラメータを適当に弄って 531349.21 → 547380.95。

その後軽い改修を色々試みるも全然スコアが上がらずほんとつらいので、いざという時用に取っておいた「絶滅寸前に一番遠くへ全部投げて時間稼ぎ」を早くも実装してしまう。
ケース平均 0.8 点くらい安定して上昇した。スコア上昇することが約束されてるって気持ちい~。
submit してスコアは 557578.13 → 576406.25。ン!そんな上がんの!?
絶滅確定なケースだと結構ギリギリの戦いになってるのだろうか。

6日目

昨日実装した悪あがき機能を強化しようとリファクタリングを行ったところ、(1000超えによるものとは別で)敵基地を攻撃するメインと言っても良い機能を誤って排除してしまい、結果としてスコアが伸びてしまった。マジか。
550845.07 → 588873.24。

悪あがきの閾値を「ラスト 1 基地」→「ラスト B/8 基地」に変更し、603750.00 → 645555.56。

下図のケースがなんか好き。
①(左上) 絶滅しそうになったので
②(右上) 悪あがきで一番遠くに移動する
③(左下) 量が量だけに移動先を占領できてしまい
④(右下) もう一度一番遠くへ移動する
f:id:iwashi31:20170516222345p:plain

…好き、というか、これを極めればかなり強みになる気がする。
敵の攻撃パターンは読めるので、その敵の攻撃と逃げた Troop の到着が被らないよううまいことやれば、きっと伸びるに違いない。
ちょっと実装重いけど!

各敵の基地に 2000 以上投げないとかでも良い気がするな。まぁまた明日。

7日目

悪あがき時、一箇所に送りまくると寄ってきた敵と潰し合ってアレかな~と思って一箇所に送る数に制限をかけるも、伸びず。

悪あがきは一旦置いておいて殲滅可能なケースを伸ばすかなぁと、殲滅可能そうな場合には攻撃するように戻したら 1 ケース平均 3pt 程度伸びた。
…と思ったら本番スコアは割と下がった。626410.26 → 615384.62。
提出前後で上位のスコアが一切変動してないので、多分もっと殲滅スピード極めないと上位には(ケースごとですら)勝てないってことなんだろう。

8日目

もはや敵の動きをシミュレーションするしか伸ばす道がない気がしてきている。
実装する元気は、少なくとも平日はない。

ちょっとした改修をしてスコア増減の平均がプラスなら提出をしてみてるけど、やっぱり本番スコアは下がってしまう。
スコアが下がるケースがあるのは厳禁か。

と思いながら小改修を続けると、悪あがきモードのトリガを「自基地の割合が B/8 以下になる」から「自分のユニット数の割合が (全ユニット数) / ((Player数) + 1.5) 以下になる」に変更したのがヒットしてガッツリ上がった!提出だ!
608395.06 → 575308.64。?????
他人のスコア、提出前と提出後を比較すると概ね下がってるんだけどなぁ…。 

不穏な感じがしてきたのでここで初めて Example Test を投げてみるが、まぁ特に TLE してそうな感じもない。
一番時間かかってるケースが 331ms でウケる。

キューでの他の人々の進捗を見てるとどうも時間いっぱい使ってそうに見えるんだけど、何してるんだろうなぁ…。

9日目

昨日の何故か本番スコアが下がったケース、他の参加者の得点増減ちゃんと一覧すると、自分より上位は平均 -250pt ぐらいのマイナス、自分より下位は平均 +220pt くらいプラスって感じだった。
なるほど、下位には基本勝ってるからスコアが伸びたケースがあってもあまり意味がなくて、逆にスコアが下がったケースだけが勝率を(下方に)変動させ得るというわけだ。
上位に行けば行くほどいかにスコアを下げないかが問われるのか。ムズい。

することが思いつかないので、0 点 submit をして各参加者との勝率を計算してみることにする。

f:id:iwashi31:20170519221523p:plain

わかったことは、

  • サンプルに負けるレベルのやらかしが 3 ケースほどある。
    • つまり、このやらかしを解消すれば 18000 点くらい稼げるはず。
    • そうか、自分の強みを伸ばすより弱みを潰す方がスコアが伸びるんだ。
  • 上位は上位でも得意な相手と苦手な相手がいる。
    • 速攻が上手な人と悪あがきが上手な人?

手元で 80 ケースサンプルと比較して負けてるのが 2 ケース。どちらも殲滅可能パターンだ。
殲滅速度を上げるべきか。

10日目

JJUG CCC と ARC と TCO があったので何もできなかった。

11日目

AM 3:05 からのこどふぉに出たら一日が崩壊した。一回休み。

12日目

9 日目には 25 位くらいまで浮上してたものの、35位↓まで下がってしまった。
そりゃ土日サボったらね。

計算時間はたっぷり余ってるが、シミュレーション実装する時間はないので、小手先の改修をひたすらやってみている。

もう後 2 日ということもあり、コミットメッセージが適当になってくる。
f:id:iwashi31:20170522233841p:plain

手元での平均スコアそれなりに上がったのに本番で -100k 点くらいなるの勘弁して欲しい。

13日目

イデアも気力も底をつきた。

14日目

同上。

おわり

暫定の最終順位 48位 / 104人。う~ん無念。
TL を見た感じ、上位の人は敵の動きのシミュレーションやってるな~(当然)というのと、どうも速攻が思いの外有効だったようだ。

レートは下がりそうな気がするけど割と楽しめたので良かった。
Round3 もがんばるぞい!