はじめに
CodinGameのコンテスト（CodinGame Spring Challenge 2020）に参加しました
結果は世界61位（LEGEND）、日本12位と健闘出来たかなと思います
Legendリーグは114人いて日本人が18人なのでLegendのうち6人に1人くらいが日本人だったみたいですね
みんな強い
ルール
詳しいルールはツカモさんが記事にしているのでそちらを参照するのが良いと思います
簡単に言うと、パックマンで相手よりたくさんポイント（ペレット）を集めたほうが勝ちで、パックマンのタイプによってじゃんけん要素が加わった感じです
tsukammo.hatenablog.com
やったこと
リーグ別に段階を踏んで改善していったものも書きますが、ここでは最終的にどんなことをやったのかだけ簡単にまとめておきます
基本的には貪欲とルールベースで評価関数によって行動を決定していました
1. 各ターンごとに自機の居る位置をまとめてpriority_queueに入れて、評価関数に応じたスコアの高い順に20MOVEまでの最短経路を評価の高い順に探索する
2. ペレットの評価はスーパーペレットが100、視認したペレットが10、あるかどうかわからない未探索のペレットは5で決め打ち
3. 近くにあるペレットの価値が高く、遠くにあるものほど価値は小さくなるので、距離の二乗分の重みを考慮
4. 衝突時は相手にリソースを打たせるルールベース
5. 相手が袋小路にいる（移動できるマスが3マス以内）でabilityが使えない状態ならkillするようにスコアを加算
他にも細かい点はありますが、だいたいこんな感じでやっていました
Wood2
最初見たときはtron battleっぽいなって思ったのでbfsで色塗りゲームをする感じで多く移動できる4方向を選択するものを組んで昇格
Wood1
いきなり複数体操作が可能になりました、しんどい
複数体が色塗りで自分の領域を作ると考えると、 floodfillが使えそう
なのでfloodfillで自分の動ける領域を作り、その中で貪欲にpelletのある方向に動くようにした
また、スーパーペレットは取らないとかなり損なので残っている間は貪欲に取りに行く
これをやると昇格
Bronze
Bronzeになるとabilityが解禁されて、情報が不完全になる
取り敢えず、見えているペレットだけを考えることにする
スキルはSPEEDが強そうなのでSPEED使えるときは使うようにする
すでに取られているのに、あると思い込んでペレットを取りに行くような動きがあったので、視界にあるのに、ペレットの情報が与えられていなかったらすでに取られたものとして補正する
ここまでのものを提出すると初日は日本5位、世界97位になった
こどげ初日
— ボンド@競プロ (@bond_cmprog) 2020年5月8日
日本5位、世界100以内でスタートダッシュ出来たかな
息切れしないで頑張りてえ〜 pic.twitter.com/reE3vjqH36
この時点での負けパターンとして、相手をまったく考慮していなかったので不利な相手が見えている状態でも突っ込んでしまう場合が結構見られた
純粋に稼ぎ負けるパターンもあった
この時点では、スーパーペレットがあれば貪欲に取りに行って、それ以外は4近傍でペレットがある方向に貪欲に取りに行っていたのでたくさん残っている部分を取り損ねるみたいな動きが目立ちました
見えている部分は情報として取り込んだほうが自明に強いのでその部分を実装
敵が見えているときは、敵の移動可能マスを計算し、基本的には近づかないようにする
場合によっては追いかけたり、衝突したほうが良かったりするけど一先ず敵から逃げる方針で実装
評価関数も入れて4方向のどっちが良いかを探索したりもしたけどpacが反復横跳びしてしまったので一旦断念（反復横跳びみんな通る道だと思う）
ここまでのを提出するとBronzeで32.5とかでした
4方向だと取りこぼしたりしていたので未探索マスがあれば今の位置からそこに向かわせるように実装
silverが解禁され無事即昇格
Bronzeボス手元で数戦しただけなんだけど結構killしてきて殺意高くなかった？
Silver
初動で大体Silverの真ん中らへんでした
敵が見えているときの情報を使うことを取り敢えず考えました
味方に対してだけfloodfillしていたのを敵に対してもfloodfillするように実装
この時点での問題点としては、floodfillで移動できないときに未探索マスを選ぶようにしていたが、その経路上に敵がいても構わず突っ込んでしまうのでそれでやられることが多かった
敵のfloodfillも考慮してたんだけど、その影響か集める効率が悪そうな気がした
固まっているところを連続で取っていったほうが効率が良いので連結成分で考慮してみる
連結成分を実装してみたが、評価が悪かったのか微妙だった
この辺りのときに、各pacを行ける範囲でbfsし、その中でスコア最大の経路を選択するという方針を思いつく
1体ずつbfsでスコア最大の経路を選択しその経路は次のpacは通れないようにする、ということで味方同士の衝突も避けれそう
そうすると、基本的には衝突するときは敵との衝突になるのでその管理も楽そうになる、天才では？
ついでに、敵をfloodfillでしていたけど敵の移動可能マスには近づかないようにロールバック
経路選択を20MOVEまで見るようにしたけど近いところのものを取らないで遠くの方にばかり行くようになってしまったので、（MAX_MOVE - distance）の重みを追加し、近いところを優先するように
ボスが解禁され、無事Goldへ
Gold
Gold入って最初のほうはリプレイ見て考察メインでしてました （体調崩したのもある）
リプレイを眺めていると、後半の取りこぼしが結構目立つ
20MOVEで見ているので、近くのものよりも遠くにたくさんある（あると思いこんでいる）ほうに行ってしまう動きがあった
そのため先程の距離の重みを二乗にしてみた
これが結構効いたっぽい
他には
// 0 : なにもない, 1：ペレット 0S00 #1#0 #11G
みたいなS -> Gの経路があったときにS -> 1 -> 1 -> 1 -> Gが最適
bfsだとS -> 0 -> 0 -> 0 -> Gと通ってしまうような試合がいくつかあった
これを解決するために、bfsをやめてダイクストラを使うことにした
価値の高い順に20MOVEの最短経路を求めるようにした
これを実装すると全体95位で2桁順位復帰、やったね
閉路に居るときにその場待機しちゃうことがあったので移動1マスごとに1重みづけを加えた
また、前のターン通って来た道に引き返して別のところに向かうという動きも多かったので、戻る移動にマイナス補正をかけた
この時点では、各pacごとに独立にダイクストラしていたが、まとめてpriority_queueに突っ込むことにした
これが結構良くて、各マスは1回しか訪れないため、味方の衝突が減ってまたいい感じにバラけて移動するようになってくれた
Legendが解禁されてボスが出現
初動のLegendが20人くらいでめちゃくちゃボスつえーとなっていた
この辺でLegend厳しいか？となり結構しんどかった
引き返す移動にマイナス補正をかけていたけど、そのせいかその場で立ち止まっちゃうpacがいたので一旦削除
流石にじゃんけん要素そろそろ入れないとやばいかな、と思いじゃんけん要素を解禁（今までしていなかったんですか？）
自分の実装だと衝突時には敵との衝突がほとんどなので、前のターン衝突していてabilityが使えるときは有利な手にswitchするように変更
Gold帯だとこれがかなり効いたように感じて、Gold下位との対戦成績が段違いに安定した気がします
これでGold1桁になり、放置して見守っていると無事Legend昇格！嬉しい！
Legend
Legendに到達するので燃え尽きたのか、正直あまり改善できず、パラメータ調整とか、ちょっとしたやつを追加するだけでメイン部分は殆どいじれませんでした
前に連続してペレットを取りたいから連結成分で見ていたけど、その部分をcomboボーナスとしてスコアに加算
ちょっと良くなった気がする
Goldのときには衝突時決め打ちswitchで大体取れてたんだけどLegend帯だと後出しが増えてきたので、後出しに変更
Goldのときは気にならなかったけどLegendだと後半の取りこぼしがまた目立つようになった
自分の得点と相手の得点から今の盤面状況を推測し、残りのペレットが大体30%くらいになったら近くのペレットの重みを増やして取りこぼしを減らすように変更
上位勢のリプレイを見ていると相手を確定でkill出来る状況ならkillするような動きが強いと思ったのでそれを実装
具体的には相手の移動可能マスが3マス以内で、cooldownがそれより大きく、自分の手が有利ならkillするように重み付けをした
Legend帯だと中々そういう状況にならないのでめちゃくちゃ効いたかはわからないけど、killするようになってそれで勝てる試合もあったので良かったんだと思う
もうちょっと積極的にkillしに行っても良かったけど実装が間に合わず
大体こんな感じでシステス前の暫定順位が61位
最終順位も61位でフィニッシュ
10日間フルでやり続けたので疲れました、楽しかった
最終提出のコードは627行でした
もう少し色々実装すべきだったかな
やりたかったこと
1.貪欲ベースで20MOVE読みしていたので、相手のほうが近いスーパーペレットを追いかけたり、食べられたりする動きが多かったので、初手を工夫したかった
2.ビームサーチなどでもう少し経路探索を工夫したかった
3.未確認のペレットの価値を5で決め打っていたけど盤面状況によって期待値を決めたかった
4.敵の行動予測をやりたかった
5.味方pacが衝突していて、残りのペレットがそのpacが取りに行こうとしている時、他のpacが反復横跳びしちゃうので、探索のときの順番を変更したかった
知見
交差点で止まると多くの情報を見られるので交差点であえて止まる
交差点の間隔の偶奇が一定なので交差点でSPEEDを使うと必ず2マス移動で交差点に止まれる
順番の考慮が結構効くらしく、順番を焼き鈍したりするといい
敵の位置予測をすると結構パターンが絞れるらしく、有利な相手に衝突する確率の高いマスに移動出来たりするかも？
感想
10日間ほぼずっと考え続けて疲れたけどめちゃくちゃ楽しかった
前回のOcean of Codeは実装で頭がやられたのと†人生†中だったのもあってあまり取り組めずSilverだったので今回Legend取れて嬉しい
序盤に割と当たり方針を引けて結局最後までその方針で走り続けられたんだけど、逆にLegend上がってからはあまり他のことを試せなかったのでもう少し最初の方に色々試してみても良かったかも
次回も参加します！！（修論とかでやばそうだけど）
