天下一 Game Battle Contest 2021 Autumn
KLabさん主催のゲームAIコンテスト「天下一 Game Battle Contest 2021 Autumn」に参加して、51位でした*1。 思ったことややったことについて書いていきます。
問題概要
一辺の長さが30の正方形内で、5台の資源回収車を操作して、フィールド内に生成される資源を収穫するゲーム。
ゲーム操作はWebAPIへのリクエストを通して行い、全プレイヤーが同一盤面上でプレイします。 ゲームはコンテスト時間中ずっと進行します*2。
資源には出現期間と重みが割り当てられており、出現期間中に同一座標に資源回収車を置くと、
(重み) / (その資源を収穫している全参加者の資源回収車数) が1msごとに得られます。
回収車の移動は (ユークリッド距離) * 100 (ms) かかります。
資源は3種類あり、その中で最も総回収量が少なかった種類の総回収量で勝敗が(概ね)決まります。
詳しいルールはこちらです。
過去回からの変更点についての所感
過去のコンテストだと、１時間ごとに獲得スコアが大幅に*3増える、かつ途中で実行中断するとかなり不利という形式だったため、最後の１時間は再デプロイが実質出来なかったのですが*4、 今回のコンテストでは中断がさほど不利にならないのと、テスト実行環境が提供されるようになったことで、コンテスト終盤までプログラムが変更できる形式になっていました。
個人的にはかなり良い改善に感じました。
やったこと
大筋は、サンプルコードの無難(?)な改修をしてたって感じでした。
サンプルコードはこちらで提供されていて、
移動先に資源が無い回収車を、ランダムに選んだ出現中の資源へと移動させる ただしこのとき２台以上の回収車が同じ資源を選ばないようにする
というものでした。
これに対して、
- 近くの資源を取りに行く
- 回収対象資源が消えた直後に次の対象に向かうように予約移動を入れる
- 到着するまでに消える資源は取りに行かない
- 出現 500ms 前の資源も選択候補に入れる
- 複数回収車が同一資源に向かうことをある程度許す
といった変更を加えました。
ゲーム終盤は、上のルールに沿いつつ種類ごと最小値が最大になるように、資源選択を手動調整してました。
コードはこちら。
所感
過去コンテストの所感的に、無難なことをやり切るだけでもコンテスト時間が短いのでそこそこ良い順位が出せるって感覚を持っていて、実際そうなったなって感想でした。 賞金圏内目指して、もうちょっと思い切ったことを試みても良かったのかもしれないなあとかをちょっと思いました。なんか目標がふわっとした状態で出てしまっていた感はあったり。
問題把握するまでに結構時間掛かっちゃったのと、考察があまり詰められず、問題の本質的なところが何なのかは結局分からないままでした*5。
サンプルコードを使いたい都合で、普段使いでない Python をこのコンテストでは使っているのですが、ここが実装速度の遅さや、自作ライブラリが無いからこの方針は辞めとこうを産んでいて、まあまあ良くない気がしているので、 次回は事前準備をして、普段使いの Rust を試験的に使ってみようかなとかをチョット思ってます。 ただ、この手のアドホックなJSONパースを良い感じに扱うライブラリが提供されているのかはまあまあ怪しい気はしていたり。
上位解法をざっくり見ての感想
資源が出現した瞬間を狙うのが有力だったっぽいですね。 ２位のchokudaiさんのこの考察とかがかなりしっくり来ました。
おつでしたー。肝は「大体の人がサンプルソースだから、サンプルソースで人が集まらないところを狙う」という部分。具体的に言うと「出現直後」にはサンプル軍団がいないので、そこを獲得するのがめっちゃ効率に寄与するのかな。 #klabtenka1
— chokudai(高橋 直大)🍆 (@chokudai) 2021年9月23日
終わりに
順位的にはもう一押し行きたい気持ちでしたが、楽しかったです（小並）。ビジュアライザがリッチだとテンションが上がりますね。
