estieプログラミングコンテスト2022(AHC014)日記編

「estieプログラミングコンテスト2022(AHC014)」の参加記が長くなったので日々の考察、取り組みは日記編として別記事化しました。

本記事では時間軸に沿って振り返りつつ今回の参加では

optunaを使った最適化
Plotlyによる結果の可視化
ccacheによる再コンパイルの高速化
AWSの64-96コア環境使った並列実行

にチャレンジして最後のAWS以外は出来たのでその話も含めています。

試したけどうまく行かなかったアイディアは日記編でも触れますが、参加後のTweetや解説動画を見てどうすればよかった？は参加記側に書いたのでそちらを参照ください。

また、参加時のメモから作成しており文体が揺らいでいる点は予めご了承ください。

コンテスト開始前

9/12-14(1週間前～)

AHC013の上位陣と自分より少し上位だった人の参加記を読む。今回の目標は

優先度: 高

Terryさんの参加記を参考にOptunaを使った最適化
前回、TLEを出した反省から時間管理をちゃんとする
ccacheの導入によるコンパイル高速化

優先度: 中

yunixさんの参加記を参考にPlotlyによる可視化を試す
AWSかGoogle cloud runを使ってテストケース実行の短時間化

にチャレンジしよう。

9/16(1日前)

夜に前夜祭に参加してついに明日からかーという気分に。

前夜祭で紹介された「ヒューリスティック問題を解く」をざっと眺める。
こんなにまとまっていたとは知らなかった。お世話になることになりそう。

9/17 AM(当日AM)

DockerにOptunaを入れてサンプルを動かすところまで確認。今まで手でチューニングしてたけど結構よさそうな感じ。

コンテスト中

9/17 PM

スコア分布を確認。

中心からの距離の二乗に比例して大きくなるので出来るだけ隅に点をたくさん持ってこれるかが重要。

ルールを確認して、考えをメモ。

45°回転した座標系も持った方が良いか
生成できる長方形の列挙を高速に行う必要がある。データ構造をちゃんと考える
操作回数に上限がないのでうまく探索できるかが勝負
ちょっと分からないのが
- 長方形を作れる候補がどれくらいあるか
- 1つ長方形を選ぶことでどれくらい候補が減るのか
長方形間に依存関係がある
基本は近くの点と組み合わせて広げていくので局所的な探索でよさそう

あと生成可能な長方形一覧などが欲しくなるので、自前のVisualizerが必要そう。

9/18(2日目)

この日は友人と六甲山へ。

山登り法#六甲山 pic.twitter.com/kHjtaeag8Z

— starpentagon (@stat_learning) September 18, 2022

9月上旬に体調を崩してしまったのですが、大分と復調してきてリフレッシュ。

移動中につらつら考えたのは

遠くまで伸ばすには長方形の組合せの妙を見つけないといけない
- Bandit法である程度幅広で見つつ徐々に伸びそうな手を重点的に試す
DFSで伸ばすと先に延ばした長方形が邪魔になる？
- BFS的に徐々に伸ばしていった方がよい？
- BFS的に全体的を広げつつ途中からはDFSで伸ばせるだけ伸ばすのがよい？
最後は「速いことは正義」になりそう

9/19(3日目)

今回は公式のジェネレータからテストセット作成。80, 2000, 10000問の3つ。80問はクイック評価用、2000問がシステス相当で基本この評価で判断、10000問はストレステストでバグ探し用。

ccacheを入れた。使い方はg++としてるのをccache g++とするだけ。キャッシュが効くので再コンパイルが爆速。

この日は長方形生成の設計。必要な情報を整理してデータ構造とロジックを考えた。

各点で

点フラグ
8方向ごとの
- 辺フラグ
- 直近点の座標

を持てば長方形あたりO(1)で生成できる。

さらにN <= 61なので「1つの点が持つ情報」や「盤面1列にある点の配置」などが64bit変数に乗る。これ最後64bit化で高速化出来るやつやな…と思いつつ、最初はナイーブに情報を持って実装。後々64bit化でデータ構造を変えることを見越してtemplate化して実装。当たり前だけどテンプレートクラスは型が抽象化されてエディタの補完やチェックがあまり効かないのが不便。 45°回転させた座標系もデータとして持ったが今見ている座標がどちらの座標系なのかがややこしい。

