Operation Clear Sky
先の6/28-30日にかけて，毎年恒例のプログラマの祭典 ICFP Programming Contest (ICFP-PC) が開催され，私も参加していました．
こんな辺境の日記を読んでいる人ならほとんどが知っているかもしれませんが，これは ICFP という関数型プログラミングに関する学会に併設して毎年開かれているコンテストです．プログラミングの腕を競うコンテストというのは最近では一部の界隈でそこそこメジャーになってきていて，たとえば有名どころでは ACM-ICPC, TopCoder, IOI, SuperCon などがそれぞれの競技ルール・参加資格の設定のもとで開かれています．
そのように多種多様なプログラミングコンテストの中でも，特に個性的なコンテストの一つが，今回開かれた ICFP-PC です．その特徴はどのようなものかというと...
- 好きな人同士でチームを組んで参加します．参加資格に特に制限はなく，学生であるか社会人であるかや年齢などを問わず，参加したいという意思さえあれば誰でも参加することができます．
- オンラインで開催されます．決められた時間に問題が公開され，世界中のチームが一斉に競技を始めます．解答の提出やランキングのチェックなどは全てウェブサイト上で行います．
- 競技時間は72時間です．これが ICFP-PC を ICFP-PC たらしめている大きな要素の一つです．
- 「正解」の無い問題が出題されることがほとんどです．たとえばあるゲームのプレイヤーAIを作成し，参加者のAI同士で戦わせて成績を競う，などの問題が過去に出題されました．
特に競技時間が72時間であるところが一番の特徴ではないでしょうか．チームによっては徹夜でコードを書いたり，チーム内でメンバーの起きている時間帯を分けて，72時間誰かしらが起きて作業をするように戦略を立てたりするそうです．毎年，コンテストの日程は土日に被るように設定されますが，どうしても1日ははみ出してしまうので，熱心な社会人プログラマの参加者はコンテストのために有給を取ったりします．
さて，今年の問題はどういうものだったかというと，大雑把に言って，地球の衛星軌道上を回っているデブリを宇宙船を操作して回収しろ，というものでした．問題文は ICFP-PC のホームページから見ることができるので詳しくはそちらを参照してもらいたいのですが，もうちょっとだけ詳しく書くことにします．
2次元で表された宇宙空間の真ん中に地球があり，その周りをいくつかのデブリが衛星軌道にのって回っています．デブリは離散時間で近似されていること以外は高校物理で習った通りそのままの動きをします．また，自機となる人工衛星も同じ物理法則のもとで宇宙空間に浮かんでいます．この衛星は装備している推進装置を使って動かすことができます．ただし，推進装置を使うには燃料が必要で，燃料以上の推進力を得ることはできません．また，地球に衝突してしまってもだめです．目的は，推進装置を使って衛星をデブリの軌道に誘導し，デブリを回収することです．宇宙空間には複数のデブリが浮かんでおり，なるべく多くのデブリをなるべく早く，なるべく少ない燃料を使って回収するとスコアが高くなります．
推進装置を使って瞬間的に加速したりすることができるため，結構簡単に制御できるのかな，などと最初の頃は考えていたのですが，実際にとりかかってみると決してそんなことはありませんでした．軌道と軌道の間を遷移するのが結構大変で，完全に真円の軌道だけ取るならまだしも，楕円軌道となるとおいそれとは行きません．それに，実は地球の他にも月が浮かんでおり，月との間で働く引力のせいで軌道が完全な楕円にならないことや，シミュレーションが離散的な時間で行われるために理論的な計算通りに動かすことができないことなど，いろいろと罠がありました．デブリと同じ軌道に乗ろうとしても，1秒だけ計算と違う時間に到達するだけで相手と数kmも離れてしまったりするので大変です．本職で宇宙船の制御をやっている人たちの偉大さを痛感しました．
さて，ここからは参加記になります．問題は上で説明したもの(Operation Clear Sky)だけでなく，いくつかの難易度に分かれていて，順に解答を作成していくことで最後の Operation Clear Sky を遂行するのに必要な道具が揃うようになっていました．ここからは問題文を読まないと意味が分からないので，コンテストに参加されていない方は 問題文 を読んでからどうぞ．あと，コンテスト期間中の様子は chunさんのエントリ にとても簡潔にまとまっています．
私はチーム Intercaml の一員として参加していました．メンバーは chunさん，gusさん，phoenixさんと私の4人です．去年の ICFP-PC に一緒に参加したよしみで仲間に入れさせてもらいました．それぞれ，軌道制御プログラム，理論計算，ビジュアライザ，基礎VMといった感じで自然に分担が分かれました．
コンテストの1日目はそれぞれオンラインでやっていました．当初，私はチームに入っておらず，飛び入りのような形で昼の12時くらいからチームに加えてもらいました．私は午前中のうちにアドホックに実装したVMを持っていたのでそれを持ち込み，とりあえず Wikipedia のホーマン軌道遷移などのエントリを読んで理論の勉強から始めました．意味もわからないままとりあえず書いてあった式をそのまま実装したところ，なにやらうまくいってしまったので，そのまま100xのソリューションを提出したのですが，なぜか CRASHED! という結果が返ってきてしまい，途方にくれるはめに．どうやら出力フォーマットが間違っている時もクラッシュしたという表示がでるらしく，ICFPのIRCチャンネルで同じような人を探して原因を見つけ出しました．
その後しばらくすると，200xに取り掛かっていたgusさんがいいところまで行っているようだったので，ふたりでコードをデバッグしたりしていました．バグを直してなんとか動かすことができたのですが，実際に実行してみると，大体目標と同じような軌道に乗せられるものの微妙に位置がずれていて終了条件を満たせません．このあたりから，時間的な離散化誤差という悪魔が片鱗を見せ始めます．とりあえずここは，私がアドホックに相手の衛星を追いかけるコードを書いてなんとか相手とランデブーさせることに成功．200xも無事に解くことができました．
そして次の300xのハードルが高かった．最初の印象としては，楕円軌道と円軌道じゃそれほど難易度は変わらないのでは，と思ってしまったのですが，軌道同士を遷移させるという観点から考えると，円と楕円では難易度にかなりの差があります．うちのチームの方針としては，とりあえず自機の軌道を円軌道に移して，さらに相手の軌道に接する別の円軌道に移り，そこからランデブーするという方針を採りました．ちょうど，100xと200xを組み合わせた感じです．このコーディングはけっこう難航したのですが，担当していたchunさんが気合で書ききり，夜中になったころにはじめてランデブーを成功させてくれました．chunさんの神性はこの辺から発揮されていたように思います．これの最適化をがんばったところ，ランキングで2位まで浮上し，チームは大いに沸きました．あと50点でトップになれたのだけど，残念ながらそこまでは至らず，そのままLightning Roundの終了時間である24時間目を迎えました．
2日目はphoenixさんの家に全員が集合して，顔を突き合わせてのコーディングになりました．残りの400xを解くにはあと二日間も時間があるということで，ゆっくり確実にとりかかることにしました．あと，この日に至ってはじめて月が存在することが明かされました．月の引力の影響で，自分とデブリの軌道が楕円からずれることになるため，誤差がもっと大きくなることになります．
私は2日目の朝からVMの書き直しに取り掛かりました．おそらく今後，VMを複製して軌道の予測を行ったり，よりよいコースを探索したりするだろうと思ったので，なるべくそういった処理が簡単になるようにクラスをまとめました．あと，自機やデブリの速度を求めたりするルーチンもVMの実行系に埋め込んでしまいました．速度や加速度の関係式が仕様で定められているので，この辺は楽にできました．
この日はいままで書いたコードのリファクタリングとか，phoenixさんが仕上げてくれたビジュアライザでデブリの軌道を見たりして作戦を立てるのがメインでした．夜ご飯は近くのファミレスに行って，食べるついでに議論タイム．みなさんの頭が良すぎるのでついていくのが大変でした．
夜になってからchunさんとphoenixさんによって少しずつ400x向けのコードが書き始められ，深夜に初提出．しかしあまりスコアは伸びず，けっこう難しい気がしてきました．
3日目は私以外はやはりphoenixさんの家に集合．私だけはこの日に大学で外せない輪講があったので自宅から参加しました．
ここから，理論的な計算と実際との誤差を修正するためのアルゴリズムを導入することにしました．使う推進力を理論計算で求めた後，VMを複製してその推進力を加えた時の結果のシミュレーションを行い，目標とシミュレーションのずれを考慮して推進力に修正を加えるというものです．たとえば自分とデブリの速度ベクトルが真逆でとても速い相対速度で交差するような場合，そのデブリを回収できるかどうかは整数時間において相手との位置がたまたま近づいているかどうかに依存し，ほとんど運次第となってしまうのですが，この方法を使うことでうまくいく軌道を探して採用することにより，ほぼ必ずデブリを回収することができるようになります．私たちのチームではこの手法をTASさんと呼んでいました．ある意味で自然なアイデアなので，たぶん上位のチームはみんなやっているんじゃないかなと思います．
あとは誤差との戦いでした．予測と誤差が出るほど，燃料を多めに使ってしまうはめになります．燃料は基地に戻れば回復させることができるのですが，燃料を無駄づかいするとその分のペナルティと回収しに行く時間のコストによりスコアが大きく下がってしまうので，なるべく燃料は節約しなければなりません．この問題は最終的に，大きな誤差を与える存在である月からの引力を打ち消すように常に推進剤を使い続けることで解決しました．推進剤を使い続けることで燃料は消費してしまうのですが，実はトータルでそれほど必要量が多くないので，誤差によって無駄に燃料を使うくらいならこちらのほうがよいのです．これでだいぶ燃費が改善し，月軌道上のデブリ以外は回収することができました．
最後にchunさんが月にデブリを取りに行くコードに取り掛かってくれました．奮闘の結果ついに月に到達し，全デブリを回収することができたのですが，残念ながらトータルスコアが悪くなってしまったのでそのコードは反映されませんでした．とても残念．
私にしては長い文章になってしまいましたが，一言でいうと，かなり楽しかったです．やはり複数人で集中的に同じ問題に取り掛かるというのは楽しいですね．私はもう高校物理すら覚えていないのですが，チームメンバーのみなさんが頭のいい人たちばかりなのでとても助かりました．その代わり，私はVMの方でチームにコミットできたかなあ... と思っています．おかげさまで順位的にも良いところに行けていると思います．結果が楽しみ．
