CodinGame Spring Challenge 2022 参加記

CodinGame Spring Challenge 2022 で優勝しました！

www.codingame.com

ゲーム内容

tsukammo さんが翻訳してくださってます。ありがとうございます！

https://tsukammo.hatenablog.com/entry/2022/04/22/010522

最終Bot内容

防衛2人 : ルールベース

攻撃1人 : chokudaiサーチ

防衛

ルールベースで頑張る

4つの役割と割り当て

拠点を守る
- 拠点内から半径5000に入ったモンスターを攻撃する。倒しきれないならできるだけ拠点に引き付けてからWINDする。できるだけ引き付けたほうがまとめて攻撃できるのでmana効率いいのではという理由。
邪魔する
- 相手ヒーロー1人を追い回す。もう一人が近づいてきたら自身にSHIELDや相手にWINDを放つ（ダブルWIND対策）
自陣付近警備
- 自陣付近(4000,4000)に来たモンスターを攻撃する。自陣からあまり離れない。
モンスター発生源付近警備
- モンスター発生源付近に来たモンスターを攻撃する。発生源からあまり離れない。発生源は自陣に近い2か所。

上の役割の方が優先度が高く、相手ヒーローの位置とモンスターの位置によってどの役割が必要かを決める。

複数のヒーローそれぞれにどの役割を割り当てるかは、割り当てた際の目的地までの距離2乗が最小になるのを総当たりで求めた。

「拠点を守る」と「邪魔する」はそれぞれ1人まで割り当てる。相手に攻撃されているときはこの割り当てになる。

緊急行動

相手にこの行動をされたらまずいと判定し、役割に関係なく行動する。

モンスターにWINDされることで拠点にダイレクトシュートされるならそのモンスターをWINDで飛ばす
モンスターにSHIELDされることで拠点までに倒せなくなりそうならそのモンスターをWINDで飛ばす
（これ欠陥があって、SHIELDの方がWINDより射程長いので間に合わないことが多い）

攻撃

15ターンのchokudaiサーチ

目的行動単位で分岐するようなゲーム木探索。目的の行動を達成するまでその行動を取り続けて分岐しないような感じ。なのでターン数のわりに分岐は少ない。

相手の行動は自分の防衛処理をそのまま適用する。

目的行動リスト

敵陣付近に移動する
敵陣側のモンスター発生源付近に移動する
モンスターのところまで移動する
モンスターにダメージを与えないギリギリの場所に移動する
モンスターから半径1100の位置に移動してWINDする
モンスターに近づいてWINDする
モンスターに近づいてSHIELDする
モンスターに近づいてCONTROLする
相手ヒーローをCONTROLする
相手ヒーローにWINDする
自身にSHIELDする

モンスターから半径1100の位置に移動するのは以下の図のようなWIND2連打狙い。

評価値

優先度順

ダメージを与えたターン数が早いほど良い
相手に与えたダメージ量が多いほど良い
モンスターができるだけ相手拠点近くまで到達できるほど良い
- モンスターのhpが0になるかWINDをかけられる場所を到達点とする
自分のmanaは多く相手のmanaは少ないほど良い

評価値1,2はダメージ量よりも速さを重視するのでこの優先度順。ダメージ量を優先すると見えていない敵ヒーローに防がれることが多かった。

評価値3は最終的な行動を決めるときには無効にする。半端に攻撃してダメージを与えられないなら攻撃せずmana温存した方が良いでしょうという理由。

その他工夫

mana50たまるまでは攻撃に呪文を使わない。
ただし、前ターンでダメージを与える行動を見つけていれば制限しない。
入力で相手ヒーローの位置が来ない場合はその場から動かさないが、3ターンの間見えていないなら存在しないものとする。
モンスターを1匹見たらそのIDからHPと出現ターン数が分かり、座標と移動方向から相手プレイヤーに妨害されてるかどうかも判断できる。妨害されてなければ対称の位置にモンスターを追加。
6ターンの間見えていないモンスターは存在不定状態とし、拠点に到達してもダメージを与えられないものとした。これをしないと既に倒されているモンスターが相手拠点に到達するのを期待して近くの敵ヒーローにCONTROLかけたりしちゃう。
存在不定状態でもmanaは貰えて、mana目的で近づく行動により索敵っぽくなる。

