CodinGame Fall Challenge 2023 で9位になり表紙のTop10入り果たしました

Last updated at 2024-01-23Posted at 2024-01-23

CodinGame Fall Challenge 2023 参加記

はじめに

2023/12/19～2024/01/08に行われたゲームAIコンテスト「CodinGame Fall Challenge 2023」に参加しました。
以下、CodinGame Fall Challenge 2023 及び Seabed Security - Fall Challenge 2023 の画像を利用しています。
CODINGAME コンテストページ
- Contests 期間限定で終了済み。こちらで表紙の TOP 10 CODINGAMERS 入り果たしました！
- Bot Programming 常設版。終了後の現時点で遊びたい方はこちらから
結果
- 9位 / 4669人 (レジェンドリーグ58人) で、Contests部門最高記録更新しました！
- Contests部門 (過去3回分良いContestの結果の和。古いContestほど減衰あり) 11位 まで上がり、こちらも最高記録更新しました！
CodinGameとは?
- 開催回毎に異なるゲームに対する AI Bot を作ります。提出すると、他の参加者の作ったAI Botと自動で対戦して順位がつきます。
- 実力に応じて リーグ分け されており、下位リーグのうちは簡素なルールにっているため参入障壁が低めです (今回に限ると、入力数が多くややとっつきにくい印象でした)。最上位のLEGENDリーグ以外にいる間は リーグBOSS というAI Botの中身が変化しない絶対目標があり、対戦ゲームでありながらソロゲーのような自分との闘いに変換もできます。各プレイヤーはリーグ昇格のみ可能で、降格することはありません。
- リプレイ は別リーグ・他人同士の対戦含めて閲覧可能なので、煮詰まった時は上位勢のリプレイを見て自分に何が足りないかをチェックすることができ、実装方針が何も立たずただ座っているだけという状況になりにくいのもCodinGameの取っ付き易さにつながっています。
  - リプレイを見るには、LEADERBOARDのページへ行って、見たいプレイヤーのVIEW LAST BATTLESの項目をクリックします。スマートフォンの場合は、ブラウザの拡大率を下げて文字を小さくしたうえで横持ちにしないとこの部分が出ないかもしれません。

CodinGame Fall Challenge 2023 ルール概要

正確なルールは公式参照。
以下、私見を交えつつ概要を説明します。
10000x10000の2次元フィールドで構成された海に生息する 12種類の魚をドローン2機を操作してスキャンし、写真を水面まで持ち帰りセーブしましょう。 対戦相手よりも早くセーブするとボーナス点がもらえます。セーブした魚に応じて後述の点数がもらえるので、 対戦相手よりも多くの点数を稼ぎましょう。
ドローンはライトを持っており、バッテリーを消費して点灯させると広範囲をスキャンできます。消灯中は至近距離ならスキャンできます。
スキャンすべき魚とは別にお邪魔者となる 鮟鱇(アンコウ) が2～6匹生息していて、ドローンを見つけると追いかけてきます。ぶつかると緊急モードという操作不能のやられ状態に長期間なってしまうので回避しましょう。ゲームへの理解度が進むにつれて、鮟鱇に対する印象が「回避無理」「回避余裕」を行ったり来たりする奥深い存在です。
スキャンできる範囲外の魚や鮟鱇の座標や速度はわからず、魚ごとに生息域y座標が制限されていることと、各魚が各ドローン自機から見て左右どちらにいるか、上下どちらにいるかぐらいしかわかりません。現在ターンになるまでに得た情報を活用してどれだけ正確に位置を推定できるかがこのゲームの鍵です。
魚はドローンの騒音に気づくとドローンと反対方向へ逃げます。その時に移動後のx座標が画面外になるとゲームから除外され、以降ドローンはスキャンできなくなります。画面左右端に近い魚は積極的に逃がして自分だけ持ち帰るのが攻撃的プレイです。 得点表赤い×がついているのが、未スキャンのまま逃げられてしまった魚です。
点数
- 下で一番深く考察しているルール箇所なので、ここだけは詳細記述します。
- 素点浅層の魚(クラゲ)が1点、中層の魚が2点、深層の魚(甲殻類)が3点
- 同一色3匹を揃えると3点 (得点表右端のトロフィー)
- 同一生息域の4匹を揃えると4点 (得点表下端の円)
- 先に成立させたプレイヤー側は得点2倍 (得点表中の星) 同着はどちらもボーナスなし
- 魚が1匹も逃げなかった場合、ボーナスなしでは48点(素点24+色12+生息域12)、ボーナスありでは96点が最高得点。魚が画面外へ逃げたり同着でボーナスが消えることにより上限が減っていきます。

