ICFPC 2018: Team manarimo

昨日までの3日間、例年通り ICFP Programming Contest にいつものチームで出た。今年のチーム名は manarimo。

公式サイト: ICFP Programming Contest 2018

成果物 (github)

github.com

今年はメンバーの1人である osa_k がアメリカで出稼ぎ労働者をしていることから、日本の5人と osa_k は Goole Hangouts で会話しながら作業していた。

-n日目

チーム結成

昨年に引き続き同じ6人チーム。

osa_k, y3eadgbe, kawatea, mkut, yuusti, pepsin_amylase

会場選定

去年は越後湯沢のスキー客向けリゾートマンションを airbnb で確保したけど周辺施設がなにもない上にインターネットが貧弱*1で、温泉以外はいまいちだった。この経験を踏まえ、今年は利便性が高いところがいいという話をしていた。

y3eadgbe が社会性を発揮してオフィスマネージャーと交渉し、コンテスト期間中に勤務先の一番大きい会議室が独占的に使用できることとなった。

-1日目, 0日目

勤務先でハッカソンが行われたので睡眠調整を兼ねて徹夜。ハッカソンに飽きたチームメンバーと一緒にクソなぞなぞを解いていた。

www.nazomap.com

72問目を解いているときに、誰かが答えを思い浮かばず「マナリモって藻、存在しそうじゃない?」と苦し紛れに言ったのを聞いたぼくが即興ででたらめな設定*2を付け加えたところ結構ウケて、あとでチーム名として採用することとなった。

1日目

チームメイトが問題を読んでいる間に回答の提出方法を読んで submit.py を実装。公式の dfltTracersL.zip をそのまま提出してテストしようとするも、コンテスト開始3時間までは提出できずに怒られたりした。

submit.py のテストを済ませたあと、生成した回答などを管理する web アプリを立てることにした。

ナナチ

熟慮の末今年の ICFPC ではメイドインアビスからツール名を取ることにし、管理アプリをナナチと命名。2015年に書いた響のコードをコピペして必要な改修を加えていった*3

energy の計算をやっている公式ツールの再利用を試みたがブラウザから剥がすのは難しそうだった(ICFPC2018あるある)ので、公式ツールを手で実行させたときに得た結果を JavaScript で抜き出してナナチに生やしたエンドポイントを通じて MySQL に突っ込むという仕組みを考案し、osa_k と分業してこれを実装した。

ナナチに登録したデータがすぐに反映されないという問題が発生。どうも MySQL の Isolation Level が REPEATABLE READ であることに起因しているっぽく、いたるところで commit して強引に解決するなどした。

2日目, 3日目

Lightning が終了したので一旦帰って寝た。休んでいる間に既存の Trace を後処理で改善するというアイデアを得たのでこれをやることにした。

ミーティ

既存のファイルはすべてバイナリの .nbt ファイルで保存していたので、後処理器に食わせるためにチーム内で使用しているアセンブラフォーマットに戻すツールを書いた。ミーティと命名。これは他にも壊れた nbt ファイルを生成した他のソルバーのデバッグに役立った。

ナナチ炎上

Lightning が終わった頃からナナチが頻繁に死ぬようになる。osa_k が jenkins を使ってすべての問題に対してソルバーをぶん回してナナチに提出する機能を作ったのだが、これを使うと何問か提出したところでナナチが止まってしまう。

一応再起動すると治るので、死ぬたびに再起動で生き返らせていた。こっちの名前をミーティにしておけばよかったと少し後悔する。

osa_k を消耗させることにより、コネクションプールを使ってないことやらナナチのプロセス数が足りないことやらどうも nbt ファイルをバイナリブロブとして突っ込んでいることやらが怪しいのではないかとなり、治してもらった。

ウェブアプリの負荷耐性を上げるという事実上の ISUCON をすることになったのでちょっと面白かった。これは2015年のチームの反省会の話題に出た(らしい)のだけど、ICFPC で使うインフラは意外と負荷がかかるので、動けばいいという気持ちでやるのはあんまりよくないっぽい。

