"CodinGame Spring Challenge 2020"に参加しました。
CodinGameにはリーグという階級分けの制度があり、各リーグのBOSSを基準にWood2, Wood1, Bronze, Silver, Gold, Legendと登っていきます。今回のコンテストで初めてSilver(の上位)まで到達することができました。
作成したAIも自分より強い敵にぶつかりに行ったり、同じ場所を往復したりはしない状態になりました。
参加経験
CodinGameへの参加は2018年のXMAS RUSH, 2019年のUNLEASH THE GEEKに続いて３度目の参加で、今回のコンテストで初めてSilver Leagueへの進出を果たしました。
取り組み
2020/05/08から2020/05/18にかけてCodinGameで開催されていました。ルールは2日目に確認したものの、実装は主に最後の週末に取り組むことになりました。 前回まではPythonで参加していましたが、速度の問題がありますので、今回はRustで実装してみました。トータルで1000行程度のプログラムになりましたが、Rustの型推論のおかげで快適にコーディングができました。
ルール
コンテスト内容はパックマンにじゃんけんを付け足したようなゲームが与えられるので、より強いパックマンのAIを作ろうというものでした。 詳しいルールはツカモさん (@tsukammo)の翻訳記事『codingame:Spring Challenge 2020 ルール要約&マップ生成ロジック説明 - tsukammoの収穫記』を御覧ください。
やったこと
10点のSuper Pelletがあれば優先的に狙い、それ以外は見えているPellet、存在が不明なPelletの順に優先しながら目的地を決定するようにしました。見えているPelletを使ってでできるだけ長い道を通りたい気持ちです。 衝突は自分が死ぬ可能性がある場合のみ移動やスキルを使って全力で避け、それ以外は気にしない実装をしました。また基本的には倍速のスキルを連発するようにしました。
前処理
- 幅優先探索で各マス間の距離を計算
- 敵の位置を初期化
毎ターン
- 10点のSuper Pelletがあれば最も近いPacに向かわせる
- 各Super PelletとPacの距離をheapに入れて、出てきた順に採用
- Super Pelletに向かっていないPacは、それぞれのPelletへの経路上のPellet数を数え、多い道に進む。
- 接敵している場合はSwitchのスキルを検討する
- 交差点での不慮の事故と袋小路に閉じ込められる以外で死なないように近くの敵からの間合いを調整する
- 直前のターンに見たが、視界から消えた敵はそこから最大1マス離れているとして考慮
発見した問題・バグと実装
- HとWを間違える
- index overflowとして発現
- 座標を配列で管理する際に
y*W + x = iとせず、y*H + x = iと実装していた
- 殺されがち
- 自分がSkillを使えないときは逃げる
- 自分がSkillを使えるときは、次の行動で襲ってくるだろうというタイミングで相手に勝てる手にSwitch
- Pac同士の目的地が交差するため、お互いが動けずにいた
- 遷移先の座標を早い者勝ちで管理した
- 視界から消えた敵の情報が更新されず、同じ場所に留まっているように見えていた、また倍速状態が続いていた
- 最後に見た時刻を管理した
- Super Pelletに向かって相手の後ろを走り続ける
- 相手の方が近ければ諦めるようにした
- 交差点で相手と衝突し続ける（敵の位置は見えない）
- 想定する位置を次ターンに持ち越し、想定通りに移動できたか確認する
- (衝突したターン数/10)+1個強い手にSwitchする
以上を実装したところで体力の限界となり、Goldには届かずという結果になった。Silver内の日本人ランキングでは4位でした。
感想
第一に楽しかったです。ちょうど週末を2回挟むスケジュールなので出やすいですし、徐々に強いAIを倒せるようになる楽しさがありました。 また、今回はPac単位での貪欲しかかけていないので、次回までに評価関数を作って手番全体で最適化できるような実装を練習しておきたいところです。対戦ありがとうございました。
