CodinGame Summer Challenge 2024 は十字キー1個で4ゲーム同時操作させるAI同士のバトルでした

Last updated at 2024-07-03Posted at 2024-07-03

はじめに

2024/06/11～2024/06/25に行われたゲームAIコンテスト「CodinGame Summer Challenge 2024」に参加しました。
以下、CodinGame Summer Challenge 2024 及び OLYMBITS - SUMMER CHALLENGE 2024 の画像を利用しています。
CODINGAME コンテストページ
- Contests 期間限定で終了済み。
- Bot Programming 常設版。終了後の現時点で遊びたい方はこちらから。
結果
- 30位 / 5237人 (日本人の中では5位、レジェンドリーグ到達者は全体で62人)でした。いつもいる順位帯よりは少し悪かったですが、何とか耐えたって感じです。
CodinGameとは?
- 開催回毎に異なるゲームに対する AI Bot を作ります。提出すると、他の参加者の作ったAI Botと自動で対戦して順位がつきます。
- 実力に応じてリーグ分けされており、下位リーグのうちは簡素なルールにっているため参入障壁が低めです。今回はWoodリーグはボスとしか戦わないかなりシンプルなつくりになっていました。
- 最上位のLEGENDリーグ以外にいる間はリーグBOSS というAI Botの中身が変化しない絶対目標があり、対戦ゲームでありながらソロゲーのような自分との闘いに変換もできます。各プレイヤーはリーグ昇格のみ可能で、降格することはありません。
- CodinGameの良いところはリプレイを見て改善を考えられるところですが、今回に限って言うとリプレイ読解難易度がかなり高く、4つのミニゲームが同時進行していく中で対戦相手が何をしようとしているのかはパッと見わからないので、そこから何かを得るには実力が必要という感じでした。

ルール

未参加状態で参照できる1次ソースはGitHubです (が、このままでは読みづらいです)。
3人の参加者が作ったAI同士が対戦します。
ゲームは100ターンからなります。
4つのミニゲーム(ハードル・アーチェリー・ローラースケート・ダイビング(飛込))が同時に開催されます。
- 一回のミニゲームは大体12～15ターン程度で、ミニゲームが終わったら結果発表ターンが1ターンあり、その次のターンから同じ種目が再び始まります。
  - なので、100ターンの間に各種目だいたい6, 7回行われます。
ミニゲーム順位に応じて金・銀・銅メダルが付き、点数としては順に3点、1点、0点です。
- 同着は全員良い色のメダルになります。なので順位は1-1-1, 1-1-3, 1-2-2, 1-2-3のパターンがあり得ます。
- 100ターン経った時点で、各種目について点数を合計して4種目の点数の積が最終スコアです。
  - 積なので、銅メダルしか取れない種目があると他がどれだけよくても0点です。
操作はUP, RIGHT, DOWN, LEFTの4択で、全部のミニゲームに対して同じ操作が送られます。
- つまり、4ゲームあるのに1個の操作指示しかできないのがこのゲームのキモです。
- 結果発表ターン中や転倒中など、どの操作を送ってもそのミニゲームへ影響しないことがあり、その瞬間は他のミニゲームに集中できます。
- Olymbitsの題材はパリオリンピックですが、このプレイ制約上転倒・コントロールミス・コンボミス多数の展開になるのが必至なのでオリンピック選手が競技しているとは思えない滑稽な画面になっています。
ミニゲームが終わる前に100ターンに達してしまった場合、途中状態になっている最後のミニゲームは全員メダル獲得なしです。

ハードル

スタートから28マス先にあるゴールへ最初に辿り着いたプレイヤーが現れたらその人が1位、2位以下はその瞬間の座標で決定します。
道中にはハードルがあり、ぶつかると2ターンハードルの座標に倒れて動けなくなります。これをスタンといいます。
方向と移動の対応
- 転倒中は方向が無視され、転倒復帰へ向けた固定の回復処理が行われます。
- UP: 1マス先のハードルを飛び越えて2マス先へ着地。2マス先にハードルがあったらその位置でスタン。唯一ハードルを回避できる行動。
- RIGHT, DOWN, LEFT: 順に3, 2, 1マス移動。ハードルに接触したらハードルの位置でスタン。

アーチェリー

ターン毎に各プレイヤーx, y座標を内部状態として持っており、ミニゲーム終了ターンに達したタイミングでその座標へ矢を放ちます。
座標(0,0)とのユークリッド距離が短いほうから良い順位となります。
毎ターン風量が1以上9以下の値でランダムに設定されており、ミニゲーム終了ターンまでの風の推移はミニゲーム開始時に固定され情報開示されています。
方向と移動の対応
- UP, DOWN: y座標負, 正の方向へ風量分移動します。y座標は下方向が正。
- LEFT, RIGHT: x座標負, 正の方向へ風量分移動します。
なお、x, y座標ともに-20と20に見えない壁があってそこより外側に行こうとするとせき止められるので、取りうる座標のパターンは41x41通りです。

