情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

天下一 Game Battle Contest 2020 に参加しました！

天下一 Game Battle Contest 2020に参加しました！
ここでは、その時の自分の挑み方を解説していきます～

天下一 Game Battle Contest 2020 とは？

天下一 Game Battle Contest 2020はKLab株式会社が主催する対戦型ゲームAIコンテストです。
今回のゲームは以下のようなルールになっています。

1. 20x20の大きさを持つ盤面の各マスに、1以上1000以下の価値が書き込まれている。
2. プレイヤーは正方形の領域を選んで、その領域内のマスを取得することができる。
この時、その領域の一辺をnとすると125(n+1)^2ミリ秒待機する必要がある。
3. プレイヤーの持っている領域の各連結成分ごとに、その連結成分の面積\times \alphaのスコアが得られる。
ただし\alphaは領域内における各マスの\frac{マスの価値}{取得人数}の最小値と定義される。
4. ゲームは1回60秒で、14:00から18:00まで計240回行われる。
なおこの際、最初の60分はスコアに1倍の補正が、次の60分は10倍の補正が、次の60分は100倍の補正が入り、最後の60分は1000倍の補正が入る。

本番での戦略

開始前

Practiceを用いて、実際の本番でAPIを叩く練習を行います。
まずAPIを叩いて操作を行えるか、逆にAPIから情報を得ることができるかなどをまず検証しました。
次に、自動で待ち時間だけ待機するプログラムなどを書きました。
次にtokenとgame_idを指定すると自動でAPIを叩き、その結果をカスタムした標準入力(競プロ勢なので、標準入力は自作の高性能なInputStreamを持っているのです)で受け取れるようにして準備完了です。

14:00 - 15:00

まずはゲームルールを読み込み、どんな戦略が良いか考えます。
とりあえず、スコア式を見ると連結成分の大きさが大きいと損をすることが分かるので、市松模様かなー？と最初の方針を立てます。
今後のことを考え、スコア計算関数など汎用性が高いものを作りつつ14:50頃に完成、動かし始めます。30位前後。

15:00 - 16:00

まずは色々検証、市松模様の大きさを1x1や2x2など変えてみたり、比較実験のために市松模様ではない貪欲アルゴリズムと変えてみたり。
この時、元のコードを残しながら新しいアルゴリズムに変えていて、各コードは関数として切り分けています(ai1(), ai2()など)。
盤面を観察していると、2x2の時は最終的に50個の市松模様領域全てを得ることができますが、スコアとしては低いことが分かります。
スコア的には1x1の方が良かったので、基本的に1マス取りを繰り返す方針で試しますが、だんだん順位が悪化していきます。

16:00 - 17:00

ある程度の人数が取得していてかつ得られるスコアが高いマスは、取ってもほぼ損をしません。
そこで、残り時間が多いほど、取るマスについて同時に複数人が取ったと仮定して貪欲にマスを得るアルゴリズムを書きます。
このアルゴリズムの方が市松模様より順位が高くなったので、市松模様を捨て貪欲に近いアルゴリズムを検討していきます。
他の人と被ると損なので、例えば最大スコアじゃなく10番目位に良いスコアの場所を取ってみたり、やっぱり2x2を取るように変えてみたり。
この時点で30位くらい。

17:00 - 17:15

本当はここからAIを変えるとスコアのロスが大きいけど、まだ入賞できそうにないので改善を決意します。
ソースコードをよく読むと気になった点が3つあったので改善。
1. 最後の10秒は3x3も加え、とにかくスコアを貪欲に稼ぐように変更。
2. 実行ログを見ると最後の1秒で3x3を投げようとしてゲーム終了と告知されたりしていたので、意味のないクエリを投げないように変更。
3. よく考えたら1x1は3x3を1回置く間に4回も置けるわけで、これを加味し忘れていたので貪欲のスコア評価にその領域を取る時間の逆数を掛ける演算を追加。
特に3番の改善の結果は大きく、改善直後から安定して20位以内に入れるようになりました。
f:id:CuriousFairy315:20200829183116p:plain:w300

17:15-18:00

ここからは、AIを書き直すときのスコアロスの方が痛いので後は座って待機。
17:20頃では26位だった順位も少しずつ伸びていき、最終順位は16位と無事に賞金を得ることができました！！
f:id:CuriousFairy315:20200829183314p:plain:w300

全体を振り返って

ゲームAIコンテストはまだ全然経験が浅く、正直言ってかなり手探りの状況から開始しました。
速く置けるけど低スコアな操作には下駄を履かせる、とかは明らかにやるべき操作なのに、これに気付くのが3時間以上経っているなんてのは完全に経験不足から起きたことで、これは対策可能なものです。
最上位の人は直近のゲームの最終盤面を機械学習させて最適な取り方を決めているらしいですし、こういった知見はこれから少しずつ集めてもっと強くなっていきたいです。

KLab株式会社様、今回は楽しいAIコンテストをありがとうございました！
そして参加者の方々、対戦ありがとうございました。楽しかったです！