Amadeus Challenge
CodinGameの14日間コンテスト。陣取りゲームです。
リプレイ：https://www.codingame.com/replay/325204606
世界2位/199人、日本1位/16人でした。人数は少ないですが、TOP5常連の強者は軒並み出場してたので上位を取る難易度は普段と変わらなかったと思います。
ルール
ルールはかなり単純でした。リプレイを見たら雰囲気はだいぶ伝わると思います。
- 味方と敵のユニットは同居できて、味方ユニットのほうが数が多ければコントロール配下の星となる。
- 1ターンに5体ユニットをコントロール配下にある星、または隣接する星に送り込める。
- 1つの星にユニットを送り込める回数は5回まで（1ターンに5体送っても1体送っても1回とカウント）
- 5つ以上ユニットが居る星を1つ選んで、その5体を犠牲にして周りの星に1つづつユニットを送り込むことができる。（通称spread）
- 隣接する星が、敵の星より味方の星のほうが多ければ敵ユニットが1体消える。
- 最終的にコントロール配下の星の数が多いほうが勝ち。
アルゴリズム概要
1手読みのミニマックスでした。ただ1手読みでもTLEするので、評価値でソートしてビームサーチっぽい処理を入れてました。
シミュレータ実装
シンプルなルールなのでシミュレータは楽勝で作れます。47msで100k回くらいの性能でした。
ミニマックス
まずは送り込む候補となる星をピックアップします。ピックアップする星は前線の星、つまり敵と味方お互いが関与できる星を候補とします。
ピックアップした星に送り込む全パターンを手とします。ただし、ユニットを送っても敵ユニットの数より味方ユニットの数が少なくなるパターンはカットしました。 それに加えてリンク数が5つ以上の星に関してはspreadも考慮します。
で、まずは味方の手全てに評価を付けてソートします。その後ソートした順にミニマックスを展開していって最優良手を選んでいきます。 ざっくり図にすると↓みたいな感じです。
評価関数
コントロール配下にある星の数がベースでしたが、敵ユニットを削れる場合はボーナスを与えて、そのボーナスが一番重い評価関数でした。
このゲームは最終的により多くの星をコントロール配下に置けば勝ちですが、ユニットをより多く持っている方が当然より多くの星をコントロール配下に置きやすいです。 なので、星の数よりもユニットの数に重きをおくような評価関数にしました。
SpecialPlanet
今回のゲームでは、下記のような作為的なマップが結構な頻度で出現しました。
この例だと、16番の星を取るとめちゃくちゃ美味しいです。なので、こういうパターンが出たときは特殊処理を入れてました。ちなみに自分はこの16番みたいな星をSpecialPlanetと読んでました。
基本は通常のミニマックスと同じですが、ピックアップする方法と評価関数を変えてました。
まずピックアップする星は、自分が送り込めるのが可能なすべての場所にします。ただしユニットを送り込むパターンは同じ星に5体まとめて送るパターンのみに絞ってます。
評価関数は「SpecialPlanetまでの距離が近い星にできるだけ多くのユニットが配置されてれば良し」みたいな評価関数でした。
ヒューリスティック
あとは到るところに色々ヒューリスティック要素を入れてました。
- 初動時に、前線が確定するまでは敵に近づいた分だけのボーナス点を与えた。
- 前線が膠着した場合は、多少不利でも敵陣に無理やりユニットを送るように調整した。
- 1つの星にユニットは5回しか送れないので、序盤は回数を節約するためにできるだけユニットまとめて送るようにした。
終盤はヒューリスティックを色々入れたり外したりが調整の中心だったので、ここには書ききれてないヒューリスティックも色々入ってます。
反省点
- 1位になった後のモチベーション管理が難しい。（イキり）
- もっと詰めるべき点があった気がするが、変更を加えても順位は上がらないので（終盤ずっと1位だったので）効果の測定が難しく詰めきれなかった気がする。