最終方針

コンテスト途中の方針は下で別途書きます。
タスク割り当て
- ルート状態において、タスクを設定します。後に複数手読んでいきますが、タスクはこのルート状態で決めた後は変化しません。
- 各ドローンに対し、やりたいタスクを1つずつアサイン、という操作を3回行います。
- やりたいタスクとは、魚のスキャン、魚の追い出し、帰還、対戦相手への接近です。
- 各タスクは目標地点が設定されます。魚の周辺か、y=500地点か、対戦相手周辺です。
- 優先度
  - 魚ターゲットのベースは、近くの画面端 > 遠くの画面端 > 深層 > 浅層です。
    - 遠くを狙って移動している途中に浅層・中層の魚をついでに回収するぐらいでいると移動方向が安定して無駄なジグザグ移動が減ります。
    - 魚を逃がしつつ中央側の自機は全力で逃がされを回避するために画面端へ移動してスキャン数有利をとり、ボーナスが不利になっても挽回するチャンスを作ることを目指します。
  - 得点表シミュレーションから帰還・追い出し判断をします。
  - 追い出さないと絶対に負けるといった状況では、無理気味なx座標中央付近の魚であっても帰還より追い出しが優先されます。
評価値
- タスク単位の状態評価で、2手読みまでしています。
- 状態評価の際は、後述のサンプリングにより魚の座標は確定しています。
- 基本的にはタスク目標地点との距離の2乗が評価値として使われます。アプローチさせたい方向に応じて、x, yどちらかに係数をかけます。例えば、深層の魚へ向かって水面から中層へ移動していく際はxの差を軽視しておくとよいです。
- 緊急モードになるなら負の大の値が割り当てられます。
  - 現在状態が緊急モードかに追加で、各末端状態中で12方向に対し600移動させた際の既知の鮟鱇との衝突判定を行い、詰みを判断します。壁で移動不可の方向はアウト扱いです。これにより、鮟鱇回避に関してはほぼ3手読みできていますし、1ターン停止すれば隅でしのげるといった延命措置だとアウトなのでちゃんと生存経路が存在する行動が評価されます。
- それ以外には、スキャンしている魚や鮟鱇との距離、画面端との距離、バッテリー残量などによって評価値が少し変動します。
- 帰還タスクの場合には、何ターンで帰還できるか、同サイドの対戦相手ドローンは何ターンで帰還できるか、という情報が参照されます。
  - 相手より早く帰還できる事が確定していて未スキャンの深層の魚がいるなら、さっさと帰還することよりも、相手の少し上をキープして未スキャンの魚追い出しを牽制することを評価します。
- 2つ目以降のタスクは、手前のタスクが全て完了しているときのみ意味を持ちます。
魚のトラッキング
- 位置・速度それぞれのx, yについて、最小値、最大値を持っていて、範囲で管理します。
- 一度判明した魚及び鮟鱇の位置・速度は、min=maxの状態で以降シミュレートされ、レーダーなどに矛盾が出るまでは有効です。
  - 矛盾は未知の魚との衝突が発生した際に発生しますが、頻度はそれほど高くないです。
- ターン数序盤、もしくは判明した時点の初速が初期生成されたものである場合、対称位置の魚に対しても得られた情報 (位置・速度・レーダー) も使われます。
  - 序盤扱いになるターン数は、魚の生息域によって異なります。
