ICFP Contest 2007 まとめ

ICFPC

ICFP Programming Contest 2007 が終わりました。僕は kuma-- として参加していました。ゆんさん、飛廉さん、僕の 3 人チームです。

今年の問題は、与えられた DNA (プログラム) にできるだけ短いコードを付け足して、その発現結果 (画像) を指定画像にできるだけ近づける、というものでした。

ちなみに何もコードを付けないと、↓のような発現結果になります。

与えられた DNA は 'I' 、'C' 、'F' 、'P' という 4 種類の塩基、というか文字からなる 7 MB くらいの文字列 *1 で、指定された方法で実行すると RNA が出力されます。RNA は同じ 4 種類の文字を 7 文字ごとにまとめた感じのリストになっていて、指定された方法で実行すると画像が出力されます。

チーム kuma-- は、まともな時間で動く DNA インタプリタを作るのに期間の半分を使ってしまったのが致命傷でした。rope なんて思いつかん。それでもゆんさんと飛廉さんの驚異的なひらめきと非人間的な解析能力のおかげで、15 位以内には入れたようです。

僕は DNA インタプリタの作成を担当しました (つまり致命傷の犯人は僕) 。結局 DNA インタプリタは 50 K step / sec 程度しか出ませんでした *2 。作る人が作れば 1 M step / sec だの 2 M step / sec だの出るそうで。がっかり。他にはこまごまとしたツールの作成や、オブジェクトの描画位置を手動で合わせる地道な作業をやりました。

課題ネタバレ解説

去年と同じ系統の、「主催者が作りこんだゲームをみんなでやりこむ課題」でした。チーム kuma-- が到達したところまで簡単に解説します。完全にネタバレですのでご注意ください。

プレイ資格

DNA インタプリタを高速に作れること。みんな余裕？

タイトル画面

オリジナルの DNA を実行すると DNA 断片が描画される (ただしすぐ黒塗りで消される) ので、それでタイトル画面 (DNA のマニュアルの表紙) に行けます。

ちなみにここでこのルートを捨てて、ほぼ全て自力描画するというルートもあるようです、ってありえねぇー！

最初にやること

マニュアルの任意のページを開くための DNA 断片の書き方を学びます。このへんは普通のゲームみたいです。しかし一気に多数のページにアクセスできてしまうので、情報過多に陥ってどこから手をつけるか混乱しました。

とりあえず目をつけたのはこの辺り (そして結局それより深いところにはいけなかった) 。このへんはゆんさんと飛廉さんがさくさく読み解いてくれました。

今から思えば僕もこのあたり中心に参戦したかったけれど、この頃僕は DNA インタプリタの改良と体調不良で死んでました。

(多分) 次にやること

AAA_geneTablePageNr のオフセットに数字を書きこんでから Gene Table のページを開くと、Gene Table (2/14) や (3/14) が見えます。指定画像に書かれているオブジェクトの名前っぽいもの (cloud とか windmill とか) が大量に並んでいて、雲だの風車だのを描画する関数群だとわかります。

それだけでも目がちらちらするのに、help-* といったカタログの別のページを開くような関数や、crack だの crypt だのといった、いかにも怪しいシンボル名が並んでいて、さらにどう攻めるか悩みます。

チーム kuma-- としては、この時点で期間の半分が過ぎていたため、よくわからない関数の深追いはあきらめて、わかりやすい関数を集めて絵を作って点数を稼ぐ方針になりました。従ってこれ以降の領域は未踏なのでわかりません。

その他・残された謎など

マニュアルの大半のページは謎のままで、はっきりいって謎ばかりですが、主催者がどういう攻略順を想定していたのかが一番気になる謎です。逆アセンブラまで作れば見えてくるものでしょうか。


飛廉さんがぼんやりとオリジナルの DNA を眺めていて、横幅 16 カラムで DNA を見ると "ACHTUNG! PORTABLE NETWORK GRAPHICS FOLLOWS" というメッセージがアスキーアートで現れることを見つけました。すげー。その後の I と C の文字列は確かに png のフォーマットになっています。それがこれ。

この画像に書いてある通り、その後にはこんな mp3 が埋め込まれていました (笑)
けれどこのページを開いても、完全数がどうのこうのと書いてあるだけで、得点にはつながりませんでした。部分点くらい下さい。


ステガノグラフィのページもよくわかりませんでした。チーム lepidum の人によると、gimp で RGB 強調したら何か見えてくるらしいですが、やはりこれもそのままでは得点につながらないようです。


あと、画像で Rot-13 はかんべんしてください (笑)

感想

去年の課題を強く意識した課題で、作り込みは去年以上だと思いました。ただしゲームバランスには難がある気がします。そういうところも含めて、例年通り楽しみました。期間中にクリアするチームがいるのか気になりますね。そもそも「クリア」はありえるのかなあ？
去年と今年と同じような傾向でしたが、来年の課題がまた同じ系統なのか、かつての人工知能系か、それとも全く別の系統か、早くも楽しみです。

*1:こんな感じ→IIIPIPIIPCIIIPFFFFFPIIIPFFFFFPIIIPCCCCCPIIIPIIIIIPIIIPIIIIIPIIIPIIIIIPIIIPIIIIIPIIIPIIIIIPIIIPIIIIIP...

*2:文字列ライブラリには Boehm GC 付属の cord を使いました