CodinGameで2020/05/07~2020/05/18の11日間にわたって行われたオンラインコンテスト「Spring Challenge 2020」に参加しました！
世界109位/4958人、日本位17位/227人（Legend league）でした。 今回は参加者がいつもの2.5倍くらいいてすごかったですね。全体に対する比率としてはいつもとそう変わらない順位が取れたと思います。最終日までLegend Leagueに上がれなかったので駄目かと思ったのですが、今回も上がれてよかったです。
$15\times 35$くらいのグリッド上に壁と通路があり、はじめ通路にはpelletが敷き詰められています。各プレイヤーはそれぞれ2〜5体のpacを持っていて、このpacを動かしてより多くのpelletを食べることを目指します。pacにはROCK, PAPER, SCISSORSの3つの状態があり、相手のpacとぶつかった場合にはじゃんけん関係において有利なpacが生き残ります。また、フィールドには4つだけsuper pelletと呼ばれる大きなpelletがあり、これは通常のpellet10個ぶんの価値があります。重要なルールとして、フィールド上のpelletと敵pacの場所は自分のpacから四方に行き止まりまで進んだ範囲しか見えなくなっています。さらに、10ターンに1回アビリティを使用することができ、5ターンの間移動距離が二倍になるSPEEDと、自分の手を変えることができるSWICHの2つがあります(試合の例)
基本的には、各pacからの10手〜13手くらいの経路をBFSで探索して一番良い経路を選んで進んでいましたが、これだけでは少し弱いので、いくつかの工夫をしました。以下に紹介します。
今回BFSをするにあたって、あるpacが各マスを踏むことに対するスコアを評価し、合計スコアが一番高い経路を選んでいました。
このゲームの目的はより多くのpelletを集めることなので、マスのスコアを決める一番大きな要因はpelletの有無になります。しかし、自分のpacの四方しか視界がないので、pelletがあると思って取りに行ったらもうなかったということが往々にして発生します。
一般に、前のターンにpelletがあった場所には高確率でまだpelletがあるでしょうが、20ターン前に見たきりの場所にまだpelletがあるかどうかは怪しいものです。せっかく取りに行くならpelletがある確率の高い場所に行きたいのですが、「pelletがあることを確認した」場所よりも「pelletがないことを確認していない」場所のほうが多くのpelletがあるように見えがちなので、これらのマスを同じように扱ってしまうと、実際にはpelletがある可能性の低い場所に行きやすくなってしまうと考えられます。そこで、pelletに対する信頼性という値を定義しました。
1ターン目には、pacがいるマスを除いて全てのマスにpelletがあることがわかっているので、全てのpelletの信頼度は1です。ここで、ターンが進むごとにすべてのpelletの信頼度に対して適当な値(たとえば、0.98など)を掛けることで信頼度の減衰を表現しました。信頼度は、そのマスを視界に収めることで1.0に戻ります。探索の際、pelletの価値には常に信頼度の値を掛けて評価していました。
各マスには、トレースという値を設定しました。これは信頼度と似た考え方で、はじめはすべての座標について0ですが、座標$(x, y)$を踏むと$trace[x][y]=1.0$になり、毎ターン減衰します。イメージ的には、ナメクジの痕のようなものです。
各座標のスコアを決めるとき、このトレースの値に比例したペナルティを与えました。こうすることで、最近味方によって踏まれたマスに行くことを避け、複数のpacが密集することを防ぐ効果があると考えました。また、終盤BFSの範囲にpelletがひとつもなくなってしまったときに目標を失ったpacが右往左往せずにより広い範囲を探索できるようにする効果もあります(多分)。
Unleash the Geekでもそうでしたが、複数のUnitを操作するマルチエージェントのゲームでは、自分のUnitを失って数の有利を取られることは直接的に負けにつながります。ここで、自分にとって不利な手のpacと出会わないように動きたいのですが、相手のpacと曲がり角で鉢合わせる場合もあり、確実に防ぐのは無理です。ここで、敵の動きを確率的に予測しようといろいろしていました。最終的には、敵がそれぞれのマスにいる確率を、pelletの価値$\times$信頼性を引数にしたsoftmax関数で予想して、一定以上の確率で自分にとって有利な敵が来そうな場所は踏まないという感じでやっていました。そんなに信頼できるものでもありませんが、やらないよりはマシだったかなという印象です。
危険マスの判定では敵の場所を確率的に予想していましたが、それとは別に、敵が過去に通った経路がわかる場合があります。敵が見えたとき、その敵を以前に見た場所と経過ターン数、SPEEDの状態などから、その間に移動することができた最大距離がわかります。これを用いれば、その敵が通ってきた経路が一意に定まる場合があり、その経路上のpelletはすでにないことがわかります。分岐があって経路全体が一意に定まらない場合でも、以前の位置から分岐までの経路と、分岐から現在の位置までの経路はわかったりするので、そこだけを消すことも意味があったと思います。
DFSでpacの通る経路を決めるにあたって、それぞれ独立に探索すると同じpelletを複数のpacが狙いに行ってしまうことがあります。super pelletがある場合などに特に顕著ですが、こういった重複を許してしまうと収集効率が大幅に落ちたりpac同士の衝突が発生したりととにかく最悪になってしまいます。
このような事態を防ぐため、pacに優先度を設定して、より優先度の高いpacが取る予定のpelletのスコアは計上しないこととしました。こうすると問題になってくるのは、優先度をどのように割り振るかということです。単純にid順としてしまっては、super pelletに一番近いpacが取りに行けなかったり、他のpacに有効なルートを潰されてしまったりといったことが起こります。
最後の二日間までこの問題を放置していたのですが、流石に直したほうがいいと思ったので、優先度の割り振りを数通り試すことにしました。pacの数が3であれば優先度の振り分けかたは高々6通りしかないので全部試すことができますが、$4!=24$通り以上になってくるとかなり厳しいので、大体10通り程度になるように適当に間引いて試しました。試した中で一番いいスコアが出たものを最終的な行動としました。
コメントや最終的に使わなかった処理を含めて1224行でした。Codingameで1000行を超えたのは初めてかもしれません。
今回もLegend Leagueに到達できたのはよかったのですが、あまり大したことはできなかったなぁという感じがしました。社会人になってもLegendにいけることがわかったのはよかったです。
コンテスト終了後の感想戦などをみて、よさそうだと思った戦略のメモ