だめだったこと

最初ビームサーチをしていたが、行動候補がなくなって時間いっぱい探索できなかったり、深さがほとんど探索できない場合があったりで安定しないため、chokudaiサーチに切り替えた。
見えていない敵ヒーローの位置をこちらの防衛コードで予測したり、相手の拠点側にいるものと仮定して探索していたが、それだとダメージが与えるのが難しくなるためか攻撃あまりしてくれない。
いっそ存在しないことにしたほうが、とりあえず攻撃行動を取ってくれて、相手が見えたタイミングでそれを突破する行動を探索してくれるので良かった。
攻撃2人でWINDを打つ戦術が台頭してきて、これはまずいと思って攻撃2人でchokudaiサーチも試してみたが探索量が足りず良い動きをしてくれなかった。実装を大きく変える必要があるため攻撃2人の戦術は諦めた。

ツール類

ログ取得ボタン

画面上部に対戦結果のログをコピーするボタンを作った（Chrome プラグイン）

毎ターン入力情報をログに出しておいて、それをローカル環境で再現するために使用した。

ログの取得コードはjavascriptでこんなんでできた。

var elements = document.getElementsByClassName('stderr');
var content = "";
for (var i = 0; i < elements.length; ++i) {
  e = elements[i];
  content += e.innerText + "\n";
}

ビジュアライザ

細かく対戦結果を分析するために作成。

射程や移動先の場所等、ゲーム画面では確認できない情報を可視化できた。chokudaiサーチで予測された将来の状態も可視化できて良かった。

ローカル対戦環境

公開されている対戦サーバーのコードを使い、ローカルで大量に対戦する環境を作った。
相性ゲーなので勝率はあまり役に立たなかったが、存在しない相手にCONTROLしたとか、manaが足りないのに呪文打ったとかのログが出るのでバグチェックに使えた。

コード長削減

コドゲではコード長制限が厳しいため、コメントや空白を自動削除するツールを作ってある。#includeファイルを展開する機能、#if/#elseで無効になるコードの削除機能もある。（需要ありそうなので公開したいけど、使用上の制限が多いのを何とかしないと……）
これを使ったうえでコード長制限に引っかかってた。あとやれるとしたらシンボル名を短いのに書き換えるとかかな。

感想

防衛のルールベース部分を考えるのがつらくて、最終日まで雑な実装になっていた。
さすがに勝てなくなってたので急いで実装しなおしでバグりまくった。作業優先度が良くなかったなあ。

過去に似ているゲームを実装していた。
SoulSnatchers（旧CodeBusters）
https://www.codingame.com/multiplayer/bot-programming/soul-snatchers

マップサイズ16001x9001で霧があって複数エージェントと類似点が多い。このときやってたビームサーチの考えとかベクトルの計算処理を流用できた。
（このゲームもルールベース色が強くて実装辛かった記憶）

Nanaedaさんとの対戦成績が極端に悪くて勝率21%しかない。3人防衛による長期戦&後半SHIELD連打で手も足も出なかった。最終日に気づいたけど対策できなかった。防衛3人だとさすがに攻撃1人じゃ崩せそうにないので攻撃人数増やすとか、長期戦用の動き考えるかかな。

戦術相性とか特定の相手への対策が重要なゲームなので後だしが有利で、最終日に有給とってギリギリまで調整できたのが良かったと思う。（あといろいろ試すために提出を何度もしていて潜伏みたいになってた。どうなのかとは思うけど……）

ログ取得ボタンは今回初めて実装して世界が変わった。
今まではターンをまたいだログ情報の取得の仕方が分からず、最終ターンにまとめてゲーム開始時からのログを出すようにしていて、1ターンのログ長制限に引っかからないように情報の圧縮に苦労していた。javascriptならこんな簡単にできるんだ。

過去のゲーム経験が活かせたこと、ツール類の充実で有利取れた感じかな。

bowwowforeachの日記

競技プログラミングをします。主にヒューリスティック/マラソン/ゲームAI。