魚のサンプリング
- 状態評価する際、魚の位置は5個サンプリングされ、それぞれに対し状態更新を行って評価値を計算し、平均をとっています。実行時間がたりないと2手目評価値計算の際のこの部分のループ回数が減ります。
- サンプリング候補は各座標未知の魚に対し128個ずつx, yそれぞれ最小値以上最大値以下の範囲からサンプリングされていて、評価値が高いものが選ばれます。
  - 基本的に現在の盤面と矛盾していない候補同士なら、乱数で加算された評価値部分で優劣が決まります。
  - 最初の5個は特殊処理で、存在可能範囲の中央の速度(0, 0)および四隅の速度(0, 0)が乱数最大値より少し大きい値として用意され、これらは矛盾が見つけられない場合は必ず採用されます。ただし、速度(0, 0)であること自体は矛盾とみなしません。文字通りコーナーケース対処のために用意しました。
- 未知の鮟鱇はレーダー状況によらず、画面外にいるものとみなします。未知の鮟鱇に怯えすぎてドローンがほとんど移動してくれなくなったためです。
行動
- シミュレーションする際、対戦相手の行動は何手目であっても固定で、無敵、すなわち鮟鱇とぶつかっても緊急モードにならないという機能をつけていつでも(0, -600), 消灯の帰還移動を行わせます。
  - 相手の行動に自分のルーチンを使うのも試しましたが、下手な予測よりも帰還判断が安定し、実行時間的にも最速だったのでこの方針を採用しました。
  - 相手が近くにいて鮟鱇の挙動が変わるときには長手数読んだ回避パスが嘘になって事故る可能性があります。
- 速度ベクトルについて、あらかじめ候補を何か所か持っておき、各移動方向に対し点灯・消灯置き1手目は、65箇所130通り
  - 1手目: 65方向
  - 2手目: 15方向 (停止, x±400, 12方向)
- 上記に加え、先頭タスクの目標座標へ向かって移動する速度ベクトルを追加します。
探索概要
- 1手目
  - 片方のドローンだけ動かして、132パターンx5サンプル平均を評価します。未評価のドローンは仮で浮上移動扱い。
  - ソートします。
  - ベストなほうから順に候補へ4つになるまで追加していきます。
    - ベストな行動限定で、それが点灯だったら消灯も追加します。消灯の時は何もしません。
    - それ以外の候補は、多様性確保のため、登録済みの候補から角度一定以内だったら候補へ追加せずスルーします。
  - ドローンは2機あるので、4x4=16パターンが初手候補になります。
- 2手目
  - 最外ループは魚座標サンプリングで、時間切れそうなら途中で終わります。
  - 初手16パターンそれぞれに対し、各ドローン2手目の32行動を評価し、2手目のベストを求め、対象初手に対する対象サンプリング回における評価値とします。
    - ここはドローンの相互作用を考慮せず、id順に決定しています。
    - 初手でタスクが終わることが明らかになる可能性があるため、サンプリングごとに別の行動をベストとしてとることを許可しています。
  - 初手16パターンのこれまでにこなしたサンプリングの平均評価値を比較し、ベストの案を採用します。
得点表
- 実装
  - 入力で得られるスコアだけでは不十分なので、GUIで表示されている表を再現できる仕組みを作りました。
  - スキャンやセーブ、逃げた魚を指定することにより、将来のスキャン順を複数パターンシミュレートができます。
- 追加で利用した概念
  - Slow: 相手が現存する魚を全部スキャン後セーブした後に、自分が現存する魚を全部スキャン・セーブしたときに得られる点数。ボーナスを全く得られないわけではなく、相手だけ逃げている魚がある都合で後からでもボーナスが確定している場合があることに注意。
  - Ideal: 相手は何もせず、自分は現存する魚を全部スキャン後セーブした時点での点数。
  - Sum: 自分と相手の合計点の理論値。(Sum/2)点確定させれば引き分け以上確定といえます。たとえば魚が一切逃げていなければ72点で引き分けです。
- シミュレーション例
  - 自機が1,2 finishした場合どうなるか、相手が1,2 finishした場合どうなるか
  - 現在の各ドローンのy座標をもとに、順番に帰還した場合に得点表がどうなるか。同着も考慮
  - 現在の各ドローンのy座標をもとに、一人だけ停滞、残り3機は順番に帰還した場合に得点表がどうなるか

リーグ別やったこと

今回は、 Wood3, Wood2, Wood1, Bronze, Silver, Gold, Legend の7リーグから構成されています。
Bronzeリーグ以降はルール変更ありません。
Silverリーグ以降は時限解放で、Silver, Goldリーグは解放と同時に昇格しました。

