おはようございます、エンジニアの japlj です。

2019 年 6 月 21 日から 6 月 24 日にかけて開催された ICFP Programming Contest 2019 に RCO アドテク部有志 8 名で参加しました。昨年 に続いての参加です。今年は新卒 1, 2 年目の若手が多いチーム構成で、チーム名は Pigimarl (ぴぎま〜る) でした。

この記事では参加の様子や、実装したソルバーの解法、またそれらソルバーの開発を支えた採点インフラの紹介をしていきます。

↓これは lambda-coin をじゃぶじゃぶ課金して得たクローンを最大限活用して広大なマップを手分けして塗っている様子 (独自ビジュアライザーのスクリーンショット)。

合宿

今年はオフィスからの参加 + 希望者は近隣のホテルに宿泊というかたちで合宿を行いました。

例年はどこかに合宿場として宿をとって参加していましたが、今年は

• ネットワーク環境、机・椅子、ホワイトボード、モニタなどの設備
• 深夜等にも参加者が集まって作業や議論をできる場所

など重要なコンテスト参加環境が揃っているオフィスからの参加にしてみました。

結果としては、いわゆる “合宿” 感が多少薄れてはいるものの、コンテスト参加のための環境としては快適であり、家の方が落ち着いて休めるという人は家から通って参加できるなど、参加者としては嬉しい形態になったようです。

↓これは寿司を食べながらアレコレ議論をしている様子と、

↓広々としたスペースで孤独に作業する僕。

作ったもの

ソルバー

今回の課題は「2 次元のグリッド上でロボットを操作して、効率よくすべてのマスを塗る」ことに関するものでした。マップ上には障害物の他にアイテムも落ちていて、拾って使うことができます。

コンテスト開始当初はロボット 1 台のシンプルな仕様でしたが、24 時間で 3 回の仕様追加の存在が明らかにされていたため、チーム内では「きっとアイテムの種類が追加されていって、24 時間の Lightning Round が終わったタイミングで、ロボットが複数台に増えるんだろうな……」と予想していました。

この予想は一部を除いて的中することになります。仕様変更への対応がとても辛い ICFPC において、追加仕様の予想を当てられたことは大きいです。しかし……そう、予想外だったその一部が、まさかあんなことになるなんて……。

ともかく、まずはソルバーが実際に動作している様子をご紹介します。

昨年に引き続き、今年もソルバーは C++ で書かれています。この様子からも見て取れるとおり、ソルバーの基本方針は

• まずは clone (ロボットを複製できるアイテム) と extension (ロボットの腕を伸ばして広範囲を一度に塗れるようになるアイテム) の回収を優先
• アイテム回収が終わったら複製を行い、ロボットを増やす
• 各ロボットが一定の領域を担当して塗っていく

という形になっています。

ベースとなる方針に対し、アイテム回収の優先度・extension の分配方法・領域の分割方法・実際に領域を塗る方法など細かなバリエーションがたくさん存在しています。

今年も結局、ソルバー開発メンバー同士でのライブラリ共有などは困難と判断して行わず、それぞれが独立して開発を行いました。ただ、今回のように処理が分けやすい (アイテム回収フェーズ → 領域分割フェーズ → 各領域を塗るフェーズ、のように分けられる) 問題では、フェーズごとの処理を複数人でそれぞれ作り、あとで結合するような協同方法が取りやすかったと思います。

そうした協同がちゃんと行えていればソルバー開発の効率が上がり、今回時間内にやりきれなかった局所最適化などを行う時間もとれたかもしれません。このあたりは反省の多いところです。

パズルソルバー

さて、先ほど述べた予想できなかった追加仕様についてです。それはコンテスト開始から 14 時間が経ったころ……なんと 3 回中 2 回目の仕様変更で複数台ロボットが解禁される衝撃の展開……！

まさか、24 時間の Lightning Round 中にロボットが複数台になるとは……いや、だとすれば、一体最後の仕様変更で何が起こるというのか？

