SPRING CHALLENGE 2020

CodinGameの10日間コンテスト。じゃんけんパックマンゲーム。

f:id:y_kwn:20200518230416p:plain

リプレイ : https://www.codingame.com/replay/467340361

世界25位/4976人、日本5位/228人でした。個人的にはあまりぱっとしない成績。

ルール

同時に2~5体のパックマンを操作しペレットを集めるゲーム。
過半数のペレットを集めたほうが勝ち。
じゃんけんで勝っている敵のパックマンを食べることができる。
アビリティとして「加速」と「グーチョキパーどれかに変身」が使える。

アルゴリズム概要

10手読み幅200のビームサーチで各パックマンの動きを決定。
パックマン毎に200パターンの動きが求まるので、どれを組み合わせるかを山登りで決定。(この辺のパラメータ調整は甘い)

最初は相手の動きに合わせて如何に動くかが肝心と思って「すわっこれはMCTSか!?」と思ったんですけど、敵と絡むことはそんなにないので敵の動きはある程度無視して自分の動きを最適化するのがベストだと思い直しました。
さらに味方同士もそんなに絡むことはないから、パックマン毎にサーチして後でマージするって方式にしました。

ビームサーチ部

10手読み幅200でサーチ。
多様性確保のために最初の2手の動きが異なる物はビーム内に必ず入るようにした。
あいこか負ける敵は行き止まりとして扱ってサーチした。(これ勝つ相手も行き止まりにしてよかったかも)
来た道を戻るような動きにはペナルティをかけた。

山登り部

パックマンが10ターン分の動きを200パターン持ってるから、各パックマンはその中から動きを1つチョイスする。選んだ動きを元に10ターン分シミュレーションして評価する。シミュレーション中敵は動かさない。
その後どれか1つのパックマンの動きを変更するという遷移で山登りする。

評価関数

小ペレットを取った数 * 10
大ペレットを取った数 * 100
なくなってるかもしれないペレットを取った数 * 1
近くの小ペレットまでの距離 * -0.1
近くの大ペレットまでの距離 * -5.0
殺される相手の移動圏内にいると -10000

小手先テクニック

敵の動きの予測

各ターンの最初に、見えない敵は1手分動きを予測して予想位置を決定した。 動き方はこれ↓

  • アビリティを使える状態なら加速を撃つ
  • なるべく大ペレットに近づく
  • ペレットに接していたらペレットを食べる

見えない敵を再び見かけたときは、その地点にワープさせた。(適当)

通路

f:id:y_kwn:20200518230020p:plain

通路(画像の黄色い部分)の入り口をチェックして、入り口にペレットがあったら通路内のペレットはまだ存在すると仮定した。逆にペレットがなかったら存在しないものとして仮定した。

とられたかもしれないペレット

ペレットは、小ペレット・大ペレット・とられたかもしれないペレットの3つの状態を持つようにした。

かちあい時の動き

f:id:y_kwn:20200518230027p:plain

かちあいが発生したら、加速と相手に突っ込むのを禁止した。
(加速したらその瞬間に取られるし、変身した相手に突っ込んだら死ぬので)

殺し

アビリティを使えない敵が袋小路に追い込まれていた場合は殺すようにした。 逆に自分が袋小路に追い込まれていた場合は勝てる相手に変身するようにした。

反省

敵の動きの予測をもっと作り込むべきだったかなあ。

戦術をもっと真面目に考えるべきだった。

諸々検証不足でフィーリングで進めがちだった気がする。

山登りより優先度順にビームサーチの方が強そう。