9/20(4日目)

基本となる長方形生成ロジックを実装。座標系が2つあってややこしい。素直に座標系は1つにして方向を8つ持つ方が良かったか…と後悔し始める。

ちゃんとロジック設計して実装したつもりがルール違反の長方形がボコボコ生成される。愚直に長方形を生成するVerifyロジックも書いて結果が一致するかチェック。

これで差分がでたら
・差分が生じた盤面と生成した長方形を取得
・テストケースとして単体テストに追加
・Visualizerを見ながらバグを特定、修正して単体テストを通す

を繰り返して着実にデバッグ。

日付が変わる頃に10,000問が完走したので提出して29.2M。感覚的に50Mくらいを目指したい。トップはすでに68.5Mまで行ってて最終的に80-90Mくらいまで行きそう。

9/21(5日目)

今日は出社。行きの電車ではこれからやりたいことをつらつらとメモに書き出し。
帰りの電車でhamamuさんが4日目で初サブミットで順調とツイートしてて思わず共感。

昨日書いた乱択アルゴリズムを改良しようかと思ったが、そもそも長方形生成ロジック用でその目的は達成したので深追いは止めよう。出社で疲れたので夜は無理せず就寝。

9/22(6日目)

前半が終わりつつあるので今後の流れを整理。

まず

乱択DFS
貪欲法

を試して、「データ構造と基本的な処理の改良(差分生成やUndo処理)」をして「探索の高度化」「データ構造の改良による高速化」をそれぞれ2日くらいやると時間を使い切ることになりそう。

正直まだこうすれば良さそうというアプローチが良く分からない。

この日は夜にDFSを実装。あとはUndo処理を書いたがVerifyと合わない。座標系の変換ミスや処理の抜けもれ、処理順の考慮漏れがあって直すのに1時間くらいかかった。

無事、DFSが動くようになって上限10Kノードで実行。平均601Kくらい。

結果の可視化でNを横軸に取るとスコアがギザギザする。

身に覚えのないバグか？と疑ったが点の初期配置の範囲が+4ごとに大きくなるのが原因で問題はなかった。

9/23(7日目)

今回から問題ごとに今までで一番良い結果をChampionとして記録するようにした。

モチベーションアップとロジックの得手不得手があれば使い分けるのに使いたい。

DFSはできた気になっていたがなんと最大スコアの更新を忘れていた！（常に最後の探索状態を返していた…）テストセットを実行し直し。乱択と貪欲だと貪欲の方がよくそれをSubmitして33.9M。

Profileを取るとやはり長方形列挙に時間がかかっている。差分生成が必要か…。実装大変そうなんだよな。

順位表を見るとRafbillさんが飛びぬけてて72.7Mまで行っている。ここから中央、辺、隅にどれくらい置かないといけないかを調査。中央～辺をみっちり置ければトップ層には近づけそうな感じ。

肝は辺に伸ばすパスを見つけるか…で確率モデルよりはロジックで詰めた方がスコアは伸びそう。依存する長方形設置が競合するかを条件化したいところ。

まずは一度、IDDFで全探索して手数は短くてもどれくらい辺、隅に伸ばせるかを確認しよう。IDDF, Hash table, 置換表を実装。深さは4～5くらいが限界か。探索ノードを500M上限にしたのを投げて今日は終了。

9/24(8日目)

探索ノード500Mでも深さ4くらいが限界。

着手可能な長方形を可視化すると序盤は候補手が100手くらいあって全探索するとあっという間に爆発する。

今回、初めて可視化にPlotlyを使った。静止画だとpyplotと似たような感じだが動的なコンテンツやアニメーションも作れるので探索の可視化にもトライしたい。

昼から狙った場所に配置するロジックを考えたけど計算量的に全然ダメなことに気づいて断念。んーー生半可なアイディアだと全然うまく行きそうにない。

お風呂に入りながら考えていたら探索の特性は囲碁に似てて

可能な着手が非常に多く枝狩りしないと探索空間が爆発する
枝狩りをしようにもある着手の良し悪しが分かるのは数十手先で評価が難しい

という構図になっている。難しさが分かったところで囲碁でうまく行ったMonteCarlo Tree Search(MCTS)が今回も有効かという気がしてくる。あまりコンペで見ないアルゴリズムなのでこれでうまく行ったらかっこいいな…とか変な欲も出てくる。

