RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 受験記

RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜

AHC003 以来の 1 週間マラソン参加でした。結果は 201 位で、順位以上に戦略面で悔いが残る結果となりました。

というのも最初の 3 日ぐらいで大体の実装を終えた後は、上位と大きな得点差があるにも関わらず根本的な方針転換に踏み切れず細かな評価関数の調整といった小手先の修正がメインになったためです。序盤で根を詰めすぎて中盤以降はスタミナも切れ、消化不良になった感が拭えません。マラソンマッチはペース配分も大事だなーと感じました。

本記事ではコンテスト期間中の思考/試行過程の整理に加えて、コンテスト後の試行についても逐次追記していこうかと思います。

問題概要

問題本文はこちら。

• 舞台は 16x16 マスのグリッド。1000 日の間にいろんな地点で野菜が生えたり枯れたりするので、なるべくたくさん野菜を収穫したい。
• 野菜は 1000 日間で合計 5000 個出現する。各野菜には価値があり、後半ほど価値の高い(=金額の高い)野菜が出る確率が上がる。
• 野菜の収穫には収穫機が必要。収穫機はお金を払って買う必要があり、$j$個収穫機を持っている時の収穫機の金額は$(j+1)^3$円。つまり買えば買うほど金額が跳ね上がっていく。
• プレイヤーは毎ターン新たに収穫機を買うか(お金が足りている場合)、どれか 1 台の収穫機を別のマス(隣接じゃなくても OK)に移動させるか、何もしないか選べる。行動を選んだ後、野菜が生えているマスに収穫機があれば、野菜を収穫できる(収穫した野菜はその時点でグリッドから消える)。
• 収穫した野菜の価値(金額)には、当該マスの収穫機と連結している(上下左右マスで連鎖的に繋がっている)収穫機の数が乗算される。つまり収穫機がいっぱい繋がってるほど収穫が増やせて嬉しい。

最終的な戦略

以下は参考イメージとして、僕の最終提出版ソースコードでの挙動を公式のビジュアライザでプロットしたものです。茶色い四角が収穫機です。途中良く分からん飛び地に収穫機が居たりしますが、そのへんは結局ちゃんと直せてませんね。

ここからはコンテスト中及びコンテスト後の思考/試行記録です。

1 日目(2021/9/5)

考えたこと

• ぱっと見問題設定が以前参加した AHC003 より複雑そうだなと思った。
• 親切にも解答コードのテンプレートとして sample_submission.py が提供されていたので、それをベースに改造する方針に。
• テンプレートは、各地点において最初(T=0)から最後(T=1000)までに登場する野菜の価値を足した(野菜の収穫終了日の考慮なし)sumfutureveges の情報を基にして収穫機を購入するというだけのもので、収穫機の移動が考慮されていない。まずは移動を考慮したい。
• 収穫機の移動先を決めるために、ある T から直近の未来(T から T+10 までとか)に高い価値の野菜が得られるであろう場所を使ってはどうか。
  ⇒ 本当はなるべく収穫機が連結した地点に機械を運べれば更にうれしい。

実装

• 直近の未来で収穫できる野菜の一番価値が低い座標にいる機械を、直近で一番収穫量が多そうな座標に移動させる方針で、4,586,304 点。

改善(辺に重みを持たせる+重み更新式の変更)

⇒86780317507 点(コード)

2 日目(2021/9/6)

考えたこと

• 夜、ベッドの中で目が冴えていろいろ考えたり、問題文の誤読に気付いたりした 　 ⇒ 野菜は期間中ずっと生えてるわけじゃなくて、一度収穫したらその分については終わり。あと複数の野菜が同一地点に同時に生えることはない。
• 最初にできるだけ収穫量を増やして機械を増やしておけば、その分将来価値が高くなった野菜を多く収穫できてリターンがでかくなる
• ループの終盤、機械を買うべきか否かの判定のために、ある時点以降で獲得できる最大の理論値を計算しておき、その何割かを下回るようなら購入しないようにしてはどうか
• 収穫完了した野菜の判定用に、各座標ごとに取れる野菜のリストを持っておき、収穫した時点が含まれる期間は nearfutureharvest が 0 になる
• 機械の購入、移動時は連結度も考慮した最高収穫量の地点を選択したい。毎回の simulate 時に連結度を座標に持たせて管理するようにしてはどうか。どの機械を動かすかの選択も、連結度が低いものを連結度の高いところに持っていっては？
• 未来の何手か先までをシミュレーションして最適行動を選択するようにできないか？ 　 ⇒ 方針を変えて、game.selectnextaction(day)～ game.simulate(day, action)を乱数でぶらしながら複数回回して最もスコアが高かったものを 　　以降の処理に回すという処理を実装してみてはどうか
• ループの中で動かせる機械の数はわずか。一度置いたら動かせない機械が多い。よって、購入した機械を置く場所は、購入時点以降で最も収穫量が多くなる地点を選ぶのはどうか。なおかつ、機械が連結することを期待して、購入機械を置く場所は極力固めたい。また、ループの終盤、その地点で購入した場合の収穫量の方が購入費より高くなる場合は買わないという選択肢をとれないか。
• 序盤から中盤(機械が 3 台ぐらいになったあたりから)にかけて、機械を 2~3 個セットになるように収穫可能地点へ移動させる戦略を実装したい。
• 最適な機械の移動先をシミュレーションする際に、countconnectedmachines()の前後で move()を呼んでないバグに気づき修正した。ビジュアライザありがとう。

改善(ループの途中でグラフの重み更新式を変更)

⇒89446267313 点(コード)

3 日目(2021/9/7)

考えたこと

