HACK TO THE FUTURE 2020予選 参加記録
HACK TO THE FUTURE 2020予選 - AtCoder
なんと全体10位で本戦に進むことができました！
やったことを軽く書いておこうかと思います。けっこう雑な焼きなまし法なので、あまり参考になるかは分かりませんが…
ビジュアライザのスクリーンショット等はexample_01.txtのものを利用しています。また記載している試行回数などは手元実行のもので、AtCoderのコードテストでは4倍くらい多く回っています。
BFSでマス全埋め（24:39、4,370,893点）
最初に挨拶代わりに 0 で正の得点を取ったのはいいとして、まず思ったのは「全ロボットはゴールさせる前提になるだろう」ということ。
ゴールと連結であればゴールからBFSで矢印を伸ばしていくことで必ずゴールさせることができるので、まずそれを書きました。
サンプル1での矢印は1298個。何となく直線で続いていたほうが後々削りやすそうかなと思ったので、1回の探索で隣4マスだけでなく、4方向に進んでブロックにぶつかるまでを見るようにしました。これが437万点。
不要矢印の削除（58:29、4,947,389点）
さすがにこれは無駄で、全く使われない矢印がいっぱいあります。この経路に沿って実際にロボットを動かしてみて、ロボットが1回以上向きを変えた矢印のみを残すようにしました。これで矢印は160個に。
さらにこの中に、「最初に決めた経路通りにロボットが進むと使うけど、実は取り除いても問題ないもの」がいくつかあります。これは愚直に、矢印全部に対して「1個矢印を消してみて全ロボットを動かして、全員ゴールできるようなら消す」ようにして消しました。これは意外とあって142個まで減りました。
これで494万点、暫定トップになっていたようです。
試行錯誤
BFSのキューに入れる順番を近い方から入れてみたり、遠い方から入れてみたり、DFSにしてみたり、過去コンテストで「4方向の探索順序を変えるとスコアが大きく変わる」というのがあったので試してみましたが、いまいち良い知見は得られず。
仕方がないので山登り法/焼きなまし法を回し始めます。
近傍1種の山登り法（1:49:17、4,950,033点）
近傍2種の焼きなまし法（3:43:46、4,962,496点）
この辺は改良と提出を何回か繰り返していますがまとめて書きます。
焼きなまし法をするにしても「近傍って何だよ…」という気分になるのですが、既に矢印によって経路ができているので、あまり経路を大きく崩すような近傍は良くない気がしました。
とりあえず試したのが「矢印を1個選んでランダムに回転させる」というもので、次に「矢印を1個選んでランダム方向に1～10マス平行移動する」と2種類交互に実行するようにしました。その矢印を通っていたロボットが、運良く違う経路に合流できてそっちからゴールできる場合、元々通っていた矢印を消せるかもしれないからです。
変更後はまず全部のロボットがゴールできるか確かめて、ゴールできなかったらその時点で却下。その後は先ほどと同じように全矢印に対して消していいか判定をして減らします。そしてスコア計算をして焼きなまし法に従い解を更新します。
サンプル1の矢印数は117個まで減り、スコアも496万点まで伸びました。
試行回数は35,000回×2種類。ただ近傍を完全にランダムに取ったので、変更するとそもそも全部のロボットがゴールできなくなって即却下される確率のほうが高いです。変更した矢印の先に矢印がなければ置いてみる…みたいな実装もしましたがイマイチでした。ここでちゃんとBFSをやり直すなどして経路を作ってあげたらマシになったのかもしれません。
近傍3種の焼きなまし法（5:53:42、4,964,370点）
コンテスト時間が半分を過ぎて順位もズルズル落ち、アイデアが尽きてきたのでとりあえず新しい近傍を開発してみることにしました。今の近傍の取り方では実行時間を増やしてもスコアが全然伸びなかったので、もっと広い範囲に解を振ってみようというものです。
これまで「回転」と「平行移動」をしていたので、3つ目として「回転と平行移動」を加えました。これだけでサンプル1の矢印数は114個になり、ちょっとスコアが伸びました。
近傍4種＋高速化（6:52:32、4,965,203点）
さらに4種類目の近傍として「縦にも横にも位置をずらして回転」というのを加えました。斜めに動かすと入る方と出る方の両方がずれるのであまり良くないような気がしたんですけど、実際に試すと意外にもスコアが伸びました。単純に振れ幅の大きい近傍が入ることで探索範囲が広がった効果ですかね…？
ただこの4種類目の近傍だけを試しても上手く行かなくて、「回転だけ」→「平行移動だけ」→「平行移動＋回転」→「縦横移動＋回転」→「回転だけ」→…というふうに順番に回していったので、近い近傍と遠い近傍をバランス良く探索できたのかもしれません。
また近傍が増えてくるとその分試行回数も必要になってくるので、小手先でできる範囲の高速化をしました。具体的には矢印を変えた後にロボットがゴールできるかの判定を、元の経路でその矢印を通っていたロボットから先に行うようにしました。本当はもっとオーダーレベルの改善ができると思うんですけど…
試行回数は約100000回×4種類。矢印の数は112個でした。
最終成績（7:54:07、4,965,312点）
Submission #8259364 - HACK TO THE FUTURE 2020予選
最後はパラメータや乱数シードガチャでわずかに点数を伸ばして終了。最後の追い上げでどんどん抜かされてハラハラでした。
振り返り
全員ゴール可能にする→不要矢印削除、というそこそこ強い初期解を素早く作ることができた…けど、早い段階での実装・提出をしていなかっただけで上位勢は気づくポイントだと思うので、強みになるのかは微妙。
斜め移動など「絶対に損するだけでしょ」と思うような振り方でも試してみるのは大事。
途中時点では高速化の恩恵が薄いと思っても、後で試行回数を増やしたくなるタイミングは高確率で来るので、他にやることがないなら高速化しておくに越したことはない。速度は正義。ただし高速化でバグらせると萎えるので実装力大事。
4時間時点でアイデアが尽きて既にお腹いっぱいな気持ちだったけど、諦めなければ何かできることはある。アルゴのコンテストと同じく、コンテスト中のモチベーション維持は大事。
本戦も頑張ります。
