HACK TO THE FUTURE 2022 本選参加記 - TopCoderの学習のお時間

HACK TO THE FUTURE 2022 本選に参加して、2位になりました。

このコンテストで高いスコアを取っていた参加者の多くが、「右手法や左手法を実現するコマンド列を作って、その繰返し回数の組合せを探索する」という解法でした。

一方、自分は右手法・左手法は作れず違う方針をとったので、どうやったのかを書き残しておきます。

天才パズルみたいに右手法左手法を賢く構築するなんて無理でしょ、という人への参考になれば。

スタート〜開始3時間時点（23376682点）

さすが本選の問題、一目ではどうやるのか全然見えないので、ビジュアライザにいろいろコマンドを打ち込んで動かしてみる。

大抵はすぐ同じ場所を動き回るだけになってしまって、繰り返しにあまり意味が無い。ただ、たまーに数十個のマスを訪問してくれるのも出てくる。

ちょっと考えて良い感じに動く一般的なコマンドを構築しようともしたけれども、すぐにはわからなかったので、 ランダムにコマンドを生成してたくさん動き回ってくれるのを探す 感じかなあ、と考える。コンピュータの計算パワーに期待しよう。

盤面サイズが20x20と小さめなのと、移動回数が5000回と少々余裕があることもあって、きっといけるだろう。

コマンドの生成方法は… 既存のコマンドの一部を変更して山登りするような方法は、途中の動きが少しでも変わるとそれ以降が全然別の動きになってしまうから、意味がなさそう。独立にランダムに生成するしかないだろう。

繰り返しのネストを4段階まで、移動回数が指定した回数以下になるようなランダムなコマンドを作って、シミュレーションして何箇所のマスを訪問できるかを調べ、一番多いものを採用、とする。なかなか実装が大変で、生成したコマンドの移動回数が思ってるのと微妙に違っていたりして、かなり苦しんだ。

1回のコマンドでは400マス中せいぜい320マスが訪問できる程度だったけど、そこから継続してまた別のコマンドを作ってシミュレーション… を繰り返せば、残っている未訪問マスをだんだん潰していけることもわかった。

結局、最初の解答としては次の貪欲法になった。移動回数が5000を超えないように気をつけつつ。

コマンドをランダム生成（移動回数1500回以下）してシミュレーションし、訪問マス数/コマンド長の効率が最大のものを採用
移動回数が4500回以下、かつ未訪問のマスがある間次を繰り返し
- コマンドをランダム生成（移動回数200回以下）してシミュレーションし、訪問マス数/コマンド長の効率が最大のものを採用
残っている未訪問マスに1つずつ移動
- 巡回セールスマン解くべきかもしれないけど、実装大変だし、そもそもこの部分に頼らずランダム生成だけで全マス拾えるようになるべきだして、BFSで1つずつ取っていくので十分だろうということでそうした

この時点の出力はこんな感じ（seed=0 265652点）。わけが分からない感じですね。

6(FL5(7(llFFRF)FFr)RF5(RR))8(LrlFL7(Fr)F)7(RrF6(lFFR)R)5(RFLF5(rrFL)4(rFF)FFL)30(FRll)24(Fr)6(F4(lrr3F)r)9(3FL)7(3(Ll3FR)FRF)9(FRl3FLF)9(llFFr)8(7(FFr)R)6(lL8(LrF)F)7(r6(FLFR)F)25(lFRl)7(RlLL9(FL))9(4(rFLrF)FF)8(8FL)9(RrFrF)25(lFRlF)9(4FRll)7(Rl5(lFR)R)5(F7(FlRFl)F)6(LrFFrlFr)

開始3.5時間時点（29612229点）

コマンドをランダム生成するときのパラメタをいろいろ変えて試していると、繰り返しはネストさせずに、1階層だけが一番良い結果になることがわかった。

頑張って任意階層ネストを実装していたのは一体…。

この時点の出力はこんな感じ（seed=0 276643点）。シンプルな形式になりました。

