菜

ハル研プロコン2019 参加記

最終順位は未確定だけど多分4位になった

人生

問題

読んで

www.hallab.co.jp

  • 書いてないけどパッケージを見るとわかること

    • エサの数{40, 60, 80, 100}・カメの数{6～25}・高さの分布{低, 中, 高}の直積で全240ステージとなっている

    • エサ・カメの座標は一様ランダムで、重なって生成されることはない

    • エサの高さは、[1, カメの数]の離散一様乱数を{低: 3, 中: 2, 高: 1}回発生させた最小値で決定される

やったこと

応募履歴見ながら思い出して書いてるのでやったけど改善しなかったことは結構書き漏らしてると思う

序盤

巡回セールスマン問題は一度取り組んだことがあって（Kaggleサンタ）知見を得ていたので1位を取りたいと思った

過去に類似の問題が出題されてたりしないか探したけど見つからなかった

厳密解が得られないかと思って整数計画問題に落としてソルバに投げてみたけど全然だめだった

ランキングを見たらTopCoder MMの赤い人とかいつもランキングで見るような人たちが上位を占めていて怖気づいたので目標を5位（賞金圏）に下げた

7日

高さがカメの数の半分より大きいエサは同時に取れない（実質的にそれらのエサをすべて食べて回るカメが存在することになる）ので、高いエサをすべて食べる巡回セールスマン問題（TSP）が解けるか試した

これを参考に枝刈り探索を実装して投げると、高いエサのTSPの厳密解が全ステージ合計で46秒くらいで得られた

TSPで得られた経路の合間に低いエサを食べたい気持ちになったが、どう探索して良いのか実装がさっぱりわからずしんどくなった

8日

そういえばビームサーチとかいうのあったなとやっと思い出した
焼き鈍しは何回か書いたことがあったけどビームサーチは書いたことが無かったので完全に記憶の外だった

高いエサのTSPはとりあえず置いておいて、全てのエサから最大ターン数が最も小さく済むエサを選び続ける貪欲を書いて投げると72,000turns, 1.5000secになった

f:id:nagiss:20191017193019g:plain

幅1のビームサーチに書き換えて投げてみると74,388, 2.1484になった
貪欲と同じ結果になるはずなのにローカルでもなんか悪くなってたので不思議に思った

この時点でのビームサーチの状態の持ち方はこんな感じ

struct State {
        bitset<100> food_is_eaten;
        vector<Point> turtle_positions;
        vector<int> turtle_turns;
        vector<int> permutations;  // エサを食べた順
        double score;
}

ビーム幅を60にしても73,886だった
似た状態が多いからビームサーチの効果が薄いのかと思い、食べたエサの集合が同じ状態はunordered_mapで弾くことにして投げると71,384になった

一つ一つのステージを見ると幅1のときよりスコアが悪いステージがあるので流石におかしいと思って原因を探した

原因は、ビームサーチの後、エサの順番から行動を復元するときに、最も良いエサへのカメの割り当てが複数存在することだった

直すの大変だなーと思ったけどカメのインデックスをソートする前に毎回iotaでリセットしたら直ってくれた

修正したビーム幅60のものを投げると66,984, 39.2265になった

f:id:nagiss:20191017195459g:plain

https://twitter.com/lgeuwce/status/1181591630890975237?s=20

ビーム幅を90にしても66,742にしかならなかった

TSPで高いエサとその間にあるエサを回収する経路を決めて、それで回収しきれないものをビームサーチで探索するのを試したけどあまりいい結果にならなかったのでこの方針はすぐに打ち切った

f:id:nagiss:20191017203207g:plain

（画像はステージ229、バグが残っている）

9日

ビューアを見ると最後の方に孤立したエサが残ってしまっていたので、ビーム幅を40に減らしてエサが残り20個くらいになってからはビーム幅を300増やす感じにしたら64,787, 39.4375になった

評価関数の改善（これまでカメの最大ターン数のみだったが、新たにエサの(30, 15)からの上下左右それぞれへの最大距離の和を加える）（基準の座標は角も試したけど中央の方が良さそうだった）をしたりすると62,519, 48.6250になった
そういえば斜め方向を試してもいいかも？と思ってたけど結局最後まで試さなかった

f:id:nagiss:20191017201632g:plain (最終ステージ(エサ100・カメ25・分布高)はスコアが悪くなってる…)

10日

色々とコードが大変なことになったので全部書き直す

11日