• 機械をなるべくまとまった状態で動かしていきたいから、行動選択の候補を減らしてはどうか？ 　 ⇒4x4 のグリッドごとに未来の収穫量を算出しておき、その上位 8 グリッドだけを機械の購入/移動先として選べるようにする。 　 ⇒ 失敗。スコアが高くなってくると最終的にグリッドをまたいで機械が連結していくので、むしろスコアが下がった。
• 機械の移動先を決める評価値をこれまで単独のマスの収穫量で考えていたが、周囲のマスも考慮するようにした。各地点で将来収穫できる野菜のトータル量を表す futurevaluetotal は周囲 1 マスを、ある t における各地点の収穫量を表す futurevaluearound は該当マスとその周囲のマンハッタン距離が 2 以下の収穫量を考慮するようにした。
• 乱数を使うアイデアを纏め始める。機械の購入/移動場所を上位 N 候補から乱数で選択したり、終盤に機械を買うか買わないかを乱数で決めたり。大きな流れとしては、例えば序盤で 10 通りシミュレーションして、その中で有望そうなやつを使って残りのシミュレーションをして、終盤に更に分岐させるのはどうか？ただし実行時間制限との兼ね合いになるので、終盤だけにするか、序盤だけにするか、スコアを見て考える。

改善(周囲のマスを考慮)

⇒49923268 点(コード)を達成。

⇒ パラメータチューニングしたらスコアがサクサク伸びて 65100048 点(コード)に。

4 日目(2021/9/8)

考えたこと

• 乱数によるシミュレーションを本格的に使い始める。main 関数の中で乱数を使うかのフラグによって処理を分ける分岐を用意し、機械の購入/移動先の決定を乱数で実施するようにした。 　 ⇒ 一度雛形を作ってしまえば後はシミュレーションのタイミング(序盤、中盤、終盤)や乱数の範囲や重み付けなど、細かなパラメータ調整や実験を繰り返せる。スコアがどんどん伸びてめっちゃ楽しい。

改善(パラメータ調整)

⇒92373655103 点(コード)。手詰まり感がすごい。

5 日目(2021/5/26)～ 6 日目(2021/5/27)

考えたこと

• 入力値として返ってくるのが自分の選んだ経路に対してかかったコストなら、最初のうちはどんどん寄り道してグラフの重みを尤もらしい値に早く塗り替えていく方が後々活きてくるんじゃないか？と思い至る
• 経路探索はこれまで全てダイクストラで最短経路選んでいたが、最初のうちは DFS+乱数でクネクネと道を選ばせてはどうか ⇒ 点数下がる
  ※後々考えてみると、一度も通ったことのない道を積極的に選ばせる、だと点数上がったかもしれません。あと、入力生成のルール上、曲がる回数が増えれば増えるほど計算した重みの正確性が落ちていくようですね。
• 下図は実験の記録。DFS で生成した経路眺めるの楽しいですよね！

改善(パラメータ調整)

• 3 日目に実装した「ループ初期段階でのグラフ全体の重み更新」の式のパラメータ微調整

⇒92821497168 点(コード)

7 日目(2021/5/28)

考えたこと

• 3 日目に実装して失敗した、過去の入力を使いまわして重み推定の精度を上げる方法はやっぱりうまくいくのではないか
• 100 ループ目までで初期のパラメータ推定やっているが、もっと早くできないか

改善(過去の入力を使った重み推定精度向上+パラメータ調整)

• 400/600/800 ループ目に突入した時点で、それまでに使用した経路と actual cost を用いてグラフの重みを調整するように変更
• 最初の 50 ループ目で重み更新式を切り替えるように、加えて 50/100 ループ終了時点で「ループ初期段階でのグラフ全体の重み更新」をかけるように変更
• その他細々としたパラメータ調整

⇒93382152783 点(コード)

8 日目(2021/5/29)

考えたこと

• やたらと点数の低い 0018.txt のテストケース(890 億点ぐらい)を眺めていると、右に一直線に進むべき経路で上下に激しくぶれながら進んでいたので、これはいかんと思いループの最初期段階では進める方向を更に厳しく制限しようと思い立つ
  ⇒ これ成功したんですが後で考えるとそれはそうで、入力生成方法がそもそもグリッドの各行、各列で重みが近い値になるようにできてたんですね…

改善(初期段階で進める方向制限+パラメータ調整)

• 最初の 50 ループでスタート-ゴールの位置関係が上下左右まっすぐの時は絶対に一直線に進むように変更
• その他細々としたパラメータ調整

⇒93417969072 点(コード)。プレテスト段階では最高のスコアに。最終日は用事があったので、実質これで自分の AHC003 は終了しました。

最終結果

3000 ケースのシステスで、2804636391585 点、163 位でした。AHC002 が 379 位だったので大健闘だと思います。レートもぐんと伸びて 1133 に。緑コーダー(β)になれました。

ただ上位の方を見ていると、皆さん当たり前のように入力生成方法を理解した上で統計的に処理されているようでした。次回からは自分も数式の羅列だからと毛嫌いせずに、ガンガン読み込んで少しでもヒントを掴んでいきたいと思います。

まとめ

AHC003 の記事の冒頭では自分が低順位の時にも AHC が楽しいと言えるか要検証という話をしていましたが、今回中盤以降は基本的に順位を落とすだけという状況に直面して、やっぱり正直しんどかったですねー。ただそれでもなお AHC の良さとして心に残ったのは、取れる選択肢が多くて何かしら試せる余地があるところです。ABC/ARC/AGC だと計算量の削減がメインタスクで、それを実現するアルゴリズムを実装できるかという比較的限定的なテーマに関する戦いになるかと思うのですが、ヒューリスティックコンでは高速化して乱数シミュレーションの回数を挙げるのも一つの手だし、評価関数いじってもいいし、そもそものアルゴリズムを見直すこともできたりとスコアの向上に結び付けられる変更が多いです。

以上です。