Spring Challenge 2020 参加記
問題概要
CodinGameのSpring Challenge 2020というコンテストに参加しました。
ゲームの雰囲気は以下のリンク参照↓
２～５体のパック（パックマンではない）を操作し、マップ上にあるペレットをたくさん集めたほうが勝ち。
パックにはRock, Scissors, Paperの３つのタイプがあり（じゃんけんのグー、チョキ、パーに対応）、敵と座標が重なったときにじゃんけんで強いほうが相手のパックを捕食する。ゲーム中に何度でも自由にタイプ変化が可能。
スピードアップも使用でき、５ターンの間移動可能距離が２倍になる。ただし、タイプ変化またはスピードアップを使用してから、10ターンの間は両方とも使用できない。
自分のパックから見えていない敵やペレットの情報は与えられない、不完全情報ゲーム。
ルールの詳細は以下のツカモさんの記事に全て書いてあります。圧倒的感謝。
結果
世界５位（日本１位）
ゲームについて考察
ゲーム木探索できるか
各パック１ターンにとれる行動は最大９通り、パックの数は自分と相手合わせて最大１０体なので、その行動の組み合わせは９の１０乗≒３５億通り。50msで調べるのは不可能な量。自分のパックだけの組み合わせなら９の５乗≒６万通りだが、これもかなり厳しいし、１手でこれなら２手以降読むのは不可能である。
では組み合わせではなく１体ずつ順番に調べたらどうか。自キャラ５体で９×５＝４５通り。これなら余裕でいける。各自３ターン先まで読めば、（９の３乗）×５＝３６５０通り。これも全探索できそう。ビームサーチ等で枝刈りを入れれば、５手先ぐらいまでなら良い感じの手が得られそう。
以上の考察から５手読みのビームサーチ系でやればある程度うまくいきそう。
（ここで計算したのは最大の状態数で、平均的な状態数はこれよりけっこう少なかったので、最終日に８手読みに増やした）
スキルの使い方
スピードアップがつよい。もうずっとスピードアップ連打でよい。そんな気がするが、これは本当だろうか？
短期的な攻防で見れば、死を回避したり角で待ち伏せしたりする以外にタイプ変化するメリットはなさそう。しかし長期的に見れば、視界内の敵の苦手タイプに変化することで敵の行動範囲を制限する効果があるかもしれない。考えてもよく分からなかったので、タイプ変化を選択肢として常にプログラムに与えておき、使うかどうかの判断は探索アルゴリズムさんと評価関数さんに任せることにした。
結果として、スピードアップをすると詰むタイミングでは代わりに敵の苦手タイプに変化するようになり、これは良かったと思う。それ以外の状況でも変化することが稀にあったが、それが有効な変化どうかは検証する時間はなかった。
最終提出プログラムの内容
先に書いた考察をふまえ、最終的に出来上がったプログラムの内容を書く。
１．アルゴリズム
それぞれのパックからChokudai Searchをやった。深さは８ターン。
パックの行動順は重要
パックの行動を１体ずつ決めていくにあたり、どのパックから順に見ていくかというのが重要である。それによって結果が大きく変わってくる。
どういう順番で調べるのが良いかは、スーパーペレットの取得を例に考えると分かりやすい。まず悪い例を１つ挙げる。スーパーペレットまでの距離が５のパックAがいたとする。このパックを最初に調べた場合、５手でスーパーペレットを取得する経路を選ぶだろう。次に調べたパックBがスーパーペレットまで距離２の位置にいたとする。このパックはどういう行動をとるだろうか？評価関数にもよるが、もし５手後より２手後の評価値を重視するような重み付けをしていたり、スーパーペレット取得までのターン数の早さを評価していたりするなら、パックBもまたスーパーペレットを取りに行く経路を選ぶだろう。さらに、次に調べたパックCが距離１の場所にいたら、パックCもスーパーペレットに向かう経路を選択するかもしれない。それか、パックBとの距離は１しか違わないので評価値の差が小さく、スーパーペレットをパックBに譲って他の場所へ行ってしまうかもしれない。
結果として、複数のパックが皆でスーパーペレットに向かったり、一番近い場所にいるパックが違う場所へ行ってしまうような行動になり、無駄な動きが生まれる。今回の場合、まずパックCの行動を調べてその後に他のパックを調べるとうまくいく。
では、それをプログラムでどうやって判断するか。
実際にはスーパーペレット以外の要因も関わってくるため難しい。スーパーペレットから最も近い場所にいるパックが取りに行くのが必ずしも最適とは限らない。では何が最適かといえば、それを判断するのが評価関数である。誰を最初に動かしたいかは、行動次第で得られる評価値が大きく変わるような場所にいるパックであり、それは探索によって調べることができる。
パックの行動順の決め方
まずパックの順番決めのための探索をする。自分以外の味方も敵も全て停止状態として探索し、それぞれのパックが作った盤面の評価値を記録する。これには8msだけ使った。
次の２回目が本命の探索。１回目の探索で最も高い評価値の盤面を作り出せたパックから順にChokudai Searchをして行動を決定していく。敵のパックは全て停止状態。これには33ms使った。
（１回目10ms、２回目35msでやっていたがなぜかタイムアウトが多発したので少し減らした）
２．行動選択
行動はほぼ全て考えるが、１手で自滅する可能性のある手はとらない。また、詰みを回避するためのタイプチェンジで敵と同じタイプになることがあったため、最も近い敵に対する有利タイプ以外への変化を禁止した。
３．シミュレーション
ゲーム本体のコードが公開されているのでそのシミュレーション部分を真似て書いた（Javaで書かれているのでc++に書き換えた）。これをやるとゲームに対する理解が深まるのでオススメ。お互いがすれ違うときも衝突するとか、食べられる場合は移動する前の座標で食べられるとか細かい処理を見落とさずに済む。
今回は敵の行動は探索せずに自分だけ探索するので、シミュレーションに少し手を加えて敵をいい感じに動かしてやることにする。もしシミュレーション上で敵を停止状態として扱った場合、（実際には敵は動いているので）シミュレーションの結果と現実の結果にズレが生じてしまう。例えば、シミュレーション上で停止した敵を食べて、敵を倒したので加点！とやるのは明らかに間違いである（現実では逃げられてしまうことのほうが多い）。このあたりをうまいこと調整してやる必要がある。
シミュレーションを改造
①相性で有利な敵と重なったとき
普通に考えたら敵は逃げるので、それをシミュレーションに入れる。敵のパックを１歩逃げさせるか、アビリティを使えるなら使用させる。これにより、逃げ道の残されていない敵のみをkillするようなシミュレーションができたので、敵パックのkill評価や詰み評価とうまく噛み合った。
②相性で不利な敵に近づいたとき
敵パックがどういう移動をするか分からないので、敵の移動可能な範囲に入った時点で自分のパックは死亡として扱うようにした。これはちょっと過激なやり方だが、やらないよりは良かったので採用した。
これは言い換えれば敵にチート能力を与えてめちゃめちゃ強く見積もっている状態なので、自パックがやや逃げ腰な動きになるのが欠点ではある。最初はこれに加えて評価関数で自パックの死亡に負の評価を入れていたが、それだと過剰に逃げすぎてダメだったのでその評価を外すとちょうどよくなった（死亡そのものをマイナス評価しなくても、死亡したらそのターン以降のシミュレーションで行動できないのでペレットを食べに行けず、他と比べてスコアは低くなる）。
本当にやりたかったのは、例えば敵パックが70%の確率で存在する場所に行くと自パックは『70%の確率で死亡しているパック』になる、というのだが、上手な実装を思いつかなかったので出来なかった。
４．評価関数
５つの評価値を計算した。
①スーパーペレットを食べたターンの早さ
これは最も重要な評価とした。他の全てを差し置いても、スーパーペレットは最速で食べたい。
②自分のパックが食べたペレットの数
（見えないセルは事前に計算したペレットの存在確率で代用する）
③自分の各パックの周囲のペレットの数
全自パックから同時に距離10マスまで幅優先探索を行い、他パックと重複しない範囲で最もペレットをたくさん出来る経路をそれぞれ計算し、そのペレット数の和を評価値とする。（コンテスト終了後にボンドさんの記事を読んで知ったが、この処理は幅優先よりダイクストラでやったほうが良さそう）
④敵パックを食べた数
敵パックの死亡=10点、詰み=9点としてボーナス
⑤最も近いペレットへの距離＋最も近いスーパーペレットへの距離 * 10
各評価値の解説
まず①の評価値によって、スーパーペレットから距離が最も近いパックがスーパーペレットを食べに行く。
④のキルのポイントがペレット10個分と高いので、キル出来るときはだいたいキルしに行く。
あとはだいたい②の評価値で動く。たくさんペレットを食べられる経路を選択する。しかし、８ターンペレットを食べた後何もない場所に取り残されてしまうのも良くないので、③で８ターン後の状態から幅優先探索を行った周囲のペレット数も考慮する。③の重みは②よりは低い。
⑤はタイブレーク的な役割で、８ターン＋１０マスの結果で差がつかなかったときに、さらにそれより遠くにあるペレットを探してそれに向かう。
詰み判定
敵が袋小路の中にいる場合のみ考える。敵パックと自分の各パックから同時にBFSをして、敵が袋小路の外に出られず、アビリティが貯まる前に袋小路の奥に追い詰められる場合、詰みとする。
５．敵位置の予測
敵の位置計算
Ocean Of Codeのときのやり方とほとんど同じで、敵の[位置, 経路]の候補を可能な限り保持する。敵はスピードアップを最大限使用して最速で移動し、途中で折り返さないと仮定した。マップの端に行くと行方不明として無視するようにした（マップ端での折返しも考えると状態数が爆発しそうだったので）。
『ペレットのある場所は通過していない』ということは分かるので、それを使って敵の位置候補を絞ることができた（敵の経路情報を持っているので、経路上にペレットがある場合その[位置, 経路]を候補から除外する）。
また、交差点で『ペレットが存在していて袋小路でない道』がある場合、敵はそちらへ向かうと断定するヒューリスティックを入れた。（効果があったかは不明）
ペレットの存在確率計算
敵が視界に入ったとき、自分の予測した候補に位置が一致するものがあれば、その経路上のペレットを敵が食べたとして確定できる。発見時に敵パックを食べていたり衝突していたりすると多少ずれるので、２マス以下のずれは許容した。考えられる経路が複数ある場合はランダムに１つ選択した（これを書いていて思ったが、考えられる経路が複数ある場合は全ての経路上のペレットを 1/経路数 の確率で食べたとしたほうが良かったと思う）
シミュレーション上での敵座標の扱い
敵の位置が確率として得られるが、確率のままシミュレーションに持ち込むのは難しかったので、最悪の場合を考えて
『自分に対して有利なタイプの敵は候補のうち自分に最も近い場所にいる』
『自分に対して不利なタイプの敵は候補のうち自分から最も遠い場所にいる』
とした。本当は確率のままシミュレーションに持っていけると良いが、実装が複雑になりそうだったので断念した。
敵の位置候補が５以上ある敵はシミュレーションに持ち込まないようにした。現実に５分の１以下の確率でしか起こらない最悪の場合を想定してシミュレーションするのは、現実から離れ過ぎだろうと判断したため。
感想
複数ユニット操作、同時着手、不完全情報、とボット開発の難しさが詰まったコンテストだったと思う。定石が分からず手探り状態だったが、結果的に上位に入れてよかった。
対戦ゲームにおける『敵を動かさないシミュレーション』はまだまだ未開拓領域だと思うので、もっと開拓していきたい。
