Codingame Summer Challenge 2026 で24位になりContests部門Top10入りしました

はじめに

• 以下、 Codingame Summer Challenge 2026 ないし BACK TRACK KING - Summer Challenge 2026 の画像を利用しています。

• Codingame Summer Challenge 2026 とは
  • 2026/9/7～2026/9/21 の間行われたBot Programmingという参加者の提出するAIコード同士を戦わせる競技です。運営が夏といったら夏です。
  • 開催回毎に異なるゲームに対する AI Bot を作ります。提出すると、他の参加者の作ったAI Botと自動で対戦して順位がつきます。
  • 今回は2次元グリッド上で行われる、同時手番2人対戦ゲームでした。
  • 実力に応じてリーグ分けされており、今回は6リーグに分かれています。
• CodinGame コンテストページ
  • Contests 期間限定で終了済み。
  • Bot Programming 常設版。終了後の現時点で遊びたい方はこちらから。
• 結果
  • 24位で過去の参加実績からいうと平均的な順位でした。
  • 最上位であるLegendリーグへ到達するためにはGold Bossを倒す必要があるのですが、それがとても強かったため、最終的なLegendリーグ到達者はわずか 28名 / 全体1,595名 といつもよりも狭き門でした。うち日本人は苦手ジャンルだったのか私含めてわずか2名でした。
  • Contests部門総合は過去良かった成績3回分(古いと減衰あり)の合計で順位が決まりますが、そちらは12位から8位に上昇しました。日本人だとトップです。

基本ルール

• 高さ最大20, 幅最大30の2Dグリッドマップが与えられます。
• プレイヤーは毎ターン3アクションポイントの線路敷設と1地域を墨で塗る行動を行います。
• マップ上に駅(町)が最大12箇所置かれており、始点・終点のペアがいくつか設定されています。
• 毎ターン、線路で接続している始点・終点ペアそれぞれについて汽車が走ります。汽車が通った線路の所有者に1マスにつき1点入ります。同時に同じマスに両プレイヤーが敷設することがあって、その場合は中立線路となり汽車は通行はできますが得点は入りません。
• 汽車が通る経路が複数ある場合、BFS距離が最小のものが選ばれます。BFS距離が最小となる候補が複数ある場合、汽車のいるマスから見て北>東>南>西の優先度で貪欲に選ばれます。
• 線路敷設は、平地なら1、川なら2、山なら3アクションポイント消費します。よって、「平地x3」「川+平地」「山」のような敷設パターンがあります。
• 同一地域が4回墨で塗られると、そこは真っ黒になって通行不可になります。以下これを沈めると表現しています。3回までなら特にペナルティなく通行可能です。駅を含む地域は塗ることができません。
• 100ターン、あるいは墨で始点・終点ペアが全部分断された時点で終了。合計得点が高いほうが勝者です。大体数百～数千点ぐらいになります。

実際のリプレイで確認

• https://www.codingame.com/replay/905442946
  • 赤対青で行われており、上部の数字が獲得した合計得点です。この数値が高いほうが勝利します。
  • 赤/青の線路はそれぞれのプレイヤーに所有権がある線路で薄茶色の線路は中立です。
  • 数字が書いてあるのが駅で、駅をマウスホバーするとDesiredという文字が表示されます。始点の駅の側に書かれているDesiredが終点の駅番号です。
  • 線で区切ってあるのが地域です。墨が塗られると地域の外周の黒が濃くなっていき、4回塗られると真っ黒になって通行不可になります。29ターン時点でどの始点・終点ペアも分断されたので終了。

アルゴリズム・方針

• 自分でリプレイ眺めてもどういう行動すれば勝ちに結びつくのかわかりづらくコードに落とし込みづらかった一方、結果的に各マスに置いた線路が何点稼いだという敷設行動と勝利への寄与度の結びつきは比較的わかりやすそうなので、最初から強化学習で行くことにしました。
• 自分でリプレイ眺めて分かった強いと思われる行動
  • 駅と同じ地域にある沈まないマスに線路を敷く。
  • 中央付近の複数の駅ペアが使う線路を敷く。
  • 完全に分断するのに必要な地域数が多い駅から線路を敷く。
  • 全部線路だった時に北東南西の優先度上汽車が通ることになる経路を最優先経路と呼ぶことにする。最優先経路上に敷く。現在接続済みの経路が最優先経路じゃなかったら、既存経路の隣のより優先度が高い位置に敷いて経路を更新し得点を奪う。
  • 墨で沈み切る前に分断先の迂回経路を確保する。
  • 敵メインの未接続経路は相乗りすると収入差を減らせるものの繋ぐお手伝いになってしまうので、できるだけ線路でコミットせず墨で沈めて分断する。
  • 墨で沈める場所を4ターンに1地域のペース以上に抱えてしまうと妨害が間に合わなくなるので、間に合わなくなりそうな分は相乗りや隣接邪魔で収支差を軽減する。逆に相手には複数地域沈めないといけない状況を押し付ける。