Wood3 (12/19)

Bronze以降とのルールの違い
- ドローンが1機
- 魚の座標が既知
- 魚がドローンの騒音で逃げない
- スキャンしたタイミングでセーブした扱い
- 鮟鱇がいない
実装方針
- 近くの魚に向かう
- 5ターンに1回点灯

Wood2 (12/19)

Bronze以降とのルールの違い
- 魚がドローンの騒音で逃げない
- 鮟鱇がいない
実装方針
- 丸底フラスコのような固定軌道を描かせる

Wood1 (12/19)

Bronze以降とのルールの違い
- 鮟鱇がいない
実装方針
- Wood2の提出でそのまま通過

Bronze (12/19-12/26)

PythonからC++へチェンジ
行動の角度候補を選出
鮟鱇回避実装
魚追い出し実装
浅層or中層の魚を1匹追い出せていて自分は全生存なら浅層中層コンプ時点で1,2フィニッシュすると、追い出しできない相手なら71vs65または71vs64で安定して勝てるので愛用していました。追い出しできる相手には全く通用しないので今は非推奨です。

Silver (12/26-1/2)

極端なy座標嗜好にして、魚を追い出せそうでない限りほぼ真下へ降りさせ、浅層4中層4深層2を目指します
得点表実装
帰れば勝ち確の帰還状況で牛歩戦術
一度見た後の魚・鮟鱇のシミュレーション (含鏡像)
12/30- 2手読みにすべく根本から工事開始

Gold (1/2-1/6)

2手読み工事完了
得点表シミュレーションベースの帰還判断の精度が上がったので、初動画面端魚追い出し重視に調整
2手読み工事前の自身の提出相手には安定して勝てるようになるも、追い出しが発生しないマップでのGold中位・下位に潜り速度で出遅れ安定して勝てず苦戦していました
1/5のLegendオープン時点ではLegend昇格者6人で参入失敗
結局Gold中位・下位対策とれないままスコア運良かった提出で放置していたところ、アクティブなGold上位5人程がみんな以下のような特徴を持つ相性良かった時間帯があり、その人たちのおかげでボスに1-0戦っただけで昇格できました。画像は昇格時の cgstats より
- 浅層4中層4深層2帰還をベースにして帰還判断が深層2匹スキャンしたら帰還のようなシンプルなものと思われる
- 浅層中層追い出せたら9匹帰還してくれて全スキャンで素体星3個とれば勝ち
- 追い出せなくてもどこかで取りこぼしがあって9匹以下で帰ってくれるなら1匹追い出し&全スキャンで素体星3個とって勝ち
- 10体で帰ってくれるなら深層2匹を追い出して引き分け
  - 深層2匹追い出しできれば何とかなる状況で2手読みで鮟鱇回避しながら安定して追い出せるようになって負け戦の引き分け率が上がったのがかなり機能しました。Legend帯では通用しないんですが。浅層4中層4深層2帰還対策は後手を踏んだ側の重要な要素なので下でもう少し詳しく書きます。

Legend(1/6-1/8)

後手に回りすぎていたので帰還タイミング見直し (後述。典型的な帰還順と得点パターンの項参照)
サンプリング
- 勝手読み排除するため四隅・中央を速度0にする
- 事故回避で動きが臆病すぎたため、見えていない鮟鱇は画面外扱い
2手読み候補で、ベストが点灯なら同じ座標の消灯を追加する
帰還するときに直接対決相手の上を取っていて深層スキャンできていなければ帰還せず隙をうかがう

最後まで実装されなかった改善点

深層2枚抜きや2匹同時追い出しを意識したターゲット2匹設定・座標設定する仕組み
帰還モード以外の時にセーブまでに必要なターン数を意識したy座標目標設定
最序盤、対戦相手のドローンと近いときに事故被弾を狙った点灯 (特に格上相手だとこれぐらいでしか勝てない)
得点表をシミュレーションする際に、未取得の浅層・中層の扱い

典型的な帰還順と得点パターン

