ICFP Content 2021にいつものメンバーで参加した。チーム名はここ最近使っているmanarimoにした。
- リポジトリ： https://github.com/manarimo/ICFPC2021/
- ポータルサイト： http://icfpc2021-manarimo.s3-website-us-east-1.amazonaws.com/best.html
- 手動ソルバー： http://icfpc2021-manarimo.s3-website-us-east-1.amazonaws.com/kenkoooo/#/problem/1
順位は終了前のスコアボード凍結時点で2位。とりあえず日本勢の中では1位になれたので嬉しい。全体1位も行けるかと思っていたけど、RGBTeamが強かった。他のチームもいい解を出し惜しみして潜伏しているかもしれないけど、少なくとも今は見えない点数に価値はないので……。
概要 & 方針
今年の問題は「脳カベ」というゲーム（自分は知らなかったけど、とんねるずの1コーナーらしい）を題材にしており、メッシュとして表現された人物を多角形の中に埋め込む問題だった。 メッシュの辺の長さをあまり変えないようにしながら頂点の座標を好きに選ぶことで多角形に埋め込む。ただし座標は整数である必要がある。そうして配置を決めたあと、多角形の各点について一番近い頂点との距離を計算し、その総和が小さいほどよい。
いかにも2016年の折り紙回を彷彿とさせる設定で、手作業で解くのが肝だと判断したので、とりあえず手で遊べるビジュアライザの構築を優先して、並列で焼きなましベースや特定のパターンに特化したプログラムも実装するという方針になった。 24時間が経過したところでルール追加の発表があり、各面ごとに特定の座標にメッシュの頂点を配置すると、他の特定の面で制限を緩和するアイテムが使えるようになるというシステムが導入された。たとえばメッシュの頂点を1点だけ多角形の外に配置したり、1辺だけ長さ制約を無視して伸び縮みさせられるようになったりする。これらも基本的には手作業で対応したが、アイテムを取ろうとするとその面では最適解を諦める必要があるケースも存在するため、アイテムを取るか取らないかは全体の最適性を考える必要がある。いかにも計画問題っぽい見た目をしているので、とりあえず各面についてアイテムを使う解と使わない解を用意して、依存している面でアイテムが取れているかどうかを考慮しつつ提出時に最適な組み合わせを計算するという方針にした（最終的には線形計画問題としてライブラリで殴った）。
最終的には以下のツール群が作られていた（だいたい時系列順）。
- bruteforce： 全ての頂点の配置を試し、有効かつ一番スコアの良かったものを出力する (@pepsin_amylase, @y3eadgbe)
- checker： 解の正当性を検査する (@osa_k, @pepsin_amylase)
- gen_web： 問題と解答を一覧するためのHTMLを生成する (@osa_k)
- ビジュアライザ： 手で頂点を動かして遊べるビジュアライザ (@kenkoooo & keita)
- 焼きなまし： 近傍としては点の1マス移動、辺の1マス移動、全体の1マス移動、次数1の点の点対称移動、次数2の点の鏡像移動、多角形の頂点上へのワープを使い、ペナルティとしてははみ出ている頂点の多角形までの距離、はみ出ている辺の個数、長さ制約を満たしていない辺の逸脱度合いを使っている (@kawatea, @y3eadgbe, @osa_k)
- 外周うめるやつ： ぴったり埋め込まれた状態から頂点をシャッフルしたような問題が複数あった（例: 64）ため、メッシュの辺の長さと多角形の辺の長さを比べて、連続して一致するような頂点列を出力する (@yuusti)
- manten： スコアボードから満点解の存在が分かっている問題に対して、メッシュの頂点と多角形の頂点の対応関係を全て試す (@pepsin_amylase)
- package_solutions： 生成した解答ファイルの中から一番点数が高いものを提出する。アイテムが追加された後は、どの面でアイテムを取得するのがいいかを線形計画問題として解くようになった (@pepsin_amylase)
- globalist-optimize： GLOBALISTが使える問題に対して、山登り法を使ってコストを最適化する (@kenkoooo)
手動ではmkut, @y3eadgbe, @kawatea, @yuustiが中心になってひたすらパズルを解いていた。64や105のような問題を、自動ソルバの力を借りずに手だけで解いていくのは見ていてかなり面白かった。
自分のやったこと
自分は主にポータルサイトの管理、手作業での解答作成、焼きなましの最適化、焼きなましの並列実行を行った。
ポータルサイト
ポータルサイトは例年はWebアプリケーションを作っているのだが、毎年I/O絡みで何かしら問題が起きたり変なバグを埋め込んで嫌なタイミングで壊れたりするので、今年は静的HTML一本で済ませることにした。最初はGitHub Pagesでホストするつもりだったが、プライベートリポジトリでは課金しないと使えないことが分かったので、予定を変更してS3にアップロードすることにした。問題と解答ファイルは全てリポジトリにコミットするようにして、ページの生成とアップロードはpushでトリガーされるGitHub Actionsで行うようにした。
基本的には良い判断だったと思う。ポータルサイトと言っても毎年データを統計処理してきれいに出すことしかしていないので、わざわざサーバを用意して毎回計算させる意味は薄い。データ量が多くなってきたら統計処理済みのJSONをReactアプリからfetchしてくる構造にスイッチしようと思っていたが、そんなに量が増えなかったので最後まで静的HTMLのままで運用していた。また、提出用スクリプトや自動ソルバの入力として既存の解を使いたいときに、全部のデータがリポジトリの中に入っているのはかなり便利だった。
生成スクリプトは手癖でRubyで書いて、規模が大きくなってきたらRustやTypeScript等のちゃんと型がついている言語にしようと思っていたのだが、結局最後まで最初に書いたスクリプトを拡張し続けることになってしまった。erbすら使わずHTMLをコード内にベタ書きしているので、最後の方はかなり管理が大変だった……。
あと、何も考えずにGitHub Actionsの中で毎回HTMLを生成するようにしていたら、毎回タイムスタンプが更新されるせいで全部のファイルが毎回S3に送られるというかなり微妙な状態になってしまい、後半で実行が遅くなって困った。S3はrsyncではないので、ファイルのハッシュで更新判定はしてくれない……。--size-only というフラグを渡すことでファイルサイズが変更されたときだけアップロードするようにできるので、しばらくこれで対応していたのだが、ページ内の数値がちょっと変わったくらいだとファイルサイズが変わらないというケースが頻発するようになってしまったので、最後はまた全部アップロードしていた。生成物だけ管理するGitリポジトリを別に作っておくべきだったかもしれない。
解答作成
最初の方は面白そうな問題をビジュアライザで解いて、問題に対する感覚を養っていた。最適解が自明でない問題については焼きなましソルバが重要だということが分かってきたので、人間が途中までやった解を読み込む機能をリクエストしたり、焼きなましの初期温度や実行時間をパラメータ化してぶん回したりしていた。あとgprofの出力を眺めてボトルネックの解消をした。
焼きなましの並列実行は、EC2でc5.24xlargeを借りて、CPUの数だけバックグラウンドジョブとして焼きなましを実行するRubyスクリプトを走らせていた。タスクのサブミット等は特に管理せず、Rubyスクリプトでコマンドを構築して一括で走らせて待つ、という仕組みでやっていたが、これはジョブキューを使って管理したほうが良かった気がする。いつもはこういう道具が必要になったらJenkinsを立ててジョブキュー代わりにしているのだが、キューの中身の管理や出力ファイルの回収などで毎回何かしらの問題を踏むので、ポータルサイトで下したような判断も相まって今回は敬遠してしまっていた。
感想
今年の問題はかなり質が高くて楽しかった。ここ数年のコンテストから良い要素を集めてくることでうまくバランス調整されていると感じた。ベースは2016年の折り紙だけど、整数座標の制約を入れることでとっつきやすくなっていたり、2017年のPunterや2019年の掃除ロボットのようなアイテム要素が入っていたりと飽きさせない工夫が随所に感じられて良かった。公式ページで問題提出後に見られるアニメーションも面白い。
問題の難易度は適度に複雑で、アイテムもよく考えると便利だけど強すぎないという絶妙なバランスだと思う。最初の時点では2016年と同様に参加者が問題を作るフェーズが来ると予想していたけど、結果的にはそういう流れにならなかったことで、運営の考えたバランスの中にうまく収められていた。