Go to Qiita Advent Calendar 2024 Top
LoginSignup
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@viewlagoonin株式会社バンダイナムコ研究所

CodinGame Spring Challenge 2023 参加記

Last updated at Posted at 2023-06-21

はじめに

  • 2023/05/25～2023/06/05に行われたゲームAIコンテスト 「CODINGAME SPRING CHALLENGE 2023」に参加したので、期間中やったことを書きました。
  • 以下、CODINGAME SPRING CHALLENGE 2023 - ANTS (Bot Programming 側) プレイ中の画像を利用しています。
  • コンテストページ
  • 結果
    • 22位/5290人 (レジェンドリーグ95人) でした。
    • Contests部門 (過去3回分良いContestの結果の和。古いContestほど減衰あり) で12位まで上がりました。単体Contestの最高順位は17位と別に突出しているわけではないので、順位安定性が評価されているようです。
      • 202306052311.PNG

ゲームルール

  • 細部は省略して書いているので正確なことは 本家のルール を読んでください。ただし、ルールに書いていないソースコード読んだ結果得た情報も一部以下には書いています。
  • 勝利条件
    • 盤面に落ちているクリスタルを集め、先に半数取れば勝ちです。
    • 同時に半数に達したら、蟻の数で比較します。それも同じなら引き分けです。
    • 100ターン経過で強制終了し、その時点のクリスタルの数・同点なら蟻の数で勝敗を決めます。
  • 構成要素
    • プレイヤー: 青と赤二人で戦います。
    • セル: 六角形のマス。穴空きの部分は移動不可です。最大9行・11+12+13+14+15+14+13+12+11=115マスから穴が空く程度の広さです。各セルには0以上の整数でセルインデックスが割り当てられています。
    • ベース: 蟻塚。後述するチェーン計算の基点になります。最大1チームあたり2か所。
      • base.PNG
    • 蟻: 各マスに何匹いるかが菱形で表示されます。1ターンにつき隣接するセルへ1マス移動できます。
    • 資源
      • クリスタル: メイン勝利条件となる資源です。
        • crystal.PNG
      • 卵: 取得した卵の数だけベース上で蟻の数が増える資源です。ベースが2つある場合はそれぞれ増えるので、卵1に対し蟻2匹となります。Wood1リーグ以上限定。
        • egg.PNG
    • 盤面上の全ての構成要素は初期状態見た目点対称に構成されますが、セルインデックスは1ずれとなり、セルインデックスの大小関係の違いにより蟻の移動が変化するので、完全な点対称とは言えません。
  • 資源回収方法
    • チェインの計算: 各資源に対し、ベースまで蟻が1匹以上のセルだけを経由して到達できたら回収できます。経路に対し、一番匹数が少ないセルの値がChainの値=回収可能量になります。経路が複数考えられることがあり、その時は審判側が最大値となる経路を選んでくれます。
    • アタックチェイン (Bronzeリーグ以上限定)
      • チェインの計算は資源マスに限らずあらゆるマスに対して計算できます。対戦相手のチェインが1以上のマスがあったとして、そのマスの自分側のチェインの値が上回っていた場合、対戦相手は資源回収の際にそのマスをチェイン計算の途中経路として使えなくなります。
      • attack_chain_example.PNG
      • 対戦相手のアタックチェインをアタックチェインで切ることはできません。例えば、以下では青2のチェインを赤3のアタックチェインで切っているので、青2の回収は防げていますが、アタックチェイン自体は切れていないので、赤1のチェインを切って赤1のクリスタル回収を妨害できています。
      • attack_chain_attack_chain_example.png
  • 行動
    • 今回のコンテストの一番独創的な部分です。蟻の移動を直接指定することはできず、ビーコンを置いて間接的に誘導します。
    • BEACON セルインデックス 強度; というコマンドを列挙します。指定したセルインデックスにビーコンがおかれます。
      • 審判処理中で強度の全箇所総和が蟻総数と同数になるようにスケーリングされるので、全箇所強度を定数倍するだけだと浮動小数点丸め誤差以外は挙動が変わらないはずですが、私は強度総和=蟻総和となるパターンしか考察していないので他の場合(配分が小数になる場合)はよく知りません。
    • ビーコンを置いた先に向かって蟻が移動しますが、蟻-ビーコン間の距離近い順・蟻が今いるセルのインデックス小さい順・ビーコンがいるセルが小さい順というように貪欲に決めていくので、行かせたい目的地へそのままビーコンを置くだけだと大抵の場合実際にやらせたかった動きになりません。この辺りは下で詳しく書きます。

ビーコン操作

