CodinGame Spring Challenge 2022で3位を取った話
CodinGameのSpring Challenge 2022というゲームAIコンテストにおいて18,288人中3位を取ることができたので、コンテスト中の考え方や解法などを残しておこうと思います。
準備期間について少し
CodinGameという名前を知ってはいましたが実際に出場したことはなかったため、コンテスト開催一ヶ月前からCodinGame上の課題を解いて練習しておこうと思いました。僕が選んだ課題はUltimate Tic-Tac-ToeというものでチェスのようなボードゲームのAIを作るというものです。そこで僕はモンテカルロ木探索を学び、AlphaZeroやNNUEを自前で実装し、来るべきコンテストに備えました。そして迎えたコンテスト当日、はやる気持ちを抑えつつ問題文に目を通すと、そこにはルール無用超次元サッカーが広がっていました。
取り組み方の基本方針
問題を読んだ感じ、今回のコンテストは理不尽ムーブの押し付け合いになるのかなという印象を受けました。ただ、攻撃のバリエーションが豊富にあるため、どの攻撃方法を実装すればいいかわからず攻撃ロジックの実装は切りがないなと思いました。また、マナや視界には限りがあり、異なる盤面のセットアップも必要になるため、複数の攻撃方法を採用するのも難しそうだと感じました。なので、初日から攻撃ロジックを実装していっても、攻撃方法を変えた時点で全てのコードを破棄することになり無駄になるのではと思いました。
反面、防御関連のロジックは攻撃と違い積み重ねが効くと感じました。ある攻撃方法に対する防御用の実装を書いた場合、たとえその攻撃方法が廃れてもコードは残しておいて常にif文で起動することができるようにしておけるからです。しかし、序盤に使われる攻撃方法はたぶんそんなに対策する価値がないだろうなという考えから初日に防御関連のロジックを実装するのも微妙かなと思いました。
ということで初日から攻撃も防御も実装しないこととなり、ゲームAIの大会でボットも作らずライブラリを作り込み続けるという日々が始まりました。
ボット概要
防御型のボットとなりました。120ターン目までは全ヒーローを使用して防御とマナ集めに徹し、そこから攻撃に移行するという戦法になっています。攻撃方法は虫にシールドをかけた上で相手をコントロールしつつ飛ばすという、時間はかかるがマナ消費を抑えられ防ぎにくいものを採用しました。
序盤から強めに攻めてくるボットにはマナ枯渇を狙え有利となっています。逆にあまり攻めてこないボットに対しては、必要以上に防衛してしまいこちらのマナが枯渇するのでかなり不利なマッチアップとなっています。上位陣は前者の攻めてくるボットが多いため、この戦法を選びました。
この記事の上の方で、防御は難しそうと書いていましたが実際はそこまででもなかったです。攻撃型のボットが乱立した結果、攻撃型同士の戦いに勝つために不完全な状態で早めに攻撃を仕掛けることになり、防御しやすくなったのではと思っています。漁夫の利。
ボット実装
相手の行動を考慮に入れた探索などはせず、現在の敵・味方・虫の位置からルールベースで次の行動を決めています。ただ前述の通りライブラリだけは充実しているので、何ターン後に虫に追いつき魔法を打てるか、そのためにはどこに向かえばいいか、虫がゴールに行くのを阻止できるか、などといったことは予め知っています。それらの情報から魔法を打つべきか動くべきかなどの行動を決めます。そして最後にどこに動くべきかなどをヒューリスティックの評価関数で決定しています。
実装面でもロジック面でも特筆すべき点は特にないように感じます。色々な情報を正確かつ手軽に入手できるように実装を固めておき、対戦のリプレイを通じて得た知見を簡単にボットに反映できるようにすることに集中していました。
感想
想定と大きく違うタイプのコンテストでAlphaZeroもNNUEも一切使わなかったけど、とりあえず楽しかった。ガムシャラに色々なモノを実装するのではなく、忙しくなるコンテスト後半に備えて実装を固めて準備できたのが人間としての成長を感じた。
