G4NP0Nのブログ

競プロとそれ以外のことについてしゃべります。

CodinGame Spring Challenge 2022 参加記

はじめに

CodinGameSpring Challenge 2022 に参加しました!

www.codingame.com

結果は288/7695位(Legend) でした!コンテスト期間中のLegend到達は初なので、大満足です。

お前は誰

北大工学部を卒業し、社会人2年目に突入した競プロerです。

コドゲは2020春が初参加ですが、ゲームAIのイロハを一切知らずに毎回適当にSilverまで上がって満足してやめてた程度のエンジョイ勢でした。

4月に突如コドゲのモチベが沸き、LineRacingでゲーム木探索を勉強したのでいざ実践!という意気込みでコンテストに臨みました。

まあ今回のコンテストではゲーム木探索使えなかったんですが。

ルール

防衛ゲームに見せかけた超次元サッカーです。

ツカモさんの翻訳+α記事がわかりやすいです。リスポーン地点の話とかスペルの細かい仕様は自分だけじゃ把握できてなかったので助かりました。

tsukammo.hatenablog.com

やったこと

探索も盤面評価もしない、攻撃2守備1のルールベースです。本当は敵の動きも見たかったのですが、とても実装が間に合わなかったので一切見てません。敵の座標すら確認していないので、このターンに確実に死にそうなMonsterにスペル打つみたいな無駄なこともけっこうしてます。

序盤

マナが初めて120溜まるまでモンスターを狩ります。

攻撃役は敵陣に近いリスポーン地点前で、防御役は防衛拠点で待機します。

各ヒーローの現在地から3ターンで攻撃可能なモンスターがいる場合攻撃に向かいます。ただし、各ヒーローに割り当てられたマナ稼ぎ拠点から離れすぎると陣形がめちゃくちゃになるので、マナ稼ぎ拠点からの距離で行動範囲を絞りました。

攻撃

Windでモンスターを敵baseまで4700以内に飛ばし、次のターンで2HeroでWindしてゴールにねじ込みました。Twitter二重の極み戦法って呼ばれてたやつですね。

ボンドさんのリプレイから着想を得ました。

 

自分が最初したときにはこんな感じ。ゴールから4600の距離で待機しておくことで、ヒーローのWIND範囲にモンスターが入ったときにモンスターから見てモンスター→ヒーローのベクトルになるようWINDを打つことでモンスターがW WINDでゴールできる位置に移動するはず!みたいなことをGeoGebraでお絵描きして確認したりしました(リンクした動画では普通にパスミスもしてますが)

 

近くにシュートできるボールモンスターがいない場合はだいたい以下のように行動していました

  1. このまま進めばシュートできるようになるモンスターがいる場合、待機継続
  2. 1のようなモンスターがいないがControl範囲内にモンスターがいる場合,CONTROLでセットアップ
  3. モンスターが近くにいない状態なので、ヒーローの片割れがリスポーン地点にモンスターを探しに行く
    • モンスターがいれば上記1,2をして拠点に戻る

あとは残りHealthが少ないモンスターを対象外にしたりとかマナの残量次第でマナ稼ぎしたりとかも入れてみてます。

はじめはゴールとの角度45度の箇所で待機してたんですが、中央は敵の防衛も手厚いのでなかなかシュートのタイミングが訪れないんですよね。最終的には(0,0)ゴールの場合(4400,1280)くらいの位置で待機するようにしました。これでかなり順位改善しましたね。本当は(4600,0)で待機したかったんですが、壁に向けてWINDしたときのボールの軌道計算が面倒だったので、楽をするために少し境界と距離をおきました。

やってることはシンプルなんですが、予想しない挙動がたくさん起きていたので、主にここの制御を精緻化するのが今回のコンテスト期間の大部分を占めましたね。

防御

みんな言ってるけど、本当に難しかったです。攻撃側が取れる戦略が多彩すぎる。

