ICFPC2018

ICFPC2018にチームmanarimoとして参加しました。マナリモとは何か一応説明しておくと、東北地方以北に分布するナリモ科の藻です。水質のきれいな湖にしか生息せず、「自然の水質管理官」と呼ばれることもあります。

メンバーは去年と同じく

  • mkut
  • osa_k
  • pepsin_amylase
  • y3eadgbe
  • yuusti
  • kawatea

の6人でした。僕はアメリカの自宅から、他の5人は日本のIndeedオフィスから参加しており、コンテスト中はHangoutでビデオチャットしてコミュニケーションを図っていました。

リポジトリ

github.com

1日目

開始と共に問題を読み始める。今年は問題文が整然としていて読みやすい。どうやら3Dプリンタ的なものを実装するゲームらしい。あと公式が必要そうなツールを一通り提供してくれていてありがたい。

問題文を一通り把握したので、インフラのセットアップを始める。とは言ってもJenkinsはコンテスト開始前にサーバを立てて入れてあったし、ポータルサイトもしばらく必要にはならなそうな上作ろうと思えばすぐ作れるので、公式のビューワを使って問題のサムネイルを生成することにした(2016年にサムネイル生成が遅れて進行が詰まったことの反省)。ビジュアライザがJSで実装されているのでseleniumとかで叩けば簡単にできそうだったが、あまり自動化の経験がないので、mdlファイルを順番に読みながらcanvasに描画されたものをcanvas.toDataUrl()で画像に変換し、手元に立てたExpressサーバに送りつけるという方法を取った(f58a9b)。画像を保存するツールなので名前はSaver Wingにした。モデルの描画が思ったより遅くてウエイトを調整したりする必要があったものの、しばらくして無事に生成できた。

サムネイルの公開や、今後割とすぐに発生するであろう改造版公式ツールの公開をどうするか考えて、git pushに反応して即座にサーバ上でリポジトリをpullするようにして、nginxでリポジトリのルートを配信するようにした。これは結構便利だった。

そんなことをしていたらid:pepsin_amylaseがnanachiという名前のポータルサイトを生成したため、systemd化してnginxから配信するようにして、ついでにサムネイルもナナチから見れるようにした。あとモデルビューワを改造してファイルをセレクタから選ばなくても見られるようにしたり、マウスで回せるようにしたりした。

f:id:osa_k:20180725145833p:plain f:id:osa_k:20180725145851p:plain

採点部分も公式がそれなりに速そうなものを提供してくれていたものの、本体がSMLをコンパイルしたやばそうなJSになっていて人が触れる感じではなかったのでNodeで動かすのは諦め、公式のシミュレータで走った結果を自動でナナチにサブミットすることでDBにログを残すようにした (8fe362)。しかしコンテスト終わってからnya3氏のコードを見たら割とお手軽にNode.js対応できたっぽいのでやればよかった……。ダミーのDOM実装を生やして無理やり動かすのはアイデアとしてはあったけど、何が呼ばれているのかちゃんとログする方法を思いつかなかったのと、DOM周りのAPI(特にファイルセレクタ)の挙動を理解している自信がなかったので諦めてしまった。次は大丈夫です。

その間にmkutがアセンブラを完成させ、kawateaとyuustiがそれを利用してAIを書いたり、y3eadgbeがモデルの解析をしたりしていた。非自明なAIが完成するのが思ってたより早かったので、これは流石に自動で採点する仕組みがないと後々困るなと思い、シミュレータの実装を始める。仕様がかなりはっきり書かれていて、特にinvariant周りが充実していたので、とりあえず書いてある通りに頑張って実装すればまあ動くだろうみたいな安心感はあった。久々にC++を書いたら細かい文法とかメソッド名とかかなり忘れていてエラー出しまくったのでつらい(JavaScriptを書きすぎてconst hoge = ...とか書いて、型名がないことで長大なエラーを生成したりしていた)。自動で採点するやつなので、名前はオートスコアラーにした(3a4a08)。結局4時間くらいかかって、書き上げた当初はあまり自信がなかったけど、一部アサーションが間違っていたり、最後にモデルとの形状一致を判定するのを忘れていたりした以外には、結局致命的なバグは最後まで見つからなかったので良かった。