一度、お風呂から上がって涼みながら冷静に考えると焼きなましも無難なアプローチ。MCTSは5秒という実行制限時間と候補の多さを考えると探索、評価が中途半端に終わって大外しのリスクもあって焼きなましを優先することに。

スケジュール的に

焼きなまし: 9/25-26
MCTS: 9/27-28
リファクタリング、高速化: 9/29-30
チューニング: 10/1

で進められるのが理想。

9/25(9日目)

この日は家族とお出かけしたので夜から開始。

焼きなましの遷移を考える。パッと思いつくのは

n手(局面更新せず)独立な長方形を選び進める
n手戻す
長方形を削除する

の3つ。とりあえずn=1を実装。AHC011のコードを使ってサクッと実装。

スコアは平均745Kに改善！ここ数日、検討して進展はあったけどスコアの改善はなくちょっとしんどい状況が続いたので素直にうれしい。

記念にSubmitで37.6M(平均スコア751K)まで行った。
次の目標は40Mで近傍追加、パラメタチューニングくらいで届きそう。

ここで一度、プロファイラでボトルネックを確認して高速化。15%くらい速くなった。

焼きなましの近傍でn=2, 3も実装。独立な長方形を選ぶのも四角形の交差判定が十分条件として使えるので実装したらサクッと動いた。今日は順調。

Optunaで焼きなましの温度チューニング。これまたサクッと動いた。今日は本当に怖いくらい順調。寝る前にチューニングをセットして終了。

9/26(10日目)

80サンプルのチューニングで平均820Kまで行った。

遷移確率も長方形の追加55%、削除45%、戻すのはほぼ0%くらいになっいてて納得感がある。戻す処理は削ってよさそう。

Optunaも初めて使った。パラメタ範囲と評価関数を与えるといい感じに探索してくれる。感覚的には手作業チューニングだと2-3回かかる作業を1発でやってくれる。

会社に行く前に再度、チューニング範囲を変えて投げる。

会社から帰ってみると平均838Kまで伸びている。これをsubmitして41.9Mで当座の40Mはクリア。

今は焼きなまし回数が10Kで平均700msくらい。時間制限5sにすると926Kまで伸びるので45Mもクリアしたようなもの。50Mが次の目標。

ちょっと安心してきてリファクタリングすることに。回転座標系も持っていたが削除。なんとこれだけで30%速くなった。

9/27(11日目)

リファクタリングの一貫で2次元配列を1次元化して固定配列にした。これで5%高速化。あとは64bit化だけどちょっとバグが怖いので今回は見送り。

Championのスコア上位のものを眺めて探索方針を検討。うまくいっているものは「密な集団」を作れている。

たしかに印が2列が並んだ状態（「良い」配置）を作れるとそこからダイヤ形状に広げていくことができる。

今まで隅にまで広げていくことを考えていたが

初期領域の端付近で2列揃えられれば辺へ集団を伸ばしていける
辺の領域に密に配置な集団を1-2個配置できれば60Mくらいまで行く

のでそこを目指した方が現実的だと思い始めた。

9/28(12日目)

考えれば考えるほど初期配置できる領域の端に「良い」配置を作って伸ばすのがトップ層との差を埋めるキーアイディアな気がする。仮に4辺すべてで出来ればほぼトップと同じスコアになる。

横に連鎖的に並べる条件は昨日はボヤっとしていたが今日、紙に書きながら考えたら

横に伸ばす方法
伸ばせるための条件

を求めることができた。これはかなり大きな進歩。伸ばせる形が分かっているので伸ばせる形に配置する問題に帰着される。

焼きなましの評価スコアをそれに基づいた形にすれば良くうまく行けば

伸ばせる配置を探す
ルールベースで伸ばす

で辺の方向には展開出来るはず。

と言うは易く行うは難しで結構実装が大変。これを焼きなまし法に組み込んでみる。

9/29(13日目)

残り時間も少なくなってきた。

焼きなまし法は探索スコアとして「良い条件」を満たしているかを評価関数化して実装したがうまく動いていない。

