ICFPC 2021 に参加しました

ICFPC 2021 にチーム「グレースたなか」として参加しました。 メンバーは cos, nojima, qwerty, seikichi の4人です。また、チームのリポジトリhttps://github.com/seikichi/icfpc2021 にあります。

問題

今年の問題はポーズをうまく変形して穴をくぐるというものです。穴をくぐることができれば成功で、ポーズの良さに応じた点数を獲得できます。穴の各頂点にポーズの頂点が近いほどそのポーズは良いとされています。以下の gif を見るとイメージしやすいでしょう。

f:id:nojima718:20210717203759g:plain

ポーズは好きなように変形できるわけではありません。辺の長さが大きく変わるような変形は禁止されています。どれぐらいなら辺の長さが変わってよいかは問題ごとに定められています。また、頂点の座標は整数でなければなりません。

問題の一覧は公式サイトにあります。

1日目

今年の ICFPC は金曜日の午後9時から始まりました。いつもどおり、自分と cos さんとでペアプロして入力を読むところから実装を開始します。ソルバーの実装には今年も Rust を使いました。Rust を使う機会が ICFPC しかないので、一年ぶりの Rust となります。

まずはヘボくてもいいので動くものを、ということで、ポーズ全体を平行移動・90度回転・鏡像反転するソルバーを作りました。これらは候補数が少ないので単純に全探索できます。

また、seikichi さんが整数計画ソルバーを使って厳密解を求める AI を作っていました。12番16番のように頂点数の少ない問題に対しては一瞬で厳密解が出るようです。

ここらで深夜3時近くになってきたので寝ます。

9時ぐらいに起床しました。

1日目終了時点でライトニングラウンドがあるので、とりあえず悪い解でもいいから全部の問題に対して何かしらの解を用意しないといけません。そこで、適当に valid な解を見つけてくる DFS ソルバーを作りました。これは穴の中の点を一つ選んで、ポーズの頂点をそこに置くという操作を繰り返すだけのナイーブなソルバーです。

1番の問題をソルバーで解かせてみたら遅すぎて解が出ませんでした。そこで、重要そうな頂点から先に置くというヒューリスティックを入れたら解が出てくるようになりました。各頂点の重要度は (すでに確定している頂点だけを考慮したときの次数, すべての頂点を考慮したときの次数) で定めました。

このソルバーの出力する解は、ぐちゃぐちゃに折りたたまれた糸くずの塊みたいな形になっていて、どう見てもスコア的には酷いものでしたが、とりあえず解が出たのでヨシ!

seikichi, qwerty ペアは問題と解を一覧で見れるサイトを作っていました。公式サイトは問題ごとにページ遷移しないといけないので、すべての情報を1ページにまとめたサイトを作っておくと検討効率が大幅に上がります。CDK と Amplify が便利とのこと。

DFSソルバーがそれなりに動いているので、出てきた解を改善すべく山登り法ソルバーを追加。これは初期解を受け取って「頂点をランダムに動かしてスコアが改善するならそれを採用する」という手順を繰り返すソルバーです。

山登り法が動いたので次はアニーリング法を試しました。山登り法よりもアニーリング法の方がスコアが改善することがわかったので以降はアニーリングソルバーをメインで使っていくことに。

そのあとは適当にソルバーを高速化したり、アニーリングの途中で参照するスコアに頂点の分散を加味するように修正したりしていました。

ソルバー班と並列してインフラ班が解を提出するスクリプトを書いてくれていたので、それを使ってライトニング用の解を提出し、一日目は終了しました。

2日目

問題に「ボーナス」という仕様が追加されました。問題で指定された場所にポーズの頂点を配置すると特定の効果を持つボーナスを取得でき、他の問題でそれを使用できるというものです。とはいえ、今の自分たちのソルバーではボーナスを活用できそうにないので、当面はボーナスを無視して既存のソルバーの改善を続けることに。

そして2日目の朝。