ローラースケート

15ターンの間で前へ移動できた距離の長いプレイヤーから順位に良い順位となります。
スケート場は楕円のトラックになっていて、1周10マスで区切られています。
リスク
- 行動や他競技者との接触状態により、ミニゲームプレイ中に増減します。
- 選んだ移動によって、後述のとおりリスクが増減します。
- 移動後に2人以上同じマスにいると、リスクが+2されます。これは、転倒復帰直後も含みます。
- リスクが+5以上になると、移動後に転倒し、2ターンの間動けなくなります。
方向と移動の対応
- 転倒中は方向が無視され、転倒復帰へ向けた固定の回復処理が行われます。
- 中央に4方向の矢印がランダムに並べられていて、何番目に配置されている方向かで行動が変わります。
- 一番左: 1マス進み、リスクが1以上ならリスクが-1されます。
- 左から2番目: 2マス進みます。
- 左から3番目: 2マス進み、リスクが+1されます。
- 一番右: 3マス進み、リスクが+2されます。

ダイビング

ゲーム終了ターン(着水) 時点のスコアが高い順に良い順位がつきます。
ゲーム終了ターンまでの入力方向の系列が与えられています。
方向と移動の対応
- 現在の指定方向と一致: コンボが+1された後、コンボの数値だけスコアへ加算します。
- それ以外の3方向: コンボが0になります。
例えば、終了ターンまで15ターンだった場合、全ターン指定方向と一致させれば、スコアは1+2+3+...+15=120となります。

各ミニゲームの攻略

大抵のゲームがDP(動的計画法)っぽくなります。
一部他のミニゲームが侵食していますが、実装区分上ミニゲーム単体毎の前処理に入っているものは述べます。

ハードル

あるマスからゴールへたどり着くのに最短何ターンかかるかは、ゴールから逆順に求まります。持ち方は3x29でも、29でスタン状況に応じて足し引きするでも。
2位決定戦は1位のゴールしたタイミングの座標を見るため、ターン数だけ見ていると間違えます。
ハードルの生成パターンは限られており、列挙したところ251パターンしかなかったので初手で前計算できます。
- 入力を受け取ってから行動を出力するまでに1手50ms以内であること、というルールがあります。ただし、初手だけ1000msと緩和されているので、前計算できるところは初手でできるだけやっておきたいのです。

アーチェリー

平方根を求める必要はないので、平方で考えます。
- 平方のパターンは198通りなので、座標圧縮のようなことができます。
ミニゲームがリセット新規開始されたターンに以下の前計算をやります。
- 残りターン逆方向に計算します。
- 41x41の座標全部に対して処理します。
- 初期化
  - 現在の平方をセットします。
  - パターン数を1としてセットです。
- それ以降
  - 現在座標から4方向移動したときの移動先の平方のベスト(min)をセットします。
  - 平方のベストが複数あったらパターン数を加算します。
上記行動により、現在のターンから最終的に平方いくつまで行けるか、そのパターン数は何か。あるいは、今4方向移動した後にどうかというのが計算でき、どれくらいの自由度があるかはパターン数でわかります。
なお、壁に当てることにより偶奇性をずらしてはじめて最小平方が0になる(壁にあてないと1)パターンがありますが、自由度が低すぎて他のゲームへ影響が出るので、壁に当たらないパスのベストは別途求めておくとよいです。
ハードルを考慮したランダム
- ハードルが大抵RIGHTやUPになる以上、途中は左下に陣取っているほうが状況がよさそうに思われます。
- というわけで、最善計算中の4方向のmin演算をする代わりに、ハードルの確率分布で選ばれるとした後の座標圧縮後の距離(0以上198未満)の期待値も求めておきます。

ローラースケート

ゲーム開始時に1対1勝率を作成します。第三者はノイズとしてランダムに配置しランダムにプレイアウトします。
- 状態区分
  - 先行側視点で何マス優位か
  - 先行側のリスク・転倒ターン数
  - 追いかける側のリスク・転倒ターン数
- 行動選択確率
  - 最終ラウンド
    - 3マス移動リスク+2の比重高くします。
  - それ以外
    - 表示順に対して大体2:3:2:3の事前分布とします。
