ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

CodinGame Spring Challenge 2020 参加記

CodinGame Spring Challenge 2020に参加して、Legendリーグ57位でした!

f:id:betrue12:20200519105641p:plain f:id:betrue12:20200518193410p:plain

対戦動画をTwitterで見て、何となく面白そうだなと思って参加したらドハマリしました。睡眠時間と休日とCodeforcesのコンテスト2回分が犠牲になりましたが、Legendリーグに進出することができて嬉しいです。

戦略

完全にルールベースです。分かっている情報からマスの得点評価をして、経路のスコアを計算しながらDFSをして、いくつかの行動パターンに従って行動します。

試合を見ながら思いついた行動パターンやスコアの補正をどんどん入れていったので、勘で決めたパラメータがあちこちに散らばってカオスになりました…。

項目ごとに列挙していきます。

進行度判断

  • 総得点の1/2が取られるまでを序盤、3/4が取られるまでを中盤、それ以降を終盤と定義し行動を少し変える。

じゃんけん

  • 距離が近くて手が負けていたら逃げる。ただしスキルが使える時は相手に勝てる手にSWITCH。
  • 逃げている途中の曲がり角で相手が見えなくなった瞬間に引き返して食われることが多いので、逃走中は引き返し禁止。
  • 手が勝っているときに追いかけるのは、絶対に相手の後を通ってペレットを得られないので微妙かなと思っていた。ただ自分がやられるとルートを崩されて嫌なので、相手も同じかなと思い追加。

スキル

  • 前記の迎撃SWITCH以外はSPEED連打。即逃げが必要な場面を除いて、使える時に使う。

マスの評価

  • どのマスが通行済(もうエサがない)かを記録。自キャラが通過したマス、視界内のマスで既にエサが消えているマス、相手の初期マスなど。
  • SPEEDを使うと交差点を通り過ぎた時に情報が得られずエサを見落とすことが多かったので、SPEED中でも次のマスから得られる情報が多いときは1マスしか進まないようにした。
  • 最初は情報がないマスに均等に期待値(残り得点数÷不確定マス数)を当てていたが、探索の効率を根本的に改善する必要があったので重み付けだけでも追加。敵を見た位置の周辺や、その敵を前に見た位置からの最短経路上の重みを減らすようにした。
  • 見えているペレットの状態と経路の形から、その周囲のペレットの存在/非存在がほぼ確定する場面がある。例えば、壁と見えているペレットに囲まれた不確定マスの領域があって、その中に自分と敵の初期位置が存在しない場合、その中のペレットは確実に存在。

f:id:betrue12:20200519103925p:plain

↑例えばこういうケースで入り口のペレットが見えていると、奥のペレットは全部残っていることが確定する。

f:id:betrue12:20200519110942p:plain

↑こういうマップ形状で奥の通路側のペレットだけ消えているのが見えた場合、その通路のペレットは高確率で取られている。

経路探索

  • 大ペレットに向かうルート。大ペレットからBFSして一番近い自キャラに割り当てる。
  • DFSルート。基本的にこれで、ルートのスコアを計算しながらDFS。
  • 未訪問の塊を掘りに行くルート。終盤に残っている塊を探すため、不確定マスだけで取った連結成分を求め、その中のペレット期待値合計が大きいところに行く。

経路スコア

色々補正項を入れていてカオス…

  • 基本的な計算式は、マスのペレット期待値に距離で減衰する係数を掛けて合計。
  • 味方を分散させるために、他の味方に近いマスは減点。
  • 序盤に袋小路に行くと減点、逃走中に袋小路に行くと大幅減点。
  • 勝てる敵がいるマスを通ると加点。
  • 引き返しは無駄が多いので減点。
  • 既に袋小路の中にいるときは奥まで取り切ると加点。これやらないと奥に1個残したりしてもったいなかった。

衝突回避

  • 味方同士が衝突すると悲しい。敵との衝突は等しく損をしているし、避けるとおいしいルートを譲ることになるので放置。
  • 各マスに「所有権」を設定し、各キャラの経路のうち最初の数ターン分で通るマスを所有扱いにして、他の味方が使わないようにした。
  • 敵と何回も衝突しているときはSPEEDを使わないようにした。相手と同じ周期でスキルを使っているとタイミングが被るので、相手がSPEEDを撃っている間に潜り込むことができる。

コード

gistに載せようと思ったのですが公開禁止だそうで…最終的に800行くらいになりました。

色々試行錯誤してたときにWinMergeで差分追うことになって辛かったので、最初からgit使えば良かった…

雑感

やり慣れている人とは全然違うやり方をしているんだろうなという気がしています。BFS/DFS/UnionFindと大量のif文と手動調整パラメータで押し切りました。

じゃんけんの攻防も大事ではありますが、とにかく探索の効率で負けているとGoldで感じたので、そこをなんとかしようと頑張りました。見えている相手の位置をもとにマスに重みを付ける、見えているマスの情報から周りの状況を論理的に推論する、うろうろしたり引き返すなど非効率な行動を抑制する、こういった地道な改善によってLegendまで行けたと思います。

見えていない間の相手の行動を読んだり、先のターンの展開を予測したり、そういったところまでやるとゲームAIっぽいなあと思うんですけど、スキルも時間も足りなかった…上位勢がどういうアプローチをしているのか気になります。

ビジュアライザを眺めるだけでも面白く、実際の試合をすぐにIDE環境に持ってきて試行錯誤できるので改善しやすかったです。負けた試合と同環境でなるべく勝てるように改善する、というのが基本スタイルでした。一方で運に左右されがちなゲームなのにデータを大量に取るということがやりづらく、何が正解なのか分からなくなってしまうのは辛かったです。

めっちゃ楽しかった。次も参加したいです。

感想戦を経て追記

上位の人の方針ツイートを見たり反省会の配信にお邪魔したりしていたのですが、山登り/焼きなまし系やビームサーチ系に落とし込んで探索時間を上手に活用している印象でした。

私の方針だとほぼ時間を使わないのでTLEとは無縁だったのですが、とにかく「想定していない状況」に弱くて、特に大ペレットとキャラの初期位置がちょっと変な形だったときに最適とは言い難い行動を取ることが多かったです。またキャラごとに順番に経路を決めていたので、他の味方の良い経路を潰してしまうこともありました。

経路のスコア化はできていたので、もう少し頑張って行動や盤面のスコア化まで作っていれば、あとは探索アルゴリズムに任せれば特殊な状況でも総合的に判断してくれそうです。正直「不完全情報だしターン毎の制限時間50msだし焼きなませないだろう」と考えていたんですが、そこを何とかするのが上位勢の実力だなと思いました。