結局、自base到達が一番早いモンスターを優先的に排除するというザ・平凡な方針に。

  1. このターンに自baseがダメージを受ける場合、WINDする
  2. 自baseとの距離が一定未満のモンスターがおり、マナに余裕がある場合WINDする
  3. 1,2でない場合,MOVEする
    • 全モンスターの動きをシミュレートし、一番早く自baseに到達するモンスターを特定
    • 1で求めたモンスターを攻撃できるようになるまでの時間を計算
    • 全モンスターを対象にbit全探索し(ただし、1で求めたモンスターを含めるもの),各モンスター集合に対して最小包含円を求める。求めた最小包含円の半径が800以下で,2で求めた時間以内に中心にたどり着けるもののうち最も多くの点を含むものを採用

防衛時に複数モンスター巻き込みは最初から考えていたものの方針が浮かばなかったのですが、Terryさんのツイートを見てbit全探索でいいじゃん!となり、最小包含円計算は適当にググって出てきた記事を参考にO(N^3)のものを実装しました。

Controlでお手玉されたりShield物量作戦にかなり弱く、攻撃役がゴールを決めてくれるまでの時間との勝負になりがちでした。

雑な日記

コンテストに関係ない要素が多々含まれるので興味ない人は飛ばしてください。

前日譚

かえでさん,ボンドさん,ツカモさんと遊んでコドゲのモチベを上げたり、

thunderさんの記事を読みながらLineRacingでLegendに到達してたりした。*1

qiita.com

次のコンテストでもLegend目指すぞ~という気持ちに。

4/21 ~23:00

コドゲ参加者とTwitterでコンテスト開始までワイワイと盛り上がるなどしていた。

4/21 23:00

問題公開。ツカモさんが翻訳記事を出してくれるのを待つのもアレなので、Deeplを駆使しつつ問題文を読む。

複数キャラ操作ゲーか……パックマンで途方に暮れていた苦い記憶が蘇る。しかも盤面がかなり大きい。DUCTは難しいのかな?とか考えながらとりあえず拠点に一番近いモンスターを狩りに行くコードを提出すると、なぜか毎回1ターン目に死ぬ。

何かと思いきや、実は入力にルールに記載されていない「ヒーローの数」とかいう固定値があるらしい。なんやねんそれ。

翌日も労働があるので、とりあえずWood2を抜けたことを確認して、就寝。

4/22

朝起きたらWood1抜けてBronzeいってるかなーと思っていたが、視界が制限されたことにより敵ヒーローの位置が取れていなかった関係でバグっていた。

直した&ちょっと適当にロジックを直して,Bronzeへ。

競プロをもともとやっていて新卒のプログラミング研修が暇そうな親友にLineRacingを布教してみたらハマってて草。

4/23

この週末はAtCoder関連のことしてた時間の方が長かったな。

 

なるほどーっつってた。確かにスプラトゥーンでもスマブラでも結局強みを押し付けるムーブが最強なんすよ。

 

新しいPCが届いたので環境構築した(っつってもVisualStudio入れるだけ)

 

kenkooooさんとカフェでお茶しながらお仕事についてやkenkooooさんご本人の経歴についていろいろと教えてもらう。めちゃめちゃ面白かった……。

 

夜はABC249に参加。ひさびさの4完で-40くらいしてしまった。Eが解けなかったのは筋力の衰えを感じる。

4/24

AHC10に参加。難しすぎませんか?DFSを早いうちに切り捨ててしまったのが大悪手だった。

Algo Artisの方達が爆死してたのが面白かった。

 

夜はARC139に参加。まさかの0完太陽をキめる。-84して逆入水。そんなことある?

まあ、どうせ青にはすぐ戻れるので気にしてないです。

4/25~4/28

労働に屈していました。頭の中で戦略を組み立てたりはしていたが、一切コーディングはできておらず。