その答えが lambda-chain とパズルの登場でした。「パズル」とは、マップの大きさ・障害物の配置・アイテムの個数などに関する制約が与えられるので、その制約を満たすマップを出力するというものです。

lambda-chain では、問題 (もともとの、マップを塗る問題) と「パズル」がそれぞれ 1 問ずつ出題されています。出題から一定時間内に、問題とパズルに対する解を送ることで lambda-chain に参加することができます。

一定時間の経過後、問題に対して送った解の良さに応じて lambda-coin が分配されます。そのうえで、解を提出したうち上位のチームから 1 チームが選ばれ、そのチームが送ったパズルの解が次の問題となります。このように、問題に対する解答と、パズルに対する解答 (＝問題の出題) を繰り返しながら lambda-coin を手に入れていきます。この lambda-coin を使うことで clone などのアイテムを購入することができ、最終提出で有利に戦うことができるようになります。

パズルを解くためのパズルソルバーが必要になることはもちろん、障害物に関する条件を課された上で出題されている lambda-chain 上の問題は上記画像のように特殊な形をしているので、lambda-chain 専用のソルバーも用意しました。

パズルの難易度は時間が経過するほど上がっていくという仕様だったため、とにかく正当なパズルの解を出すことを最優先していくつかのパズルソルバーを作りましたが、実はそこまで難しいパズルはなかったようでした。むしろ、細い一本道からなる出題をすることで全員の解を同じにしてしまい、強いチームから相対的に lambda-coin を奪うような方向性を考えたほうがよかったかもしれません。

ビジュアライザー

今年も公式でビジュアライザーが提供されていました。ただ、そちらはロボットを増やすとどうも動作が重くなるようだったので、独自でビジュアライザーを作りました (この記事に貼られているマップなどの画像は独自ビジュアライザーのものです)。

独自ビジュアライザーは高速なビジュアライズや、複数台ロボットの色分け表示といった機能の他に、手動で問題を解く機能にも重点がおかれており、特に小さいケースでは職人の業が冴え渡りました。

↑手動で問題を解いている図。右上にコマンドの履歴が表示されており、undo 機能を駆使しながら職人が最適化を行えます。

採点インフラ

今年の参加メンバーには ICFPC でのインフラ周りを経験したことのある人がいなかったので、事前に昨年度のような問題形式を仮定した採点インフラを構築する予行演習 (もし形式が昨年と同様だったら流用できてラッキー) を行っていました。

実際には、テストケースがいくつか与えられ、手元でできるだけ良い解を出して送信するという昨年同様の形式だったので、事前に作っていた採点インフラをほとんどそのまま流用でき、スタートダッシュに成功しました。

以下は Pigimarl 採点インフラの概要を図にしたものです。

ここでは、いくつかの特徴的な点を紹介します。

ソルバーと commit hash の対応付け

昨年などは、ソルバーやバリデーター、ビジュアライザーなど全ての成果物をひとつのリポジトリに集約していましたが、今年はソルバー専用の github リポジトリを用意しました。これは、採点インフラ側が 1 つのソルバーとリポジトリの commit hash を対応させるという設計になっているためです。

ソルバー開発者から見たソルバー開発と採点の手順は以下のようになります:

1. ソルバーに対応するブランチを切る。このとき、ブランチ名によってソルバーのディレクトリを指定する。
2. ソルバーを開発して github に push する。
3. github からの webhook によってポータル (webアプリ) 側にソルバーが登録される。
4. 登録されたソルバーを選択し、入力となるテストケース (の集合) を指定して実行させる。

このような設計にしたことで、「あれ？このスコアはどういうアルゴリズムのソルバーが出したんだっけ」というときにすぐに該当のコミットに飛ぶことができ、同じ名前のソルバーでも細かいバージョン違いが発生しやすい ICFPC という状況下での混乱を抑制することができました。