前提

  • 次のターンどういう蟻 from セルインデックス to セルインデックス にしたいかは最小費用流で割り当てを決めているものとします。
    • コストは蟻のいるセルを上流側、移動先を下流側として、max(移動距離, 1) とすれば意図通りになります。max(*, 1)なのは停止しようと1ターンは消費するよという意味。
  • さらに、距離2以上のマッチングがあった蟻に対しては次ターンの移動先どこにするか経路復元で求まっていて、全蟻既に距離1になっているるものとします。
    • なお、以下の例では距離2以上のセルインデックス-セルインデックスマッチング例はそもそも出していません。
  • 以下ではビーコンコマンドを書くとき、BEACONと書くのが冗長なので、単に数字2つのセミコロンの羅列で書きます。(例) 23 2;15 2;9 2;7 2;5 2;13 2 左が対象セルインデックス、右が強度です。
    • また、焦点をあてている蟻以外の蟻は別の場所に停止隔離していて、その分の強度のビーコンは登場していなくても暗に指定しているとします。

初級

  • 1次元で、ベース側へ戻る蟻がいない場合が初級です。初動では1次元の状況が多く、卵をとれないと出遅れるので、初級をできるようにするのは圧倒的にコスパ高いです。

  • 初期状態

    • 2_3_2_2_2_1_with_cell_index.PNG

  • 目標状態

    • 2_2_2_2_2_2.PNG

  • 単に目標状態と同数のビーコンにした場合

    • 23 2;15 2;9 2;7 2;5 2;13 2

    • 2_3(1)_2_2_2_1.PNG

    • 2_2_3_2_2_1.PNG

    • 2_2_3(1)_2_2_1.PNG

    • 2_2_2_3_2_1.PNG

    • 2_2_2_3(1)_2_1.PNG

    • 2_2_2_2_3_1.PNG

    • 2_2_2_2_3(1)_1.PNG

    • 2_2_2_2_2_2.PNG

    • このように、4ターンもかかってしまいます。

  • やりたい移動

    • 23 2;15 2;9 1;7 1;5 1;13 5

    • 2_3(1)_2(1)_2(1)_2(1)_1.PNG

    • 2_2_2_2_2_2.PNG

    • 1ターンで行けます。

  • 考え方

    • まず、停止する予定の蟻はさっさとその場にビーコンを置いてしまってよいです。距離1の蟻だけ残ると、以下のようになります。
    • 0_1_1_1_1_0.PNG
    • 移動予定の蟻がいないマスのうち、そこへ置くと望みの位置へ移動してくれる位置に置きます。今回の状況は全部右へ移動すればよいので、 13 4 としましょう。
    • 0_1(1)_1(1)_1(1)_1(1)_0.PNG
    • 0_0_1_1_1_1.PNG
    • あとは、停止するビーコンを足して、23 2;15 2;9 1;7 1;5 1;13 5 を得ます。
    • 大事なことは、停止蟻-ビーコンペアを除去した後の盤面において、「移動しようとしている蟻」がいる場所にビーコンを置くと移動しようとしていた蟻が動かなくなるので置けないという点です。
    • 行かせたい場所に上記理由によりおけなかったら、同じ方向へ行ってくれる別の場所、一次元の場合だとさらに先のマスへ置くことになります。初級状況だと先端へ置いておけば安定です。

中級

  • 1次元であっても、ベース側へ戻る蟻がいると先端へ置いておけばOKとはいかなくなります。ここからセルインデックスが本質になります。

  • 初期状態

    • 3_0_4_0_5_0_with_cell_index.PNG

  • 目標状態

    • 2_2_2_2_2_2.PNG

  • 貪欲に停止以外端に置く (失敗)

    • 23 2;9 2;5 2;13 6
    • 2(1)_0_4(2)_0_5(3)_0.PNG
    • image.png

  • 蟻の現在地点から目標地点へ経路をたどっていき最初に見つけた「移動しようとしている蟻がいないマス」にビーコンをたてる (失敗)

    • 23 2;15 2;9 2;7 2;5 2;13 2 今回の場合、単に目標地点にビーコンを置くのと同じ置き方になります。
    • 3(1)0(2)4_0_(2)5(1)_0.PNG
    • 2_3_2_2_2_1.PNG

  • 正解

    • 23 2;15 1;9 2;7 1;5 2;13 4
    • 3(1)0(1)4(1)0(1)5(2)_0.PNG
    • 2_2_2_2_2_2.PNG
    • なお、セルインデックスの並びが変化すると正解が変化します。
    • この辺りになってくると、審判と同じ順番で処理をしていって、今までに確定した蟻を惑わす位置にもビーコンを置けなくしたうえで次のセルインデックスへ進むといった処理が必要になります。遠くの位置にビーコンを置くことで無理やり帳尻を合わせると、後続のセルインデックスで置けなくなる範囲が広がっていくので、あきらめ方をビームサーチするなど必要そうです。

  • 私は上の解を直接見つける実装はできておらず、さっき失敗した、蟻の現在地点から目標地点へ経路をたどっていき最初に見つけた「移動しようとしている蟻がいないマス」にビーコンをたてるプラン、および、単純にいきたい場所にビーコンを置くプランの2種類を初期解として、そこから独立に山登りしました。蟻の動きはシミュレータを移植してわかっているものとします。

  • 山登りの流れ

    • 3_0_4_0_5_0_with_cell_index.PNG

    • 23 2;15 2;9 2;7 2;5 2;13 2 (再掲)

    • 2_3_2_2_2_1.PNG

    • 15が余っていて13が足りないので 23 2;15 1;9 2;7 2;5 2;13 3

    • 3(1)0(1)4(1)0(2)5(1)_0.PNG

    • 2_2_2_3_2_1.PNG

    • 7が余っていて13が足りないので 23 2;15 1;9 2;7 1;5 2;13 4

    • 3(1)0(1)4(1)0(1)5(2)_0.PNG

    • 2_2_2_2_2_2.PNG

    • ちゃんと途中状態を経由できるように、目標との総距離がより近づいたから登ったとみなせる評価関数にするか、同点は確定遷移するか、焼きなましにする必要があります。

