ICFPC 2018 に参加しました

ICFPC 2018 にチーム「銀閣寺GOLD」として参加しました。 メンバーは以下の４人です。

• cos
• nojima
• qwerty
• seikichi

また、チームのリポジトリは https://github.com/seikichi/icfpc2018 にあります。

問題

今年の問題は小さなロボットたちを操って3Dプリンタ的な作業を行うことです。

R×R×Rの三次元の空間があって、その中に "nanobot" というロボットが配置されています。 ロボットは各ターンに移動したり分裂したり voxel を埋めたりできます。 ロボットをうまく操って、与えられた3Dモデルをプロットしてください。 ただし毎ターン、エネルギーが消費されていきます。 消費されるエネルギーをできるだけ小さくしてください。

プロットしている間、プロット済みの voxel が宙に浮いた状態になってしまってはいけません。 しかし、エネルギーを大量に消費することで High Harmonics 状態 (voxel が宙に浮いてもよい状態) にすることができます。

0日目

去年の ICFPC のブログに「C++ は飽きたので来年は Rust で」って軽い気持ちで書いたら、本当に Rust を使うことになってしまいました。 Rust は The Book を読んで AtCoder の問題を何問か Rust で解いたことがある程度の経験しかありません。 チームのメンバーも大体同じようなレベルでした。 こんな状態で ICFPC ができるのかと結構不安でしたが、当たって砕けろみたいな気持ちで ICFPC に突入しました。

1日目

深夜１時に ICFPC スタート。 問題を読んで役割分担を決めました。 この時点で深夜２時か３時ぐらいだったので就寝。

11時に起床。cosくんとペアプロすることになりました。 まずはトレースファイル（ロボットのコマンド列を並べたバイナリファイル）を出力できるようにライブラリを作り始めました。

このときたぶん初めて Rust でユニットテストを書いたんですが、#[test] でテスト関数を書いて cargo test するだけでテストが動くのに感動しました。 C++ の時代はまず gtest を用意して心のこもった Makefile を書かないとテストできませんでした。

トレースファイルのエンコーダーを作った後はコマンド群の挙動をシミュレートするシミュレータを作ってました。 シミュレータはコマンドを実行して状態を更新したり各ロボットの動きが不正じゃないかをチェックしたりするプログラムです。

シミュレータがチェックすべきものの中に「各 voxel が grounded かどうか」というものがあります。 毎ターンすべての voxel を舐めて grounded かどうかを調べていると滅茶苦茶遅そうなので、grounded 判定は UnionFind で連結成分を管理しておく方針でやることにしました。

「これ、２日目に Full な voxel を Void にできるコマンドが追加されたりしたら崩壊するよね…？」
「ははは、まさかね…」

一方、seikichi-qwerty 班がロボットをグリッド状に分裂させて、それぞれで並列にモデルを構築していく AI を作っていました。 ライトニングにはこれを提出。

↓ GridFissionAI の様子（ライトニング用じゃなくて Full 用なので並列度が違うけど動作はほぼ同じ）

2日目

Void, GFill, GVoid コマンドが追加されました。 Void は full だった voxel を void にできるコマンドです。 見事にフラグが回収されて絶望が深い。

また、これまではモデルを構築する問題だけでしたが、構築済みのモデルを完全に削除する disassemble 問題と、構築済みのモデルから別のモデルを構築する reassemble 問題が追加されました。

とりあえず、reassemble 問題は disassemble 問題と assemble 問題をそれぞれ解いてくっつけると解けるので、まずはその方針を実装することに。

また、ライトニングに提出した AI は Harmonics が常に High の状態だったので、まずは Harmonics が Low で十分な問題は Low で解けるようにしようということで、

1. Harmonics を Low のままにして問題を解いていく
2. シミュレータで voxel が宙に浮いているか調べる
3. 宙に浮いていたら Harmonics を High にする
4. プロットしていって再び grounded になったら Harmonics を Low にする

というロジックを入れました（AI班が）。

自分は追加されたコマンドをシミュレータに実装し、崩壊した grounded の判定をナイーブなアルゴリズムで直したりしてました。 しかし、ナイーブな grounded 判定アルゴリズムは遅すぎて大きいサイズの問題が全然終わらないことが判明。 仕方がないので、Void、GVoid が来ない限りは UnionFind で効率的に判定、Void、GVoid が来たら全部再計算という方針にしつつ、典型的な Void では再計算を避けるために以下のヒューリスティックを実装しました。

Void の対象の voxel について、以下が成り立つとき、再計算は不要。

• その真上が void かつ、
• その真下が full かつ、
• その周囲4つの voxel すべてについて「それが void または その真下が full」

3日目

qwerty さんが二次元 GVoid を使ってモデルを disassemble する AI を作ってました。

また、cos くんが grounded である状態を保つように BFS で良い経路で voxel を埋めていく AI を作ってました。 ロボット同士がぶつからないように移動させるのがすごく大変だったようです。

また、seikichi くんが grounded を維持しやすいように支柱を立てつつ GridFissionAI っぽいことをし、最後に支柱を消す AI を作ってました。 動きが楽しい。

自分は GFill を使って assemble していく AI を作ろうとしました。 今回自分はずっとシミュレータをやっていたので、３日目で初めて AI に取り掛かったのですが、予想以上に難しい。 AI を分裂させたり、お互いにぶつからないように移動させたりといった、ぱっと見そんなに難しそうに見えない作業が普通に大変で、かなり手間取りました。 結局、コンテストの時間内に GFill AI を完成させることはできませんでした。

そしていよいよラスト１時間。 AWS で 72 コアマシンを借りて並列で AI をぶん回します。 複数個の AI があるので、すべての AI で各問題を解いて、最もエネルギー消費量が少ない解を提出するようにします。

流石に１時間もあれば余裕で提出できるだろうと思っていましたが、AI の計算が意外と終わらなかったり、途中で VM がディスクフルになって計算をやり直すはめになったりして、結局 zip を提出できたのは終了３分前でした。 めっちゃハラハラした……。

所感

• Keep

  • Rust は最高でした。
    lifetimeとかでハマるかと思ってたけどそんなことはなく、むしろコンパイラのメッセージが超親切だし cargo が便利だし、実行速度・コンパイル速度共に申し分ありませんでした。 また、４人のメンバーの環境が Windows, WSL, Linux, Mac と見事にバラバラであったにもかかわらず、全くそれを意識することなく開発できました。

  • カンバンは便利でした。
    今年初めて GitHub の project 機能を使ってみました。 毎年三日目ぐらいになると、何をやっていいのかわからない、他の人が何をやっているのかわからない、という状況になっていましたが、今年は状況が把握しやすかったです。

• Problem & Try

  • AI とシミュレータのインテグレーションがあまり上手くいきませんでした。 本来であれば、シミュレータが実装した関数を AI の実装に再利用できるべきですが、シミュレータのインターフェイスが微妙で AI とシミュレータの間で実装がかなり重複してしまいました。 重複を減らせれば AI をもっといっぱい書けたのではないかと思います。

    もうちょっと早くインテグレーションが上手くできないことに気付いていれば何とか対応できたと思うので、次からは1日目の後半ぐらいには AI とシミュレータをくっつけてみるべきだと感じました。

  • 三日目で、GFill AI に5～6時間ぐらい費やしましたが結局完成しませんでした。もうちょっと早く見限って提出準備の自動化など、インフラ的な作業をやっておくべきでした。

結果

9位だったようです。 初めてのトップ10入りです。嬉しい！