ここを書きたくて記事を書き始めたので、ある意味 本記事のメインコンテンツ です。帰還の仕方で困っている人の助けになれば幸いです。
1,2 finish vs 3,4 finish
- ※ 1,3 finish vs 2,4 finishであっても、同サイド同士のレースで両方勝っていれば実質1,2 finish扱いです
- 1,2 finishできるなら12匹は不要で、11匹76点あれば勝ち確定です。
- 10匹先着ボーナスにはおおよそ魚2匹分の価値があります。あとから2匹のうち1匹回収できれば勝つので、後着側は未取得2匹を逃がしてから帰るのがマストです。
- 別生息域・異色が2匹欠けるとボーナス不足なので追加スキャンが必須です。
- 以下は、10匹先着 vs 12匹後着(2匹追い出し済み) の点数比較です。
  - 浅層4中層4深層2, 浅層4中層3深層3(同色): 64vs64 引き分け特に前者はテンプレ中のテンプレ展開です。逃がされる前にもう1匹スキャンできればいいので基本的には先着側有利です。
  - 浅層4中層2深層4 68vs62, 浅層2中層4深層4 72vs60, 浅層3中層4深層3(同色) 66vs63, 浅層3中層3深層4(同色) 68vs62: 先着側勝ち
    - こうなりそうなら、後着側は2,3同着finishでもいいのでボーナスを削る必要があります。
  - 浅層4中層3深層3(異色) 58vs67, 浅層3中層4深層3(異色) 60vs66, 浅層3中層3深層4(異色): 62vs65 後着側勝ち後着側の理想形です。
1,3 finish vs 2,4 finish または 2,3 finish vs 1,4 finish
- 対称位置がお互いに先に帰って素点ボーナスを取り合い、同一生息域ボーナスや色ボーナスだけ片方が先行するパターンです。
  - 典型的には、ドローン1機は深層1匹スキャンしたらすぐ帰るような戦術をとっていると発生しやすいです。
- 当然3番手を取れたほうが色・生息域ボーナスがある分強く、4番手側が対抗するには1匹逃がせているぐらいは必要です。
- あまり起きませんが、1, 2番手側がたまたま色ボーナスとれる配置だと4番手側有利になります。普通1番手は浅層2中層2深層1になりがちですが、帰り際に浅層や中層を追加で重複スキャンできるなら色ボーナスが発生しやすくなります。
- というわけで、1番手は典型的には浅層2中層2深層1の色ボーナス無しで帰還することになります。1番手側がちゃんとこの典型的な仕事をできていれば、4番手側は遅れてしまったとしても全スキャンと1匹逃がしさえできれば引き分けに持ち込めます。
深層2即帰還決め打ちプレイヤー対策
- 自分自身が Gold 帯にいた時はちゃんと気づけなかったのですが、今 Gold 帯を攻略するなら多分こうだろう、という話をします。
- 深層2即帰還は10匹先着だから強いのであって、浅層・中層どちらかが欠けていると弱いのですが、それを理解せずに決め打ちで帰還しているプレイヤーには浅層or中層を1匹逃がして全部スキャンしてから帰還するだけで瓦解します。
  - 浅層3中層4深層2後、残り深層2: 67vs69(浅層無い色を後スキャン) または 64vs72(浅層無い色を先スキャン) 決め打ち側負け
  - 逆の立場でいうと、1,2finishは強いですが、相手が帰還の気配を見せていないのに相手のスキャン可能数-2未満しかスキャンできていない状況で帰還して海底で工作させる余地を残すのは危険といえます。少なくとも1体はもう少しスキャンを続行するか、完全に帰還せずに同サイドの相手より1ターン早く帰還できる状況をキープしておくのがよさそうです。