ボンドルド

後処理器その1にボンドルドと命名。命令を1つ前のwaitと交換するのを貪欲に繰り返し、すべてがwaitだけになったターンをスキップすることで圧縮を図る。だいたい数%から10%ほどの energy 節約効果があった。

yuusti のハローワークや mkut のスプラシューターコラボ、kawatea のシヴァと組み合わせてハロワボンドルド・スシコラボンドルド・シヴァ神ボンドルドというソルバーにするなどしてチームの成果物に組み込まれた。

プルシュカ

ボンドルドは一定の成功を収めたものの、生成された出力を見ると順番を入れ替えられないばかりに長々と待たされている状況があることに気がついた。

そこで、本当に入れ替えてはいけない依存関係と同時に実行しなければならない依存関係を解析して DAG を生成し、ここから適切に命令列をつまんでいくという賢しらかつ ICFP っぽい手法を考案した。プルシュカと命名。

入力の命令列は harmonics やら volatile check が正しいという仮定を置くと、だいたい以下のような依存関係に気をつければいい気がしてくる: 

同時実行制約
  • グループで実行する命令: GFILL, GVOID, FUSIONP, FUSIONS
  • 同時に実行される FILL / VOID
順序制約
  • 別のターンに実行された FILL / VOID はその順序を保つ
  • 同じボットの中では移動系 (SMOVE / LMOVE) と場所に依存した効果を持つ命令の間ではその順序を保つ(場所依存命令の場所を変化させないため)
  • すべての命令はそのボットを生成した FISSION より後
  • すべての命令は FUSIONS / HALT より先

FILL / VOID の同時・順序制約は harmonics チェックをサボるために入れた雑な条件。これを実装してボンドルドを過去にするぜ、と息巻くも実行すると途中でエリア外に出る命令を実行しようとしたり、実行できる命令がなくなったりしていまう不具合に遭遇した。

エリア外に入れるやつはどうも移動命令の順番を入れ替えるのが悪いっぽく、同じボット内での移動命令どうしに順序制約を入れると治ったが、最初の目論見である移動の大胆な最適化が予想以上に難しいことを示しており動揺した。

実行できる命令がなくなってしまうのは、よく調べてみるとどうもデッドロックらしいことが明らかになった。例えば、2つのボットがお互いの場所へ移動しようとする SMOVE 命令を構えている場合、どちらかを先に実行することはできない。分散処理の有名問題を踏み抜いてしまい、ICFPC らしさと絶望を感じた。

どちらかを邪魔にならない場所にどかすよう命令を追加するという雑な方法で回避するアルゴリズムを実装したが、これのバグは取り切れず、バグを踏まなくてもこれによって最適化の結果ターン数がかえって長くなってしまう現象などが発生し、この時点で完全に心が折れてプルシュカの方針は諦めることにした*4

コンテストの残り時間はボンドルドの改良に費やしたり唯一神の訃報に驚いたりしていた。

感想

非ゼロの貢献ができてよかったけれど、ナナチはかなり負債を残して osa_k や y3eadgbe に苦労をかけたし、プルシュカは投入した時間に見合う成果ではなかったのが残念。

毎年 webapp をコピペしていることを考えると ICFPC 用 webapp ライブラリが作れるのではないかとちょっと思ったりした。

宿題

  • プルシュカの方針は実現可能なのか。

特にデッドロックを依存グラフから検出できるか。移動命令の制約を保っているので各命令での場所はわかるはずだが、グラフに WAIT が現れないのでどうなんだという感じ。

  • MySQL のコネクションの動作やブロブの扱い方を学ぶ。

*1:モバイルwifiで提供されていて、mkutが音楽を聞きながら作業しようとして一瞬で通信量を使い果たした

*2:github の README に書いてある

*3:響を改造したのでヴェールヌイにしようかと思ったけど熟慮の末やめた

*4:一応ごく一部の成功例は最終提出に使われた