• 強化学習手法選択
  • 試行を増やすための軽量さを重視して、上位リプレイからのBC(Behavior Cloning, 模倣学習)で事前学習済みモデルを作ってからのPPO(Proximal Policy Optimization)にしました。
• 推論はC++、学習はPython + PyTorchでした。
• ネットワーク選択
  • 経路探索情報が必要なので、ある程度広い視野が必要です。
  • Dilated Convolution, ResNet, U-Net, Transformerあたりを試して結果的にU-Netにしました。
• ネットワークサイズ
  • 32チャンネル 3段(20x30, 10x15, 5x8), 段の間は 2x2 max pooling, パラメータ数130,000程度になりました
    • 提出はコードとNN重み合わせて100,000文字以内に収める必要があります。UTF-16LEを使えばサロゲート領域など特殊な部分を避けても32768パターン以上確保できるので、1文字あたり15bitぐらいの情報量にはできます。
  • 学習中は提出サイズ気にせず大きいモデルで学習して教師モデルとし、DAgger (Dataset Aggregation) + QAT(Quantization-Aware Training, 量子化認識学習) で蒸留しました。
    • 稼働させた所持GPUがRTX4060とGTX1080なので、GTX1080 (VRAM 8GB)で問題なく学習できるサイズという制約で大きさを設定した結果900,000程度のパラメータ数になりました。
    • DAggerでは、生徒モデルの行動によって生じた局面について大モデルを教師として推論最終層の値を得て、学習データに追加します。
    • 提出モデルはfp32で学習した後、層別にビット数を変える量子化を行います。提出サイズとパラメータ数の兼ね合いから、平均7bit程度になりました。
    • 各層のbit数を定めた後QATを開始します。QATでは、重みをfp32で管理しつつもforward演算するときに量子化する前提の演算結果を使いlossを計算することで、量子化後の推論結果が教師モデルに近づくように追加学習します。
  • メモリ制約は文字数制限と比べると無視できるので、初手で重みを展開すれば以降は普通にfp32演算でよいです。
• 出力
  • 墨ヘッドと線路ヘッドがあります。どちらも20x30の2Dグリッド状の出力。
  • 墨ヘッドの出力をもとに墨地域を選定。地域内の各マスの出力 x を softmax(βx) で重み付けした加重平均 (β=4.0) を地域ごとに比較します。β=0 なら単純平均、β→∞ なら最大値になるので、その中間で最大値寄りの集約です。
  • 墨塗った後の盤面内で線路敷設マスを決めます。アクションポイントが残っていたら敷設後の盤面で再度推論を繰り返します。
  • 検討したが不採用
    • 狙う駅の始点・終点ペアを線路敷設前に予測するようなヘッド・処理をいろいろ試していたのですが、結局やめてシンプルにしました。
    • 相手の行動を予測して盤面へ反映する系は全部切りました。
• 入力特徴量
  • 20x30の43平面。
  • 入力そのまま転記するだけのタイプは特筆事項が無いので以下省略します。
  • 中央グラデーションとして、中央が1, 4隅0として内挿
  • 盤面内か (与えられるマップは常時20x30とは限らずもっと小さいことがあるため)
  • 駅セル
    • 何ペア接続中か, 何ペア未接続か
  • 地域 (マス単位だが同一地域同じ情報)
    • 地域マス数
    • 墨を塗れない (駅がある) 地域か
    • 地域内の所有者別線路数, 差
    • 相手が直前墨塗ったと思われる地域か
    • 地域を沈めた時の点数増減
    • 地域を沈めた後その外周だけ経由するシンプルな迂回ができるか
    • 地域を沈めた後いずれかの始点・終点ペアが分断されるか
  • 経路探索系情報
    • 大雑把に全ペアのmax集約・平均集約をしています。
    • 最短距離については、コストが安いものと、最優先経路、あとはBFS距離最短のもの全部というのを別チャンネルで用意
    • 出発点、到着点それぞれに対し、対象マスから接続に必要な残りhop数
    • 墨が1～3回塗られている部分については移動コスト増加扱いにしています。具体的な増分はハイパーパラメータ探索で決定。
    • 線路敷設段階では墨ヘッド出力情報を用いていますが、このとき1回塗った扱いと、沈めるまで塗った扱い両方経路計算して別々に入力平面へ与えています。
  • 得点は、現在得点や差と、1ターンあたりの稼ぎや差をそれぞれ持ちます。