- 残りターンが短いほうから逆順にプレイアウト結果を計算し、1手プレイするごとに計算済みの分布を参照しサンプリングします。
- 全状態埋める前に時間切れするのを防止するため、いったん制限時間に対し十分余裕のある固定プレイアウト回数で全部埋めたあと、1プレイアウトずつ増やしていきます。水平分割から垂直分割への切り替えというイメージです。
各ターンの勝率
- 状態+その時の1対1勝率が3個あったところで、じゃあ3人対戦したときのメダル期待値はどうなるの?の計算はよくわからなかったので、おそらく正しくはないですがひとまず以下のようにしました。
  - 1人選び、そのプレイヤーがいる勝率2つから分布を合体します。
  - 残り2人の序列が不明なパターン(両方に負けている or 両方に勝っている) のみ、3つめの分布に従って分布を合成します
  - 上記処理を1人目に選ぶ対象を3人全員に対して行って平均をとります。
  - 最終的に各プレイヤーに対し金メダル確率何%, 銀メダル確率何%, 銅メダル確率何%という3値を出します。
- 自分の行動は4パターン、相手2人の行動は4x4=16パターンで、相手の16パターンを加重平均を計算します。
  - 加重平均は深く相手の手を読んでいるわけでなく条件反射的なものだけ考慮しました。
  - 表示順に対しての事前分布
  - 最終ターンは3マス移動リスク+2にボーナス
  - コンボ中の相手のダイビング方向にボーナス
  - ハードル目の前4マス状況に応じたボーナス (ハードル直前のUPにボーナス etc.)
- というわけで最終的に、自分の4方向それぞれに対し、自分の金銀銅はそれぞれ何%か、相手の金銀銅はそれぞれ何%かという9次元ベクトル、全体で36次元ベクトルとなり、これを評価値に使います。
  - 2手目以降のシミュレーションは一切しません。

ダイビング

指示された方向を入力するのがこのミニゲーム単体行動で見たときの最善行動です。シンプル。
追加情報
- 相手が今後スコアいくつまで伸ばせるかは計算できるので、その点数を超えていたらあとは何でもOKです。
- 相手がこのターンミスした後のスコア理論値はいくつかも情報として有用です。

探索部

他の人のpostmortemを読んでいるとMCTS系(DUCT等)が大多数だったみたいですが私はひたすら幅4x512のビームサーチで自分の手だけ改善していました。
- 4x512とは、初手方向別に幅512の探索をしたという意味です。
シミュレーションは、既知のゲームしか行わずリセットはしません。ローラースケートは初手しかプレイしません。
- ダイビング序盤のころにはスルーして最後の方でコンボすれば効率いいよねという状態になっていたので、これがよかったのかは不明です。少なくとも探索ノード数は増やせました。
評価関数
- 相手の手は最善手でスコアいくつになるかはわかっているので、そこに追いつくか否かの地点に不連続なボーナスを用意しました。
  - 逆に、相手が緩むと追いつけるという部分に対するモチベーションが少額しか発生しませんでした。
- ダイビングスコア素点などは上記ボーナスと比べると少額になっており、メダル状況が等しいもの同士で使われる程度でした。
- ローラースケートのみは前項で述べた通り連続的な値を持っているので、他種目の小さな差よりはローラースケートの勝率変動の方が影響力強くなっていて、メダル状況が同じもの同士ならローラースケートの状況が良くなるように動く、という感じになっていました。
  - 結果的に同レベル帯の勝ちパターンでは大体ローラースケートで優位(金3銀2の11点以上)なことが多かったです。
- 種目間の比重
  - 各種目の得点に2ずつ下駄を履かせて(序盤の0点問題を回避するため)、銀メダル1枚取る前後のスコア差分を4種目それぞれについて出し、4種目の最大値で割っていました。
  - あとはミニゲーム毎の残りターン数におおよそ反比例する項をかけます。
ダイビングの特殊処理
- 上記評価関数だと、ダイビングでまともなコンボを見つけてくれる確率が低かったので、決め打ちでテコ入れしました。
  - もちろんスコアやコンボの比重を上げればコンボも見つけてくれますが、全種目中途半端になって弱くなったため不採用でした。
- 具体的には、ダイビングで6点(金2)に到達するまでは比重を高くし、金メダル取れる状況から参戦して絶対に譲らない状況にします。
  - ゲーム開始直後は確定で行います。
  - 金2枚目は、最後まで2人以上でコンボを繋ぎ続ける不毛な争いをしたときに他種目の状況がどうなるかをみて、互角以上の時だけ入るようにしました。
- Goldボスはしばしば最初から付き合ってラスト直前で中途半端に降りてくれるので、特効行動になっていました。これを入れてから明らかに勝率が上がりました。
- Legendリーグだと、ここまで露骨にBronzeボスクラスのダイビング決め打ち行動している人はまずいないのでローラースケートが被りづらく(被ると衝突するので不利)、そこそこ機能していました。

リーグ別やったこと

