はじめまして、learningBOX株式会社 開発部 開発課 バックエンドエンジニアの松永です。

CodinGame の Spring Challenge 2023 という、ゲームAIを作って参加者同士で競わせるコンテストに参加しましたので、結果や実装方針についてつらつらと書きます。

ルール

ツカモさんのブログが詳しいです。

ざっくり説明すると、以下のように点対称なフィールドが与えられるので

菱形で示される蟻さんロボットをビーコン(各マスの青枠や赤枠)で誘導して移動させ

自軍のベースから資源までの経路が繋がると資源を獲得でき、たくさん獲得した方が勝ち！というゲームです。

集める資源は黄色のクリスタルです。なお、灰色の丸い方(卵)を取ると蟻の数を増やすことができます。

コンテストはいくつかのリーグに分かれており、参加者は Wood2 リーグからスタートして昇格していくシステムになっています。リーグの昇格とともにルールが追加される場合があり、先ほどの卵についてもWood1から追加される要素です。

結果

全体で 5290人中 205位 でした。上位4%くらいなので、悪くないです。

実は最終日(月曜)のAM5時半頃までSilverだったのですが、なんとかGoldに滑り込み、その日は仮眠とってシャワー浴びて出勤しました。これを会社のブログ記事として出すことが自分の首を絞めることに繋がらないか不安になる今日この頃です。

なお、リーグ昇格後には昇格時のコードでリーグ内での順位が再計算されるのですが、上記の順位は到達時にそのまま得られています。Silver帯が魔境すぎました。

また、今回は学部時代の母校も妙に頑張っていました。前回参加時は人数が少なすぎて集計対象外だったのですが・・・。

実装方針

完全ルールベース

機械学習的手法はおろか、探索過程での確率的な状態遷移(焼きなまし法)による最適化も行っていません。

「こういう時は、こうする」

というのを、全て温かみのある手作業で実装しました。

ターンごとの基本的な流れは以下の通りです。

• 入力
• ゲームの状況に関する有用な情報を計算(自陣に近い側の残りクリスタルの総数など)
• ターンごとの状況および初期値(フィールドの大きさ、ベース数など)に応じて以下の"戦略"から1つを決める
• • 卵優先戦略(ベースの区別無し)
  • 卵優先戦略(ベースごとに独立)
  • クリスタル優先戦略(ベースの区別無し)
  • クリスタル優先戦略(ベースごとに独立)
  • 前線維持戦略
  • アグロ戦略(ベース2個用)
  • 妨害戦略(ベース1個用)
  • 経路保存戦略
• 選択した戦略に基づきビーコンを設置するマスとその強度を計算
• • 設置はマスごとに行う(フォーマットを統一できるため、実装上は始点と終点を同一マスとしたLINEコマンドを使用)
• 出力

書いていて「"戦略"とかいうの乱立させすぎだろもっと取捨選択・統合して突き詰めろよ」と思いました。思いついたものをとりあえず実装して再現なく増えていった感が否めないですが、実際のところ他の戦略から処理を使いまわしたりすることが多々あったので、あと1日あればもうすこし統合しつつブラッシュアップできていたかもしれません。

とはいえ、8位の方もルールベースで戦略を決定していたようで、方向性としては間違っていなかったと思います。

(焼きなましのアプローチは私も発想としてあったのですが、CodinGameのターンごとの時間制限の性質上Pythonでは難しい気がしますね。。。)

ターンごとの"戦略"の流れ

それぞれの戦略では、以下の流れでパスを決定しています。

• 戦略ごとのアルゴリズムによって"ターゲット"のマスを選ぶ
• 選んだマスとベースを用いて最小全域木を構築
• • ベースを始点としたプリム法で実装
  • 重みはBFSで全点対の最短距離を前計算したものを使用
• 得られた各辺(親, 子)について、子から親に向かって距離が小さくなるように経路復元
• • 全域木を作ってから経路復元するのみるからに冗長そう
  • もともと最小全域木をそのままLINEコマンドで結んでいた名残でもある
• (戦略によっては)強度を計算し、強度と蟻の数次第でターゲットを追加して経路の再計算を繰り返す
• (戦略によっては)前ターンの経路を流用するかどうかを判断
• • 厳密には、「前ターンの経路から資源枯渇等に伴い不要になった辺を削除した経路」を流用
  • この辺の条件は割と適当
• 新規に構築した経路or流用した経路を用いて、強度を確定させて情報を返す

経路の流用に関して補足します。

①から④の経路をつなぐ以下のグラフについて②の資源がなくなった場合を考えると、

以下のように繋ぎなおすのが最短になります。

しかし、このような辺の繋ぎなおしは蟻の移動を伴い、辺が途中で途切れている間は一切の資源が取得できません。常に最短経路を選択する場合、相手の行動を考慮しなかったとしても短期的に損する可能性があります。

そのため、場合によっては経路を維持することが有効になりえます。自分は主に資源の枯渇によって不要になったマスを考慮しつつ、獲得可能な資源マスの集合に変化が無ければ流用する方針を採用していました。

ちなみに、上記のグラフはReact DnDの練習のために少し前に自作したものを使っています。

余談、いや、本題なのですが、弊社ではフロントエンドチームとバックエンドチームが分かれているものの、なんだかんだで両方書ける人が多数在籍しています。

私はもともとバックエンドエンジニアとして入社しておりReactはド素人(チュートリアルちょっと触ったくらい)だったのですが、彼らに刺激されて「Reactなにもわからない」と言いながら遊ぶようになりました。(Reactなにもわからない)

learningBOX株式会社では一緒に働く仲間を募集しています。一緒に刺激を受けましょう。

