HACK TO THE FUTURE 2019予選に参加しました。8時間中7時間半ほど参加して22位でした。前回より1位だけランクアップしましたが順位表の1ページ目には入れず残念。
試行ログ
まずは周囲に壁をつくるだけの初期配置を試し、80904点。
マークを盤面いっぱいにランダムに配置して点数を計算する方法を実装し、91248点。試行回数は手元で2700回ほど。
山登り法を実装。すなわち、ある盤面に対してランダムな位置にランダムなマークを配置し、点数が上がれば採用。114674点。このあたりで方向性がつかめてくる。
ベストなスコアを出す盤面について、付与されたマークの数を数えてみると、LやRの出現頻度がD, T, #よりもかなり多いことに気付く。そこでマークとしてLやRのみしか使わないようにする。119184点。
このあたりからはかなり怪しい修正を繰り返した。値は上がったり下がったりを繰り返していたので、どれがどれくらい効いたかがよくわからない。
- 焼きなましの導入。点数の減少率が閾値以下であれば、ある確率でその変化を受け入れる。
- マークを配置するマス目を左上からラスタスキャン順に全部試す
- スコアが変わらなければ遷移
- 変更するマスが必ず今と異なるマークとなるようにする（これは当たり前）
- スコアの計算をするとき、停止カウントが4以上のマスにも点数に違いを与えて少しでもよい状態の方に遷移しやすくするように変更。
最終的なベストスコアは126504点で22位。正の点数を取った人が518人なので上位5%にすべりこめた。
本番中に気付いていたが実装できなかったアイデア
- 点数再計算のとき、影響を受けるマス以降のみを再計算
本番中に気付かなかったアイデア
- 命令列の圧縮
- L, Rのマス上で動きに影響を受けるロボットだけ再計算する
- 中央に近いマスから順番にマークを変える（終了後の動画より）
- 初期盤面を全部Lで埋めて始める notさんのツイート
- L, Rしか使わないと決めることでシミュレーションのコードを簡単化
- example_01 の解をコードに埋め込む
感想と反省
終了後の動画解説の通り、L, Rだけ使うという方針に早期に辿りつけたのはよかったです。しかしD, T, #も用意されているからにはどこかで使うべきなのではないかとの疑念が頭を離れず、その後もちょくちょく復活を試みていたのは結果からいうと時間の無駄でした。また、LとRしか使わないことを決断してしまえばもっと高速化できる余地がありましたが、その発想に至れませんでした。
ずっとZipで配布された盤面のみを使って検討をしていましたが、検討が煮詰まってくるとローカルの点数から提出後の点数を予測するのが難しくなっていました。サボらず複数盤面からローカルの点数を算出したほうが結果的には無駄がなかったかなと思います。