評価関数に残ったエサを結ぶ最小全域木の大きさを入れたい気持ちになったので、マンハッタン距離での最小全域木をO(|V|log|V|)でやる方法を調べて実装したけど重すぎてだめだった

食べたエサの集合が同じものを弾くとビームの終端の方でビームが細くなるので最後の方だけunordered_mapを使わないようにする改善をしたりしたら61,687, 51.4296になった

12日

ビームサーチした後、山登り（エサ順列の2箇所をランダムに選んでrotateかswap）するようにして色々調整したら59,546, 59.6484になった
（次の日くらいにreverseも試したりして結局rotateだけが残った、ただ最終提出では確認してないのでもしかしたらreverseも入れたほうが良かったかもしれない）

f:id:nagiss:20191017204527g:plain

ちょっとずつしかスコアが上がらないのでしんどくなっている
このままちょっとずつ改善してても30位は安泰だと思ったけど目標は5位なので別の方法を並行して考えていた

高いエサのTSPを調整してみたら20秒くらいになった

高いエサのTSPを解いて閉路を得た後、閉路から順列を適当にひとつ取り出して、それらのエサに関してはその順に取る制約をつけてビームサーチをして山登りをしてみたが66,793, 54.9921だった

13日

山登りを焼き鈍しに変えるのを試したけどあまり良い結果にならなかった

ビームサーチの評価関数に残ったエサの高さの総和/2を加えると58,581, 59.6250に改善した
（この時点で評価関数が最終提出と同じになった）

高いエサのTSPをする解法を改善して、閉路から取り出す順列を任意に（具体的には、高いエサを1つ食べるまではエサを自由に選んで良く、高いエサを1つ食べた時点で他の高いエサを閉路の両隣以外すべてロックし、以降高いエサを食べるごとにその隣の高いエサのロックを解除する）したら58,572, 58.0703になった

f:id:nagiss:20191017211256g:plain

(最終ステージは改善が大きい)

3割はTSPを解く20秒の意味だった

このあたりでビームサーチの状態の持ち方は最終提出と大体同じになった

struct State {  // ビームサーチの状態
    bitset<100> food_is_eaten;
    bitset<100> food_is_available;  // 食べてないエサについて、食べていいかどうか
    Array<char, 25> turtle_positions;
    Array<int, 25> turtle_turns;
    Array<char, 100> permutations;  // エサを食べた順
    bool closed;  // 閉路の好きな頂点を使っていいかどうか
    int score;
}

14日

TSPを使わない方の解法のビームサーチをchokudaiサーチに変えると57,574, 58.0781になった

chokudaiサーチに変えると結果が良くなるのはある程度の確信を持っていて（この問題ではビームの終端で離れたエサが残っているか決まってくるので多様性が重要になり、chokudaiさんの記事の通りchokudaiサーチは多様性を確保できるため）（chokudaiサーチで多様性を確保できる理由は正直はっきり理解できていない）、数日前から考えていたが、せっかく一度最後まで探索するなら結果を次の探索にフィードバックできないか考えていたのでなかなか実装を始めていなかった（この可能性はshindanninさんが言及している）

一度最後まで探索し、最後に残ってしまったエサにペナルティをつけ、次の探索ではそのエサが残っていたら評価関数に加算するようにすれば、そのエサは早く食べられるようになるはず
ただ、ペナルティを具体的にどう決めるかとか、実装が大変そうとか考えて無限に足踏みしていた
結局、これをすると探索して見つけたすべての状態に対して評価関数を再計算しなければならないと思い断念し（各エサについてのペナルティが二値ならbitsetで所謂64倍高速化はできそうだとは思ったが）、普通のchokudaiサーチを実装した

ただ、コンテスト後のchokudaiさんのツイートを見るとこれをすれば実現できたかもしれないとなった

chokudaiサーチのイテレーション数を増やすとメモリが足りないっぽくRuntime Errorが出るようになったので、状態をchar型で持つようにしたらなんか実行時間が短くなった
回す回数が増やせたので57,186, 58.1953になった

TSPを高速化した
プロファイラを使ったらソートがボトルネックになっていたので、比較関数の式の計算結果を予め配列に確保しておいたりしたら9秒になった
（他の初期化処理も含めて9秒なので本当はもう少し早いかも）

このときに限らずVisualStudioのプロファイラを使ってこまめに色々と処理時間を改善していた

reserveしたのにvectorのpush_backが遅いと思ったら、vectorをコピーしたときにcapacityはコピーされてないのに気づいてないだけだったということがあったりした

