ICFP Programming Contest 2017 参加記

皆さん、こんにちは! エンジニアの二木です。今回は ICFP Programming Contest (ICFPC) への参加記です。

フィックスターズとICFPC

ICFPCとは国際関数型言語学会(The International Conference on Functional Programming; ICFP)の主宰するプログラミングコンテストで世界各国が参加する国際規模のイベントになります。毎年夏ごろに開催され、期間は3日間のチーム戦で、最初の1日目までの提出プログラムで競う部門(Lightning contest)と3日間すべてを使って競う部門(Full contest)の2部門があります。

問題を解くために72時間が与えられますが、難易度は総じて高く、アルゴリズム開発、インフラ構築、ビジュアライザ作成など実装にも時間が掛かることが多いので、効率よく開発していく必要があります。因みにチームには人数制限はありません。

フィックスターズではプログラミングコンテスト好きが多いので毎年有志を募ってICFPCに参加しています。2011年から参加しているので今年で7年目になります。参加当初は勝手が分からず100位あたりでしたが、近年では10位前後ぐらいをウロウロしています。因みに、これまでの最高順位は2013年の2位でした。

そして今年もICFPCに参加するために社内で有志を募ったところ、6名のメンバが集まり、例年と同じく合宿形式で参加することになりました。

準備

今年は三浦海岸駅近くのホテルで4泊5日の合宿になりました。宿泊代と旅費はすべて会社で出してくれます。また、宿泊についてもすべて手配していただいています。いつもありがとうございます!

さて、毎年宿泊先の条件として次の3項目を挙げています:

1. ネットワーク
2. 居室もしくは会議室を1日24時間利用できる
3. 温泉!

3番目に挙げた温泉は重要で、精神力が削られる72時間を乗り切るための切り札となります。

また、これまでのICFPC参加の経験から、以下の事柄が大事であることを学びました。

スケジュール管理

• 時間の配分
• 作業の調整

情報の共有

• Wikiやホワイトボードを利用
• 定期的な短いミーティング

課題の理解・共有

• できるだけ早期に
• 課題が出されて1時間後ぐらいに内容を共有・すり合わせ

作業環境

• 開始前に確認
• 慣れているツールを使う
• 新規に利用するツールがあるなら事前に確認

新規に参加するメンバもいるので事前によく理解してもらってから挑みました。

問題

関数型プログラミングの継続的な人気と関数型プログラミング言語でのラムダに対する需要の増加に伴って、ボトルネックはラムダ鉱山から輸送ネットワークに移ってきている。君の仕事は、ラムダ鉱山から世界中のプログラマへラムダを運ぶためのパントの舟路を決めることだ。君は他のパント乗りと競争して、最高のラムダパント乗りとして勝利しよう!

これが今年の問題です。因みにパント(punt)とは平底で両端が方形の舟のことです。

これだけだと意味が分かりませんが、要はあるノード(mine; 鉱山)からエッジ(river; 川)を伝ってできるだけ長い距離を取るゲームになります。つまり、グラフに対する辺取り合戦ですね。細かいスコアの決め方などはリンク先の説明を読んでみてください。

余談ですが、ちょうどこの合宿と同日に開催されていた社内のボードゲーム会で「チケット・トゥ・ライド」というゲームをプレイしていたそうなのですが、これが今年のICFPCの問題と似たルールで、面白い偶然もあるものです。

開発

さて、4泊5日の開発内容を順を追って箇条書きで列挙してみます。

1日目

• 職場から電車で1時間ちょいで、午後6時に現地入り。
• 一部屋が広くて6人でそこに泊まっても十分快適。
• 円卓を囲んでのコーディングは思いのほかやりやすかった。
• 食事が美味しい。 → ここ重要!
• 三浦海岸だったので三崎マグロの刺身や寿司がとても美味しかった。
• 温泉に入ってリフレッシュ → 外に遊びに行くことはもちろんできないので気分転換できることは重要!
• ICPCやら、TopCoderやら、GCJやら、社内プロコンやら、コンテスト関連のTシャツを着て気合い入れて待機…とは言っても今年のホテルはどこでも浴衣でOKだったので半分ぐらいは浴衣でしたが。
• 午後9時からコンテスト開始。
• 少し開始が遅れる。
• 始まったばかりのこの時は、まだみんな元気いっぱい。( ^ω^ )
• 最初の30分で内容を把握してみんなで情報を共有する。
• ざっくりしたスケジュールを決めてみんなで好きなことを始める。
• まずは、インフラ1名で残りはAI作成に回る。因みに自分はAIチーム。

• AI作成
  • mineからできるだけ長くなるようにriverをつなげる戦略
  • 最長の地点を見つけてそこまで伸ばす戦略
  • mineにつながるriverを取得して他のプレイヤーを邪魔する戦略
  • mine同士を連結にする戦略
  • 評価関数の検討
  • 利用できるアルゴリズムの調査

• C++の場合
  • グラフは自前なので設計が大事
  • 仕様変更に対応するのがそこそこ面倒
  • アルゴリズムはすべて自前で用意する必要がある
  • きちんと高速化を考えた設計だと速い! → 重要!

