ICFPC 2018 参加記 - wataの日記

今年もチームUnagiのいつものメンバーで参加。今年の問題は最大４０体のロボットを並列に操作して指定された３Dオブジェクトを出来るだけ効率よく構築・破壊するというタスクだった。各ロボットにどう仕事を割り振るかやお互い干渉しないようにどう動かすかなど、見た目以上に難しくてかなりの良問だった。暫定１位なので勝ててると良いなあ。

https://icfpcontest2018.github.io/full/live-standings.html

役割分担

wata & chokudai : 構築ソルバ
iwi & tos : 破壊ソルバ + 便利ライブラリ
imos & sulume : インフラ + ローカルシミュレータ

例年、役割分担や解法の議論とかのチームプレイはかなり良い感じなのだが、皆バラバラの言語を使うため、同じ機能を複数言語で実装したり、特に仕様追加がある問題の場合はすべての言語で仕様追加が必要だったりで、非常に無駄が多いのが問題点だと感じていた。そこで今年はRustで統一しようという話になっていた…はずだった…が始まったら皆バラバラの言語で書き始めて暗雲が立ち込めた。が、思ったより実装が色々重い（まともな点数を取るソルバを一から書くのがかなり大変）ということで結局最終的にはRustにそれなりに収束して色々なルーチンが色々なソルバで再利用されて過去最高効率だった。例えば最終的な破壊ソルバは高速初期配置(by tos) → 3Dダイクストラ(by iwi)を内部で使う支柱破壊(by wata)を逆再生した支柱建築(by iwi) → 平面GVoid (by iwi) → 高速集合(by tos) といった感じで色々なパーツを組み合わせることで出来上がっており、言語統一の力を感じた。来年さらに統一が進めば最強になるのではないだろうか。他のチームもRustを使ったところがそこそこ居たみたいだしRustの時代来てますね。とてもオススメですよ！以下ソルバ班の流れ。

１日目

事前情報でLive Standingsがあって最終提出のみが最終順位に反映されるとあったので、2014年みたいな独自のマシン語仕様が与えられてその上で動くAI作るタイプかなあと勝手に想像していたが完全に違った。優勝した2013年や2016年に近い形の、コンテスト時間中にどんどん問題を解いていくという、一番得意な形式だったのでやる気が出た。

スコアの計算式的にHarmonics(ブロックを宙に浮かせる操作)は常時オフ以外お話にならないので存在を忘れることにし、宙に浮かせることなくオブジェクトを構築する方法を考える…が分からない…とりあえず適当な方法で構築して詰んだら諦めるソルバを作り、解けなかった問題については個別に対策を考えようということになった。

効率を考えると各ロボットが3×3の四角柱を縦に一気に構築するのが良さそう（移動一回あたり9マス埋めれる）ということになり、すでに作ったところからGroundedを保つように上 or 下に四角柱を構築していくソルバを書くことにした。障害物を避けながら目的地に到達するルーチン（競プロ力を発揮し、位置→ターン数で幅優先する代わりに、位置×方向→(ターン数,そのターン中にまだ進める歩数)でダイクストラをすると、辺の数が減って高速化出来る）や、初期配置・集合ルーチンなど、色々なソルバで必要になるであろうパーツが多すぎて大変だったので、iwi & tos によりRustでライブラリ実装が行われた。ここで言語が発散しなくて本当に良かった。

結局3×3の方針は、小さい問題はロボットが余って暇をする＆大きい問題は遅すぎて実行が終わらない＆結構詰む、でうまく行かなかった。chokudaiは全体をy座標が同じ層に良い感じに分割・順番付けしてGroundedを保つように上に行ったり下に行ったりしながら構築するソルバを実装したが、こちらもLightning終了までには全問解き切ることは出来ず、Lightningは提出なしで終了した。

二日目

