今回の課題は近年稀に見る面白さでした。要約するとこんな課題。
- 車とその燃料を開発して、市場に投入せよ。
- 市場に投入された車の設計書は参加者全員に公開される。燃料の設計書は公開されない。
- 他社の車の設計書を解析して、他社の車用の燃料を開発し市場に投入することもできる。売上はほぼ折半 *1 。
- 燃料の売上を競う。
以上より目的は、「解析が難しい車を設計して投入し、燃料の売上を寡占する」かつ「他人の車を解析して燃料を作り、売上を奪う」ということになります。すばらしい皮肉的な設定。
さらに ICFPC らしさとして、
- 車や燃料の設計書は trit 文字列 (0 と 1 と 2 のみからなる文字列) で書かれる。trit 文字列の仕様は非公開。適当に作った設計書を投入してみて、パースエラーのメッセージを元に、トライアンドエラーでフォーマットを推理しなければならない。
- 燃料を投入する際は、設計書自身ではなく、設計書を生成する工場を投入する。工場は簡単な回路として記述され、この記述は多少人間にも読めるけれど、詳細はやはり不明。エラーメッセージを元に推理しなければならない。
という要素もありました。
以下、詳しい説明とともに、やっていったことを思い出しながら書き出してみます。
回路
回路は全体として 1 入力、1 出力。入力と出力はすべて 0 か 1 か 2 の数列。入力にはサーバが内部的に保持する数列が順に (クロックごとに) 与えられる。出力が燃料の設計書として扱われる。
回路の中は 2 入力 2 出力のノードで構成されている。出力と入力をつなぐ信号線には順方向と逆方向があり、順方向なら同じクロックで、逆方向なら 1 クロック遅れてデータが送られる。
以上の情報を元に、回路記述のフォーマットを解析する。回路記述はサンプルコードをちょっといじりながら送信していくと、パースエラーの情報でフォーマットがつかめる。行指向で、
- 先頭行は「回路全体の入力がどのノードのどっちの入力につながるか」
- 中間行は 1 行につき 1 ノードの説明で、「このノードの入力がどのノードの出力から来ているか」が 2 つ、「このノードの出力がどのノードの入力に行くか」が 2 つ
- 最終行は「回路全体の出力がどのノードのどっちの入力から来ているか」
を書いている感じ。
それがわかれば、今度はノードがどういう演算をしているのかを推測する。
X X X X | | | | | +----+ | +----+ +----+ | +----+ | | | | | | | | | | | | | +-*-*-+ | +-*-*-+ | | +-*-*-+ | +-*-*-+ | | | | | | | | | | | | | | | | | | | | | | | | +-*-*-+ | +-*-*-+ | | +-*-*-+ | +-*-*-+ | | | | | | | | | | | | | +----+ +------+ +------+ +----+ | | | | | X X X X
以上のようなノードが 1 個だけの回路を 4 通り作り、それぞれの出力を比較して、ノードがそれぞれどういう計算をしているのか推理しました。サーバの入力が不明なので大変だった *2 。
推理の結果として、
- 2 入力を L と R とすると、出力は L-R と L*R+2 になる (ともに mod 3) 。
- 逆方向の信号線は 0 で初期化されている。
ということがわかりました。つまりこんな感じ。
L R L-R L*R+2 | | +-*----*-+ L\R | 0 1 2 L\R | 0 1 2 | | ----+------- ----+------ | | 0 | 0 1 2 0 | 2 2 2 +-*----*-+ 1 | 2 0 1 1 | 2 0 1 | | 2 | 1 2 0 2 | 2 1 0 L-R L*R+2
ここまでは開始 4 時間くらいでわかって、そこからは以下の作業をしました。
- 任意の入力を受け取って、常に 0 を出力するノードの組み合わせ (プリミティブ) を試行錯誤で作った。見つけたのは以下のようなの。
+-------------------------------------------+
| +--+ +--+ +--+ +--+ +--+ +--+ |
+--* *- -* *- -* *---* *- -* *- -* *--+
| | X | | X | | | | X | | X | |
?---* *- -* *- -* *---* *- -* *- -* *---> 0
+--+ +--+ +--+ +--+ +--+ +--+
- これを元に、2 入力から 1 出力をするプリミティブを探索でいっぱい作った。例えばプリミティブ 012120201 は、以下のような対応を計算する (trit 版 half-adder) 。
R\L | 0 1 2 ----+------- 0 | 0 1 2 1 | 1 2 0 2 | 2 0 1
- さらにこれを元に、同じ値を複製する (X を入力して X と X を出力する) プリミティブを作った。
以上のプリミティブからカウンタが作れます。さらに「カウンタの値をデコードして trit 文字列を出力する回路」を作れば、デコーダ部分を変えれば所望の trit 文字列を出力する回路を生成できるようになります。
「所望の燃料の設計書を生成する回路を生成するプログラム」を作ったらこの段階は一応クリア。回路が小さい方が高得点なので、ここはまだまだ改善の余地があったと思うけれど、手が足りませんでした。
開始 9 時間くらいで、
- search_table.rb (150 行): 2 入力 1 出力のプリミティブを探索するプログラム
- compiler.rb (200 行): 俺言語から回路記述を生成するプログラムのコンパイラ
- gencode.rb (150 行): trit 文字列からそれを生成する俺言語を生成するプログラム
を書いて、サーバにサンプル回路を送信して受理されることを確認したところで寝た。
ちなみに、終了後の shinh さんとの会話でわかったことですが、上のやり方は完全にムダで、カウンタつくらなくてもシフトレジスタみたいな回路にすればもっと簡単かつ小さい回路記述を出力することができます。残念。
trit 文字列 (設計書) の解析
開始 15 時間くらいで起きて、trit 文字列の仕様の解析を始めた。
辞書順でいろいろ入れてみると、そのうち、tank 番号がどうこうというエラーメッセージが出ることに気がついた。これで自然数のフォーマットがわかる。
trit 文字列 -> tank 番号 0 -> 0 10 -> 1 11 -> 2 12 -> 3 220 -> 4 2210 -> 5 2211 -> 6 2212 -> 7 2222000 -> 8 ...
みたいな規則性に気づけば、これは以下のような BNF で表されることに気がつく。いや、2 時間くらい悩んだんだけど。
<num> = 0
| 10
| 11
| 12
| 22 <num> [num+2 個の trit]これを手がかりに他の箇所を解析していくと、リストの構造を見つけることができる。
<type list> = 0
= 1 type
= 22 <num> [num+2 個の <type>]ここまでわかると、後は糸が解けるように他の箇所もわかる。
<bool> = 0 | 10 <pipe> = <num list> <chamber> = <pipe> <bool> <pipe> <car> = <chamber list>
車の設計書は
燃料は、上記と同じ構造を使って以下のようになっている。
<row list> = <num list> <matrix> = <row list> <fuel> = <matrix list>
これを元に、車の設計書のパーサを作ったり、単純な燃料 (を出力する回路) を作って他人の車の燃料を提供してみたり。ここで開始 20 時間くらいだったと思う。
submit の管理
ちょっとやってみるとわかるけれど、主催者の提供する Web インターフェイスが非常に貧弱。自分がどの車に燃料を submit したかわからないし、他人の車にちまちま燃料を submit するのもとても大変。
しょうがないので、mechanize を使って、車の設計書を fetch したり、燃料を submit したりするスクリプトを書いた。サーバの負荷を考えるとちょっとどうかと思うのだけれど、どう考えても手作業でどうにかなる大変さではないので、これは課題の一環として想定されている作業だと判断した *3 。
開始 26 時間くらいだったと思う。これによって順位が 6 位くらいに上がって、これが今大会で最高の位置だった。これは lightning division の段階でやっときゃよかったかなあ。
ソルバの生成
ここからがこの大会の本番。他人の車を解析して燃料を作る。その前に設定を簡単に言うと
- 車は複数のチャンバからなる。
- チャンバは上下 2 本のパイプからなる。
- パイプは複数のセクションからなる。空気を吸って、差動エンジンに流す。
- セクションは 0 から 5 のいずれかのタンクにつながっている。空気がセクションを通るごとに、タンクの種類に依存して成分の構成が変えられる。
- すべての成分において、上のパイプを通って出てきた空気の成分が、下のパイプを通って出てきた空気の成分より多ければエンジンは作動する。
という感じ。細かいところは全部無視して説明しています。詳しいことは問題文読んでください。
「タンクの種類に依存して成分の構成が変えられる」というところがポイント。タンクごとに n x n の行列が決まっていて、空気が通るごとにその行列に成分のベクトルを乗算した感じに変わります (n は成分の数) 。
要するに、
- 燃料: 6 個の行列: M0, M1, ..., M5
- パイプ: 上記の行列を指定した順番で乗算した行列 (各セクションのタンク番号が 0, 0, 1 なら M1 * M0 * M0 とか)
- チャンバ: 上のパイプの行列の各要素が、下のパイプの行列の対応する各要素と等しいか大きければ作動する
- 車: すべてのチャンバが作動すれば OK
実際には補助チャンバとか、ある種類の材料は厳密に大きくないといけないとか、細かい条件はありますが問題文を読んでください。
さらに抽象化すると、
- 燃料: 6 個の行列: M0, M1, ..., M5
- 車:
という条件式の集合
という定義になります。
「他人の車を解析して燃料を作る」とは、車 (条件式の集合) を満たすように燃料 (6 個の行列) を作れ、ということになります。行列の次元も自分で決めないといけません。これは非線形な整数計画問題です。
とりあえず次元を1 で決め打ちして、[1, 1, 1, 1, 1, 1] 、[1, 1, 1, 1, 1, 2] 、[1, 1, 1, 1, 2, 1] 、[1, 1, 1, 1, 2, 2] 、[1, 1, 1, 2, 1, 1] 、……という感じに総当たりするバカなソルバを作った。あと、車の設計書を自動で fetch して、このバカソルバで解けたら submit する自動化スクリプトをぶん回した。ここで開始 30 時間くらい？それからまた寝た。
多分開始 39 時間くらいで起きた。非線形整数計画問題について調べて、この問題は MINLP (Mixed Integer Nonlinear Programming) と呼ばれているっぽいとわかった。MINLP のソルバは Matlab とか R とかならあるみたいなんだけど使えないので、フリーのソルバに限定して探したところ、Bonmin というのが見つかり、これをセットアップして使うようにした。かなり頑張ったんだけれど、Bonmin のフロントエンド？である AMPL のフリー版の制限で、変数や制約の数が 300 と切られているので、大きな問題は解けなかった。
解けない問題を観察していたら、1 次元で解ける車でも、一部のタンクの比率をとてつもなく大きくしないといけない車が結構あるような気がしたので、それに特化したソルバを作ってぶんまわした。これで開始 48 時間くらい。
こういうソルバとか数学できないとダメぽい問題はとても苦手なので、このへんで脱落してしまった感じ。後半伸びなかったのはその辺。大会中にこの warpup 書いたりしてた。
その他
作業の多さにぐったりした。
- 解けない問題を観察して、解く方法を考える。
- 回路生成方法を見直す。
- submit 済み問題を管理するスクリプトなど環境整備をもっとする。
- 難しい車を作る (ここはチームメイトの飛廉さん (妻) に考えてもらっていた。でもせっかく作ってもらった車がサイズ制限にひっかかって、二人でがっかりした) 。
結構並行して考えることが多い問題だったので、今年は間違いなくメンバが多い方が有利ですねー。
残り 3 時間の時点で、簡単でもいいから車を乱造して送信するスクリプトを書いて、タイムアウトぎりぎりで一応 submit 制限数の 72 台をアップロードした。そこで終了。
総評
問題は ICFPC 2004 だったか (アリのやつ) に次ぐくらいの面白さだったと思います。運営もかなり良かったと思う。
問題文だけからサーバの重さは想定されて、実際たまに落ちてたけれど、健闘した方だと思う。少なくとも自分ではできない。ただ、車の設計書の長さに後から制限がついたのは「最初からやっとけ」という感じだった。
Web インターフェイスはスクリプトによる submit を奨励しているとしか思えないもので、それならいっそ xmlrpc とかの API を提供すればよかったんじゃないかなと思う。
スコアリングはちょっと不満かも。市場に先に投入した方が非常に有利で、そのおかげで後半ダメすぎたわりに上位 30 位くらいには入れたんだけど、サーバが落ちたりなんたりしている時間を考えるといまいちかなという気はする。
まあでも、「ゲームを作らせるならドイツ人」*4 というぼくの先入観を裏切らない素晴らしい大会だったと思う。年休とった価値はあった。
他にもいろいろ書きたいことがあるので、またそのうち何か書くかも。