アニーリング法ではなく、グラフのエッジをバネとみなして物理法則をシミュレートする方式で解を作ってみるとどうだろうかと思って物理ベースソルバーを作ってみました。しかし、壁に埋まったバネがすごい勢いで遠くにぶっ飛んでいく現象(ゲームでまれによく見るやつ)が多発してまともに動きませんでした。

一方、cos さんはポーズの頂点を(制約を満たさない位置に)移動させ、そのあと制約を満たすように周囲の頂点の座標を調整するようなルーチンを作っていました。このルーチンを使って初期ポーズを shrink して穴にはめ込むソルバーが作られ、(DFS ソルバーだと解が求まらないような) 頂点数が多い問題に対して解を出力することができるようになりました。

別の DFS も試してみたいということで、頂点ではなく辺を置いていく DFS ソルバーを作りました。与えられたグラフを橋で分解すると複数個の2-連結グラフになります。2-連結なグラフは耳分解ができるので、耳を順番に置いていく感じで DFS をします。これにより、それぞれの耳がどの頂点に戻ってくるかが事前にわかるので、絶対に戻ってこれないような座標に頂点を置かないように枝刈りすることができます。また、直前に置いた辺と同じ方向に優先して置くことで、潰れた解を避けやすくできます。

seikichi さんは整数計画ソルバーの改善をやっていました。何をやっていたのかは把握していません。すまぬ…。

あとはアニーリングソルバーのベンチマークをとって高速化をするなどしてました。cargo flamegraph で簡単にこんなグラフが出てくるので便利。

f:id:nojima718:20210719011229p:plain
アニーリングソルバーの flamegraph

また、seikichi・qwerty ペアは AWS で Lambda でソルバーを並列実行して、結果を DynamoDB に保存する仕組みを作っていました。パラメータごとの結果を WebUI から確認できるのでソルバーの改善に役立つ優れものです。

f:id:nojima718:20210724172403j:plain
WebUI はこんな感じで、問題と解とパラメーターとスコアなどが確認できます

3日目

DFS をビームサーチに変えてみたり chokudai サーチにしてみたりしましたが、単純な DFS より良くはなりませんでした。

seikichi さんが整数計画ソルバーを改善しているのを横目にこの日は寝ました。

そして3日目の朝。

cos さんがアニーリングソルバーに頂点を穴の外周に向かって引っ張るようなムーブを追加しました。このヒューリスティックがかなり効いて多くの問題のスコアが伸びました。

最終日ということもあり、ソルバーを走らせる時間も Lambda の実行時間の限界である15分近くに設定するようになりました。実行時間を伸ばすことでアニーリングソルバーの解が露骨に改善されましたAWS への課金が捗りますね。これが金の弾丸…!

AWS のコンソールを見ると並列で実行されている雰囲気がわかります (これはアニーリング10分で実行したときのやつです。たぶん)。

f:id:nojima718:20210719010854p:plain
Lambda で 700 並列でソルバーを動かす

夕方からはアニーリングの最適な初期温度を調べていました。大幅にスコアが上がったりはしませんでしたが、無視できないぐらいにはスコアが改善されました。

最後に、すべての問題を最新のソルバーで解きなおしたり、スコアの上がり幅が大きそうな問題に対して乱数ガチャ(乱数シードを変えながらアニーリングを連打する)をしたりして、提出する解をつくりました。

順位は 20 位でした。お疲れ様でした。

完走した感想ですが

  • やっぱり Rust は安定して便利
    • rust-analyzer や cargo がよくできている
    • ライブラリも完成度が高いものが多い
    • (今回は使わなかったけど) いざとなったら WASM にコンパイルできるという安心感がある
  • 金の力は偉大
    • 素朴なアルゴリズムでも計算機をブン回せば良い解が出たり
      • しかし、手元で走らせたときと結果が違いすぎてチューニングが難しかった
    • Lambda のおかげで現実的な料金で 1000 並列とかできる
  • 理不尽さが足りない
    • もっと理不尽なコンテストのほうが競プロガチ勢との差が縮まってよかったのに…