仕様追加で破壊問題・再構築問題が追加され、更に矩形領域の一括構築・破壊操作(GFill,GVoid)が出来るようになった。3×3で埋めるよりGFillしたほうが明らかに効率が良いので、作りかけのLightning用ソルバを破棄。３種類の問題をどう解くのが良いかの議論になり、chokudaiソルバが詰む予定のケースがあるらしいので再構築ソルバを作れば詰んだケースの救出も出来るのではと思ったが、chokudai方針の層構築に比べて３D構築は実装が非常に難しい＆結局chokudaiソルバが全問解けそうという感じになったので破壊ソルバを作って一旦更地にしてから構築ソルバで再構築するという方針に決まった。破壊ソルバは、Groundedを保つように少しずつ壊すより、Harmonicsを思い出してGVoidで一層ずつ一気に消した方が簡単だしスコアも良さそうということになり、iwi & tos が担当することになった。

構築ソルバの方は破壊操作が加わったことにより、支柱を同時に構築することでGroundedを保つ戦略が取れるようになった。こうすると下から順に一層ずつ構築していくことが出来、最後の支柱破壊以外は障害物なしの二次元問題になるので非常に楽。下からの構築以外に真ん中からx軸方向 or z軸方向に半分に分けて横方向に一層ずつ構築というのも同じ方針で出来るので実装した。構築する向きによって必要な支柱の数が違うし、y方向ではなくx or z方向だと半分に分けて二層同時に構築するので一層あたりのロボット数が半分になり、暇になることの多い小さい問題での効率が上がった。

三日目

ようやく全ての構築問題に対して解答が出来た。スタート地点遠すぎだった。次に層構築で2D・1DのGFillを使う最適化を行った。作りたい層を良い感じにGFill可能な矩形領域のジョブに最初に完全に分割しておいて、その分割に従ってロボットを矩形の頂点に移動させてGFillしていくことにした。ロボットへのジョブの割当は一番近いところに貪欲に割り当てることにし、デッドロックしないように、既に他のロボットに割り振られたジョブをより近いロボットが暇になったら奪い取るという実装にした。Groundedを保つ順で構築しないといけないという依存関係がジョブにあり、支柱周辺のように依存関係の根本付近が細い場合に大量のロボットが暇になってしまうので、ジョブにロボットを割り当てたら完了を待たずに依存先のジョブにも先回りでロボットを割り当てたり、同じターンに同時に依存先までGFillしたりする最適化をした。

破壊ソルバの方はHarmonicsを必要な時だけオンにする最適化が入った段階で、ローカルシミュレータは通るけど公式シミュレータだと落ちることが発覚。公式とのシミュレーション結果に差がある問題を確認するために一旦提出した（潜伏していたわけではない）。破壊ソルバ・ローカルシミュレータ両者のバグは取れたけど、一問でも落とした瞬間敗北確実なスコア計算式なので念の為公式シミュレータを使って最終確認する機能をimosが実装した（ブラウザでページを開いておくと公式シミュレータが繰り返し走って結果をサーバーに送るのでマイニングと呼ばれた）。問題によっては単純な上からの面破壊だとHarmonicsが長時間必要になるため、構築ソルバの支柱破壊ルーチンを逆再生することで支柱建築をし、そのあとで破壊するという最適化が行われた。

最後に、30×30×30以下の小さい問題で結構負けていたのを、tos & chokudai が手動で解いたり、ソルバのパラメータを変えて実行したりして、最終的にほぼ全ての問題で凍結時点でのスコア基準で満点 or 満点-1のスコアが出た。

最終提出物を作る段階になって、最新版の破壊ソルバを使うと再構築問題が大量に死ぬことが発覚した。実は再構築問題は破壊ソルバの解と構築ソルバの解を単純につなげるだけではダメで、破壊ソルバの終了時点で原点に集合した際のロボットIDが1以外になっていると、構築ソルバの初期状態が違うので順番を並び替えないとダメだった。支柱建築をしない版の破壊ソルバは規則正しく動く性質上、必ずID=1が残るように集合していたため、それまで気づかなかった。このバグは時間内に修正できなかったので再構築問題は支柱建築なしの破壊ソルバとの組み合わせで解答を提出した。