上級

  • 今まで1次元しかやっていないですが、実際は1次元ではないです。仮に木が1次元初級とみなせても、その経路が曲がっていると木の先端を指定したら最短経路は別でしたということもありえます。
  • とはいえ、上級用の特別なアイディアはなかったので、ベースから構築済みの木を伝って各点まで行く経路をそれぞれ1次元問題とみなして、分岐の根本側を多重処理しないように注意しながら中級で述べた初期解を作成しました。
    • どの森上にもいない蟻はひとまず単に目標地点にビーコンを置いて山登りに丸投げしました。
    • コンテスト中できていませんが、ベースをまたぐのが苦手な初期解になってしまったのでベースを経由する二つの1次元問題を直列接続して一つの1次元問題とみなしたほうがよさそうでした。

リーグ別やったこと

  • league_level.PNG
    • 6リーグから構成されていて、コンテスト開始直後はBronzeまでの3リーグ、以降日が経つにつれて徐々に上位リーグが開放されていきます。
    • リーグを上がるためには、提出後進捗100%の状態で、各リーグに設定されたボスのスコアを上回っている必要があります。
    • ボスは基本天敵のいない環境※でスコアを伸ばしていくので、開放と同時に突破しておくのが一番楽だと思います。出遅れてからギリギリボスを上回って昇格したら既に上位リーグ中位にいたという事象はよくあります。 ※天敵は通常すぐリーグ昇格するので
      • 今回はGold Bossが開放当初全一のスナップショットだったのでそこだけ開放時突破が実質不可能で今でも全く勝てませんが、他は順調にいきました。
  • コスパ良かったものに☆
  • Wood2
    • BFSを実装。
  • Wood1
    • 資源に対する全域木・セルでいうとシュタイナー木をプリム法で構築。☆
      • ただし、蟻が尽きたらそこで打ち切り。
    • 普段よりボスが強い印象ありました。
  • Bronze
    • Wood1のコードをそのまま放置していたら通過。
  • Silver
    • ビーコン数を蟻数に合わせる。
    • 森を作った後、実際にどう蟻を割り当てるかを決める。資源に対しそこまでのチェインを1ふやすのに何匹蟻が必要かというのは都度計算できるので、効率評価し貪欲に決定。
      • ベースが2か所あったら1個だけ使う、両方使うの3パターンそれぞれ構築・評価する。
    • 蟻-目標位置を最小費用流で割り当て。
    • ビーコン操作頑張った。☆
    • シミュレータ移植できたので、ビーコンを現在の解の隣に置く山登り。
  • Gold
    • 自陣とれば勝ちかどうかを判定しておく。勝ちなら敵陣へは無理していかないし、負けなら遠征する。 ☆
    • ビーコン操作引き続き頑張った。
    • 山登りの際に、移動後の多寡で、多いところから少ないところへ配分する近傍を追加。☆
      • 詳細は上に述べた通り。
      • 何匹配分するかは、移動元の蟻の匹数以上のビーコン強度があると絶対そこから移動してくれないので、max(1, それが解消される最小強度)だけ取り除き、その分を他の目標匹数に足りていないランダムな一か所へまとめて渡す。
  • Legend
    • 森を構築する際に、今アリがいる位置によって既に資源までのチェインができているならそれを再利用する。
      • 民族大移動防げるかと思ったが案外あまり効果がなかったです。
    • 対戦相手の行動として、山登らない初期解をやらせておく。
      • 停止・目標地点そのまま・蟻操作後と3パターン平均やったが、シミュレーション回数が減るのが痛かったので、目標地点そのままだけで固定した。
      • アタックチェインの勝負で強かった印象。
  • Forum にあった上位解法と比較してやっていないことのうち特に重要そうなもの
    • 2手以上読み。
    • 序盤卵だけみた森構築。
    • シミュレータ高速化。特に、蟻移動先候補を前計算で絞っておく部分。

おわりに

  • 当初ゲームジャンル的にはグラフ理論バリバリで苦手ジャンルに見えましたが、今回の蟻の観察のように仕様理解度で戦うのは結果的に好きなジャンルでした。
  • この記事を読んでこのゲームに興味を持った方は、今からでも Bot Programming のページから遊べます。是非遊んでみてください。

備考

この記事は株式会社バンダイナムコ研究所のエンジニア独自の研究成果で、バンダイナムコグループの製品及びサービスやその他開発業務とは関係がございません。そのため、質問やお問い合わせにつきましてもお答えできないことがございますので、予めご了承くださいますようお願い申し上げます。

3
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?