複数キャラを用いた盤面,Action管理をどう実装するのが楽か?という部分について悩んだ。3体個別操作は自分の実力では難しそうなので、攻撃か防衛役どちらかを2人重ねて実質攻撃役と防衛役の2キャラ操作とみなせないか?と考えていた。

4/29

スプラトゥーンをしていました。

4/30

ようやくコーディング着手。

この時点で攻撃2防衛1の構想はできていたが、Silverに上がるためには守備だけどうにかなればよさそう。

1週間頭のなかで考えていたことがとっちらかりすぎてどこから手を付けていいのかわからなくなったので、Scratchみたいな感じでやりたいことを日本語で書いてみる。

1人防衛役のコードを書く。この時点ではまだ丁寧にクラス設計とかをしていた。

完成した防衛役コードを3人全員に適用する。攻撃なしでもSilverに上がることができた。

5/1

7時

早くに目が覚めたので、今後の実装方針を考える。

この時点ではまだ結構時間に余裕があると思っていたので、呑気に彼女と買い物に向かう。無印良品でゴミ箱とスリッパを買った。

11時

コンテスト期間を5/3までだと何故か勘違いしていたが、この時点で残り24時間と少ししかないとようやく気付き、焦る。

正直今回はLegend無理かもな……となかば諦めの境地に。

とりあえずGoldを目指して攻撃役のコードを書き始める。とりあえずゴール角45度の距離4600の箇所で二重の極み発動をただ待つだけの攻撃役コードを書く。

15時

完成したのでとりあえず提出してみたらGoldに上がった。えっこんな簡単でいいの?

防衛用コードにbit全探索と最小包含円を実装する。敵の読みも入れようとしたが実装が重いわりに効果が不確定だと思ったのでそちらには手を付けず。

この辺からまともな設計をすることを諦め、すべてのロジックをべた書きするスパゲッティ実装になり始める。

19時

LastBattlesを見て意図せぬ動きをしているものを見つける→デバッグ→暫定修正をする、を数時間繰り返す。

パラメータを適当に弄ったりもした。無駄な時間なのはわかってるけどやっちゃうんだよね。あとは勝った試合を眺めて時間を溶かしてた。

5/2

2時

ゴール角45度で待つよりも、真横で待つほうが敵の防衛も薄いしモンスタースポーン地点に近いのでよいと気が付き、攻撃待機拠点の場所を変更する。これが功を奏し、Gold200位くらいに。

5時

ゴールできない状況なのに二重の極みセットアップしたり、逆にゴールできる状況なのに無駄にControlを打っている試合がいくつかあったので、攻撃役のロジックを変更。

さすがに体力の限界を感じ、修正したコードを提出する。就寝。

12時

目覚ましが鳴ったので起きる。リビングで彼女が唐突にAmazonで買ったらしいオカリナを吹いててめっちゃ笑った。順位を確認。Gold40位で、かなり惜しい感じがする。

あまりにも眠かったので、パラメータを一部変更し、二度寝

13時

起床。順位表を確認するとGold4位でクソデカい声が出る。出かけたと思っていた彼女が実はソファで昼寝しており、ジト目で抗議された(ごめんなさい)

飯を食っている場合じゃねえ!ってことで、COMPを流し込む。COMPはいいぞ(唐突なステマ

www.comp.jp

 

何か改善できそうな余地がないか必死に考える。

考える。

 

考える……。

 

 

 

考えていたら他の人の提出でボスのレートが下がり、Legendに到達した。やったね。

Silver到達から40h以下でLegend到達できたので、まあまあスピーディにLegend行けた気がする。うれしい。

 

あとはTwitter見たり漫画読んだりゴロゴロしながらコンテスト終了までを過ごしました。

 

おわりに

めちゃめちゃ楽しかったです!!今回のLegendは普段に比べてめっちゃ緩いみたいな話もあったけど、まあそんなに気にしていないです。

俺が†Legend†や!

CodinGame最高!

*1:この辺の話も記事にしようと思ってたんだけど記事にする前にコンテストが始まってしまいました