• Python+networkxの場合
  • プロトタイプ作成が簡単
  • 大抵のアルゴリズムが揃っている
  • ノードやエッジに情報を加えるのも容易で扱いが楽なので仕様変更にも簡単に対応できる
  • 高速化が苦手でチューニングしたC++にはだいぶ劣る → 今回の場合はかなり致命的
  • グラフジェネレータを作るのは楽

• インフラ・ビジュアライザ
  • PythonとJavaScript
  • AIチームのメンバからの要望が大変

• 午前3時ごろには就寝。

2日目

• 午前7時半に朝食。美味しい。
• AIチームは時々議論しながら対戦ルーチンの戦略を考える → これ大事!
• インフラ担当はビジュアライザも一緒に作成する
• 午後9時までにlightning divisionのコードを提出しなければならないのでスケジュールを考える→これまでの参加内容から午後5時に仕上げるつもりで対応する(仕上がるとは言っていない)
• 午後7時に夕飯。美味しい。…がlightning division締め切り直前なので急いで食べて戻る。
• 何とか提出を終える。
• バグがちょっと入っているっぽいが検証の時間が取れなかった。 → これは仕方がないか
• そして温泉に入ってリフレッシュ。気持ち良い。
• あと、2日間あるのでメンバはまだ余裕っぽい表情。(^J^)
• 午前3時頃就寝。
• 就寝と起床はメンバによって結構バラバラ。

3日目

• 午前7時半に朝食。美味しい。
• できあがったAIをそれぞれ対戦させて盛り上がる。
• 対戦システムはJenkinsを使って作成。
• 午後7時に夕飯。
• 明日の夕飯は締め切り近くて食べられるかわからないので味わって食べる。 → 美味しい
• いつの間にか残り1日になっている。ちょっと焦る。
• 適当に風呂に入りそして寝る。

4日目

• 午前7時半に朝食。美味しい。
• 午後9時がコンテストの締め切り。
• グラフジェネレータの作成→もっと早くに作っておけばよかった。
• 午後7時の夕飯は食べられなかった。悲しい。
• 夕方までには一通り終わって検証フェーズを入れるつもりだったがバグ取りが思い通りに行かず入れられなかった
• 午後9時になりコンテスト終了。お疲れさまでした!
• 夕飯を取れなかったので外に出てコンビニで買ってくる。あまり美味しくない。
• この後はゆっくりと温泉に入って疲れを癒す。
• 疲れていたので早めに就寝。

5日目

• 午前7時半に朝食。美味しい。
• ホテルでは衣類やアメニティなどが全部揃っていたので持ち込みはPCぐらいで良かったようだ。
• 少しだけ反省会。
• 午前11時にチェックアウト。
• 帰宅。

ビジュアライザ

今回作成したビジュアライザです。ビジュアライザがあるとないのとではAI作成の開発のしやすさは段違いです。また、目で見えるのが単純に楽しいですし、モチベーションの維持にもつながっています。つまりビジュアライザは大事!

結果

今回の結果は以下の通りでした。

Lightning Contest

• • 80チームが参加
  • Round 1
    • 6位
    • Round 2に進出!
  • Round 2
    • 4位
    • Final Round進出!
  • Final Round
    • 4位
    • バグ: 評価マップ2種のうちの1つでスコア0点…2つのmineを取る戦略だったがマップに1つしかmineがないとすべてパスしてしまったのが原因
    • それでも4位だったのは健闘した方かと
    • 主催者側からのコメントもあったので載せておきます:
      

      The \$ound of .\ and fixstars both did very well on the Edinburgh map, scoring an order of magnitude more than other teams. However, fixstars had problems with the coauthor map and so The \$ound of .\ are a long way ahead.

Full Contest

• • 146チームが参加
  • Round 1
    • 13位
    • Round 2に進出!
  • Round 2
    • 34位
    • Final Round進出ならず…
    • バグ: 他チームでsplurgeが入ると何故か不正処理扱いになりゾンビに…

まとめ

毎年のことですが、72時間集中のコーディングは精神力をかなり削られます。なので、快適なコーディング空間とか、温泉でリフレッシュとか、美味しい食事とか、こういった環境がとても重要だったりします。

そして、業務と同じようにスケジュール管理がとても大事であり、いかに効率よく、それぞれのエンジニアが協力し合ってコードが書けるかを、3日間に凝縮しているわけで、チームで開発するという経験だけでも素晴らしい価値があると思っています。これって会社で開発しているプロジェクトの縮図のようであって、なかなか面白いですね。

結果については、コードの検証時間がもう少しあれば…とも思いましたが、条件はどのチームも一緒でどこも多かれ少なかれバグはあるんだろうなと思います。これを経験としてより良いやり方を考えるのが大事ですね。

さて、来年のICFPCにも参加する予定ですので、今後もよろしくお願いいたします!

This site uses Akismet to reduce spam. Learn how your comment data is processed.