そもそも出力解がおかしな解になっている？Verifyが通らない。が、実はVerify用のコードが間違っていたり、デバッグ用に一時的に入れたコードが間違っていたりとちょっと疲れが出ているのか品質が下がってきている。

変な挙動をしなくなるように直すのが精一杯で、ちょっと休憩。

夜にリフレッシュな頭で書き直してプログラム自体は良くなってきたが、「良い条件」を満たした集団を焼きなまし法で作るのはどうも難しそう…という感触になってきた。

9/30(14日目)

焼きなまし法の評価関数が複雑になってしまって挙動が追いきれないのでシンプルなものに戻して自作のVisualizerで確認。

やはり「良い」配置を作る方針は良くて、うまく誘導するように評価関数を作りたいけどあちらを立てるとこちらが立たず、こちらを立てると意図しない状態を重視し始める…といったことが続く。

ここ3日ほど捧げたけどスコア向上がなく辛くなってきたので別の改良案へ。

ルール上、「辺をはる」⇒「点を打つ」はいいが、逆はできない。ただ、手順を入れ替えることができればOKなのでそれを認めてあげた方が探索の自由度が上がる。

評価スコア最大化の焼きなまし法ですぐに効果があるかは微妙だが良い配置を探す際には効くはずなので一度実装してみることに。

アイディアは長方形の先行関係を有向グラフで表現してトポロジカルソートするだけ…なのだが、なかなかバグが取れない。理由は3つあって

「先行関係」を抜けもれなくチェックできていなかった
高速化の過程で人間が理解しにくいデータ構造になっておりバグに気づけなかった
プログラムが大きくなりある変更が想定外の場所で影響を出すことが増えた

でそれぞれちゃんとやろうよとしか言いようがないが、システムテスト後は本質的にはお役御免なプログラムでどうするかは悩ましい。

日付が変わってもまだバグが取れないしここ1週間近くまったく本質的な改善をしていない。焦燥感というか諦めに近い感情を感じながら明日もあるので就寝。

10/1(15日目)

ついに最終日。起きてから落ち着いてデバッグしたら原因が分かった。やはりスッキリした頭で考えないとダメ。

他にも盤外になるケースの境界値でバグがあり修正。今までよくすり抜けていたな…

手順修正のロジックは閉路を検出してノードを削除して必ず展開できるようにした。これまたデバッグに苦労して昼過ぎにようやくちゃんと動いた。良かった…

最後、うっすら懸念していたのが実は性能向上につながらないことでドキドキしながらテストを回したらなんと

計算時間が5-6割増しくらいになってスコアはほぼ同等

で向上にはつながらず…。うぅぅ…マジか。これは正直辛い。

確率的に実行する、ハイパーパラメタチューニングの時に実行する／しないも試すなど未練がましく最後まで粘ったけどこのロジックを使うとスコアが1割以上下がる。泣く泣く最終提出からは外すことに。

もうここから何か新しいことをするのは無理で複数回実行と時間いっぱい回すロジックを書いた。あとは探索関係のパラメタをチューニング。平均926Kだったのが950Kくらいまで伸びた。

最後、不要なコードを削除してコードを見直すとちょこちょこバグを発見。修正したコードを最後18時過ぎに提出して今回のAHCは終わりを迎えました。

コンテスト後

1週間、何も本質的な改善ができなかったので順位はあきらめてましたが暫定テストで88位と過去最高に近い位置。問題自体が難しく100位付近は高速化勝負になった？

Twitterを眺めたりwataさんの解説動画を見たりして過ごす。かけた時間が長い分、他の人のアイディア・考察とオーバーラップする部分が多く共感や気づきが多くて楽しい。

途中状態の良し悪しを評価するのは無理では？と思っていたけどwataさんの解説を見ると多くの点を作りながら伸ばすにはある種の条件が必要。言われてみるとなるほどなーという話。その考察に基づいたrandom playoutで50Mを越えるらしい。すごい。

日曜にシステスが終わり最終順位は84位で過去最高を更新！ただ、トップ層はやはり「良い」配置を作って伸ばし切っていたようで、自分も実装しきれてたら…という気持ちも正直あります。アイディア自体は良かったので次の機会は実装しきるのを目標に参加したいですね。

最後にスポンサーのestieさん、作問のwataさん、運営のAtCoderの皆さん、そしてTwitterで共有してもらった皆さんありがとうございました！