ICFP Prorgamming Contest のチーム戦テクニック集
Competitive Programming (2) Advent Calendar 2018 の 10 日目の記事です。
概要
ICFP Programming Contest (ICFPC) で好成績をおさめるための、おもに年度にまたがって再利用可能なノウハウについて説明します。ワイワイ合宿して72時間プログラミングし続けるのは単純にクソ楽しいのでみんなにも同じ沼にハマり込んでもらうためにこの記事を書きました。
2013年以降の出題傾向
問題形式
大きく分けて Problem Solving (2013, 2015, 2016, 2018) と Game AI (2014, 2017) の2種類があります。Problem Solving はある問題クラスとそのインスタンスが複数与えられるのでそれに対する解を出力するというもので、要するに普通のマラソンマッチです。Game AI は対戦ゲームのAIを開発して強いほうが勝ちというやつ。
取り組みやすいのは Problem Solving です。この記事も主に Problem Solving 系に適用できる話をしていきます。
Game AI が難しいのは主に次の理由によります
- 強さの評価が難しい
- 必然的にリモート実行になる（後述）
強さが1つの軸に乗って評価できるようなゲームが出題されることはまずなく、つまりAI同士に相性があったりするので、強さを定量的に評価するのがまず難しいです。それでも大まかな目安があると助かるのは間違いないので、多くのチームでは自動対戦システムを用意してイロレーティングなどで強さを評価しているようです。
実行環境
- 手元 (2013, 2015 予選, 2016, 2018)
- リモート (2014, 2015 決勝, 2017)
リモートは計算資源をどれだけ使えるかが明確でないのがキツいです。2017年は実行環境のVMが配られましたが、年によっては実行環境も明確でない場合もあります。
2018年の出題方針としてリモート実行は避けようというのがあった（https://icfpcontest2018.github.io/assets/report.pdf）ので、これが引き継がれるなどすれば来年以降も手元実行になるんじゃないかと予想しています。
ICFP的要素
- Theorem proving (2013)
- Compiler development (2014)
- Concurrency (2018)
個人的にはあると普段やらないタイプのプログラミングをすることになって楽しいので好きです。勝敗にはあまり影響しないと思います。
事前準備
ICFPC の準備は会場選定から始まります。以下の条件を満たすところがいいでしょう。
- 高速なインターネット
- 十分な空間
- いつでも食事や休憩ができる設備
学生の場合だと食料を買い込んで大学の研究室に引きこもるのがいいと思います。社会人勢は開発合宿に行くのもアリ。
まず AWS なり GCP なりのアカウントを用意して強いマシンを1台借ります。複数台のマシンを管理するのはだるいのでクラウドで借りるインスタンスは強いのを1台だけのするのがおすすめです。そこでさえプログラムが動けば全く問題ないようにすることでインフラ管理の負担を最小化します。そこに Jenkins を立てます。AWS の場合は公式にステップバイステップのガイドがあるのでそれに従うといいです。
Jenkins というと、学生競技プログラマーの場合イケイケ社会人エンジニアが使う謎のイケイケツールという印象しかない人もいると思いますが、今回はこれをたんに「ブラウザからプログラムを実行してそのログがあとから見れるやつ」として運用します。
ソースコードの管理は Git で行うと Jenkins が勝手に最新のコードでプログラムを実行するようにできるので便利です。コンテスト終了後に公開するのも簡単です。学生なら GitHub で無料でプライベートリポジトリが作れます。
チーム編成
ICFPCにおけるタスクは大きく分けてAI開発とAI開発のためのサポートツール開発（以下インフラと呼ぶ）です。
AI班: 人数を増やして多様性で殴る
Problem Solving にせよ Game AI にせよ AI 開発メンバーの絶対数が多ければ多いほど有利だと思います。増やしたAI担当に何をさせるのがいいかというと、それぞれがかんがえたさいきょうのAIを書かせるのが72時間コンテストではベストのように感じます。問題の多様性やゲームAI相性問題に対してAI開発者の多様性で対処する作戦です。
AI担当が多いほうが嬉しいもう一つの理由としてはコミュニケーションコストの問題が挙げられます。この戦略ではAI開発は独立に行われるためAI担当者どうしのコミュニケーションはあまり行われないことになります。全員が使うであろうコード部品やデータ構造や問題の基本的な考察などは共有されますが、AIの方針は各位で異なっていてそれらに向かってひとり黙々と開発を進めていくことになります*1。3日間という超短期のプロジェクトで成果を出すにあたってはコミュニケーションコストを削るためにもAIに人数を置くほうがいいという考え方です。
インフラ班: 競技webサービス開発
タスクは2つです。
- サーバー管理
- ツール作成
サーバー管理はコンテスト開始前に Jenkins などを立てた人がやるといいでしょう。必要なソフトウェアをインストールしたり、必要に応じて Jenkins Slave を追加したり*2、ツール開発で作られた web サービスを実際に立てて管理したりします。
ツール作成の最初の大きなゴールは、AI班の人のAI開発以外の仕事を自動化することです。そのために必要なのは
- AIプログラムの入出力仕様
- 過去のAIプログラムの計算結果を管理するいい感じのデータベース
- Jenkins からAIプログラムを実行する仕組み
- 問題の入力などを可視化
- 公式サーバーをスクレイピングしていろいろやる
- これらを一覧できるポータルサイト
あたりです。これらを AI 班の非自明AIが出来上がり始める頃には揃えておきたいので開幕はかなり忙しいです。
AIプログラムとの入出力仕様は、うちのチームの場合メンバーがみんな競プロ勢なので競プロっぽい入出力フォーマットを策定しています。
過去の結果を管理するデータベースは必ずしも MySQL のような RDBMS である必要はありません。出力のファイルとそのメタデータを記した json ファイルとかで十分なケースもあります。これをしょぼエンジニアリングと呼ぶか72時間動けばいいICFPCならではの割り切りと呼ぶかは微妙なところ。
可視化は近年の問題の場合だと公式からブラウザ上で実行できるビジュアライザが配られます。それでも（意図的にか意図せずか）十分な機能がついてないことが多いので、フロントエンドに強い人が一人いると強いビジュアライザができたり公式ツールの改造がはかどったりして便利です。
公式ツールの再利用は結構重要なテクニックです。いちからビジュアライザを書くのはだるいというのもそうなんですが、公式ビジュアライザは正しいことが保証されたシミュレータでもあるからです。2018年は公式ビジュアライザで計算したスコアと自前のスコアラーの結果が一致するかを確かめるのが重要なテクでした*3。公式側でこういう利用を対策している場合もあり、2016年は有理数座標での折り紙でしたが公式シミュレータは内部計算に浮動小数点数を使っていました。
大量に同時実行したAIの出力を POST リクエストでポータルサイトに投げるような設計をした場合はその負荷にも注意が必要です。ポータルサイトがボトルネックになって計算結果が失われるという悲しいながらも割と起こる事故があります。ISUCONするはめにならないよう。*4
スタートダッシュで基本的なツールを揃えたら、AI班の人と相談しながらビジュアライザを強化したりほしそうなツールを作ったりします。
実際の編成
最近は osa_k がサーバー管理をやり、amylase, y3eadgbe, osa_k がインフラツールの開発に邁進、kawatea, mkut, yuusti が AI 開発という（おおまかな）分担になっています*5。
実際の初動としてはみんなで問題を読んでそれぞれの感想を言いあい、なんとなく上のような分担に収束して各自手を動かすという感じです。
コンテスト終盤の動き
注力するべき問題を絞る
終盤になってくるとどういう問題が難しくてどういう問題なら手が出せそうか、そしてそれぞれの大まかな効果が見積もれるはずです。例えば最適解の点数がわかるタイプの問題なら改善の余地があとどれくらいあるかはその入力インスタンスの重要性を示す重要な指標です。
残り16時間くらいの段階でチーム全体で時間をとって優先度付けするといいと思います。
インフラからAIに転職
基本的にインフラツールの仕事はどんどん減っていきます。そうなると無限に仕事があるAI班に転職するわけですが、弊チームでの転職事例を思い起こすと、
- すでにある出力を後処理して細かく改善する
- 人間ソルバーになる
- 高速化
が手を付けやすいタスクだと思います。特に人間ソルバーはプログラムではどうしようもなかった問題に対する唯一の解決策なので意外と重要です。
AI 班の人にノウハウを教えてもらって新規開発してもいいけどこっちは難易度高め。
まとめ
プログラミングコンテストが好きな人なら、何か一つは面白そうなタスクがあったと思います。ひたすらAI書いてたい、イケてるビジュアライズをしたい、作業を自動化してチームの生産性が向上するのが見たい、手でパズル問題を解きたい……
同じことを感じた人たちでチームを作ってひと夏の思い出づくりに合宿してみませんか？
ちなみに
ICFPC 2018 の Lightning 1位, 2位 と Full Contest 3位, 4位 は1人チームでした。他人と群れるのは嫌いだ、という方にも ICFPC はおすすめです。
おまけ: 過去の失敗集
サーバーのストレージを使い尽くす (2015)
つらい。3日だと大した額にならないからでかいEBSつけましょう
Unagi の潜伏に引っかかる (2016)
仮に潜伏だとわかっていても勝てなかったわけではありますが、気をつけましょう（何に？）
インフラコードとAIコードの管理がグダる (2017)
この年は Game AI で、インフラ用のコードとAI用のコードをまとめて git に置き、タグを付けたコミットを成果物として扱い、自動対戦の対象とするようにしていました。しかし時と共にインフラの前提や必要なインフラコードが置き換わっていき、一方で過去のコミットのインフラコードは変化しないので……
インフラコードとAIコードは基本的に入出力以外でコミュニケーションしないのでリポジトリを分けたほうが安全だと思います。
会場のインターネットがゴミ (2017)
airbnb で確保した物件の「インターネットあり」がモバイルwifiで、コンテスト開始前に通信制限に引っかかりました。
開発合宿の実績があるところにしましょう。
インフラアプリのパフォーマンスが足りない (2015, 2018)
ISUCON しないように（2回め）
