問題概要
CodinGameのSpring Challenge 2022というコンテストに参加しました。
ゲームの雰囲気は以下のリンク参照↓
3体のヒーローを操作して敵陣に虫を叩き込むゲーム。虫(以下、モブ)を攻撃するとマナを2もらえ、マナを10消費することでスペルを使用できる。スペルは以下の3つ
・WIND:周囲の敵ヒーローとモブを指定した方向に吹き飛ばす
・CONTROL:指定したヒーローまたはモブ1体を次のターン指定の位置に移動させる
・SHIELD:指定したヒーローまたはモブ1体に、一定ターンの間WINDとCONTROLを無効にするシールドを付与する
自拠点にモブが到達すると拠点のHPが1減り、HPを3失うと負け。相手の拠点のHPを0にすると勝ち。どちらもHPが残った状態のまま220ターン経過すると拠点のHPが多いほうが勝ちとなる。
ルールの詳細は以下のツカモさんの記事に全て書いてあります。
結果
世界126位(日本24位)
ゲームについて考察
探索できる?
ヒーローの行動として、最低限MOVE8方向、WAIT、WIND1方向は欲しい。キャラ1体の行動をそれら10個として、最大6キャラが近くで相互作用するので、組み合わせると次の盤面の数は10^6通りになり、多すぎる。コドゲで1ターンに評価できる盤面数は経験的に10^3~10^5ぐらいなので、全キャラの行動パターンを組み合わせると1手先も探索できないケースがありえる。そのためDUCTのような探索は使えないか、使えるとしてもキャラがあまり重なっていない盤面だけで、そういう盤面ではDUCTする意味あるか疑問に思う。さらに移動8方向はたぶん弱いので16方向とか、さらにその間を場合によって足していくとかしたほうが良さそうだが、それをするなら山登りのような方法で移動する角度を細かく改善していくほうが強そう。
つまり、焼くか?
焼きますかぁ。
最終提出プログラムの内容
先に書いた考察をふまえ、最終的に出来上がったプログラムの内容を紹介します。
1.アルゴリズム
焼きなまし4ターン読み。長さ4のAction配列を持ち、それを焼きなます。
まず相手視点で10msだけ焼きなましを行う(自分の行動は全てWAIT)
次に自分視点で焼きなましを行う。このとき相手の行動は先に決めた4手分のうち1手目と2手目だけを実行する。理由は分からないが4ターン分実行するより2ターン分のほうが強かった(Fogのせいで不確定要素が多いとか、相手プレイヤーとの戦略の違いとかが原因だと思う)
最初の40ターンはモブ発生地点付近でマナを稼ぎ、それ以降は攻1守2構成で行動する。
盤面評価は1ターンに3000~5000回程度でした。
2.状態遷移
焼きなましの状態遷移は、4ターン✕3人の行動=12個の行動のうち1つを変化させる。遷移の種類は以下の通り
WAITに変更
MOVE(角度ランダム、距離最大)に変更
MOVE(角度ランダム、距離ランダム)に変更
WIND(角度ランダム)に変更
SHIELD(自分)に変更
SHIELD(モブからランダムに1体)に変更
に変更
CONTROL(HEROまたはモブからランダムに1体、角度ランダム、距離最大)に変更
例外的に、WINDのみ2人同時に同じ方向のWINDに変更する遷移も用意した。ロマン砲*1や二重の極み*2対策。
3.シミュレーション
本家のJavaのコードをc++にそのまま書き換えただけ。ただし野良モブが陣地内に入るかの判定は1ターンずつシミュレーションする方法から円と直線の交点を計算するやり方に書き換えました。
4.評価関数
おおまかには以下の8つの評価値を計算しました。
①拠点HP差
②自ヒーローが指定位置付近にいるか
指定位置とは、序盤40ターンはモブの発生地点付近、それ以降は攻撃ヒーローは敵陣付近、守備ヒーローは自陣付近。そこから距離2000以内にいないとマイナス評価。
③コンテスト終了10分前にノリで入れてしまったもうほんとに全然ダメな間違った評価
敵ヒーローをコントロールして敵陣外に引っ張り出す評価。モブが敵拠点付近にいるときだけ発動する。。。はずだったが、見えていないけど位置推定で存在を予想した仮想モブに反応してしまっていて、実際にはモブは敵拠点にいないのに無意味に敵ヒーローをコントロールし続けてマナ枯渇して終了。コンテスト終了直前は落ち着きましょう。
④自陣内、敵陣内のシールド付きモブ(1人防衛を突破可能なもの)
1人で防ぎきれないHPを持ったシールド付きモブ。守1構成には確定ダメージとなり、守2構成に対してもシールド付きモブを複数発生させるとわりとダメージを期待できる。また逆に自分がそうされないように立ち回るためにもこの評価が有効。
⑤防衛ヒーローは自陣付近の敵ヒーローへ近づく
自ヒーローが敵ヒーローの近くにいることで、WINDによる攻撃を防げることが多かった。特に敵ヒーロー付近のモブを画面外方向へWINDして森に返すのが有効っぽい。
⑥自陣内、敵陣内のモブのHPとか距離とかと、マナ使用量のバランス
最も拠点に近いモブのHPと距離を主に評価。あとは自陣内のモブのHP合計とか。
また「自陣内のモブの数*11+マナ使用量」でマイナス評価すると、マナ10以下(=SPELL1回)で排除できるモブだけ拠点外にWINDで飛ばすとかしていい感じだった。「自陣内のモブの数」の評価だけだと拠点付近のモブを5回ぐらいコントロールして自陣外に連れて行こうとするし、「マナ使用量」だけだと剣だけでモブをなんとかしようとするので自陣内がモブだらけになりがちだった。
⑦敵陣へ向かうフリーのモブの数(HP20以上)
将来的に敵拠点に到達するモブ。これを評価することによって、その辺のモブをコントロールで敵陣へ向かわせてくれる。敵陣に入ると④の評価によってシールドを張るのでシールド飽和攻撃ができる。
HPの低いモブを送ってもただのマナ源プレゼントになってしまうのでHP20以上に限定。
⑧獲得マナ量
マナ使用量とは別で評価した。マナ獲得よりマナを無駄に使用しないことのほうが重要。
5.焼きなましで評価値が下がるときに遷移するか判定
一般的に、評価値が大きく下がるときは遷移しにくくして、少しだけ下がるときは遷移しやくすると良くなるが、今回は評価値が8つもあってやりにくいので単に乱数で100分の1の確率で遷移するとした。それでも山登りよりは良い結果になりました。
真面目にやるなら1つひとつの評価値に遷移確率を設定してあげるのが良いと思います。
感想
評価関数の設計に手こずりすぎて本質を理解できないまま終わった感じでした。
評価関数ベースのやり方は拠点にダメージを与える/受ける最後の詰めの部分の攻防が上手いというのが利点だと思っていますが、今回は
・霧で敵拠点まわりが見えない
・霧の外からダイレクトアタックができる
とかであまり利点が活きなかった感じはしました。
そのぶん相対的にルールベースが強いので、私ももう少しルールベースに寄せても良かったかなと反省です。
ロマン砲などの超次元サッカー戦略*3がとれる点に関してはエンターテイメントとしては楽しいが競技としては微妙に感じました。WIND重ねても最大ふっとばし距離は1人分のWINDまでとしてほしかった。まぁこれはこれでおもろい回だったと思います。
おまけ
コンテスト終了後に③の評価値をいろいろいじってみたがあまり良くなりませんでした。③の評価を消し去ったところ63位まで上がりました。