オートスコアラーの導入で機械的に提出を評価する目処が立ったので、とりあえずその時点で存在していたAI全部を全ての問題に対してぶん回してトレースを生成し、後からオートスコアラーで点数を付けるというパイプラインを構築した。APIエンドポイントはJenkinsで、c5.18xlargeをSlaveにして186個のジョブをリモートトリガでキューに突っ込むことで、お手軽並列実行環境にした。これをやった結果、yuustiのAIがバグっていることを発見したりした(「大体正の点数を取る.cpp」というAIなのに正の点数を取れておらず、おもしろコミットが生えたりした)。

このへんで朝の6時(開始から19時間)になり、流石に眠くなってきたので、186個並列キューのやり方をy3に託して寝た。

2日目

ずっと眠くてあまり覚えてない。こういうときオンラインだと人と話してモチベーション高めつつ眠気を飛ばすみたいなことがやりにくくて不便。とりあえず起きたら昼の12時で、寝てる間に来ていた更新をmkutがまとめていた。モデルを壊す問題と作り変える問題が増え、更に範囲コマンドも追加されたらしい。範囲コマンドの実装やばそうだけど、まあこれ以上変更が来ないならアドホックに行けるかなぁと思いつつ昼飯を食べに行く。

とりあえず面倒くさそうなシミュレータ実装は後回しにして、新しく増えた問題を確認してみる。すると、どうもほとんどのモデルがLightningそのままっぽいことが分かった。再構築問題はいくつか新しいモデルがあったものの、密度の高い立方体を切り出して彫刻するやつとか、逆にモデルを埋め立てて立方体にするやつとかで、Lightning以上に見た目がやばそうな問題は増えてなさそうだった。

新しく増えたVoidコマンドの実装はしばらく考えたものの、voxelを削除すると地面に結合している判定に使っていたUnion Find木が壊れるためどうもうまい方法が思いつかない。結局Voidは後回しにして、簡単なGFill対応とDisassembly, Reassembly問題の対応を先にやって、うまい実装をもう少し考えることにした(後から考えると、ここでAIに時間を割いとけばよかったかもしれない)。

結局Union Find木が壊れるのは防げなさそうだが、kawateaが作ったAIはGVoidを使っていっぺんに大量のvoxelを消すものだったので、じゃあ普通のVoidはあまり使わなくて大半がGVoidになるだろうし、GVoidで最大303とか消されたら流石に1からUF木を再構築するしかないだろうと思って、とりあえずVoid系が来たらUF木を作り直す実装を書いた(127541)。その後しばらくして、消されたvoxelの隣接6セルがVoid後も連結ならUF木をアドホックに修正するだけでいいことに気がついて、枝刈りを入れた(4c1723)。

その後はy3がDBの変更をしたのでオートスコアラーを追随させたり、AIのコードを読んだりしていたら寝落ちしていた。

起きたら8時くらいだった(確か)。公式のStandingsをインポートして内部ランキングに表示したり(437646)、評価がまだ終わっていないtraceを採点するために、接地判定をスキップしてオートスコアラーを高速化したりしていた。

3日目

そのまま3日目に突入。Voidを入れると接地判定をスキップしても構築モードよりえらく遅くなるのでなんでだろう、と思って調べていたら、Union Find木を再構築するときに無とブロックをuniteしていたのを発見して直した(2729ce)。

id:pepsin_amylaseがこの辺りでアセンブラの最適化を行っており、結構な成果を残したっぽい。詳細は以下のブログを読もう。

pepsin-amylase.hatenablog.com

この頃になると結構サーバの稼働率も上がってきて、それに伴ってナナチが謎の死を遂げたりするようになったので、プロセス数を増やしたりしてアドホックに対応していた。あとyuustiのAIが無限にログを吐いて、300GB割り当てたはずのEBSをまるまる食い尽くしていたりした。ログ問題はともかく、ナナチはよくMySQLのコネクションが取れないと言って死んでいたので、これMySQLに1MBくらいのBlobを突っ込んでるのがよくないんじゃないの、という話から今までMySQLに保存していたtraceをS3に移行する作業をしたりして、当面はなんとなく安定している風になった。

