MM98参加記
MM98で自分が何をやったのか自分が忘れないためのメモ。
問題設定を説明するのは骨が折れるので、ググってください。
最終的に提出したものの方針をつらつらと書きます。
概要
- 姫がいるあたりを長方形領域で切り出す。
- 長方形領域の隅に固まって移動する。
- 分散しつつ長方形領域を塗る。
- 自由な姫がいなくなったら固まって全体を移動してモンスターを駆逐する
決めなきゃいけないこと
- 姫がいる周りの長方形領域をどれぐらいのサイズで切り出すか決める必要がある（これは定数にした）。
- 長方形領域のいくつの隅に向かうか決める必要がある（はさみうちみたいなこともしたいため）。
- 分散しつつ長方形を塗るとき、どうやって分隊を構成するか（少ないとモンスターにやられやすくなるし、多いと塗りにくくなる）。
- 長方形をどうやって塗るか。
具体的な流れ
- 初期状態を受け取ると、分隊の最小人数とどの隅の組み合わせに向かうかを決定するためにモンテカルロみたいなことをする。つまり、姫とモンスターを乱数で動かし、それをmove関数に投げることでシミュレーションを走らせ、適当なターン数で打ち切ってスコアを計算することを各パラメータで繰り返して平均スコアが最高だったパラメータを採用する。
- 乱数によって結果がかなり違うので、xor shiftのseed値についてもモンテカルロを走らせた（ちなみに、モブを動かすseed値もパラメータによって差が出ないようにしているが途中で消えたりするとずれるのでどこまで意味があるのかは不明）。
- 長方形を塗るときは、分隊ごとに基本的に周辺で最も塗られた回数が少ないエリアを選んで塗っていく。ただし、全体のうち半分は1ターン遅れて出発する（姫がすり抜けるのを防ぐため）。対角の隅に到達して、まだ姫が残っていたらこれを繰り返す。この際に分隊の最小構成人数を1だけ増やす。すでに姫を連れている騎士がピンチだったら、その騎士は安全なエリアに進む。
- 自由な姫がいなくなったらまとまって、全体を塗るだけ。
結果
とりあえずコンテストが終わった段階では22位とかであまり芳しくなかった。
乱数の気分によってスコアがかなり変化したのでもう少し安定するように工夫する必要があった（間に合わなかった）。
多分長方形を塗るロジックをもう少しちゃんと詰めるべきだった（分け方とかがさすがに適当なため）。