戦略別の紹介

ターン毎に行うそれぞれの戦略について軽く紹介します。だいたい名前の通りです。

• 卵優先戦略

文字通り、卵を優先して取得します。取得数が少ない場合は他の資源を混ぜたりもします。

初期クリスタルが非常に少ない場合などを除き、基本的にこれからスタートします。

ベースに関して区別する戦略と区別しない戦略の2パターンを用意しており、区別させる場合は各マスにいる蟻について「近い方のベースに所属」しているものとみなし、ベースごとに独立して経路と強度を生成しています。

ベース間の距離が離れていて卵の分布に偏りがあるような場合、ベースの区別をせず一方のベースにいる初期蟻が他方のベース付近の卵に誘導されたりしてしまうと、非常に長い待機時間が発生してしまいます。

一方で、ベース間の距離が近いときに偏りがある場合、自分の管轄の卵を取りに行くよりも他のベースの卵を取りに行く方が良いケースがあり、それならばそもそも区別しなくていいじゃないか、という話になりそうです。

そのため、入力で複数ベースが与えられた場合は基本的には区別しつつも、ベースの距離が近い場合のみ区別しないように戦略を選択しています。

• クリスタル優先戦略

これも文字通りです。卵優先の場合は取得数が少ない(蟻が余る)場合クリスタルもターゲットに混ぜたりしていますが、クリスタル優先ではそんなことはしません。

クリスタルを優先したい頃というのはゲームエンドの頃であり、卵を取りにいくのは悠長であるためです。

• 前線維持戦略

自分のベースと相手のベースの位置を基づき、互いに距離が等しい(前線)のクリスタルおよび前線より少し自陣側のクリスタルを最優先に取得します。

フィールドが点対称なので、お互いのベースから等距離にあるマスの資源を確保することが勝敗に直結することは想像に難くありません。

• アグロ戦略

クリスタルがあまり多くないフィールドなどで序盤に卵を優先しているとテンポが悪くて負けることがあったので、「結局、場合によっては卵・クリスタルを見境なく取りに行くのも大事だよね」という発想で生まれました。言うほどアグロではない気もします。

元々はベースの数を問わず使用していたのですが、最終提出時にはベース2個の際にしか使っていません。初期の頃と比較して卵優先戦略で蟻が余りそうなケースなどの処理が改善されていることもあり、コンテスト期間があと1日あれば選択と統合ののち単独の戦略としてはなくなっていたかもしれません。

• 妨害戦略

リーグが上がると、自分の蟻による経路の重みが相手を上回っている場合、相手の経路を遮断することができるようになります。

つまり、ベースが1つのときに相手のベースを抑えれば相手は一切の資源を獲得できなくなります。

妨害時に辺を変更するような対策をしていない相手を遮断できると場合、相手は取れない資源を取ろうとし続け、一方的に詰ませることができます。

とても魅力的な戦略ではありますが、ベースが複数ある時の理想的な妨害方法が確立できなかったため、ベースが1個の入力値でのみ使用しました。

• 経路保存戦略

先述した経路の流用を試みる戦略として作られたものです・・・が、主要なロジックが他の戦略に逆輸入されたため、実質「他の戦略の条件に該当しないからとりあえずやっとけー」みたいな感じで残っています。

こちらも、コンテスト時間があと1日残ってればなくなってたと思います。

その他寄与したこと

正直、戦略がどうのというよりこっちの方が大事まであると思います。

• ビーコン強度

Silver到達からずっと

• • 強度1決め打ちをベースにして未達のマスなどに重みづけ
  • 資源量、距離などに応じて増減

といった小手先の改善で実際の蟻の数と向き合うことから避けていたのですが、結局蟻の数とビーコン強度が対応するように実装しなおしました。ライン取りや判断をうまくやればビーコン強度は気にしなくてもGold到達は可能かもしれません。

• 現在スコアの情報を生かす(Silverから入力に追加)

自陣サイドの資源の総和と現在スコアを足してもなお初期クリスタルの半数に届かない場合、相手陣から奪い返すのが必須になります。

これは一見して自明なのですが、私は最終日まで割と

「結局勝てる相手には序盤からリードしてるし前線も確保できてることが多そうだし、現在スコアとにらめっこするよりも経路の最適化を頑張れば自ずと勝てるんじゃ？」

と軽視しがちでした。Gold到達時の提出差分を鑑みると想像以上に重要だったように思います。

自分の場合、勝利条件を上回るように敵陣にも経路を繋ぎに行ったり、負けそうな局面からワンチャン狙いに行くために妨害戦略を実行する判断材料にしています。

おわりに

今回参加して改めて感じたのですが、CodinGameは以下の点からプログラミングコンテストに馴染みがない初心者の方にもおすすめです。

• ボスを倒すという明確な目標がある
• • 初心者にも目標がわかりやすく、かつ段階的
• ビジュアライザが非常によくできている
• • 視覚的に考察しやすいですし、モチベーション的にも良いです
• 難解なアルゴリズムの知識が必ずしも必要でない
• • 今回の私の解法もルールベースが主体です
  • アルゴリズムに関しては幅優先探索など基本情報技術者レベルの知識があれば十分戦えます
• 対戦ゲームである
• • 相手の動きが見えるので対策や攻略、改善がしやすいです

また、実務開発では「実際の実装時間よりも既存のコードを読んで確認する時間の方が長い」ということがしばしばありがちですし、マネジメント系の仕事が増えるとコードを書く機会も減ってきます。

「最近、数百行のコードをガーっと書く機会減ってるなぁ・・・」

という方々にもおすすめです！是非やりましょう。そして生活リズムを破壊しましょう！