• 報酬
  • 勝敗で+-0.5, そこからtanh(スコア差/800)/2で+-1へ漸近させます。
  • 補助報酬として、得点獲得に寄与した線路敷設行動に小さな報酬を与えます。学習進むにつれて減衰させます。
• 前処理・後処理・学習データの補正
  • 分断されたエリアあるいは袋小路地域への敷設・墨など、意味のない行動はマスクして選ばれないようにします。これは学習データに対しても処理しています。袋小路はLowLink使って判定。
  • 線路敷設は極力3アクションポイント使い切る (意味のないエリアしかなくなったらそこも許容)
  • 出力の線路敷設については、実行時間余裕があったら最初の線路敷設候補上位3個まで、それぞれ2本目以降のプレイを探索して、全アクションポイント消費した時点のコスト補正ありのlogit和が最大のものを選ぶようにしています。
  • U-Netのmax poolingで偶奇性の差があったので、マップサイズが小さい場合は四隅にずらして配置する水増しを行いました。
  • 最序盤の線路敷設行動は、PPOを進めると中央狙撃されるのを嫌がってか中央を避けるようなプレイをしてしまって悪化していたので、minimaxに近づけることにしました。
    • 対戦相手は、こちら側の線路だけ明らかになった状態で推論させる。つまり後出しじゃんけん状態。こうすると学習モデル側がどこに線路をプレイしようと適切な位置に墨で攻撃してくるので、中央をプレイするようになりました。

リーグ別やったこと

• リーグとは

  • Legend以外のそれぞれにはボスがいて、規定回数プレイ後にボスのスコアを上回る瞬間が発生すると次のリーグへ進めます。
  • 

• Wood(9/7)

  • Woodリーグはチュートリアルなので、ゲーム勝敗ではなく、問題文に書いてあることをやる必要があります。
  • Wood2
    • 線路を駅1ペアつなぐだけでOK。
  • Wood1
    • 敵の線路を墨で沈めればOK。

• Bronze(9/7)

  • ここから本来のルールで固定されます。
  • 上位勢が初日からかなり強い。
  • ひとまずint8量子化・Dilated Convolution・駅ペア出力ヘッドありでPPOの枠組みを組んだら通過。
  • 無駄な行動のマスクあたりは早めに実装。

• Silver(9/11)

  • 上位勢の成長が著しい。
  • 経路探索系の特徴量を詰める。
  • 量子化ビット数を層別可変に。
  • Silver Bossがいつもより順位高い提出を採用したらしく、Goldへ到達する敷居が高め。

• Gold(9/14)

  • U-NetやTransformerを比較実験しU-Netを採用。
  • 墨1～3段階をコスト増加扱いにするときの最適コストをハイパーパラメータ探索。
  • Legendリーグオープン時点でGold Bossとのスコア差9ぐらい (ボスが33台、自分が24前後)。スコア差2.5～3ぐらいでおおよそ勝率67%なので、差9は全くといっていいほど勝てないレベル。
  • 差を埋めるためにまずモデルサイズ制約を取っ払うとどうなるか調べた。大モデルだとちゃんと提出モデルより強くなることが確認できた。さらに提出モデル直接学習よりも蒸留のほうが有意に強くなったので大モデルを蒸留するプランに変更。
  • 経路探索情報を全体集約にすることで駅ペア出力ヘッドを捨てるシンプル化を試したらだいぶ改善。
  • 墨による分断が下手で沈めるのそこじゃない隣だよというパターンが多かったので、分断できるかや周辺だけで迂回できるかの情報を追加
  • QATを実装
  • 上振れで昇格するまで提出を繰り返す
  • ここから最後の一押しを他の人がしてくれる
  • 

• Legend(9/18オープン, 9/20 23:52に到達)

  • すでにあと17時間しかない、かつジャッジサーバが渋滞していて対戦が進まないのでやれることがあまりない
  • 線路敷設のターン内探索を実装
  • ひたすらコード長減らしてモデルサイズに回す

まとめと感想

• Legend昇格が最終日までもつれ込んだのは今まで参加した13回のうち今回と初参加の時とあと1～2回ぐらいしかないので久々の体験でした。コンテスト終了までにGold Bossを超えられるかというプレッシャーとの戦いはCodinGameの醍醐味ですね。
• 今回採用されたゲームのゲーム性もあると思いますが、2週間で100,000文字のソースコードにニューラルネットワークを詰め込んで学習・改善をやりきれないとLegend到達すら危うい時代が到来しており、今までの順位をキープすることすら厳しいです。上位になるハードルがかなり上がったなと感じています。
• PC・GPU2台フル稼働だったので、夏といいつつ9月開催だったのは室内温度的に助かりました。

備考

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