日付が変わる頃になって、オートスコアラーにアホみたいな最適化漏れを仕込んでいたことに気がつく。GVoidはどうせUF木を再構築するから接続判定とかいらないじゃん、と言ってたのに、普通のVoidとコードを共有したせいでGVoidで消される各セルごとに接続判定が走っていた。これを消したらめちゃくちゃ速くなって、今まで大きいマップで3分以上かかっていたスコアリングが30秒くらいで終わるようになった(([9d8025]https://github.com/osak/ICFPC2018/commit/9d8025b609515c5d99743d0e6e029f9710b7ecb2))。

しかしこの高速化でサーバへのアクセス頻度が上がったせいか、ナナチがまた不安定になり、解答のSubmitがコケまくるという非常事態が発生した。ログを見たところ、またMySQLのコネクションが取れなくて死んでいるっぽい。PythonMySQLコネクタのドキュメントを調べてコネクションプールを有効にしたが、それでも改善しない。結局MySQLとコネクタの気持ちになって考えたところ、毎リクエストごとにmysql.connector.connect()を呼ぶ必要があるっぽいという気持ちになったので、試してみたところそれ以降全然落ちなくなったので正解だったらしい(53a2eb)。仕事ではJDBCに飼い慣らされているので、クエリごとに裏で勝手にコネクションプールしてくれるだろみたいな雑なイメージを持っていたが、どうもそんなに甘くはないらしい……。

サーバが一段落して、残り12時間を切ったけど誰もReassembly問題を解いていないっぽいので聞いてみると、全消しと普通の構築を組み合わせてReassembly問題の解にするという案があるらしい。やるだけっぽいので書いた(a2d7b6)。なんかファンシーな名前にしたかったが、3日目の脳は限界だったので安直にcombinerという名前になった。これを走らせると、自分は何も賢いことをしていないのにReassembly問題が次々と埋まっていってかなり面白い。一部のモデルはそもそも単純な構築や破壊問題になっていないので、これらに対して良い解を見つけるためにダミーの問題を追加したりした。

Jenkins上でyuustiのAIが延々と走りながらログを吐いてディスクを食いつぶしていくことに文句を言ったところ、どうやら中が空洞のモデルを作ろうとして、中にNanobotがいるのにGFillでフタをして脱出不能になることがあるらしく、労災と呼ばれていた。このままだと色々と不便なので、労災者が出たら心中することになった

終了3時間前くらい、y3が色々なものを手動で解いてSubmitし始める。やばい。kawateaも当然のように文字の形をした問題を手動で解いている。やばい。

スコアボードを見てUnagiの強さに絶望したりしつつ、特にドラマチックな逆転とかはなく終了。最終提出一覧

総評

インフラ構築は一部トラブルが起きてつらい気持ちになったものの、全体的には悩むことなくスムーズに構築できたので良かった。インフラができた後はちょいちょい管理業務があったものの、総じてちまちまと余裕はある感じだったので、もっとAI構築に時間を割くべきだったと思う。しかしHangout参加だと人と議論するのが難しいのでうまくできたかは謎……。そもそも例年だと、暇になったらAI作ってる人に欲しいものがないか聞いて回ってたんだけど、今回はそういうのできなかったし、遠隔のコミュニケーションは難しい。

MySQLのBlobをやめてS3に移行したのが正しかったのかは謎。実際Blobが大量に詰まってるテーブルにカラムを追加しようとしたら激烈に遅かったので何かまずい使い方ではあるっぽいが、最終的にはコネクションプールの仕方を間違っていて死んでいただけだったので、Blobがどれくらい悪いのかは分かっていない。ただ、最初の方でid:pepsin_amylaseがファイルをS3に上げることを主張していたのに、自分がS3にファイルを置くと取り扱いが面倒くさそうだしBlob突っ込めばいいでしょみたいに言ったのは良くなかったと思う。フタを開けてみれば、S3はpublicなhttpのURLも取れるし、権限付与もEC2インスタンスにIAMロールをくっつけるだけなので、超簡単だった。

シミュレータは、この記事を書きながら、そもそも各人のマシンで公式JSを走らせてもらう手もあったなあと今更ながらに思った。ファイルを複数選択してもらえるので、適切にmdlとnbtをシミュレータに突っ込んでいけば半自動でサブミットできたはず。大きい問題に対してどれくらい公式シミュレータが対応できていたかよく分からないが、その方針で一度は実装するべきだった。

チームでAWSを使うにあたって、Organizationを使って支払いは自分のメインアカウントでやりつつ、IAMにしか実体のないサブアカウントでまっさらなAWS環境を作り、そこから更にIAMユーザをぶら下げるという環境を作った。これはかなり勉強になった。

チームでコンテストやるならやっぱりリアルで集まったほうが楽だし楽しいですね。しかしUnagiに勝ちたかったなあ(勝てなかったと会社のマネージャー氏に報告したら「また勝てなかったの???」みたいな感じで煽られた)。

補足

マナリモの話はid:pepsin_amylaseのでっち上げです。