- 浅層・中層を逃がせないなら、片方は奥へ行きすぎないようにプレイして3,4 finishを回避します。奥に残したほうで頑張って全スキャンと1～2匹追い出しをします。ボーナスを1点でも削れていれば逆転のチャンスはあり、例えばよくある浅層2中層2深層1色一致なしを同着にできていると、1匹逃がして先着側の2往復目より先にセーブできれば64vs61で逆転可能です。実は、ルール概要に貼った対Gold Bossの状況がまさにこれです。自分自身がGold帯にいた時は3,4finishを避けて最低1機は帰還順争いに参入するという意識が足りなかったので苦戦していたのだと思います。
- 3, 4finish確定してしまった時は、深層2匹逃がして引き分け狙いしかないです。Gold帯ならシンプルに1機1匹割り当てでいいですが、Legend帯だと少し上をキープされて追い出し前に追加スキャンを狙われるので、1機は帰還させます。以下のように持っていきたいところ。
  - 対戦相手が両方帰還するなら残り1機が2匹追い出しを頑張り、帰還役は(1)帰り切るか(2)途中で引き返して相手がついてくるかを問う、の2択。
  - マンツーマンディフェンスしてくるなら深層役はy座標深くなりすぎないよう警戒しながら誘導しつつ、帰還役が浅層・中層を相方の分までスキャンして本来取れない星を取りに行くことで有利を狙う展開 (実装間に合いませんでしたが)

TIPS

仕様
- ドローン移動
  - 600.5未満ならOKなので、(600,24)のような移動が可能です。
- 相手ドローンのライト区別
  - バッテリーの増減で判断可能です。
- スキャンタイミング
  - 移動後に行動で指定したライト点灯・消灯に応じてスキャン判定が発生します。
- 魚の生存判定
  - レーダーblipが存在しなかったら逃げていることが判明します。
  - 魚が見えている場合、騒音判定・速度は確定したら変更できないので、魚の画面外移動は1ターン前に確定します。確定している状態からだとどういう行動をしても次ターンスキャンできないのであきらめるしかないです。
- 鮟鱇のシミュレーションでバグらせやすい部分
  - 鮟鱇同士の衝突
    - 衝突後は速さ270ではなく、200です。
  - 残像
    - y<2500の鮟鱇が移動できない位置にも衝突判定時は移動しようとしていて当たり判定があります。y=2500付近で事故りやすいドローンはこれを考慮できていない可能性が高いです。
    - 上記残像判定と実際にy=2500でのクリップ処理による鮟鱇移動位置の違いのせいで、ドローンと鮟鱇との距離が500以内なのに緊急モードにならないことがあります。次ターン緊急モード確定なのでそこまで意味はないですが。
  - 完全一致
    - 追跡で2匹以上の鮟鱇の座標が完全に重なったとき正しい動きをしているかはちゃんと検証しておいた方がいいです。他の鮟鱇と衝突しない移動をします。
- ゲーム終了条件
  - 魚を逃がすタイミングでまだゲーム終了してはいけないのにゲーム終了することがあります。例えば、お互いセーブなし11匹逃げている状況で12匹目を自分だけスキャンして12匹目を逃がすと、本来帰還途中で鮟鱇にやられた場合引き分けになってしまうので帰還するか200ターン経つまで続けなければならないが、魚を逃がしたタイミングでゲームが終了してスキャンが自動セーブされます。これを利用して、あとは帰るだけとなった時に魚を逃がして終わらせるケースがありえます。
初心者向け戦術
- セーブは y<=500 で可能で y=500 より上へ行く意味はないので、それより地上の座標になっていたらy=500まで戻せます。
- 未スキャンの魚を意図せず逃がしてしまっている場合、単純な解決策としては、消灯中のx<1800, 7199<xへの移動を低評価にしておくとよいです。もちろん、もっと正確にできます。
- 魚を追い出すときは、できるだけ消灯したほうが変な鮟鱇呼び寄せが起きないので成功しやすいです。
- 深層の魚をスキャン完了するターンを短くすることは最重要なので、その付近になったら連続でライト点灯させましょう。

おわりに

開始当初は純粋にシャトルランTAの早いほうが勝つ位置推定精度勝負ゲームになるかと思われましたし実際最終1位はそういう動きを学習していそうに見えますが、後手を引いたときの対策が色々出てくると多様性が出てきて面白くなってきました。
シルバー帯の頃から10位付近にいたので終始モチベーション高く取り組めました。
2手読み実装中はバグ取り期間が長く沈んでいましたが、振り返っても最終的にどこかでやらなければならないことだったなという感じです。改善するとしたらもっと早く取り組み始めるべきだったかもしれないというぐらい。
期間中の順位表はいつもよりも信用ならなかったように感じました。特にGold帯は進捗100%になるだけではまだ対戦数が足りていなそうです。
Contests部門初の一桁順位になれてうれしいです！

備考

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

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up