ICFPのコンテストに参加しました

http://icfpcontest.org/2010/
一週間遅れですが、簡単なレポートを。ここに書くのほぼ一年ぶりか…
今年は流れで某Mくんと2人でチームを組んで参加。チーム名tokorobashi。名前の由来は近いうちに明らかになるかもならないかも。最終結果は7点。
今年は特にサーバへのsubmitとかを便利にしてくれるインフラ整備をがんばる余地がいっぱいあったので、もうちょっと人数多くないと戦えてなかったかもしれない。でも結局、「本番」に到達できなかったのであんまり関係なかった。
大会の詳細はどっか他のサイトを見てください。(http://d.hatena.ne.jp/mr_konn/20100618/icfp2010taskあたりがわかりやすいか?)

一日目

6月18日(金) 21:00〜

開始。最初はサーバが重くてチーム登録ができなかったので、とりあえず英文よむよむよむ。結局、サーバの調子をみてチーム登録をやりながら、気分を落ち着けるために和訳文作成をはじめてしまって日付が変わるくらいまでその作業をしてた。Mくんはそんな僕をしりめに最初の回路構造を考えてたぽい。

6月19日(土) 0:00〜

日付が変わったころに、だいたいの問題を理解してなにはなくとも「回路」を生成しないと話にならないことに気がつく。で、問題にのっているサンプル回路を眺めてフォーマットを想像する。一つのゲートが二入力二出力なので、1行が1ゲートをあらわしていて、入出力の先が書いてあるんだろうなあ、くらいの想像はついた。最初の行と最後の行の意味がわからず1ゲートの回路(と思われるもの)をいくつかsubmitしてテスト。最初はエラーばっかし。

ログを見返してみたらもうこの時点で「これ入力も推測せなあかんのか?それとも定数を出力するような回路が組めるのか?」と結構本質的なことをしゃべってる。もっと早い時点で後者だと信じて突き進むべきだったよ。

1:00〜

1時間くらい試したところでM君の「最初と最後はXの場所っぽいよな」という発言で回路記法をようやく理解。ただしこの時点では、遅延する線としない線の法則がわかっていなかった。
記法がわかったので、1ゲートのいろんなバリエーションを入力して出力を収集。1ゲートは4パターンしかないので、それぞれに名前をつけて共有したりしてた。そうこうしてるうちに、ゲートを通過させなければサーバの入力が取れるなと気がついて、全部の出力が自分自身の入力になっているゲート一個だけの回路を入れてみる。こんなの。

X:
0R0L0#0R0L:
X

無事にとおってサーバ入力がとれた。これがとおってから「X::X」で充分だったことに気がつく。で、実はここでゲートの入出力表を作成するのには充分な情報が得られているらしいのだが、「遅延」のセマンティクスがまったくわかっていなかったので、そこでつまづいてしばし悩むことになる。あとで聞いてみたら、会社の先輩も同じところでつまっていた。

2:00〜

どういう線が「遅延」されるのかさっぱり理解できていなかったので延々悩む。「右出力は常に遅延されるのでは?」などという頓珍漢な仮定を僕がだしてしまったので余計迷宮入り。このへん良く覚えてないが、4:00くらいまで悩んで、わからないなりにも回路シミュレータをrubyで実装したりしていた。気がついたら次の日の昼頃になってた気がするが良く覚えていない。

19:00〜

悩みながらなかなか寝られなかったりしたので、起きたら夜だった。ひどい生活。
寝てる間に、M君がゲートが2つの回路を自動生成して出力を収集してくれていた。まるっきり同じ出力をする回路とかでてきて、なかなかおもしろい結果に。それらを眺めつつ、悩んでいたら2時間くらいたっていて… そしてやっと遅延のセマンティクスに気がつく。

二日目

6月19日(土) 21:00〜

単純に、「自分より前かあるいは自分のゲートに出力されている線が遅延される」ということにやっと気がついた。配線のトポロジは同じでもゲートの順番が違う回路をちゃんと試していたらもっと早く気がついていたかもしれない。
なんにせよここで、配線の初期値(後ろのゲートの出力が入力になっている場合の、初回の値)の推定を含めて入出力表を求める作業にはいれることになった。回路シミュレータを改造して、いままでの回路と既知の出力値をぶちこんで入出力表を埋めていくプログラムを組んだ。
人間が解くように、「確定できるところだけ表を埋めていく」ようなコードにしてしまったので、1ゲートの回路だけじゃ求まらなかった。が、M君が収集してくれた2ゲートの回路の結果もいれたら動いた。2、3バグを直したらすぱーんとそれっぽい表ができて喜ぶ。初期値も0以外では成立しないという結果もでた。
「ありうる表を全て試して、まずいことが起こった表は捨てる」という方法だと1ゲートの回路だけで表がでたみたい。どうも僕は全探索への苦手意識がありすぎる。ちゃんと全探索でいける計算量を見積って探索できるようにならなきゃだめだな。
で、回路シミュレータがようやくまともに動くようになったので、サンプルの回路を動かして"the key"を得た。そしてまたもや途方にくれる。

23:00〜

"the key"はわかったものの、それを出力する回路をどう構成すればいいか全くわからない。たまーに、入力したい段数分遅延させたらいいんじゃないかなあというぼんやりしたイメージは浮かんだものの、具体的な構成方法が全くわからないので、その発想はすぐ消えてしまうのであった。
しっかりした目標がさっぱり立たないので、まず「入力にかかわらずに決まった値を出力する1入力1出力の回路」を考えはじめる。そういえばgraphvizでの回路の図示も実装してみたが、左右の出力がちゃんと左右に配置されなくてあんまりわかりやすいものにはならなかった。

6月20日(日) 0:00〜

ノートに回路を殴り書きしながらうーんうーんと頭をしぼって、ようやく「任意の入力を受けとって0を出力する」回路の構造の概要を思いつく。が、ちゃんと作ると10ゲートを越える回路になりそうで、かつ似た構造を2つ重ねたものだったので、まず手書きする気は起こらない。こういうのは自動生成だろうと思って、ちょっとだけ書くのが楽な、回路を生成するためのDSLもどきをrubyで実装しはじめる。

2:00〜

このへんで簡単に回路を合成できるような機能までを含めて回路自動生成コードができてた。その上で「0を出力する回路」ができたので、それを元に1を出力するもの、2を出力するものを作ってライブラリ化。この時点では「これを作ったからといって"the key"の生成になにも寄与してないじゃないか むきー!」という気分になっていたのだが、実はこの蓄積が最後の最後にちょっとだけ役立った。
あと本大会の目的が勝ち負け関係なしの「なんとか得点を得ること」というものに下方修正されたのもこのあたり。
それ以降どうしてたかちょっと覚えていない。たまに「マルドゥックスクランブル」を読みかえして勇気をふるいたたせつつ、回路の内容がさっぱりわからないのでヒントを求めて問題に書いてある回路を解析しはじめてすぐに絶望的な気分になったりする。

7:00〜

問題に書いてあるサンプル回路の解析、などという無茶なことをはじめたせいで、回路の左出力は引き算であること、回路自体は遅延する線の数だけ変数を持つ漸化式で表現できること、などなどには気がつくがそれ以上のことはわからず、何もすすまない。絶望して寝た。回路の夢を見た気がする。

15:00〜

こんどは夕方には起きたが全く進展なし。相方とも時間があわず1人絶望をかかえて愚痴をtwitterに吐き散らしたりする。「全然やった気がしない!」とか叫んだ。

三日目

月曜日は仕事を休めなかったので実質日曜の深夜までがタイムリミット。

6月20日(日) 21:00〜

相方M君と話して「やっぱり入力関係なく数値を出力する回路を作るしかない」という方針を再確認。再確認したところで、希望の入力を出力するためには、多段に遅延する回路を作るしかないよなあ、というところに戻って、今度はイメージが消えないうちに真面目に考えはじめる。
最初は、任意の数値が出せるような構造が思いつかなかったのでadhocに1番目に1を出す回路、それに加えて2番目に1を出す回路、、というふうにインクリメンタルに手で回路を考えはじめる。回路生成プログラム上でコーディングしながら回路シミュレータで結果を確認して試行錯誤。入力がなんであれ先頭から「11」を出力する回路はできたが、3番目でややこしくなりすぎて途方にくれる。

23:30〜

一段ずつ手で回路の構造を考えるのは複雑になりすぎたので、一定の形式で任意の数列が出力できるような構造に思いをめぐらせる。そしてここでようやく思いつく。
入力によらず0,1,2を出力し続ける"定数回路"は既に手にはいっているので、左に入力された値に対して、右入力に繋げる"定数回路"を適切に選んでやれば、左出力の出力の値は完全にコントロールできる。こういうゲートを逆向きにN段繋ぐと、入力によらずN個の数字を出力する回路ができあがる。いわば、出力したい値を各定数回路にエンコードした回路を構成できる。ただし"定数回路"のゲート数はそれだけで10や20はあるものだったので、回路規模は10n 〜 20nくらいの大きなものになる。
とはいえ、この時点では回路のサイズなんて知ったこっちゃないので、そのまま急いで「指定した出力を行う回路生成プログラム」をコーディング。定数回路のライブラリが既にあったのでほぼそれを繋ぎあわせるだけで実装完了。30分かからなかった。

6月21日(月) 0:00〜

コーディングが完了したので,"the key"を出力する回路(確か260ゲートくらい)を生成して、どきどきしながらsubmit。

circuit output starts with
     11021210112101221
this is a legal prefix
Congratulations.
You have submitted a circuit that produces the key prefix.

とおった!長かったー!
本当はここからが本番のはずなのだが、もうタイムリミットと言える時間だったし、任意の数列を吐ける回路生成ツールができたのである程度満足してしまう。Mくんにツール群を託して風呂へ。

1:30〜

風呂からあがったらスコアボード上で得点が増えていた。MくんがCarとFuelの構造おかまいなしで、"the key"に適当に数字をくっつけてsubmitするのを試しており、"the key"に"1111"をくっつけただけのやつでも最初のほうのかなりの数のCarにパスすることを発見していた。最後に訪れたsubmit祭り。
とはいえ僕はもう得点にあんまり興味がなくなっていたのとサーバが無茶苦茶重くなっていたので、CarとFuelのエンコーディングのところの問題を読みなおしたりしながらじっとsubmit祭りをみまもる感じに。ちょっと難しそうなCarにsubmitしてもらってそのエラーメッセージを見たりしていたが実質的にはもう何もせず。

3:00〜

結局25台のCarにsubmitを通したところで疲れたり満足したりタイムリミットだったりして終了。

score: 7.124
others' cars solved: 25
cars submitted: 0

まとめ

以上終わり。自動生成して都合のよい回路を探索するようコードは一行も書かなかった。というか回路を育てていくアルゴリズムがぱっと思いつかなかったので、思いっきりスルーしてた。もうちょっとそっち方面の勘を養っとくべきかもなあ。
今回は「回路の構成のしかたがわからん」ということにつきる。最後にぎりぎり「Carに合うFuelを生成したり、Fuelが生成しにくいCarを作る」という今回のお題の入口には立てたものの、「他のプレイヤーとのコミュニケーション」はさっぱりできませんでした。エンコーディングの推測は楽しそうだったので、まだ余裕があるうちにそれが役立つ局面までは辿りつきたかった。残念。