CodinGame Spring Challenge 2022に参加しました。(常設名:Spider Attack)
いつものゲームAIです。
結果はLegendリーグ156/400位で、全体156/7,705位でした。あと日本人28/445位。
ゲーム概要
ルールはツカモさんによる翻訳記事があるのでそちらに丸投げします。*2
簡単に要素を挙げると、
・非グリッド(厳密には巨大グリッド)
・不完全情報(戦場の霧)
・2P×3キャラ(+中立ユニット)同時着手
という探索絶対殺すマンです。
最終的にやったこと
ルールベース。プレイヤー番号ごとに位置を考慮するのは大変なので、入力を反転させて常に自分が左上プレイヤーだと思い込むようにする。
80ターンまでマナを稼いで、攻撃2:防御1に分かれる。
マナ稼ぎ
モンスターの出現位置は固定(出てくる角度でちょっとブレるくらい)なので、その位置に居座る。これで基本的には拠点にモンスターを近づけずに稼ぐ。倒しきれずに拠点に向かいそうなモンスターはCONTROLで出現位置に跳ね返す。敵に先に喰われることが少ないので、最高効率かはともかく安定する。
この時拠点に向かうモンスターが視野外で見逃してしまうのが痛いので、拠点に向かうモンスターのspawnerから遠い順>拠点に向かわないモンスターのspawnerから近い順で攻撃しに行くようにした。
防御
拠点に一番近いモンスターを追いかける。追いつく前は追いつくターン*3から最短ルートを計算する。追いついた後は角度と速度を適当な分解能で全探索し、後続モンスターの巻き込みや敵ヒーローからの逃げで貪欲に移動する。
間に合わない場合のWIND、操られたことがある場合のSHIELDなどもルールベースで撃つ。あとは拠点外のモンスターを画面外KBで消したり。
マナ稼ぎ時には他のヒーローが下側からの侵入を防いでくれるのでその前提で守るが、下側のヒーローが攻撃に出るとホイホイ侵入されて不安定になる。やられる前にやろう!
攻撃
複数の攻めに同時対応できない状況を目指した。
・SHIELD付きモンスターでゴールを狙い、駄目でも相手ヒーローを奥に押し込む。*4
・相手ヒーローをCONTROLで引きずり出す。*5
・2人同時WINDで4400飛ばして直接ゴールを狙う。1ターン前に1人WINDで+2200も狙う。
CONTROLとWINDは相性が悪いかも?
リーグ別やったこと
Wood2, Wood1
待機位置を設定して、拠点内に敵がいれば倒しに行く。いなければ待機位置に戻る。
Bronze
WINDやSHIELDのシナジーを見越して、攻2守1構成で実装スタート。攻撃担当2人を定位置に立たせてSHIELDとWINDを同時に叩き込むことで、連携攻撃実装の練習とした。防衛はWINDを使うくらいでそのまま…だけど防衛力が足りず、攻1守2にしたところで昇格。
Silver
細かい計算で最適化したり、固定位置待機でなく巡回できるようにしたり。守2は相互作用を考えて担当を割り当てたりするのが大変で(大変なためうんうん唸るだけで実装しなかったので)、やはり防衛が安定せず。ルールを読み込んだところspawnerが4つしか無いことに気づき、spawnerでマナ稼ぎしながら拠点に近づかせない方針に。これでやられる前にやれば守備は雑でもいいので、攻2守1に戻す。
Gold
後続モンスターの巻き込み、モンスターをspawnerに送り返すなど、更に最適化。2人で同時WINDするのを作る。防衛役が自己SHIELDを張るかを相手の戦術に合わせる。Legend昇格の決まり手がSHIELDをやめるってどうなん?(じゃんけんなので。)
Legend
条件チェックを厳密化など。*6マナ効率が良くなったので、攻撃開始ターンを120→80に早期化。
雑多考察メモ
AHC008風な同時着手の振る舞い作りの問題だが、こちらは誰かの行動を決めたことによる影響が多岐に渡り、管理しにくい。こういうケースの対処法は、手元のゲームプログラミング本によるとダブルバッファが良いらしい。State全体をダブルバッファにしてもいいが、一部だけダブルバッファにしてもいい。私が偶然していた実装はStateを変化させずに決定済の行動だけ持って判定時に考慮に入れるという方法で、この後者に近かった。多分このゲームだと前者の方が合いそう。
攻1守2と攻2守1の違い。攻2は攻め方が多彩になり、同時に何かすることによるシナジーも生み出せる。守2は、モンスターが弱く1人で対処できるうちは並列として機能するため、片方が操られたり飛ばされたり、隙間から攻められたりというのに強い。モンスターが強くなると、1人では削りきれないモンスターを共同で倒す直列の動作をするようになる。つまり、序盤から終盤にかけてどちらも安定度が増す。どちらが良いかは難しいが、10日の完璧な実装で強いのは攻1守2、10日の雑実装で強いのは攻2守1だろうか。4400砲や6600砲の有効度で決まりそう。
マナアドバンテージ。中途半端な攻撃は自分のマナを減らし、敵のマナを増やすだけ。普段は無駄遣いせず、ここぞという時に飽和攻撃するのがいい。WIND合戦は1:1くらいで双方消耗するが、SHIELDは自分だけ消耗して相手は稼ぐことになりやすい。実際に攻めるのはマナを使うが、マナを使わずに相手陣に居座り、相手に対処を空撃ちさせる(そしていざ本当のチャンスとなれば実際に叩き込む)という方法もある。
事故は起こるさ。視界2200に対してヒーロー2人がそれぞれ最高速度で近づくと1600で、視野外から一気にWIND範囲に入ってしまったり、一度CONTROLされると復帰の手が無かったり、WINDで飛ばした先でもう1回WIND出来たりと、とにかく事故は起こるさの設定。相手の認識外から行動を起こしたり、想定外の行動を起こすのは有効度が高そう。
感想
勝ち筋を自分で選べるゲームで、最終戦術を何にして実装リソースを注ぐかを決めるのは難しかったです。また、特定の戦術(≒特定個人)へのメタも存在する環境でした。プログラマ同士の対戦をエージェントが代理でやるみたいな感じだったのと、何かが視界に入ったときには対処困難というのがあり、それよりゲーム木探索したいはちょっとありましたね。*7
これはこれで楽しいんですが、正しい道に進んでいるか分からない、ゴールが見えない系なので半月マラソンラッシュの締めとしては重かったです。処理順が複雑なのもあって、綺麗なコードを書くのも難しかったですし。
順位的にも目標の上位2%に微妙に届かなかったのですが、去年のコンテストよりは伸びていたので爆死の傷は癒せたかなというところです。*8
あと、流石に疲れたので休みたいです。
余談
monsterくん、いくら攻撃されても気にせず直進し続けるの異常だよ
— TERRY (@terry_u16) 2022年4月30日
このツイートで何かに似ていることに気づいてしまったのですが、このゲームのビジュアライザをよく見ると…。
・1Pは青い服
・拠点回りは黄金とまでは言わないが黄色い畑
・つまり「青き衣をまといて金色の野に降り立つ」
・なんか体に悪そうな霧が出てる
・森から出てきて直進し続ける虫
・そんな虫をCONTROLで森へ帰したり相手の拠点に送り付けることができる
・WIND(風)
・去年のパクリ元はジブリ
…ナ●シカじゃん。