50(FFr3FLr)38(FRFLr)33(FFLFrr)22(rFrl4Fl)25(r3FLrF)38(LrRlF)38(FrllF)49(llFR)39(FLFRl)35(FlFRl)32(lFrrRF)35(FFlrr)36(lLrFR)42(RlrF)38(rFRFL)36(rrFLF)26(FFLFFrR)13(RFLllRRFLl5F)28(rFFRlFL)21(rFRRFrRrF)3(LF)24(RFlLr3F)16(RFRr3FRFFLL)54(rF)RFLFLFR5FLFR2FRFLFRFRFL2F

開始5時間時点（43527432点）

いろいろと最適化

コマンドの生成では n(XXXXX) の形を生成してからシミュレーションしてたけど、n回の繰り返した場合だけしか調べないのはもったいない。 XXXXX 部分だけ生成して、繰返し回数は1〜99まで全部試すようにした
- 繰り返しのシミュレーションの途中で、一度来た場所に戻ってきたらその時点で打ち切る
高速化のため、毎回コマンド生成するのではなく、最初に10000個くらいコマンドを生成しておいて使い回す

この時点の出力はこんな感じ（seed=0 442878点）。

72(Rl4FLrF)69(lFFRlFRlF)85(FlrFRll)48(R3lrFF)56(FlLr3FR)97(RlFLF)51(lFRlFLFR)44(3RrFrF)19(FrFlrRl)11(3FRll)23(rr5Fl)41(lFL3FR)

開始6時間時点（失敗）

これまでは乱択greedyなので、当然の拡張としてビームサーチにしてみた、が、遅くなるばかりで弱い…。実装頑張ったのに…

開始7.5時間時点（49205425点）

最初に手でコマンドを作って試してみてたときの事を思い出すと、10000個コマンドを生成してシミュレーションしてるけど、ほとんどのコマンドはゴミのような動きしか出来ず全然役に立っておらず、 採用されうるコマンドは偏っているのでは 、という仮説を立てた。強そうなコマンドだけ候補として生成できれば、実質の探索速度を向上できる。

そこで、もう1つ次の仮説を立てた。

いくつかの盤面で広く動き回れるようなコマンドは、他の盤面でも有用な可能性が高い

ということで、配布されている seed=0〜9 の10個の盤面を使って、コマンドを生成・選別した。

ランダムにコマンドを5万個生成する
10個の盤面それぞれで、 N*N 通りの各位置からスタートしてシミュレーションする。訪問できたマス数の合計を評価値とする
- 各スタート位置について4方向それぞれでやりたかったけど、ちょっと遅すぎたのでランダムな1方向だけでやった
評価値の高いほうから1万個を採用する。それらのコマンドを解答の中に埋め込んで使用する

埋め込んでる様子はコードの18行目をご覧ください。

この時点の出力はこんな感じ（seed=0 472098点）。

72(Rl4FLrF)96(rFr3lFL)78(lFLrrFRl)57(FLrFR)95(lFLrrFRl)70(FRlFRlFL)28(Frr5FL)30(FLFRrFLr)22(LrFFrFF)17(rFRFlFlr)

開始8時間=コンテスト終了時点（58758892点）

各コマンドについて繰返し回数は1〜99で試してたけど、もっと増やした方がよかった。999回まで試すようにするとスコアが跳ね上がった。数百箇所移動しないといけないのだからそりゃそうだ。

この時点の出力はこんな感じ（seed=0 555956点）。

226(FLrrFRll)39(FRlFl4F)87(FLrrFRll)55(LFrr4F)46(FLrFlrR)85(lFLrrFR)33(FFlrFRll)

感想

本選らしく、最初はどうやれば良いかわからないところ、コンテスト中の間じゅうどんどんスコアの天井が上がっていって「そこまで縮むのか」となり続けるのが面白かったです。

あとから振り返ると8時間中3時間くらいは無駄な実装に費やしていたことになるけど、やってみないとわからない部分が大きかったから何ともなあ。

ただ、最初から任意階層ネストのコマンドを作ろうとしてたのは良くなかったようには思う。まずはシンプルに始めて、良さそうな方向を見極めつつ肉付けしていくのが理想。