ハル研プロコンを通してVisualStudioに慣れていった
デバッガとプロファイラが便利だった

TSPの制約をつける方のビームサーチもchokudaiサーチに書き換え、57,109, 55.4062になった
高速化とか調整とかをすると56,539, 59.3593になった

f:id:nagiss:20191017211304g:plain

15日（最終日）

最終日のBGM

www.nicovideo.jp

山登りを焼き鈍しにしてスコアが良くならなかったのを思い出すと、山を登りきれていないんじゃないかという考えになる（前日とかに山登りで一定回数スコアが上がらなかったらbreakするみたいなことをしたけどうまく行かないとかもあった）ので、スコアが改善しそうなところに絞ってrotateをしたい気持ちになる

エサ順列から区間を選んでrotateするとき、区間の両端のエサは距離的に近い方がそりゃ改善しやすいはず
距離の近いエサの対を選ぶのにはマンハッタン距離最小全域木の前処理を流用できた
流用しやすくなるのでコードをきれいに書くのはやっぱり大事っぽいと思った

これがうまくいって54,630, 55.1484で目標の5位に到達した

エサの挿入先に少しランダム性を出したり（選んだ挿入先が順列のn番目だったとして、ランダムにnに±1する）、山登りを焼き鈍しに変えたりするとさらにスコアが伸びて4位になった

この後は焼き鈍しパラメータの調整とかをして終了した

f:id:nagiss:20191017212854g:plain

思ったこととか

  • 目標を達成できて良かった

    • 目標があったおかげで目先の小さい改善に気をとられないで済んだと思う
    • 去年はReleaseビルドを知らないで手元の環境おっそ！！！！とか言ってたし成長したなあ…

  • 評価環境へのoverfitがどこまで許されるのかわからなくてしんどい

問題規定には

特定のステージに依存したチューニングを行うことを禁止します。例えば、X番目のステージの時は、あらかじめ用意した配列に基づいて行動を決定するというような処理は禁止とします。

とあるけど、プロコン速報 vol.2 には

パッケージに含まれているチェックプログラムのコードを見るとわかりますが、全てのステージは同じではなく、
・低いところが多いステージ
・高いところが多いステージ
・二つの中間のステージ
の3段階のステージがあります。ステージの特徴を踏まえてカメを動かすことで、効率よくエサが取れるようになるのではないでしょうか。

とあって、ステージを3つに分けてチューニングすることは許されてそうな雰囲気はある気がする

ステージを分けてチューニングしたら結果が良くなるのはそれはそうだけど、あからさまにやるのはまずそうなので、間接的にやる方法を考えたりした（結局あまり上手い方法が見つからずできなかった）

（去年は30位に入るためにステージを特徴から2つに分けて戦略を変えるとかをしたけどかなりアレだなあと思っている）

  • 上位が強すぎる

    • 自分が最初の提出をした時点からほぼ不動だったしいい解に行き着くのが早すぎる
    • めちゃくちゃ時間つぎ込んでも上位陣の中盤のスコアに勝てないのはきびしい…

  • 最終提出のイテレーション数を10倍にするのを試したらローカル（初期シード）で52,317になった

    • 最終ステージのスコアは366だったけど他の戦略で363が出たことがあったので最適解からはまだ遠そう

  • 今回ビームサーチを実装したのでマラソンマッチで使われる主要なアルゴリズムをだいたいコンプリートできた気がする

  • 焼き鈍しを本来の意味(？)で使えたことがないのでこのままで良いのか不安がある

    • 十分に高い温度からゆっくり焼き鈍すと最適解に行き着くのが本来の焼き鈍しだってどこかで聞いた気がするけど、現状山登りの亜種みたいにしか使えたことがない
    • 本来の焼き鈍しと違うことをしているなら遷移確率の式(p=exp(dE/T))も最適なのか気になる気がする
      • まあでも多分温度管理とかの方が重要そうなので気にしてもしょうがない部分な気もする
        • 何もわからない

  • C++って意外とそこ最適化してくれないのかーってことがあったりするなあと思った

  • k-means++とかでクラスタリングする解法の人が何人かいて、そういうのもあるのかと思った

    • そういえばハル研プロコン2017で結構使われてたみたいだった（参加してないけど去年だったかに下調べで見た気がする）

      • 中盤めっちゃ実行時間短いのにスコアが強くてなんなんだ…とずっと思ってた

  • 赤コーダーに褒められて嬉しい

  • chokudai幅

まとめ

人生…