6/11～6/25に行われた『CodinGame SUMMER CHALLENGE 2024 BY FIVERR』に参加しました。
最終順位はGoldリーグの67位（全体の129位）でした。
本記事では、解法の細かな説明というよりは、参加したことがない人に参加ハードルやレベル感が伝わるような内容を紹介します。
コドゲ（CodinGame）とは？
ゲームAIの学習教材や対戦コンテストを提供しているプラットフォームです。
お題となるゲームのルール、ジャッジ環境、入出力形式が提供されており、ユーザーはそのゲームをプレイするAIプログラムを作成するだけで「自分が作成したAIの良さ」を他のユーザーと競うことができます。
「自分が作成したAIの良さ」というのは、1人用ゲームであればそのゲームのスコアであり、対戦形式の場合は実際に他のユーザーが作成したAIと対戦した際の戦績です。
「ゲームAI」と言われて深層強化学習をバリバリ使用した高度なものを想像するとハードルが高く感じるかもしれませんが、if文とfor文が書ければシンプルなルールベースAIを作ることはできます。
ゲームのジャンルや制約も多種多様で、様々なゲームAI手法の勉強と実践に役立つプラットフォームです。記事の最後に紹介します。
常設ゲームの他に年2回程度、本記事のように2週間掛けて競う大きなコンテストが開催されます（コンテスト終了後、常設になります）
コンテスト概要
『olymbits』という名前のオリジナル3人対戦ゲームです。
4つのターン制コマンド制ゲーム（競技）を同時にプレイすることを繰り返し、100ターン後のスコアで最終的に3プレイヤーの順位が決まります。各競技は10-15ターン程度で終わり金メダルから銅メダルが手に入り、各競技で獲得したメダルに基づいてスコアが決まります。
各競技は比較的易しいのですが、「あるコマンド（例えばLEFT）を入力したら、4つのゲーム全てでそのターンの行動がLEFTになる」というのがこのゲームのポイントです。その行動はある競技ではそのターン最善の行動だとしても、他のゲームでは最悪かもしれず、「数ターン先を見据えて、このターンにこの行動をしたら盤面はどうなるのか」「今はどのゲームを優先してどのゲームは捨ててもいいのか」という点が重要になってきます。
より詳しい日本語のルール要約はツカモさんの記事がとても良いです。
今回のコンテストの参加人数は、登録者が18,147人、1回以上提出者が5,237人です。
6つのリーグに分かれて対戦し、最終的に最上位のLegendリーグには62人、その次のGoldリーグには980人（+62人）が到達しました。
自分はGoldリーグの67位なので、全体の129位です。
フランス企業が主催のため、5,237人中約2,000人がフランス国籍で、それ以外にも世界各国の参加者がいます。
日本人参加者も370人おり、特にLegendリーグは62人中11人が日本人でした。問題文やフォーラムでの議論は英語で行われていますが、日本語でも高度な解法を知ることができます。
Wood → Bronze（～2904位）
ここからは、各リーグごとに「どういうことができればいいか」という紹介をします。
ルールは上記ツカモさんの記事でご確認ください。
UP：1つ先のスペースを飛び越えます。合計2スペース分前進します。
LEFT：1スペース分前進します。
DOWN：2スペース分前進します。
RIGHT：3スペース分前進します。
Woodリーグは特殊ルールで、ハードル走しかありません。
WoodからBronzeに上がるには、1つのハードル走で最適な行動ができればよいです。
ハードル走の最善手は以下になります。
- 1スペース前がハードルならUP
- 2スペース前がハードルならLEFT
- 3スペース前がハードルならDOWN
- 3スペース前までにハードルがなければRIGHT
これは標準入出力とif文とfor文を書ければ実装できますね。
ところで「DOWNはUPでもいい」「4スペース前がハードルの場合、LEFT→RIGHT、DOWN→DOWN、RIGHT→LEFTのどれでもいい」「ゴール直前はRIGHTでなくてもいい」などの気づきはのちのち重要になってきます。
Bronze → Silver（～2373位）
Bronzeから競技が4種類に増えます。
各競技の最善手を指せるプログラムを作成する一方で、どの競技のメダルを目指すとスコア効率がいいか考える必要があります。
スコア効率
スコアは「各競技のメダル数（金×3+銀）の積」なので、ここでは例えば単純に「今メダル数が1番少ない競技の最善手を優先する」でいいでしょう。
ハードル走
Woodと同じです。
飛び込み
明らかに文字リストに完全一致させるのが最善です。
スピードスケート
0番目:1スペース前進し、リスクは1減少します。
1番目:2スペース前進し、リスクは変化しません。
2番目:2スペース前進し、リスクは1増加します。
3番目:3スペース前進し、リスクは2増加します。
まず1人プレイの場合、最初の2ターンと最後の1ターンだけ3番目を選び、それ以外は2番目を選ぶと最善です。
多人数プレイの場合の最善手がよく分からないのは他のプレイヤーも同じで、何してもメダルが多少取れるので無視してもいいです。
一応作るとしたら、
- ラストターンは3番目を選ぶ
- スタンした相手がいるスペースには入らない
- それ以外は1番目を選ぶ
とかでしょうか。
アーチェリー
各プレイヤーはx座標とy座標を持つカーソルを操作します。毎ターン、 各プレイヤーは上下左右の方向を選び、その方向の現在の風の強さの数値分だけカーソルが移動します。
指定ターン経過後、プレイヤーは同時に矢を放ちユークリッド距離で座標(0,0)に近い順に順位が決まります。
入力情報：
今後の風の強さを示します。0番目が現在の風の強さです。
例「9914113315261」
まず簡単なヒューリスティックとして、「このターンでできるだけ(0, 0)に近づく行動をする」という戦法が考えられます。Silver到達はこれで十分です。
が、のちのためにより強い戦法（厳密解法）も紹介しておきます。
例えば今の座標が(2, 0)で、残りの風の強さが「13」とします。この時、上記ヒューリスティックでは「まずは左に動かし、(1, 0)とする。次に左に動かし、(-2, 0)とする」になります。しかし最善手は「まず右に動かしてから左に動かす」ですね。
このように次のターン以降の情報も含めて最善手を求めることができたら嬉しいです。
アーチェリーは最大15ターンあるので、あり得る行動は4^15通り（約10^9通り）あり、全探索は間に合いません（各ターンの行動は50ms以内に出力する必要があります）。ところで問題文をよく読むと
The x and y coordinates are capped in within [-20;20].
と書いてあります。つまりカーソルのあり得る状態は41*41通りしかありません。これに15ターン掛けても約25000通りしか状態がなく、遷移は4通りであり、これらを状態および遷移とするDP（動的計画法）が十分高速です。
（この議論がピンと来ない、あるいは実装できない場合はAtCoderやアルゴ式がオススメです）
実装はメモ化再帰で「ターンt、座標が(x, y)から最後まで進めた場合のユークリッド距離の最小値」を求めるのが簡単です。
また、上下左右対称なので、状態を21*21に減らして高速化できます。
更に、「ある状態から上に進めて(0, 0)に到達することが分かった（もっと言えば、他プレイヤーに勝つことが分かった）」場合、右左下に進めた場合を試すまでもないので、枝刈り可能です。この枝刈りは更に工夫可能です。素朴なDFSでは「上上上…上」から試すと思いますが、これが最善手になる状況は少なく、それよりも上述のヒューリスティックのような手から探索した方が(0, 0)に早く到達する可能性する可能性が高く、探索の早い段階で枝刈りを発生させることができます（move ordering）。ただしこれを実装することによるオーバーヘッドがたかだか最大深さ15遷移4パターンに見合っているかというと微妙で、この競技では「1手目から明らかな悪手」というケースは少ないので、探索順に手を加えずに枝刈りを入れるだけでも効果的だと思います。多分。
「（スケート以外）各競技に特化した場合、ちゃんとその競技では全て金メダルになる」というのをブラウザ上で適宜実行して確かめると実装バグに気づけます。
Silver → Gold到達（～1042位）
競技ごとに各行動に評価値を付ける
毎ターン競技ごとに「ある行動を取った場合の評価値」を計算し、競技ごとの評価値に重み付けをして足し合わせ、1番評価値の高い行動を選択するようにします。
ある行動$a$の評価値 = $\sum$ (競技に対する重み付け × 競技ごとの行動$a$の評価値)
重み付けは、この時点では全て1でもいいです。メダル獲得数が競技ごとに偏ってしまう気がしますが、実際は割といい感じになります。「Gold到達 → Gold上位」の章に書きます。
競技ごとに各行動の評価値をどう設計するかは重要ですが、最初から難しいことをやるのは大変で、とりあえずは「最善手なら4、次善手なら3」とかでも有用です。
（これと「ルールを正確に理解する」を合わせるとGold到達しそうです）
自分は「ある行動をしたあと、全員が最善手を続けた場合のメダルが何色になるか」で評価しました。
- 単独1位確定になる行動
- 全員最善手を続ければ単独1位になる行動
- 全員最善手を続ければ1位になる行動
- 全員最善手を続ければ2位になる行動
- 全員最善手を続ければ3位になる行動
のようにです。評価値は始めは④を5として、③はその3倍の15、②は18、①は20、⑤は2位との差に応じて0-4みたいな感じでした。
ルールを正確に理解する
ジャッジコードを読んだり、ビジュアライザを眺めて改善点を探してみます。
ジャッジコードにはルール文に書かれていない仕様や定数が記載されているため、一読すると得をします。コドゲはコンテスト中に解法言及してもよく、このあたりの情報はTwitterや公式discordでも拾うことができます。
例えば以下のような「どんな行動を選んでも変わらない」場面を正しく把握していると他の競技で有効な行動を優先することができ、かなり順位が上がります。
- スタン中の行動はなんでもいい
- ゲームオーバー中の行動はなんでもいい
- 100ターンまでに終わらない競技の行動はなんでもいい
- 既に何をしても単独1位確定ならなんでもいい
「100ターン経過時にもプレイ中の競技がある」というのは気づいてみると当たり前ですが、盲点で自分はSilverの途中まで気づきませんでした。スタン復帰タイミングのOff-by-oneなども実験コードを書いてビジュアライザで読むなりジャッジコードを読み込むなりしないとよく分からず、差を付けることができます。
Gold到達 → Gold上位（～129位）
先読みして行動の評価値を計算
例えばハードル走で4スペース前にハードルがある場合、「LRU, RLU, DDU, DUU, UDU, UUU」はいずれも最善手です。
このように数手先読みした上で各競技の行動列の評価値を計算し、最も評価値が高い手を列挙し、その1手目で多数決を取り行動を決定しました。
6-8手くらいは無理なく全探索できるはずです。
なお、8手読めたとしても「3手先で次のアーチェリーが始まる」ような場合は2手しか読まないようにしました。discordでは「盤面をランダム生成して8手先まで読む」というアイディアも出ていましたが、微妙な気がします。
スケートが終わるタイミングはどうでもいいので無視しても良さそうです。
重み付け調整
ある行動$a$の評価値 = $\sum$ (競技に対する重み付け × 競技ごとの行動$a$の評価値)
- 獲得メダルが少ない競技は重要
- 1 + (4競技の最大スコア - 競技スコア) / 3 * 0.05
- 競技スコア := 金メダル数 * 3 + 銀メダル数
- 3は切り捨て除算
- 競技の終盤は序盤より重要
- 2 - 0.2 * min(3, 競技の残りターン)
の2つの積を競技の重みとしました。
競技ごとの重み付けがバラバラになると多数決が機能しづらくなるので、あまり競技間の重み付けが多様にならないようにしています。
数字は単に何度か提出して一番良かったものを採用しています。
評価値のパラメータ調整
- 単独1位確定になる行動
- 全員最善手を続ければ単独1位になる行動
- 全員最善手を続ければ1位になる行動
- 全員最善手を続ければ2位になる行動
- 全員最善手を続ければ3位になる行動
のようにです。評価値は始めは④を5として、③はその3倍の15、②は18、①は20、⑤は2位との差に応じて0-4みたいな感じでした。
④から1位プレイヤーが最善手を取らずに逆転して金メダルを取れることがそこそこあるので、③は④の3倍にはならなそうだなと思っていました。
一方で①②③の比率に根拠はなく、10回くらい提出して1番良かった①32、②24、③16、④7を採用しました。
1度提出すると結果が出るまで30分くらい掛かりますが、定数値を変えるだけなので、仕事の休憩中にスマートフォンから提出できます。
より本格的にパラメータチューニングするのであればローカルでジャッジを動かせるようにするといいかもしれません。
Gold上位 → Legend到達（～62位）
Legendに到達するにはこういう改善に取り組む必要があったかなという反省点です。
MCTS・DUCTの採用
自分が使用した評価値は、「その後各競技で相手プレイヤーが最善手を続けると仮定した場合の場合の順位」を使っています。しかし、実際には競技ごとに最善手が異なる以上、全競技で最善手が続くわけがなく、その点で評価の精度が下がっています。
「実際に相手が取り得る行動」に対して自分の順位やスコアを評価するのが良さそうです。この改良を行う際に、モンテカルロ木探索や、その同時着手ゲーム版のDUCTが使えます。
実際、LegendではDUCTを使用している人が多いです。
これまでDUCTを書いたことはありませんが、TERRYのブログや『ゲームで学ぶ探索アルゴリズム実践入門』は読んでいたので存在は知っていて、初日の時点で「最終的には使うのが強そうかな～」とはぼんやり思っていました。
しかしある程度良いルールベースが出来ていない段階で使ってもいい順位が出ないのは目に見えていたので、Goldでそこそこの順位を取るまでは手を付けなくて正解かなと思います。
休日を残した状態でGold上位であれば写経してみるのは手でしたが、MCTSも導入できていない状態から平日の夜にやり切れる腕力はなく、今回は見送りました。次回は導入できるよう、もう少し単純な同時着手ゲーム（『ゲームで学ぶ～』のサンプルゲームなど）で実装するところから素振りしておきます。
スケートボードの評価値改善
スケートボードを上手くプレイするのはLegend解法を見ても難しそうだなぁという感想です。
「自分の4択について、相手の今ターンと3人の次ターン以降を完全ランダムで競技終了までモンテカルロ法して、1番期待値いい手を選ぶ」とかがリーズナブルかつ強力だったかもしれません。
仮に相手の手を高い精度で予測できる場合、スタンを予知でき、有利に進めることができます。
一見してゲーム理論の知見が役立ちそうで、「3人ゲームのナッシュ均衡になるような混合戦略を求めて、基本的にそれを使う」「他のゲーム状況やこれまでのプレイ傾向から相手の着手を予想してエクスプロイトする」ことができれば、それが強いだろうなとは思いました。
これ自体は国内外の上位の人たちも最終構想として持っていたようですが、「まぁこの期間で実装しきるのは大変だよね」という感じで、それで成功したという報告は見当たりませんでした。
評価値・重み付けの改善
Legend帯の解法ツイートを読むと、上手く最終的な順位予想により近い評価関数を使用していたり、直感的な良さを数式に反映していたりして勉強になりますね。
たとえば、「残りターン数と獲得メダル数が同じでも、残りのゲーム回数の期待値は競技ごとに異なるので、スコア期待値も異なる」というのは盲点でした。
リンク集：日本人Legendの解法
適宜更新します。
3位：Nanaedaさん
15位：bowwowforeachさん
17位：montplusaさん
19位：ichyoさん
30位：viewlagoonさん
34位：y_kawanoさん
37位：KawattaTaidoさん
42位：itigoさん
48位：ValGrowthさん
52位：tachanさん
58位：besukohuさん
リンク集：参加記
リンク集：常設
それぞれ対戦形式、1人プレイ形式の常設ゲームの紹介記事です。2020-2021年の記事なので直近の問題はありませんが、概要や難度が整理されていて、学習教材の参考になりそうです。
コドゲ上でAlphaZeroを使う際に参考になりそうな記事。
コンテスト形式でゲームAIを実践する場合、Kaggleのシミュレーションコンペも良さそうです。制約の差で有効な手法の傾向に差があるかもしれません。