AWS Batch での採点実行

実際のソルバーの実行は AWS Batch 上で行いました。これにより、普段は費用の発生を抑えつつも場合によってはすぐに数十〜数百 vCPU までスケールさせることができ、ソルバーの開発・改善が非常に高効率で行えました。

ポータルから Batch job として起動されるエージェント (Docker コンテナ化されたアプリケーション) は、指定されたソルバー (commit hash) を clone してきてビルド & 実行を行い、出力のチェック (バリデーション) を行ったのちに結果を S3 にアップロードします。

ソルバー側で新しい言語やライブラリを使いたいときは、このエージェントの Dockerfile に追記することで楽に追加できます。(といっても実際のところソルバーはほとんど C++ だけで書かれましたが……)

独自ポータルサイト

ICFPC 参加中に最も向き合うことになる独自ポータルサイト (Django 製の web アプリケーション) です。

テストケースの一覧表示、現在の得点状況確認、ソルバーの管理など、快適なコンテスト参加を支える機能が揃っています。

ポータルからは、画像のようなテストケースごとの課金/無課金でのベスト点数確認や、上述したソルバーを選択しての採点実行のほかにも

↑各テストケースに対するソルバーのランキングを見ることができたり

↑lambda-chain のブロックたちの様子 (と現在の所持 lambda-coin 数) が確認できたりします。

また、このポータルサイトのもうひとつの重要な役割が lambda-chain への参加です。ポータルに登録されたソルバーたちの中から一軍ソルバーを選ぶことができるようになっており、新しい lambda-chain のブロックが出るたびに一軍ソルバーたちが自動実行され、最も良かった解が lambda-chain に送信されます。

パズルのソルバーについても同様に、github への push によってポータルに登録され、一軍として選択されたものが自動実行されて lambda-chain に送られるようになっています。

ポータルが lambda-chain に参加している様子は専用の Slack channel に逐一通知され、コイン採掘の現状を見守ることができます↓

まとめと結果

結果は、194 チーム中 3 位 (Lightning 部門も 3 位) でした。

しっかりとチームの実力を発揮して良い順位をとることはできましたが、あと一歩で入賞 (2 位以上) だったのは悔しいところです。次回は入賞して ICFP に呼ばれたい……！

感想としては、問題自体はオーソドックスでありながら奥が深く、lambda-chain も (息つく暇もない仕様追加のトドメとしてやってきた点を無視すれば) 目新しく面白かったと思います。lambda-chain へ参加するためのソルバー実行の仕組みづくりも (Lightning Round 終了 4 時間後から開始→のちに延期という無茶なスケジュールであることを無視すれば) 楽しめました。

総合的には、やり残してしまった点・次回への課題はありつつも、オフィス環境の良さや事前準備がピッタリ当たったことも含めて力は発揮しきれたかと思います。そして何より個人的にはとても楽しく参加できました。性急な仕様追加と無茶なスケジュールを無視すれば……。

よくある質問

• Pigimarl って何？

ICFPC とは全く別の文脈で、ポータルのことを「ポタール」と typo してしまったことに因みます。

そのため、チーム内では各種名称がポタール化され、ポータルサイトは「ポタール (potarl)」、ソルバーのリポジトリは「ソバール (sobarl)」、Batch job のエージェントは「きま〜る (kimarl)」(スコアが決ま〜る) と呼ばれていました。

Pigimarl は「ぴぎまる」をポタール化したものになります。

• ぴぎまるって何？

社内 (の一部) でよく使われる文字列で、意味・語源は誰も知りません。

広告

RCO アドテク部では、協力して難しい問題に取り組むのが好きなエンジニア、あるいは寿司を食べながらアレコレ議論するのが好きなエンジニア、あるいはクラウドを活用したシステムの開発を得意とするエンジニア、あるいは手動での最適化もバリバリ行える職人気質のエンジニアなど、要はすごいエンジニアを募集しています。

採用ページ