Wood2(6/11)
- ハードル1ゲームのみ。
- ハードル位置に応じて貪欲に前に進みハードル手前に来たら飛ぶだけ。
Wood1(6/11)
- ハードル4ゲーム同時進行。
- LEFT(1マス移動) - UP(2マス移動,ジャンプ) の手順が必要な場合、LEFTは効率が悪いのでこの配置が2箇所以上ない限りLEFT必要なシーケンスは見捨てる。あとは手前のハードルに座標合わせて跳びます。
Bronze(6/11)
- Bronzeリーグ到達RTAは15位でした。
- ここからハードル・アーチェリー・ローラースケート・ダイビングの4種目になり、以降ルール固定です。
- 1位確定するまでダイビング。確定したらハードル、アーチェリー。
  - Silverリーグ解放時点で上がってしまったのでBronzeボスと直接対決しませんでしたが、この時点のと戦うとずっと不毛な争いします。
Silver(6/14)
- シミュレータを組む。
- 各ミニゲーム単体のソルバーを書き、最善行動の集合を出力します。その行動最善なら1というビットが行動毎に立つイメージ。2の4乗で16パターンです。
- 獲得メダル数・残ターン数に応じてミニゲーム単位の最善行動とマッチしていたらスコアに加算。スコア最大行動を選択します。
- Goldリーグ解放と同時に昇格しました。
Gold(6/18)
- ランダム行動時のゲーム単位のメダル期待値をきちんと計算。
  - 分布計算時の浮動小数点演算が膨大だったので不採用でした。
    - 例えばアーチェリーは平方パターン数毎に確率が存在する198次元ベクトルとなり、金銀銅をつけるために内積が必要だがこれが重いです。
- 4種目同時にどう頑張るのか見当がつかなかったので、ひとまず2種目を頑張る行動系列を探すDFSにしてみました。
  - (ダイビング+他) ダイビングのコンボ数が長い系列から順に他種目へ当てはめてスコア計算します。
  - 1番頑張る種目を制約条件と見て、その種目でメダルの色が悪化しない行動に限定した状態で2種目目の評価値を最大化する探索を実装しました。
    - 1番頑張る種目とは、主に金メダルを取りうるが確定していない種目。この辺は1位タイか、自力2位可能かなど細かく分岐して順位付けしました。
- 6/21 Legendリーグ解放・Gold Boss出現。こちらとスコアが7くらい違って絶望。※スコアは1日2上げるのも結構しんどいイメージ。終了前にGoldボス超えられるかどうかというラインです。
- 2種類探索(制約+最大化)をミニゲーム組み合わせごとに何パターンか作って試した結果、相手の最善手に対して順位変動する・しないの地点に不連続な大きいボーナスを与えればそれが実質制約となって、1個の関数で全部よしなにビームサーチできそうだとなりました。
  - ビームサーチ実装完了時点でスコアが5程改善しGold1桁順位に。だいぶLEGENDリーグ到達の希望が出てきました。
- ミニゲーム単位の残りターン数に応じた評価値重みづけや同点時の処理を主に調整してGold1-2位あたり安定していました。
  - 同点をよしとするとGold Bossが環境内で一番協調的でGold Bossを助けてしまっている感があったので同点をよしとしない調整に変更。
- 6/23 ダイビングの決め打ち処理を入れて40人目のLegendリーグ昇格！
Legend (6/23-25)
- 実装可能な時間がほぼなかったのでパラメータ探索メイン。主に種目間の評価値や対戦相手のメダルに対する重み調整をしていました。
- ローラースケート前処理のプレイアウト精度向上・高速化。
アイディアはあったが時間切れで実装できなかったこと
- もう少し時間があったら、終盤に点数を見て、逆転にはこの種目の金が必要とか相手に銀を渡してはいけない、といった種目取捨選択方針の実装はしたかったです。

おわりに

今回はFall Challenge 2020の時のように、そもそもソロプレイとして効率よい行動を見つけられていないと相手の手を読んでもしょうがないというタイプのゲームだと思っていたので他の人がDUCTだらけだったのは驚きでした。
- 実際はローラースケートが次のターン以降の方向対応がわからないせいで深くまで読んでも使えず、それよりも探索深度が浅くてもちゃんと相手の八方美人な行動を読んでそれに対する対応を考えていかないといけないゲームだったみたいですね。
ローラースケート以外の狙った1種目を勝てるようにしつつスコア低い種目を攻める、というところ(Goldリーグ到達程度と思われます)までは目標が明確で実装は1種目ずつ段階的に進んでいきやすい一方、そこから先に行く時にリプレイから学びを得づらく大変でした。
最終的に見た目は普通のビームサーチになりましたが、そこに至るまでにダイビングコンボ長い順に探索するとか、アーチェリー最短距離維持しながら他種目を頑張るといった、1種目目を制約とみなし2種目目を最大化するという途中段階があってのそこへの到達でした。
次回は大方針選択ミスしないように引き出し増やし頑張ります！

備考

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

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